Определение задачи линейного программирования. (ЗЛП)

ЗЛП состоит в максимизации (минимизации) линейной функции при линейных ограничениях.

Пример 1.1:

найти (1.3)

при ограничениях:

(1.4)

ЗЛП, записанная в виде (1.3) и (1.2), называется общей задачей ЛП, заданной в произвольной форме записи.

Любую ЗЛП можно записать в виде:

найти при условиях , но при этом вводится дополнительное условие:

(1.5)

(1.3) и (1.5) - стандартная форма записи ЗЛП

Любую ЗЛП можно представить в виде:

найти (1.6)

при

(1.7)

(1.6) и (1.7) - представляют собой каноническую форму записи ЗЛП.

ЗЛП в произвольной постановке всегда может быть приведена к стандартной и канонической формам с помощью следующих преобразований (Û - знак преобразования):

1. ; (1.8)
2. ; (1.9)
3. если , то ; (1.10)
4. ; (1.11)

^~ - означает, что эту переменную дополнительно вводят.

1. (1.12)

Преобразования 3-5 приводят к увеличению размера задачи.

Пример 1.2:

В стандартной форме:

В канонической форме: