Искусственное начальное решение

пример. min z = 4x₁ + x₂.

max (– z) = – 4x₁ – x₂.

Если начальное решение x₁ = x₂ = 0, то

– не является допустимым решением.

Добавляем искусственные переменные R_i.

Начальное решение x₁ = x₂ = 0.

– не является допустимым решением.

Исходная задача будет иметь решение только в том случае, когда полученная задача имеет решение R₁ = R₂ = 0.

Двухэтапный метод

1) min r = R₁ + R₂.

Если эта задача имеет решение при r = 0 при R₁ = R₂ = 0, то исходная задача также имеет решение, причем оптимальное решение составленной задачи является начальным решением исходной.

Если же r = R₁ = R₂ = 0 не выполняется, то исходная задача решений не имеет.

2) Решается исходная задача

min r = R₁ + R₂; max (– r) = – R₁ – R₂.

Итак,

Метод больших штрафов (М – метод)

max (– z) = – 3x₁ – 2x₂ – 3x₃ – MR₁ – MR₂.

M>>1.

R₁ = R₂ = 0 – Если это получим, то исходная задача имеет решение, если этого не получим, то исходная задача не имеет решения.

Б	С	Xопт	– 3	– 2	– 3			– M	– M
x1	x2	x3	s1	s2	R1	R2
R1	– M					– 1
R2	– M						– 1
– z		–10M				M	M
R1	– M		5/4		1/2	– 1	1/4		не надо
x2	– 2		3/4		1/2		– 1/4		не надо
– z		–4				M			не надо
x1	– 3				2/5	– 4/5	1/5	не надо	не надо
x2	– 2				1/5	3/5	– 2/5	не надо	не надо
– z		–4			7/5	6/5	1/5	не надо	не надо

x₁ = 0; x₂ = 0; x₃ = 0; max (– z) = – 4; min z = 4.