Метод искусственного базиса

(М-метод).

Если система ограничений представлена неравенствами вида или равенствами, то начальный опорный план не может быть найден так же просто, как в предыдущем методе. В таких случаях начальный опорный план отыскивается с помощью искусственных переменных.

Пример:

Приведем задачу к каноническому виду:

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

Для исключения из базиса этих переменных, их вводят в целевую функцию с большим отрицательным коэффициентами М. Таким образом из исходной получается новая М – задача.

Выбрав в качестве начального базиса векторы А₅,А₇,А₈, решаем полученную М – задачу с помощью табличного симплекс-метода. Для этого рассчитаем оценки (строку ).

Выразим х₇ и х₈ из ограничений:

Подставим эти выражения в целевую функцию и приведем подобные:

Заполним первую симплекс таблицу:

Баз.перемен.	Решение	А1	А2	А3	А4	А5	А6	А7	А8
Х5					-1
Х7
Х8							-1
	-5М	-1-2М	-2-5М	-3-5М	-5-3М		М

Дальнейший расчет как в предыдущем методе. Постепенно из решения задачи уйдут все искусственные переменные.