6.9. Пример

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

	1	2	3
1	3	8	2	35
2	7	4	8	30
	15	20	30	=

Опорный план этой задачи найден методом северо-западного угла.

Приписываем к таблице строку для платежей , и столбец для платежей . Псевдостоимости записываем в левом углу клетки, а стоимости – в правом.

Из условий в базисных клетках получаем систему уравнений:

Полагая , находим последовательно платежи и псевдостоимости для свободных клеток. Получаем таблицу

	1	2	3
1	15 3	[-] 20 8	12[+] 2	35	0
2	-1 7	[+] 0 4	[-] 30 8	30	-4
	15	20	30	=
	3	8	12

Стоимость перевозок по плану этой таблицы

Так как клетка (1,3) имеет отрицательную цену , то план не является оптимальным. Строим для клетки (1,3) цикл. Цена цикла . По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1,2) не стали отрицательными). При этом стоимость плана изменяется на . Для нового плана вычисляем новые значения платежей и псевдостоимостей:

	1	2	3
1	[-]15 3	-2 8	[+] 20 2	35	0
2	9 [+] 7	20 4	[-] 10 8	30	6
	15	20	30	=
	3	-2	2

Стоимость перевозок по плану этой таблицы

Полученная таблица имеет клетку (2,1) с отрицательной ценой . По циклу этой клетки переносим 10 единиц груза, при этом стоимость плана уменьшается на единиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:

	1	2	3
1	5 3	0 8	30 2	35	0
2	10 7	20 4	5 8	30	4
	15	20	30	=
	3	0	2

Стоимость перевозок по плану этой таблицы

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