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

К левым частям ограничения (4) добавляют неотрицательные искусственные переменные w_i.

В ЦФ искусственные переменные вводятся с коэффициентом +М в случае нахождения min и с коэффициентом -М в случае нахождения max.

Полученная задача всегда имеет предпочтительный вид. Такая задача называется М-задачей.

Предположим, в системе ограничений (2) все ограничения имеют непредпочтительный вид. Составим М-задачу при указанном положении:

M – большое положительное число.

ЗАМ: если имеются предпочтительные ограничения, то добавлять в него w_i не надо.

Теорема: если в оптимальном решении X ^* = (x ₁, …, x_n, w ₁, …, w_m) М-задачи все искусственные переменные w_i = 0, то решение X = (x ₁, …, x_n) является оптимальным решением для исходной задачи (2).