2. Транспортная задача: условия оптимальности опорного плана, метод потенциалов.

Потенциалы и_i и v_j приписываются каждому поставщику и потребителю. Всего потенциалов п+m. Для заполненных клеток, которых т+п— 1, выполняются условие

.

Они служат теми уравнениями, из которых находят значения потенциалов. Эта система уравнений имеет бесчисленное множество решений, любое из которых составит искомую систему потенциалов. Чтобы найти какое-либо одно решение, значение одного из потенциалов нужно выбрать произвольно. Остальные устанавливаются из системы уравнений для заполненных клеток. Обычно считают, что u₁ = 0, и вычисляют остальные потенциалы.

Для каждой клетки вычисляют оценки:

.

Если опорный допустимый план оптимален, то ≥ 0. Если же есть хоть одна отрицательная оценка, то план не оптимален. Тогда в базис вводят клетку с минимальной оценкой. Эту клетку называют перспективной.

Экономический смысл оценки в том, что она показывает, на сколько можно уменьшить транспортные издержки при загрузке данной клетки единицей груза.

Для улучшения опорного плана для перспективной свободной клетки строится замкнутый цикл. Вершинам этого цикла присваиваются знаки: свободной клетке – «плюс», следующей по часовой или против часовой стрелки клетке – знак «минус», следующей клетки – «плюс» и т.д.

В клетках с отрицательными вершинами выбирается минимальное количество груза λ, которое будет перемещаться по циклу. Оно прибавляется к грузу в вершинах с положительным знакам и вычитаться из поставок в отрицательных вершинах. В результате подобных вычислений баланс не нарушается.

Алгоритм метода потенциалов:

1. построить опорный план по одному из правил;

2. вычислить потенциалы поставщиков и потребителей и , решив систему уравнений ;

3. вычислить оценки для всех свободных клеток. Если все ≥ 0, то опорный план оптимален. Если же для всех свободных клеток > 0, то оптимальный план единственный. Если же хоть для одной свободной оценки =0, то имеется бесчисленное множество оптимальных планов с одним и тем же значением целевой функции;

4. в случае если есть < 0, то строиться цикл, расчетная таблица заполняется заново и алгоритм начинается с пункта 2.

15