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

Предполагается, что задача сбалансирована.

Алгоритм включает: Предварительный этап:

1. В матрице перевозок построить начальный план X ⁽⁰⁾.

2. Решением системы определить потенциалы всех пунктов в начальном плане.

3. Вычислить оценки небазисных переменных (свободных клеток) и записать матрицу D ⁽⁰⁾.

Основной этап (получены X ^(k) и D ^(k)):

1. Проверить оценки в D ^(k). Если нет положительных, то перейти на п. 9.

2. Определить максимальную оценку D_kr = max D_ij.

3. В матрице X ^(k) построить цикл пересчета на клетке kr.

4. В построенном цикле вычислить q₀ =min X_ij, ijÎ нечет.

5. Прибавить q₀ в четных вершинах цикла и вычесть в нечетных, результат – матрица перевозок X ^(k+1).

6. В матрице D ^(k)) провести выделение строк и столбцов по решению X ^(k+1) (по элементам, базисным в новом решении).

7. К выделенным столбцам прибавить, а из выделенных строк вычесть D_kr, результат – матрица D ^(k+1).

8. Перейти на п.1 основного этапа.

9. Конец.

Примечание. Если имелись запрещенные перевозки (некоторые C_ij=M), то соответствующие переменные в последнем решении должны равняться нулю. В противном случае задача неразрешима.

Пример: Решить методом потенциалов транспортную задачу

(ПО	Потребитель (ПН)	Кол-во груза
B1	B2	B3	B4
A1
A2
A3
Потр-ть					S=80

(ПО)	Потребитель (ПН)	Кол-во груза
B1	B2	B3	B4
A1	10 -			+
A2	+		-
A3			15 +	25 -
Потр-ть					S=80

Решение. Задача сбалансированная. Начальный опорный план перевозок строим по правилу северо-западного угла. Полученный план невырожденный (табл.). Число базисных переменных (занятых клеток) r=m+n-1=3+4-1=6, они выделены цветом.

Значение критерия в начальном плане

Вводим потенциалы для ПО и для ПН так, чтобы для базисных клеток выполнялись равенства:

Полагая последовательно находим остальные потенциалы:

Вычисляем для свободных клеток:

Матрица оценок для начального плана перевозок:

В начальном плане строим цикл на клетке с максимальной оценкой. Это клетка (1,4). Находим значение вводимой переменной: =min(10,15,25)=10.

Переместив q₀ по циклу, получаем новый план перевозок для которого первая итерация улучшила критерий на 90 единиц.

Находим матрицу оценок. С этой целью в D ⁽⁰⁾ отмечаем элементы, соответствующие базисным в X ⁽¹⁾, и строим цепочку выделения. Так как в строке с максимальной оценкой других отмеченных элементов нет, выделенной оказывается только первая строка. Вычитая из нее D_kr, получаем матрицу.

.Как следует из анализа матрицы D ⁽¹⁾, решение X ⁽¹⁾ не является оптимальным. Следующее решение получаем с помощью построенного в X ⁽¹⁾ цикла, перемещая по нему : Мы получили новый план перевозок с критерием .

Матрицу оценок этого плана находим преобразованием матрицы D ⁽¹⁾ аналогично описанному выше.

В матрице есть положительный элемент, поэтому на клетке (3,2) строим цикл пересчета. Определяем и, перемещая 5 по циклу, находим очередной план перевозок, кот соответствует значение критерия . Преобразуем матрицу D ^(II).

Эта матрица не содержит положительных оценок, следовательно, план является оптимальным. Согласно этому плану от 1-го поставщика надо поставить 10 ед. продукции 4-му потребителю, от 2-го поставщика - 20 ед. первому и 10 ед. четвертому потребителям, от 3-го поставщика - 5, 30 и 5 ед. соответственно 2, 3 и 4 потребителям. Такая схема перевозок обеспечивает минимум суммарных затрат, которые = 150.

Примечания. Метод потенциалов применим и для решения трипланарных задач. Отличие лишь в том, что циклы пересчета и цепочки выделения строятся не на плоскости, а в трехмерном пространстве.