Задачи линейного программирования
Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
; (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. Приведение к канонической форме задачи линейного программирования:
Решение.Введем в каждое уравнение системы ограничений выравнивающие переменные х4, х5, x6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные х4, x6вводятся в левую часть со знаком "+", а во второе уравнение вводится х5со знаком "–".
Итак:
Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на –1:
В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть неотрицательными. Допустим, что
где 
.
Подставляя данное выражение в систему ограничений и в целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:
2.11.2. Примеры построения экономико-математических
моделей задач линейного программирования
Рассмотрим процесс построения математических моделей задач линейного программирования на примерах.
Пример 8. Определение оптимального ассортимента продукции.
Предприятие изготавливает два вида продукции – П1 и П2, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья – А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1 и вида П2 дан в табл. 2.3.
Таблица 2.3
Дата добавления: 2015-12-16; просмотров: 919;