M-задача

Метод искусственного базиса применяется для решения канонической ЗЛП в случае, когда задача не имеет начального решения с базисом из единичных векторов (ортонормированным базисом).
В этом случае в уравнения, не содержащие базисной переменной, добавляют со знаком «+» неотрицательные переменные, называемые искусственными.
В отличие от дополнительных переменных, искусственные переменные влияют на целевую функцию Z(X), они входят в нее с коэффициентами М, причем в задачу на максимум с коэффициентом –М, в задачу на минимум с коэффициентом +М. Величина М предполагается достаточно большим положительным числом (M>>1), значение которого не задается. Поэтому такая задача носит название М-задачи.
В случае решения задачи на максимум расширенная задача имеет вид:

при ограничениях:

x_j≥ 0.
Векторы A_n₊₁,A_n₊₂,…,A_n₊_m называются искусственными векторами. Данная задача имеет начальное опорное решение

с базисом Б = (A_n₊₁,A_n₊₂,…,A_n₊_m) (в этом случае исходный базис целиком состоит из искусственных векторов).

Справедлива следующая теорема.

Если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи;
если в оптимальном решении М-задачи хотя бы одна искусственная переменная отлична от 0, то исходная задача не имеет решения (из-за несовместимости системы ограничений);
если М-задача не имеет решения из-за неограниченности целевой функции, то и исходная задача решения не имеет.

Особенности алгоритма метода искусственного базиса

Виду того, что начальное опорное решение расширенной ЗЛП содержит искусственные переменные, входящие в целевую функцию с коэффициентами -М (max) или +М (min), оценка разложений векторов условий Δ_j= C_бX_j -c_j состоит из двух слагаемых Δ_j= Δ’_j +Δ’’_j( M). Т.к. М – велико, то на первом этапе расчета для нахождения векторов, вводимых в базис, используется только слагаемое Δ’’_j( M).
Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного решения, исключаются из рассмотрения.
После того как все векторы, соответствующие искусственным переменным, исключены из базиса, расчет продолжается обычным симплексным методом с использованием оценок Δ’_j, не зависящих от М.
Переход от решения расширенной ЗЛП к решению исходной ЗЛП осуществляется с помощью указанных ранее замечаний.

Пример. Найти решение следующей задачи.
Z(X)=x₁+x₂+4x₃→max
x_j≥0 (j=1,2,3)
Приведем задачу к каноническому виду:

x_j ≥ 0 (j=1,2,3,4,5,6)

Z(X)=x₁+x₂+4x₃+0x₄+0x₅+0x₆-Mx₇→max

В первых двух уравнениях содержатся базисные переменные x₄ и x₅ (это дополнительные переменные), а в третьем базисная переменная отсутствует, поэтому введем искусственную переменную x₇, которая и будет являться базисной. Решаем М-задачу.
Составим симплексную таблицу:

Базис	C_б	В	1	1	4	0	0	0	-M
Базис	C_б	В	A₁	A₂	A₃	A₄	A₅	A₆	A₇
A₄ A₅ ← A₇	0 0 -M	20 24 6	1 2 1	4 1 1	1 3 0	1 0 0	0 1 0	0 0 -1	0 0 1
	Z₀= 0-6М		-1 -1М↑	-1 -1	-4 0	0 0	0 0	0 1	0 0
A₄ ←A₅ A₁	0 0 1	14 12 6	0 0 1	3 -1 1	1 3 0	1 0 0	0 1 0	1 2 1
	Z₁=6		0	0	-4↑	0	0	-1
←A₄ A₃ A₁	0 4 1	10 4 6	0 0 1	10/3 1/3 1	0 1 0	1 0 0	-1/3 1/3 0	1/3 2/3 -1
	Z₂=22		0	-4/3	0	0	4/3	5/3
A₂ A₃ A₁	1 4 1	3 5 3	0 0 1	1 0 0	0 1 0	2/10	1/10	1/10
	Z₃=26		0	0	0	4/10	6/5	9/5

Все оценки положительны, поэтому решение X₃ = (3,3,5,0,0,0) оптимально.
Отбрасывая дополнительные переменные, получим ответ: Z_max=26 при X*=(3,3,5).

Для более подробного ознакомления с алгоритмом M-метода рекомендуем воспользоваться калькулятором.

Пример. В этом методе ограничения изменяются введением искусственных переменных таким образом, чтобы экстремальная точка новой задачи находилась достаточно легко. Каждой искусственной переменной назначается большой положительный штраф М с тем, чтобы в оптимальном решении полученной задачи значение этой переменной было равно нулю.

Решим прямую задачу линейного программирования симплексным М-методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 2x₁+x₂+3x₃ при следующих условиях-ограничений.
x₁+2x₂+x₃≤1000
3x₁+5x₂+2x₃≤1500
x₁≥100
x₂≥100
x₃≥200
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
1x₁ + 2x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ = 1000
3x₁ + 5x₂ + 2x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ = 1500
1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ = 100
0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆-1x₇ + 0x₈ = 100
0x₁ + 0x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ = 200
Введем искусственные переменные x.
1x₁ + 2x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ = 1000
3x₁ + 5x₂ + 2x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ + 0x₁₀ + 0x₁₁ = 1500
1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ + 1x₉ + 0x₁₀ + 0x₁₁ = 100
0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆-1x₇ + 0x₈ + 0x₉ + 1x₁₀ + 0x₁₁ = 100
0x₁ + 0x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ + 0x₉ + 0x₁₀ + 1x₁₁ = 200
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 2x₁+x₂+3x₃ - Mx₉ - Mx₁₀ - Mx₁₁ => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x₉ = 100-x₁+x₆
x₁₀ = 100-x₂+x₇
x₁₁ = 200-x₃+x₈
которые подставим в целевую функцию:
F(X) = 2x₁ + x₂ + 3x₃ - M(100-x₁+x₆) - M(100-x₂+x₇) - M(200-x₃+x₈) => max
или
F(X) = (2+1M)x₁+(1+1M)x₂+(3+1M)x₃+(-1M)x₆+(-1M)x₇+(-1M)x₈+(-400M) => max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

1	2	1	1	0	0	0	0	0	0	0
3	5	2	0	1	0	0	0	0	0	0
1	0	0	0	0	-1	0	0	1	0	0
0	1	0	0	0	0	-1	0	0	1	0
0	0	1	0	0	0	0	-1	0	0	1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x₄, x₅, x₉, x₁₀, x₁₁,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,1000,1500,0,0,0,100,100,200)

План	Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁
0	x₄	1000	1	2	1	1	0	0	0	0	0	0	0
	x₅	1500	3	5	2	0	1	0	0	0	0	0	0
	x₉	100	1	0	0	0	0	-1	0	0	1	0	0
	x₁₀	100	0	1	0	0	0	0	-1	0	0	1	0
	x₁₁	200	0	0	1	0	0	0	0	-1	0	0	1
Индексная строка	F(X0)	-400M	-2-1M	-1-1M	-3-1M	0	0	1M	1M	1M	0	0	0

Иногда такую таблицу представляют с дополнительной строкой для М.

План	Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁
0	x₄	1000	1	2	1	1	0	0	0	0	0	0	0
	x₅	1500	3	5	2	0	1	0	0	0	0	0	0
	x₉	100	1	0	0	0	0	-1	0	0	1	0	0
	x₁₀	100	0	1	0	0	0	0	-1	0	0	1	0
	x₁₁	200	0	0	1	0	0	0	0	-1	0	0	1
Индексная строка	F(X0)	0	-2	-1	-3	0	0	0	0	0	0	0	0
M		-400	-1	-1	-1	0	0	1	1	1	0	0	0

Переходим к основному алгоритму симплекс-метода.

План	Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	min
1	x₄	1000	1	2	1	1	0	0	0	0	0	0	0	1000
	x₅	1500	3	5	2	0	1	0	0	0	0	0	0	750
	x₉	100	1	0	0	0	0	-1	0	0	1	0	0	0
	x₁₀	100	0	1	0	0	0	0	-1	0	0	1	0	0
	x₁₁	200	0	0	1	0	0	0	0	-1	0	0	1	200
Индексная строка	F(X1)	-400M	-2-1M	-1-1M	-3-1M	0	0	1M	1M	1M	0	0	0	0

Посмотреть все итерации
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план.
Окончательный вариант симплекс-таблицы:

План	Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁
5	x₄	350	0	0	0	1	-0.5	-0.5	-0.5	0	0.5	0.5	0
	x₈	150	0	0	0	0	0.5	1.5	2.5	1	-1.5	-2.5	-1
	x₁	100	1	0	0	0	0	-1	0	0	1	0	0
	x₂	100	0	1	0	0	0	0	-1	0	0	1	0
	x₃	350	0	0	1	0	0.5	1.5	2.5	0	-1.5	-2.5	0
Индексная строка	F(X5)	1350	0	0	0	0	1.5	2.5	6.5	0	-2.5+1M	-6.5+1M	1M

Оптимальный план можно записать так: x₁ = 100, x₂ = 100, x₃ = 350
F(X) = 2*100 + 1*100 + 3*350 = 1350

x	f₁(x)	f₂(x)	f₃(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

M-задача

Особенности алгоритма метода искусственного базиса

Правила ввода данных

Поиск

Процесс

Сообщение