Оглавление | Назад | Далее | Глоссарий понятий
Метод потенциалов
Пусть одним из рассмотренных в п.2.6 методов найден опорный план, содержащий n + m - 1 занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправления Аi некоторое число ui (i = l, ..., m) и каждому пункту назначения Bj - число vj (j = 1, ..., n). Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.
Вопрос об оптимальности опорного плана решает следующая теорема:
Теорема 5. Если для некоторого плана X*= (xij ), (i = l, ..., m; j = l, ..., n) транспортной задачи выполняются условия:
1. ui + vj = cij для xij > 0 (для занятых клеток), (2.22)
2. ui + vj < cij для xij = 0 (для свободных клеток), (2.23)
то план X* является оптимальным.
Из теоремы следует, что если для некоторой свободной клетки
ui + vj < cij , то план не является оптимальным.
Отметим, что система (2.22) (m + n - 1) уравнений содержит (m + n) неизвестных ui , vj , и потому, приравнивая одно из них, например u1 к нулю, однозначно определим остальные неизвестные.
Для «улучшения» опорного плана (при невыполнении условия (2.23)) выбирают свободную клетку с max (ui + vj - cij ) и строят для нее цикл пересчета (сдвига).
Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки.
Далее, в свободную клетку помещают груз величиной λ, равной минимальному значению из всех чисел в отрицательных ячейках цикла. Во все положительные клетки прибавляется λ, из отрицательных - вычитается λ (сдвиг по циклу). Нетрудно подсчитать, насколько изменится (уменьшится) стоимость перевозок при новом плане:
, где 
- сумма тарифов в положительных вершинах, 
- в отрицательных вершинах цикла.
Новый опорный план снова проверяют на оптимальность с помощью системы уравнений потенциалов.
Заметим, что в результате пересчета по циклу может оказаться число занятых клеток меньше, чем n+m-1 (план называется вырожденным). В этом случае следует заполнить числом «0» пустую клетку, имеющую минимальный тариф, и не образующую с занятыми клетками замкнутого прямоугольного контура.
Свойство 1. Если, для некоторого оптимального плана X*= (xij ), (i = l, ..., m; j = l, ..., n) транспортной задачи, выполняется условие: ui + vj = cij для xij =0 (для свободных клеток), то, существует как минимум еще один оптимальный план, для которого общая стоимость плана перевозок остается прежней, поскольку (ui + vj) – cij = 0.
Свойство 2. Любая выпуклая линейная комбинация двух оптимальных планов также является оптимальным планом.
Это свойство можно использовать для улучшения планирования, при этом можно учесть особенности, которые не были учтены в математической модели задачи (ранее взятые договорные обязательства, сложившиеся традиции в отношениях и т. д.).
Оглавление | Назад | Далее | Глоссарий понятий
