Пример № 2. Транспортная задача закрытого типа, представленная в сетевой форме, без ограничений пропускной способности

Сетевой способ решения задачи не требует составления матрицы перевозок, а позволяет вести расчет прямо на схеме путей сообщения – сети.

Сеть состоит из вершин и звеньев. Квадратами обозначены вершины (станции) отправления. Числитель внутри квадрата – номер вершины (станции) отправления, знаменатель – объем отправляемых вагонов (продукции). Кружками обозначены вершины (станции) назначения, числитель – номер вершины, знаменатель – объем потребления. Числа на звеньях – расстояние перевозок (или другой критерий оптимизации) c_i,j+1 между станциями i и j+1.

Условия задачи взяты из примера № 1. Схема (сеть) дороги с указанием объема отправления, прибытия вагонов и расстояния между станциями указаны на рис.1.

	Рис. 1. Исходные данные к примеру № 2 Эта задача закрытого типа, так как суммарное количество избыточных пустых вагонов равно суммарному количеству требующихся вагонов (420 = 420). Математическая модель задачи будет выглядеть следующим образом. Общее суммарное расстояние перевозки (целевая функция) Система ограничений:
	(i=1,2,3,4)	(j= 1,2..7)

x_ij ? 0, (i = 1,2,...,4; j = 1,2,...,7), где a_i – ресурсы i-го пункта отправления; b_j – потребность j-го пункта назначения.

Решение транспортной задачи в сетевой форме начинают с составления исходного плана.

Точных алгоритмов составления исходного опорного плана не существует. Рекомендуется начать составление исходного опорного плана с вершины, имеющей наибольший объем отправления, и выбирать звенья с наименьшим расстоянием (затратами), назначая на них максимально возможные перевозки. Следует избегать встречных перевозок.

Распределение перевозок необходимо осуществлять таким образом, чтобы обеспечить отправление всех вагонов со всех станций отправления и удовлетворить потребность в пустых вагонах всех станций назначения. Возможный исходный план перевозок приведен на рис.2.

Рис. 2. Исходный план перевозок

Н ачальное значение целевой функции (общее суммарное расстояние перевозки) для исходного плана перевозок составит

L_нач = 70· 15 +30· 70 + 50· 17 + 30· 11 + 40· 18 + 50· 25 + 30· 11 + 20· 9 + 60· 16 + 70· 17 = 7370 ваг-км.

Звенья называются базисными (занятыми), если по ним осуществляются перевозки. Направление перевозки указывается стрелкой, число около стрелки – объем перевозки по данному звену (количество вагонов) x_j,j+1.

Алгоритм решения транспортной задачи, представленной в сетевой форме, методом потенциалов такой же, как и транспортной задачи, представленной в матричной форме:

1. Исходный опорный план проверяется на условие «вырождения».

К_з S – 1 ,                    (10)

где К_з – число занятых звеньев сети; S – число вершин, вошедших в полигон сети.

Данному условию должен отвечать любой план перевозок, в том числе исходный опорный план. Если это условие не выполняется, то исходный опорный план составлен неверно и необходимо найти замкнутый контур (или контуры) из базисных звеньев и “снять” с него минимальную перевозку.

Если К_з = S – 1 , задача решается обычным порядком.

Если К_з < S – 1 , задача называется “вырожденной” и распадается на несколько самостоятельных задач. Чтобы этого избежать, на свободные звенья назначаются дополнительные фиктивные перевозки (перевозки равные 0). В нашем примере условие вырождения выполняется (10 = 11 – 1), поэтому задача не является “вырожденной “ и решается обычным порядком.

2. Начальный потенциал выбирается произвольно и присваивается произвольной вершине (рекомендуется начинать с наиболее удаленной вершины).

Первой вершине присваивается потенциал V₁ = 100 ( см. рис. 2).

3.Через занятые базисные звенья определяют потенциалы каждой последующей вершины V_j+1, связанной с предыдущей вершиной V_j по формулам:

перевозка “попутная”

V_j+1 = V_j + c_j,j+1,              (11)

перевозка “встречная”

V_j+1 = V_j - c_j,j+1,              (12)

где c_j,j+1 – критерий расстояния (или другой показатель критерия оптимизации) на заданном звене.

4. Пункт 3 повторяется до тех пор, пока всем вершинам сети не будет присвоен потенциал. Это возможно, если выполняется условие «вырождения» К_з = S – 1. Звенья с фиктивными перевозками рассматриваются как занятые.

Исходя из формулы (11), потенциал вершины 5 будет равен V₅ = 100 + 15 =115, а потенциал вершины 2 равен V₂ = 100 + 17 = 117. Далее присваиваются потенциалы от вершин 5 и 2. Вершина 5 не имеет связующих (занятых) звеньев ни с одной из вершин сети. Вершина 2 связана с вершиной 6 (V₆ = 117+17 = 134), вершиной 8 (V₈ = 117 + 11 =128), вершиной 11 (V₁₁ = 117+18 = 135) и вершиной 9 (V₉ = 117 +11 = 128). От вершины 11 по формуле (12) определяется потенциал вершины 4 (V₄ = 135 – 25 =110). От вершины 9 определяется потенциал вершины 3 (V₃ = 128 – 9 = 119). От вершины 3 определяются потенциалы вершины 10 (V₁₀ = 119 + 17 = 136) и вершины 7 (V₇ = 119 + 16 = 135). Присвоенные потенциалы обозначены подчеркнутой цифрой около вершины (рис.2).

5. Полученный начальный план проверяется на оптимальность. План считается оптимальным, если соблюдаются следующие условия:

/V_j+1 – V_j /≤ c_j,j+1, при x_j,j+1 = 0 (звено свободно),               (13)

/ V_j+1 – V_j /= c_j,j+1, при x_j,j+1 > 0 (по звену назначена перевозка).

В нашем примере для звена 5–2 условие оптимальности выполняется (/115 – 117/ = 2 < 24), а для звена 5–6 – не выполняется (/134 – 115/ = 19 > 12) и нарушение составляет 7. Аналогично, имеются нарушения на звене 1–7 (/135 – 100/ = 35 > 28) и звене 8–4 (/110 – 128/ = 18 > 16). Нарушения соответственно 7 и 2. Для остальных звеньев условие оптимальности выполняется. Данный план не является оптимальным, так как имеются нарушения условия оптимальности [см. формулу (13)].

6. Корректировка плана производится в следующей последовательности:

а) строится замкнутый контур, состоящий из звена с наибольшим нарушением, и базисных звеньев: (5–6) – (6–2) – (2–1) – (1–5);

б) выбирается направление движения по контуру от вершины звена с нарушением, имеющей меньший потенциал, к вершине с большим потенциалом (от вершины 5 к вершине 6) и далее по выбранному контуру;

в) определяется минимальная встречная перевозка в данном контуре: min {50;30} = 30 в звене (1–2). Это значение принимается для дальнейшей корректировки;

г) “обходится” контур по выбранному направлению и вычитается найденное значение из всех встречных потоков, прибавляется к попутным. При этом звено 2–1 освобождается от перевозки, а на звеньях вне контура перевозки остаются без изменений (рис. 3).16 20 50 18

Р ис. 3. Скорректированный план перевозок (первая корректировка)

Значение целевой функции составит

L = 100· 15 + 30· 12 + 20· 17 + 30· 11 + 30· 11 + 40· 18 + 50· 25 + 20· 9 + 70· 17 +  60· 16 = =7160 ваг-км.

Согласно алгоритму решения транспортной задачи, представленной в сетевой форме, методом потенциалов (пункты 1–5), данный скорректированный план также проверяется на оптимальность [формулы (10–13)].

В данном плане имеется нарушение условия оптимальности [см. формулы (13)] в звене 4–8 (/121 – 103/ = 18 > 16). Поэтому согласно пункту 6 алгоритма решения транспортной задачи, представленной в сети, методом потенциалов корректируется план перевозок (рис. 4).

Рис. 4. Скорректированный план перевозок (вторая корректировка)

После проверки по условиям оптимальности видно, что данный план является оптимальным (отсутствуют нарушения условий оптимальности).

Конечное значение целевой функции составит

L_кон = 100· 15 + 30· 12 + 20·17 + 30· 11 + 70· 18 + 30· 16 + 2· 25 + 20· 9 + 70· 17 + 60· 16 = 7100 ваг-км.

Как видно из расчетов, итоговый план перевозок улучшен по сравнению с исходным на 270 ваг-км (L_нач – L_кон = 7370 – 7100).

ревозок) относительно начального плана на 20 ваг-км (5790 – 5770 = 20).