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

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

М-метод заключается в применении правил симплекс-метода к так называемой М-задаче.Она получается из исходной задачи добавлением к левой части системы уравнений исходной канонической ЗЛП таких искусственных единичных векторов с соотвествующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичныхлинейно независимых векторов.

2.Теорема для отыскания оптимального плана исходной задачи.

В целевую функцию искусственные переменные вводятся с коэффициентом (- М) для задач на max и с коэффициентом (+ М) для задач на min, где М – достаточно большое положительное число.

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