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

Пусть имеется матрица перевозок, соответствующая начальному решению х_ij ≠ 0 (распределенные ресурсы). Для свободных переменных (ресурсы не распределены) x_ij = 0. Клетки, соответствующие свободным ресурсам, помечены звездочками.

В крайний левый столбец матрицы введем неизвестные u_i, а в верхнюю строку – неизвестные v_j. Переменные u_i и v_j называются потенциалами. Они должны для всех i, j, соответствующих начальному решению, удовлетворять линейной системе уравнений

u_i + v_j = c_ij, (1)

Ранг системы уравнений для всех базисных решений равен n+m–1, и, следовательно, систему всегда можно решить следующим способом. На первом шаге полагают u_n = 0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения (1), так как значение другой неизвестной в этом уравнении уже известно. Это верно до тех пор, пока не найдены все неизвестные. То, какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб.

Последовательность действий алгоритма

1. Составить и решить систему уравнений u_i + v_j = c_ij для клеток, в которые распределены ресурсы. Для облегчения расчетов рекомендуется задаваться нулевым значением одного из неизвестных (например u₃=0).

2. Определить расчетные значения затрат z_ij для клеток, в которые ресурсы не распределены (со свободными переменными):

z_ij = u_i + v_j;

3. Вычислить разность заданных и расчетных затрат

_ij = c_ij – z_ij

и проверить условие оптимальности _ij > 0.

Если все _ij > 0, то исходный план является оптимальным, и переходят к пункту 5, в противном случае переходят к построению нового плана.

4. Построить новый план (уточнить опорный план).

Выбрать _αβ,_ равное максимальному по модулю _ij из состава отрицательных _ij, т.е.

_αβ = max |–_ij|, _ij < 0.

Индексом αβ помечена свободная переменная x_αβ, которая соответствует _αβ. Соответствующую β клетку транспортной таблицы отмечают знаком “+”.

Кроме клетки αβ транспортной таблицы, знаками «–» и «+» помечают клетки таблицы, в которые ресурсы распределены таким образом, что в каждой строке и столбце число знаков «+» будет равно числу знаков «–»,причем в каждой строке и в каждом столбце содержится максимум по одному «+» и «–».

Проставленные в таблице знаки «+» и «–» образуют прямоугольник, в клетках которого расположены соответствующие знаки. Этот прямоугольник представляет фрагмент матрицы, который состоит из четырех клеток, в которых проводят перераспределение ресурсов.

–	+	αβ<0
+	–

Затем определяют минимум M из всех элементов, помеченных знаками «–», и выбирают клетку Z*, где этот минимум достигается. При этом Z* обозначает клетку, в которую ресурсы далее распределяться не будут, а все ее содержимое будет распределено между остальными тремя клетками по следующему правилу:

а) в клетку αβ новой таблицы, записывается число M;

б) клетка Z* остается пустой;

г) в остальных клетках, помеченных знаками «+» и «–», число M вычитается из стоящего в клетке числа или складывается с ним, в соответствии со знаками;

д) содержимое клеток фрагмента переносится в матрицу, а остальные клетки остаются без изменений.

	Вγ	Вβ
Аα	хαγ–М	+М	αβ<0
Аε	Хεγ+М	0	Z*

Для его построения нового опорного плана строится фрагмент опорного плана относительно клетки αβ, имеющей отрицательный потенциал.

5. Определить значение целевой функции, с учетом перераспределения в матрице (уточнение матрицы проводится до тех пор, пока хотя бы одно значение _i <0).

Далее рассчитываются суммарные затраты по новому плану:

На следующих шагах оптимизации повторяются пункты 1–5 алгоритма до тех пор, пока все δ_ij не будут больше 0.