Пример 2. Решение транспортной задачи

Найти оптимальный план перевозок транспортной задачи, имеющей следующую таблицу издержек:

Сток Исток				Запасы:
Заявки:

Решение:

1. Методом «северо-западного» угла найдем опорный план перевозок:

Сток Исток				Запасы:
Заявки:

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

r = n + m – 1 = 3 + 3 – 1 = 5 ¹ 4

План получается вырожденный.

Сток Исток				Запасы:
							40-e
				e
							20+e
				20-e
Заявки:

Чтобы избежать этого, нарушаем баланс запасов и заявок на e в 1 и 3 строках, не нарушая общего баланса. Теперь:

r = 5,

а найденный опорный план можно использовать в дальнейшем для решения задачи.

Стоимость найденного плана перевозок равна:

L = 20×10 + 20×5 + 23×5 + 20×6 = 535.

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

2. Вычислим цену цикла для k = 4 свободных клеток.

3. Вычислим максимальное количество груза, которое можно перенести по циклам с отрицательной ценой.

4. Для свободных переменных с отрицательной ценой цикла вычислим характеристику .

(i,j)	2,1	2,2	3,1	3,2
g	- 5	- 2	- 5	- 4
g×max x	- 100	- 40	- 100	- 80

5. Перенесем max x₂₁ = 20 единиц груза по циклу свободной переменной х₂₁, уменьшив значение целевой функции на 100 единиц, то есть:

Сток Исток				Запасы:
							40-e
				e
							20+e
				20-e
Заявки:

В результате получим следующий (уже не вырожденный) план перевозок:

Сток Исток				Запасы:
							40-e
				20+e
							20+e
				20-e
Заявки:

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

r = 5

Стоимость найденного плана перевозок равна:

L = 20×5 + 20×4 + 20×6 + 3×5 + 20×6 = 435

Попытаемся еще улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

2. Вычислим цену цикла для каждой свободной переменной.

3. Максимальное количество груза, которое можно перенести по циклу свободной переменной х₃₂ = 20.

4. g₃₂×max x₃₂ = - 80.

Сток Исток				Запасы:
							40-e
				20+e
							20+e
				20-e
Заявки:

5. Перенесем 20 единиц груза по циклу переменной x₃₂, , уменьшив значение целевой функции на 80 единиц.

В результате получим следующий план перевозок:

Сток Исток				Запасы:
							40-e
				40+e
							20+e
				e
Заявки:

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

r = 5

Стоимость найденного плана перевозок равна:

L = 40×4 + 20×6 + 3×5 + 20×3 = 355

Еще раз попытаемся улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

2. Вычислим цену цикла для каждой свободной переменной.

3. Максимальное количество груза, которое можно перенести по циклу единственной свободной переменной х₂₂, имеющей отрицательную цену цикла, равно бесконечно малой величине e. Полагая e = 0, получим окончательный оптимальный план перевозок:

4.

Сток Исток				Запасы:
Заявки:

стоимость которого равна:

L = 40×4 + 20×6+ 3×5 +20×3 =355

Примененный метод «ликвидации вырождения» путем изменений запасов на бесконечно малую величину e не всегда удобен, так как требует дополнительных действий с бесконечно малыми величинами e. Значительно проще было бы не изменять запасы, а вместо величины e поставить в базисной клетке нуль. Тогда базисная клетка будет тем отличаться от свободной, что в ней нуль поставлен, а в свободной нет.

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

Рассмотрим теперь другой метод решения транспортной задачи – метод потенциалов.