Сток Исток				Запасы:
		10		5	4	40-e
		20		20+e
		6		4	5	23
20				3
		7		3	6	20+e
				20-e
Заявки:	20	20	43	83

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

r = 5

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

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

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

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

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

4. g32×max x32 = - 80.

Сток Исток				Запасы:
		10		5	4	40-e
		20		20+e
		6		4	5	23
20				3
		7		3	6	20+e
				20-e
Заявки:	20	20	43	83

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

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

Сток Исток				Запасы:
		10		5	4	40-e
				40+e
		6		4	5	23
20				3
		7		3	6	20+e
		20		e
Заявки:	20	20	43	83

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

r = 5

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

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

НЕ нашли? Не то? Что вы ищете?

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

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

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

Сток Исток				Запасы:
		10		5	4	40
				40
		6		4	5	23
20				3
		7		3	6	20
		20
Заявки:	20	20	43	83

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

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

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

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

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

Лабораторная работа № 4 (4 часа)

Решение транспортной задачи методом потенциалов

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

Пусть имеется транспортная задача:

Будем условно считать, что каждый из пунктов отправления вносит за перевозку единицы груза платеж ; в свою очередь каждый пункт назначения также вносит за перевозку единицы груза сумму .