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

Таблица 5.11

Таблица 5.10

Таблица 5.9

Пн По	В1	В2	В3	В4	Запасы	αi
А1	2 15	1 4	5 7	11 6
А2	5 7	4 18	8	14 9
А3	3 4	2 11	6 7	12 13
Потребности					70=70
βj

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

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

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

Пн По	В1	В2	В3	В4	Запасы	αi
А1	- 2 5	1 4	0 7	+ 6 10
А2	5 17	4 18	3 8	9 9
А3	+ 8 7	7 11	6 17	- 12 3
Потребности					70=70
βj

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

Пн По	В1	В2	В3	В4	Запасы	αi
А1	2 2	1 4	-4 7	6
А2	5 17	4 18	-1 8	9 9
А3	4	2 11	6 17	8 12
Потребности					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+1 с потребностью .

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

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

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