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

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

; (2.29)

; (2.30)

; (2.31)

. (2.32)

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

В частном случае, если , то система (2.30)-(2.31) состоит только из линейных неравенств, а если I=M, то из линейных уравнений.

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

; (2.33)

; (2.34)

, (2.35)

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

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

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

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

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

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

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

, где l – свободный индекс, .

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

Решение.Введем в каждое уравнение системы ограничений выравнивающие переменные х₄, х₅, x₆. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные х₄, x₆вводятся в левую часть со знаком "+", а во второе уравнение вводится х₅со знаком "–".

Итак:

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

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

где .

Подставляя данное выражение в систему ограничений и в целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:

2.11.2. Примеры построения экономико-математических
моделей задач линейного программирования

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

Пример 8. Определение оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции – П₁ и П₂, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья – А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П₁ и вида П₂ дан в табл. 2.3.

Таблица 2.3