Задачи линейного программирования

Задачей линейного программирования (ЗЛП)называется задача исследования операций, математическая модель которой имеет вид:

(2)

(3)

(4)

(5)

При этом система линейных уравнений (3) и неравенств (4), (5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция называется целевой функцией, или критерием оптимальности.

Если математическая модель задачи линейного программирования имеет вид:

то говорят, что задача представлена в канонической форме.

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности.

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

4) если некоторая переменная не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: где i — свободный индекс,

Пример. Приведение к канонической форме задачу линейного программирования:

Введем в каждое уравнение системы ограничений выравнивающие переменные Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные вводятся со знаком «+», а во второе уравнение вводится со знаком «-». Итак:

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1, получим

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