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

Будем применять метод потенциалов, согласно которому опорное решение является оптимальным, если ему соответствуют m+n действительных чисел u_i и v_j называемых потенциалами. Для занятых клеток u_i + v_j = c_ij, для свободных клеток u_i + v_j - c_ij ≤ 0

Одному из потенциалов дается произвольное значение, например, 0. тогда остальные потенциалы определяются однозначно. Если известен u_i, то v_j = c_ij - u_i и наоборот, u_i = c_ij - v_j.

В методе потенциалов также вычисляют оценки свободных клеток

. Если все , то опорное решение является оптимальным.

Продолжим рассмотрение примера 1. Проверим исходный опорный план на оптимальность. Положим u₁ =0. Тогда v₁= c_1,1– u₁= 2-0 =2.

Далее надо рассматривать ту из занятых клеток таблицы 2, для которой один из потенциалов известен.

Последовательность пересчетов следующая:

Клетка (3,1). u₃ +v₁ =c_3,1 = 3; u₃ =c_3,1 - v₁= 3 – 2 =1; u₃ =1

Клетка (3,3) u₃ +v₃ =c_3,3 =8 v₃ =8 - u₃ =8 -1 = 7; v₃ =7

Клетка (2,3) u₂= 5 - v₃ = 5-7 =-2 u₂ =- 2

Клетка (2,2) v₂= 1 - u₂ = 1 –(-2) =3 v₂ =3

Данные заносим в таблицу потенциалов 3.

Таблица потенциалов 3

Потребности b_j	u_i

Запасы, а_i

		-2

v_j

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

Так как , план не оптимален, необходимо одну из базовых переменных заменить на одну из свободных переменных

Для этого строится цикл для , все вершины которого, кроме одной, находятся в занятых клетках, клетках рассмотренного выше опорного плана.

Вершины с координатами таблицы 3 (1,1), (1,3), (3,1), (3,3) являются вершинами цикла Свободная клетка отмечается знаком +, остальные поочередно отмечаются знаками (-) и (+)

У вершин со знаком минус выбирают минимальный груз (в задаче 60), его прибавляют к вершинам со знаком +. После преобразования, меняются знаки вершин. Получаем новый цикл и новое опорное решение

Первоначальный цикл Новый цикл


	+		-

	-		+


	-		+

	+		-

Предыдущее опорное решение Новое опорное решение

Изменение стоимости перевозок

L(X_опт1) = 90*2+50*3+300*1+100*5+60*8 = 1610 усл. ед.

L(X_опт2) = 30*2+60*2+300*1+100*5+ 110*3 = 1610 усл. ед., целевая функция не уменьшилась, поиск решения продолжается.

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