Случай 3

Случай 2.

Пусть система ограничений ЗЛП представлена в виде:

(),

()

().

Приведем систему к каноническому виду. Для этого прибавим к левым частям неравенств новые неотрицательные переменные.

(),

()

().

Переменные () являются предпочтительными. Случай 2 свелся к случаю 1.

Пусть система ограничений ЗЛП представлена в виде:

(),

()

().

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

при

(),

()

()

().

Переменные () являются предпочтительными. Случай 3 свелся к случаю 1.

Теорема 1: Если в оптимальном плане М-задачи все искусственные переменные будут равны 0, то план является оптимальным для исходной задачи.

Теорема 2: Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных не равна 0, то исходная задача не имеет допустимых планов, т.е. ее условия несовместны.

Дата добавления: 2014-11-18