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

Решим транспортную задачу методом потенциалов. За исходное решение примем базисное решение, полученное методом наименьшей стоимости.

Таблица 2.13

Базы	В1	B2	B3	B4	B5	Запасы
A1
A2
A3
Пот-ребн.

Составим систему потенциалов для заполненных клеток табл.2.13.

Имеем:

Получим:

Потенциалы _i для строк записываем в дополнительном столбце справа, а потенциал столбцов _j в нижней дополнительной строке (табл. 2.14).

Таблица 2.14

Базы	Потребители	Запасы	ai
B1	B2	B3	B4	B5
A1
		40 -	+ 10
A2							-2
		+	- 20
A3							-4
Пот-ребн.
bj

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

Достаточное условие оптимальности не выполнено для клетки A₂B₂.

Составим для нее цикл пересчета. В таблице 2.14 он отмечен штриховыми линиями.

Находим минимальное число для клеток, которым присвоен знак минус.

D = min (40,20) =20 - величина сдвига по циклу.

После пересчета по циклу получим:

Получаем новый план перевозок (табл.2.15).

Таблица 2.15

Базы	Потребители	Запасы	ai
	B1	B2	B3	B4	B5
A1
A2							-9
A3							-4
Потребности
bj

Стоимость перевозок составляет:

руб.

Составим систему потенциалов для заполненных клеток табл.2.15.

Имеем:

Полагая ₁= 0, находим потенциалы.

Получим:

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

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

Наименьшая стоимость перевозок составила 1950 руб.

Таким образом, оптимизация позволила получить экономию

Z₁ - Z _min =2090 - 1950 = 140 рублей.