Обоснование метода потенциалов

Метод потенциалов основан на второй теореме двойственности для задачи линейного программирования для двойственной задачи.

Если переменная X_ij≠0, то соответствующее решение двойственной задачи:

X_ij≠0 U_i + V_j = C_ij =› U_i º 0

x_lk = 0 U_l + V_k < C_lk C_lk - U_l - V_k > 0

a_lk > 0, если нет, то строим новое начальное решение и т.д.

Если a_lk = 0, то имеет место альтернативный оптимум и выполняется еще одна операция и этот элемент выбирается за разрешающий.

Vj Ui	V1	V2	V3	V4
U1				2			3	2		4			3
U2	-1	4		5	1		3			1			2
U3	-2	2		2			1	4		4	1		2
U4	-2			0	-1		0	0		0	-1		0

U₁ + V₁ = 2 U₁ = 0

U₁ + V₂ = 3 V₁ = 2

U₁ + V₃ = 1 V₄ = 3

U₁ + V₄ = 3 V₂ = 3

U₂ + V₃ = 1 U₂ = -1

U₂ + V₄ = 2 V₃ = 2

U₃ + V₂ = 1 U₃ = -2

U₄ + V₁ = 0 U₄ = -2

U_i + V_j = C_ij

U_i = C_ij - V_j

V_j = C_ij – U_i, U₁ º 0

U_i + V_j < C_ij

Vx_ij^* = 0

U_i + V_j < C_ij

a_lk = C_lk - U_i - V_i > 0

a_lk = 0

Решение не оптимальное, находим следующее решение.

(r, s) = {l; k │ min a_lk < 0} = (4,2)

min a_lk = -1

X0=		+20	40-
	-30	0*+

Строим цикл, начиная с разрешающего элемента 0^*, таким образом, чтобы в вершинах его были ненулевые элементы.

Помечаем вершины, начиная с разрешающего нуля, чередованием знаков + -.

Θ₁ = min {x_lk^-}= min {40,30} = 30

X1=			+10		30-
		-30		0*+

f_o(x¹) = 2·50 + 3·10 + 3·30 + 1·20 + 2·10 + 1·40 + 0·30 = 300

f_o(x¹) = f_o(x⁰) + Θ₁ (∑C_pq⁺ - ∑C_ef^-) = 330 + 30 · (2 + 0 – 3 + 0) = 300

Vj Ui	V1	V2	V3	V4
U1				2			3	2		4			3
U2	-1	4		5	1		3			1			2
U3	-2	2		2			1	4		4	4		2
U4	-3	-1		0			0	1		0	-1		0

На каждом этапе необходимо делать проверку:

C_ij = U_i + V_j – проверка.

a_lk = C_lk – U_l - V_k

a₄₄ = 0, то имеет место альтернативный оптимум.

Q₂ = min [30^-; 30^-] = 0

X2*=			40
		0-

f_o(x^2*) = 2·50 + 3·40 + 1·20 + 2·10 + 1·40 + 0·30 = 300

f_o(x^2*) = f_o(x^1*) + 30*(3 + 0 – 3 – 0)

Vj Ui	V1	V2	V3	V4
U1				2			3	2		4			3
U2	-1	4		5	1		3			1			2
U3	-2	2		2			1	4		4	1		2
U4	-3	1		0			0	1		0			0

Ответ: f_o(x^*) = 300

X2*=

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