z(X ) =3 140 + 4 20 +8 10 + 2 130 +3 80 +5 20 =1180 <1950.

Отметим, что методом Фогеля обычно получается план, близкий к оптимальному, или сам оптимальный план.

Замечание 2.2. В общем случае опорный план транспортной задачи состоит из m + n −1 занятой клетки (по числу базисных переменных). Такой план называется невырожденным. Нередко при решении транспортной задачи возникает вырожденный план с меньшим числом занятых клеток (когда какие-то из базисных переменных равны 0). В этом случае выбирается свободная клетка (или несколько свободных клеток – в зависимости от вырожденности плана) с наименьшим тарифом, которая в дальнейшем формально считается занятой с нулевой перевозкой.

§ 2.3. Решение транспортной задачи методом потенциалов

Вторым этапом решения транспортной задачи является проверка построенного плана на оптимальность и его улучшение (если он не оптимален) с помощью метода потенциалов. Применение метода потенциалов основано на следующей теореме

Теорема 2.1. Если опорный план X =(xij ) транспортной задачи является оптимальным, то существуют потенциалы поставщиков

Условия (2.2) образуют систему с m+n неизвестными ui , vj

и, в общем случае, m + n −1 уравнений. Так как число неизвестных системы на единицу больше числа уравнений, то одну из неизвестных можно задать произвольно, а остальные найти из системы.

29

Числа ∆ij =ui +vj −cij называют оценками свободных клеток. Таким образом, согласно теореме, опорный план будет оптимален, если

методом Фогеля. Потенциалы будем записывать в первые строку и столбец вместо обозначений поставщиков и потребителей.

u1 = −5, а из u3 +v1 =3 заключаем, что v1 = 2 . Все потенциалы найдены

(см. таблицу 2.6).

Теперь находим оценки для свободных клеток

∆11 =u1 +v1 −c11 = −4 < 0, ∆12 =u1 +v2 −c12 = −12 < 0, ∆14 =u1 +v4 −c14 = −16 < 0, ∆21 =u2 +v1 −c21 = −10 < 0,

∆33 =u3 +v3 −c33 = −5 < 0, ∆34 =u3 +v4 −c34 = −3 < 0.

Результат записываем в таблицу 2.6 (где в свободных клетках в квадратике записаны оценки). Все оценки отрицательны, поэтому план

30

Пример 2.3. Теперь проверим на оптимальность план перевозок, полученный методом минимального тарифа. Ясно, что в силу большей суммарной стоимости перевозок план не оптимален, но вы-

го методом минимального тарифа, получаем таблицу 2.7. Как видим, среди оценок есть положительные, поэтому, как и ожидалось, опор-

Чтобы улучшить опорное решение X транспортной задачи, введем понятие цикла. Напомним, что циклом называется последовательность клеток таблицы транспортной задачи, в которой две и только две соседние клетки расположены в одной строке или столбце. Цикл обычно изображают в виде замкнутой ломаной линии, соединяющей вершины цикла, расположенные в клетках таблицы.

A1B3 , и A3B3 . Кроме этого, сопоставим каждой вершине цикла знак и

перевозку, при этом свободной клетке сопоставляем знак «+», а для остальных клеток знаки чередуются. Получим следующий цикл, изображенный на рисунке 2.1. Теперь сделаем перестановку по циклу, а именно: из всех вершин, отмеченных минусом, вычтем минимум из всех перевозок, означенных этим знаком, т.е. в читаем ∆ = min(80,90) =80, а ко в сем вершинам с «+» прибавим ∆. Получим

новые значения перевозок, обозначенные на рис. 2.1 в скобках.

31

При этом клетка A1B1 (обозначена знаком «()») становится сво-

бодной, и мы получаем новый опорный план (таблица 2.8). Общая стоимость перевозок равна

z(X ) =3 140 + 4 30 + 2 130 +3 80 +5 10 +14 10 =1230 <1950.

Полученный план лучше начального, и, оценивая его оптимальность с

(рис. 2.2). Так как ∆ = min(30,10) =10, то после перестановки по циклу

кавший в таблице 2.6. Его оптимальность уже была проверена.

Задачи для самостоятельного решения

Решить методом потенциалов транспортные задачи

32