Метод двойного предпочтения

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

Оптимальность плана транспортной задачи.

Метод потенциалов

Пусть одним из рассмотренных в п.2.6 методов найден опорный план, содержащий  занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправления некоторое число  и каждому пункту назначения - число . Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.

Вопрос об оптимальности опорного плана решает следующая теорема:

Теорема 5. Если для некоторого плана ) транспортной задачи выполняются условия:

1. для  (для занятых клеток), (2.16)
2. для  (для свободных клеток), (2.17)

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

Отметим, что система (2.16) уравнений содержит  неизвестных  ,  , и потому, приравнивая одно из них, например к нулю, однозначно определим остальные неизвестные.

Для «улучшения» опорного плана (при невыполнении условия (2.17)) выбирают свободную клетку с  и строят для нее цикл пересчета (сдвига).

Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки.
Далее, в свободную клетку помещают груз величиной λ, равной минимальному значению из всех чисел в отрицательных ячейках цикла. Во все положительные клетки прибавляется λ, из отрицательных - вычитается λ (сдвиг по циклу). Нетрудно подсчитать, насколько изменится (уменьшится) стоимость перевозок при новом плане:

, где - сумма тарифов в положительных вершинах, - в отрицательных вершинах цикла.
Новый опорный план снова проверяют на оптимальность с помощью системы уравнений потенциалов.
Заметим, что в результате пересчета по циклу может оказаться число занятых клеток меньше, чем  (план называется вырожденным). В этом случае следует заполнить числом «0» пустую клетку, имеющую минимальный тариф, и не образующую с занятыми клетками замкнутого прямоугольного контура.

Пример 1

Проверить оптимальность опорного плана ТЗ, решенной, в примере 6.
Решение. Составляем систему уравнений потенциалов:

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

Таблица 2.10

					Запасы
	13	7 15-	11 +	5 15	30
	11	8 12+	13 36 -	7	48
	6 18	10	12 6	9	24
Потребности	18	27	42	15	102

при этом будет  

В системе потенциалов для этого плана лишь 1-ое уравнение заменялся равенством .
Тогда, положив , находим  
Убеждаемся, что для всех свободных клеток выполняется условие (2.17). Следовательно, план и  

Свойство 1. Если, для некоторого оптимального плана

транспортной задачи, выполняется условие:  для  (для свободных клеток), то, существует как минимум еще один оптимальный план, для которого общая стоимость плана перевозок остается прежней, поскольку

Пример 2.

Проверить оптимальность ТЗ, определенную таблицей (табл.2.11).

Таблица 2.11

	2	7	3	6	2	50
	9	4	5	7	3	50
	5	7	6	2	4	50
	10	40	20	60	20	150

Решение. Ведем построение опорного плана методом наименьшей стоимости (таблица 2.12)

Таблица 2.12

	2 10	7	3 20	6	2 20	50
	9	4 40	5	7 10	3 0	50
	5	7	6	2 50	4	50
	10	40	20	60	20	150

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

Получаем опорный план:

Вычислим общую сумму затрат на перевозку груза по этому плану:

Составляем систему уравнений потенциалов:

Полагая