6.5. Открытая транспортная задача

Транспортная задача называется открытой, если запасы груза превышают потребности в нем или, если потребности невозможно удовлетворить имеющимися запасами. Для решения задачи в этих случаях вводят фиктивного потребителя или поставщика груза. На этих (реально не существующих) участников перевозок и записывают недостающее количество груза или потребности в нем. Стоимости перевозок от фиктивных станций полагаются равными нулю. Тогда задача становится закрытой и решается методом потенциалов. Для примера, ниже приведена задача, в которой введен фиктивный потребитель В₅, позволяющий вывезти все грузы из пунктов А₁, А₂, А₃.

	В1	В2	В3	В4	В5 *
А1	5 ^10	9	4	11	0 40*	50
А2	21 15	7	6 35	14	0	50
А3	7 5	5 40	10	6 25	0	70
	30	40	35	25	40

В этом примере построен опорный план по методу наименьшей стоимости. Фиктивный потребитель и перевозка равная грузу, который фактически остается на станции А₁, помечены звездочкой. Задача, записанная в таблице, является закрытой и ее решение можно довести до получения оптимального плана (предлагаем Вам сделать это самостоятельно).

6.6. Проблема вырожденного плана задачи

При определении первого опорного плана нередко возникает ситуация, когда число занятых клеток меньше величины m+n-1. В этом случае система (6.5) не позволяет определить потенциалы потребителей и поставщиков. Решение проблемы рассмотрим на примере. При построении опорного плана методом северо-западного угла в клетку А₁-В₁ была внесена перевозка x₁₁ = 50, при этом, первая строка и первый столбец были вычеркнуты одновременно (что и привело к вырожденности плана). Такую клетку следует запомнить или отметить с тем, чтобы после заполнения всей таблицы ввести фиктивную перевозку в вычеркнутую строку или столбец, выбрав клетку с наименьшей стоимостью. В примере это клетка А₁-В₃, которая в дальнейших расчетах считается занятой с перевозкой равной нулю.

	В1	В2	В3	В4	В5
А1	5 50	9	4 0	11	8	50
А2	21	7 40	6 10	14	12	50
А3	7	5	10 25	6 25	19 20	70
	50	40	35	25	20

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