Открытые транспортные задачи.

Таблица 5.11

Таблица 5.10

Таблица 5.9

П_н П_о	В₁	В₂	В₃	В₄	Запасы	α_i
А₁	² 15	^{1 4}	^{5 7}	^{11 6}
А₂	⁵ 7	⁴ 18	⁸	^{14 9}
А₃	^{3 4}	^{2 11}	⁶ 7	¹² 13
Потребности					70=70
β_j

Для определения потенциалов решим следующую систему:

Положим α₁=0. Тогда β₁=2; α₂=3; β₂=1; β₃=5; α₃=1; β₄=11. Найденные потенциалы вносим в таблицу 5.9.

Вычисляем псевдостоимости для свободных клеток и проставляем их в левые верхние углы клеток. Выбираем свободную клетку, в которой ; например, выберем клетку (1,4). Строим цикл пересчета, проходящий через эту клетку, и произведем по нему максимально допустимый сдвиг h = 10 (в отрицательных клетках наименьшей перевозкой является х₂₃=10). После сдвига клетка (2,3) становится свободной, а клетка (1,4) - базисной. Получаем новый опорный план, записанный в таблице 5.10.

П_н П_о

В₁

В₂

В₃

В₄

Запасы

α_i

А₁

¹⁴

⁰⁷

⁶

А₂

⁵ 17

⁴ 18

³⁸

⁹⁹

А₃

^{8 7}

^{7 11}

⁶ 17

¹²

Потребности

70=70

β_j

Вновь строим систему потенциалов, рассчитываем псевдостоимости, строим цикл пересчета, проходящий через клетку (3,1), делаем по нему максимально допустимый сдвиг величины h=3.

П_н П_о	В₁	В₂	В₃	В₄	Запасы	α_i
А₁	² 2	^{1 4}	^-4⁷	⁶
А₂	⁵ 17	⁴ 18	^-1⁸	^{9 9}
А₃	⁴	²¹¹	⁶ 17	^{8 1}²
Потребности					70=70
β_j			-4

После сдвига получим опорный план, записанный в таблице 5.11. Построив систему потенциалов и рассчитав псевдостоимости, видим, что для всех свободных клеток . Поэтому опорный план оптимален.

Итак, оптимальный план имеет следующий вид: х₁₁=2; х₁₄=13; х₂₁=17; х₂₂=18; х₃₁=3; х₃₃=17.

При этом f_mln = 2•2 + 13•6 + 17•5 + 18•4 + 3•4 + 17•6 =353

При рассмотрении транспортной задачи (5.1 - 5.4) предполагалась справедливость равенства . Такие транспортные задачи называются закрытыми.

На практике часто возникают так называемые открытые транспортные задачи, для которых .

Если , то задача состоит в отыскании наиболее дешевого плана перевозок, при котором полностью удовлетворяются потребности пунктов назначения В_j (); при этом не все запасы пунктов отправления исчерпываются.

Если же , то потребности пунктов назначения не полностью удовлетворяются, а запасы пунктов отправления исчерпываются.

Открытая транспортная задача сводится к закрытой следующим образом.

Пусть . Введём фиктивный пункт назначения В_n₊₁ с потребностью .

Будем считать, что c_in₊₁=0 при всех . После решения полученной закрытой транспортной задачи опустим перевозки в пункт В_n₊₁; получим оптимальный план перевозок для открытой транспортной задачи.

Аналогично, в случае справедливости неравенства вводится фиктивный пункт отправления А_m₊₁, и дело сводится к решению закрытой транспортной задачи.

Пример. Пусть исходные данные приведены в таблице 5.12