Метод потенциалов нахождения оптимального плана перевозок

Проверка плана перевозок на оптимальность и переход к лучшему плану осуществляется методом потенциалом. Принцип нахождения оптимального плана перевозок транспортной задачи методом потенциалов основан на следующем утверждении.

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

• для всех занятых клеток ;

• для всех свободных клеток .

Отсюда следует алгоритм нахождения оптимального плана перевозок:

1. По построенному плану перевозок каждому поставщику ставят в соответствие число ( ), каждому потребителю – число ( ). Числа и , называют потенциалами. Значения потенциалов подбирают так, чтобы для всех заполненных клеток выполнялось равенство:

. (3.8.6)

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

2. После того как потенциалы найдены, для каждой свободной клетки вычисляют оценку . Если все оценки свободных переменных , то полученный план перевозок оптимален.

3. Если же есть хотя бы одна положительная оценка , то план не является оптимальным и необходимо перейти к новому, улучшенному плану. Для этого нужно какую-либо заполненную клетку освободить, а некоторую свободную клетку заполнить. Будем заполнять ту свободную клетку , для которой положительная оценка наибольшая (если несколько свободных переменных имеют равные наибольшие оценки – выбирают любую).

4. Для выбранной свободной клетки с наибольшей положительной оценкой строят замкнутый цикл: соединяя последовательно клетки цикла отрезками прямой, получаем замкнутую ломаную линию; для нее каждое звено лежит либо в строке, либо в столбце и только одна из вершин ломаной находится в свободной клетке . Этой клетке условно приписывают знак «+», а следующей клетке цикла по ходу часовой (или против часовой) стрелки ставится знак «–», а далее знаки чередуются.

5. Среди значений , соответствующих отрицательным вершинам цикла, отыскивают минимальное число Проводим перемещение по циклу числа : это число прибавляют к числам, стоящим в клетках со знаком «+», включая свободную клетку цикла, а из чисел в клетках со знаком «–» вычитают . В результате такого перемещения баланс по каждой строке и каждому столбцу не нарушается, изменяется лишь набор занятых клеток. Клетка , которая ранее была свободна, становится занятой, а клетка, в которой стояло число , станет свободной. В результате перемещения числа  по клеткам замкнутого цикла получается новый план перевозок .

6. Строим новый план перевозок в распределительной таблице, вычисляем значение транспортных затрат. Новый план перевозок проверяем на оптимальность, то есть возвращаемся к пункту 1 алгоритма. Записываем систему уравнений для новых заполненных клеток, ищем потенциалы и т.д. Если план оптимальный – закончить расчеты, вычислить значение транспортных затрат. Если план не оптимальный – перейти к этапу 3. Процесс повторяют до тех пор, пока не будет получен план, для которого все оценки .

Сделаем несколько замечаний:

• для любой свободной клетки можно построить только один цикл;

• потенциалы, как и циклы, для каждого плана определяются заново;

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

• при переходе от одного плана перевозок к другому значение целевой функции изменится на величину:

, (3.8.7)

где  – число, перемещаемое по циклу, составленному для свободной клетки , а – оценка, соответствующая этой клетке.