Алгоритм метода потенциалов. 1. Записать условие ТЗ в виде таблицы

1. Записать условие ТЗ в виде таблицы.

2. Проверить условие .

3. Построить опорный план, при этом число загруженных клеток должно быть равным r = m+n-1 и соблюдаться условие (1.26), (1.27).

4. Проверить план на отрицательность, для чего выписать матрицу стоимостей и подобрать потенциалы таким образом, чтобы U_i+V_j+C_ij=0 в загруженных клетках. Если во всех незагруженных клетках C_ij>=0, то план является оптимальным.

5. Если план отрицательный, т.е. U_i+V_j+C_ij<0 в незагруженных клетках, то его надо улучшать. Для этого следует выбрать из всех C_ij<0 максимальный по модулю, т.е. C_ij= - max[C_ij], C_ij <0.

6. Начиная с этой выбранной клетки матрицы стоимостей построить цикл, пользуясь данными выше определениями. Потом, начиная с выбранной клетки, перенумеровать вершины цикла, двигаясь, например, по часовой стрелке.

четн

7. Из всех маршрутов, приходящихся на вершины цикла с четными номерами, найти маршрут с минимальной перевозкой X_ij^*= {X_ij}.

Затем объем этой перевозки вычесть из всех объемов перевозок, приходящихся на четные номера цикла, и прибавить к объемам перевозок, приходящихся на нечетные номера.

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

8. Перейти к пункту 4.

Пример. Решить ТЗ с условиями (1.25) - (1.28).

1. Запишем ТЗ в таблицу 1.13.