Теорема о существовании оптимального решения

Пусть одним из методов решения транспортной задачи найден опорный план, содержащий m+n - 1 занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправления А_i некоторое число , и каждому пункту назначения - число , .

Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.

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

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

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

то план является оптимальным.

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

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

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

, (40.3)

где - сумма тарифов в положительных вершинах, - в отрицательных вершинах цикла.

Новый опорный план снова проверяют на оптимальность с помощью системы уравнений потенциалов.

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

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