Симплекс-метод, решение задачи с искусственным базисом

2) Решим задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").

Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х₃ ≥ 0 и х₄ ≥ 0 получим:

Система ограничений предлагает только одну допустимую базисную переменную x₄, только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R₁ ≥ 0 и R₂ ≥ 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R₁, R₂ и x₄. Получили, так называемую, М-задачу:

Данная система является системой с базисом, в которой R₁, R₂ и x₄ базисные переменные, а x₁, x₂ и x₃ свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

итерация 0

БП	x1	x2	x3	R1	R2	x4	Решение	Отношение
z	-4	-16	0	0	0	0	0	-
R1	3	4	-1	1	0	0	6	6/4=3/2
R2	1	3	0	0	1	0	3	3/3=1
x4	2	1	0	0	0	1	4	4/1=4
Оценка	-4	-7	1	-1	-1	0	-	-

В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х₂, он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R₂ выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации переменная х₂ из свободной перейдет в базисную, а переменная R₂ из базисной – в свободную. Запишем следующую симплекс-таблицу:

итерация 1

БП	x1	x2	x3	R1	R2	x4	Решение	Отношение
z	4/3	0	0	0	16/30	0	16	-
R1	5/3	0	-1	1	-4/3	0	2	6/5
x2	1/3	1	0	0	1/3	0	1	3
x4	5/3	0	0	0	-1/3	1	3	9/5
Оценка	-5/3	0	1	-1	4/3	0	-	-

Разрешающий столбец х₁, разрешающая строка R₁, R₁ выходит из базиса, x₁ входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:

итерация 2

БП	x1	x2	x3	R1	R2	x4	Решение	Отношение
z	0	0	4/5	-4/5	32/5	0	72/5	-
x1	1	0	-3/5	3/5	-4/5	0	6/5	-
x2	0	1	1/5	-1/5	3/5	0	3/5	-
x4	0	0	1	-1	1	1	1	-

Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R₁, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, получено оптимальное решение x₁ = 6/5; x₂ = 3/5; z_max = 72/5.