М-задача
Дана задача: найти
наибольшее значение функции
при ограничениях:
.
Составим расширенную задачу,
которую назовем М-задачей.
Найти наибольшее значение
функции
при ограничениях:
.
В каждое уравнение, в котором нет базисной
переменной, вводим переменную 
, где 
, с коэффициентом 1, эти переменные называются
искусственными, и они образуют искусственный базис. Искусственные переменные
вводятся в целевую функцию с коэффициентами –М, если задача решается на
максимум, и +М, если задача решается на минимум, где М сколь угодно большое
положительное число. Система ограничений расширенной задачи совместна.
Исходное опорное решение
где 
, 
.
