В. 43 Алгоритм метода потенциалов

Метод потенциалов предназначен для решения транспортной задачи в матричной по­становке. Потенциалы - это двойственные переменные. Сам метод - прямой, на каждом шаге выбирается одно из двойственных ограничений, которое не выполняется и исправ­ляется таким образом, чтобы не нарушить ограничения прямой задачи. Постепенно в двойственной задаче ограничения будут выполнены, что будет означать оптимальность в прямой задаче.

Таблица для метода потенциалов имеет следующий вид:

Каждая ячейка (i, j) таблицы хранит информацию о цене (с_ij) и о количестве перевозимого товара (x_ij). В процессе решения задачи часть клеток будем называть базисными (их всегда будет m+n-1), а остальные - небазисными (или свободными).

Алгоритм

Шаг 0. Замкнуть задачу, если она не замкнута. Перейти на шаг 1.

Шаг 1. Нарисовать начальную таблицу. Перейти на шаг 2.

Шаг 2. Рассчитать начальный план перевозок (например, методом северо-западного угла) и выделить базисные клетки. Вычислить значение целевой функции. Перейти на шаг 3.

Шаг 3. Рассчитать значения потенциалов. Положить u₁=0 (или любому другому чис­лу). Остальные потенциалы рассчитать с помощью базисных клеток, исходя из уравнения u_i+v_j=c_ij. Перейти на шаг 4.

Шаг 4. Для свободных клеток рассчитать оценки s_ij=c_ij-v_i-v_j. Если все s_ij≥0, то найдено оптимальное решение. Перейти на шаг 6. Иначе выполнить шаг 5.

Шаг 5. Из небазисных клеток выбрать ту, у которой оценка s_ij минимальна и для нее выполнить следующую процедуру:

• Построить цикл для этой клетки. Цикл - это замкнутая ломаная линия, кото­рая чередует вертикальное и горизонтальное направления и проходит только по базисным клеткам. В исходной клетке поставить «+» и далее по циклу расставить, чередуя, «+» и «-».

• Вычислить λ=min{x_ij: «-»}. Клетку, на которой достигается этот минимум, убрать из базиса (только одну), а клетку (i,j) (у которой минимальная оцен­ка s_ij) сделать базисной.

• Нарисовать новую таблицу, с пересчитанным планом перевозок: для клеток с «+» прибавить λ к х_ij а для клеток с «-» - вычесть. Остальные клетки остаются как были. Пересчитать целевую функцию: z’=z+min s_ij *λ.

Перейти на шаг 3.

Шаг 6 Конец алгоритма.

На шаге 3 у нас m+n-1 уравнений и n+m неизвестных. Поэтому возникает неоднозначность, разрешить которую можно, определив одну из переменных заранее (например, u₁=0).