Симплекс-метод с искусственным базисом или М-метод

М-метод заключается в приложении правил симплекс-метода к
М-задаче, которая строится на исходной добавлением к левой части системы уравнений в канонической форме исходной ЗЛП единичных векторов неотрицательных искусственных переменных. В целевую функцию исходной задачи при решении на максимум добавляется произведение числа (- М) на сумму искусственных переменных, где М – достаточно большое положительное число.

При применении к М-задаче симплекс-метода оценки j будут зависеть от «буквы М». Поскольку М – достаточно большое положительное число, из базиса будут выводиться в первую очередь искусственные переменные. В процессе решения М-задачи в симплекс-таблице следует вычеркивать искусственные векторы по мере их выхода из базиса. Если все искусственные векторы выделены из базиса, то получаем допустимое решение. Если оптимальное решение М-задачи содержит искусственные векторы или М-задача неразрешима, то исходная задача не имеет допустимых решения.

Рассмотрим числовой пример М-метода.

Найти максимум целевой функции: max f( )=3x_l+2х₂+х₃ при условиях:

2х₁+х₂=8,

х₁+х₂+х₃=6,

х₁ 0, х₂ 0, х₃ 0

Решение. Матрица условий исходной задачи содержит только один единичный вектор, добавим один искусственный вектор (искусственную неотрицательную переменную y₁ в первое ограничение).

Построим М-задачу: найти максимум целевой функции max f( ) = 3х₁ + 2х₂ + х₃ - My_l при условиях:

2х₁+х₂+y₁=8,

х₁+х₂+х₃=6,

х₁ 0, х₂ 0, х₃ 0, y₁ 0.

М-задачу решаем симплекс-методом. Начальный опорный план (0,0,6,8). Решение проводим в симплекс-таблицах (табл. 7).

Таблица 7 – Решение задачи ЛП М-методом

Номер симплекс-таблицы		сj					-М
ci	П Б	в0	х1	х2	х3	y1	со
	-М	y1
	х3
-		-8М+6	-2М-2	-М-1			-
		х1 х3			0,5 0,5
-

В начальной таблице наименьшее _jсоответствует переменной х₁ – она вводится в базис, а искусственная переменная y₁ из базиса выводится, так как ей отвечает наименьшее симплексное отношение. Столбец, соответствующий х₁, из дальнейших симплексных таблиц вычеркивается.

Полученное решение является допустимым планом исходной задачи. Для него все _j 0, поэтому он оптимальный. Следовательно, получен оптимальный план исходной задачи (4,0,2), максимальное значение целевой функции f (X*) = 14.