Решение задачи линейного программирования методом искусственного базиса

Пусть имеется исходная задача (1)-(3). Тогда построим расширенную задачу:

– сколь угодно большое число (множитель).

– штраф за нарушение ограничений.

Теорема 10: пусть – оптимальное решение расширенной задачи, тогда:

· если искусственные переменные , , то решение является оптимальным и для исходной задачи.

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

· если расширенная задача неразрешима из-за неограниченности критерия, то и исходная задача неразрешима из-за неограниченности критерия.

Замечание: если исходная задача является задачей минимизации, критерий расширенной задачи должен иметь вид .