Лекция: Задачи линейного программирования.

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

(3.2)

,,; (3.3)

,; (3.4)

,,. (3.5)

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

В частном случае, если Ø, то система (3.3) – (3.4) состоит только из линейных неравенств, а если, то – из линейных уравнений.

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

; (3.6)

,;; (3.7)

,, (3.8)

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

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

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

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

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

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

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