Решение открытой транспортной задачи вида (б)

Пример 2.7. Найти оптимальное распределение поставок для транспортной задачи открытого типа, приведенного в табл. 2.9.

Решение. В данном случае суммарный спрос потребителей больше, чем суммарная мощность поставщиков: (45+35+55+65=200)>(40+60+90=190).

Таблица 2.9.

Введем «фиктивного поставщика» и в таблицу поставок добавим дополнительную строку (табл. 2.10) так, чтобы задача стала закрытой. Для этого запасы фиктивного поставщика следует принять равной 10=200-190. Коэффициенты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу (например, нулю, как в табл. 2.10). согласно теореме 2.3 (о потенциалах), конкретное значение этого числа не влияет на оптимальное распределение поставок.

Таблица 2.10.

Первоначальное базисное распределение поставок для сформулированной закрытой транспортной задачи найдем, например, по методу наименьших затрат.

Таблица 2.11.

	-1		-2(4)
			-3(6) 2 0 0 5 0 0 0 6 (6.12) 0 1 1 0 -2 -1 -2 0
			-2 -4(2)
-2	-2 -1	-2	-2(4)

2(3)

1(5)

0(1)

Для удобства укажем последовательность заполнения таблицы поставок:

х₄₄ =10, х₁₂ =35, х₃₄ =55, х₁₃ =5, х₂₃ =50, х₂₁ =10, х₃₁ =35. В результате приходим к следующему базисному распределению поставок (табл. 2.11).

Установим, оптимально ли это базисное распределение – найдем для него матрицу оценок (2.12). Так как среди оценок свободных клеток есть отрицательные, то найденное распределение не оптимально. Переведем поставку в одну из клеток с наименьшей отрицательной оценкой, например, в клетку (4, 3). Цикл для этой клетки изображен на рис. 2.4.

Рис. 2.4

Поставка, передаваемая по циклу, равна х₄₃ = min (50, 35, 10) = 10. Передвигая по циклу поставку, равную 10 единицам, приходим к следующему распределению поставок (табл. 2.12).

Таблица 2.12.

			0(7)
			-1(3) 2 0 0 5 0 0 0 6 (6.13) 0 1 1 0 0 1 0 2
			-2(2)
-2	-1	- 2	2(6)

0(8)

-2(4)

-1(5)

-2(1)

Так как оценки всех свободных клеток (2.13) для этого базисного распределения неотрицательны, то распределение поставок табл. 2.12 оптимально и транспортная задача решена.

Как видно из таблицы поставок 2.12, поставка 10 единиц 3-му потребителю должно быть доставлено от фиктивного поставщика, то есть, заявка потребителя В₃ останется неудовлетворенным на 10 единиц. Такое распределение поставок является оптимальным, то есть, требует наименьших затрат на перевозки.