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

Пусть одним из рассмотренных в п.2.6 методов найден опорный план, содержащий n + m - 1 занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправления А_i некоторое число u_i (i = l, ..., m) и каждому пункту назначения B_j - число v_j (j = 1, ..., n). Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.

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

Теорема 5. Если для некоторого плана X*= (x_ij ), (i = l, ..., m; j = l, ..., n) транспортной задачи выполняются условия:

1. u_i + v_j = c_ij для x_ij > 0 (для занятых клеток),          (2.22)
2. u_i + v_j < c_ij для x_ij = 0 (для свободных клеток),     (2.23)

то план X* является оптимальным. Из теоремы следует, что если для некоторой свободной клетки 
u_i + v_j < c_ij , то план не является оптимальным.

Отметим, что система (2.22) (m + n - 1) уравнений содержит (m + n) неизвестных u_i , v_j , и потому, приравнивая одно из них, например u₁ к нулю, однозначно определим остальные неизвестные.

Для «улучшения» опорного плана (при невыполнении условия (2.23)) выбирают свободную клетку с max (u_i + v_j - c_ij ) и строят для нее цикл пересчета (сдвига).

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

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

Пример 2.7.1.

Свойство 1. Если, для некоторого оптимального плана X*= (x_ij ), (i = l, ..., m; j = l, ..., n) транспортной задачи, выполняется условие: u_i + v_j = c_ij для x_ij =0 (для свободных клеток), то, существует как минимум еще один оптимальный план, для которого общая стоимость плана перевозок остается прежней, поскольку (u_i + v_j) – c_ij = 0.

Пример 2.7.2.

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