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

В частном случае, если , то система (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