7.1. Задачи линейного программирования
п
f(X) = 2 С ;Xj max(min); (7.2) y=i
І ayxj^bi, і el, 7cM = {l,2,...m}; (7.3) y=1
n
S aijxj -ty, ІЄМ; (7.4) y=i
Xj > 0, у є /,/сЛГ={1, 2, ..., л}. (7.5)
При этом система линейных уравнений (7.3) и неравенств (7.4), (7.5), определяющая допустимое множество решений задачи W, на-зывается системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией, или критерием оптимальности.
В частном случае, если / = 0, то система (7.3) — (7.4) состоит только из линейных неравенств, а если / = Л/, то — из линейных уравнений.
Если математическая модель задачи линейного программирования имеет вид:
f(X)=%Cj-Xj^> min; (7.6)
y=i
п
ZauxJ=bi,i = l,m; (7.7)
у=1
6/ > 0;
Xj>0,j = T^i, (7.8)
то говорят, что задача представлена в канонической форме.
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме.
Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот.Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
если в ограничениях правая часть отрицательна, то следует умножить это ограничение на —1;
если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
если некоторая переменная хк не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: хк = х?к — хь где ? — свободный индекс, х/к > 0, х? > 0.
Пример 7.1. Приведение к канонической форме задачи ли-нейного программирования:
min L = 2х{ + х2 — х3;
2х2 - х3 < 5; х\ + *2-х3>-1; 2хх — х2 < -3; хх < 0, х2 > 0, х3 > 0.
Решение
Введем в каждое уравнение системы ограничений выравнивающие переменные х4, х5, х6.
Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные х4, *б вводятся в левую часть со знаком «+», а во второе уравнение вводится х5 со знаком «—».Итак:
2х2 — Х3 + х4 = 5;
Х\ "Ь х2 — х3 — х$ — — 1;
2Xj - х2 + х6 = - 3;
х4 >0, х5 > 0, х6 > 0.
Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на — 1:
2х2 — х3 Х4 = 5;
—Xj — Х2 Х3 Х5 = 1 \
—2xj + х2 — х^ = 3;
В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть неотрицательными. Допустим, что
Xj = Х?1 - х7, где Xу! > 0, х7 > 0.
Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:
2х2
-X7! -Х2
— х3 + х4 =5 + х3 + х5 + х7 = 1
—2х/1 + х2 — х6 + 2х7 =3; Lmm = 2х/1 + х2 - х3 - 2х7; x'j > 0; xf > 0, / = 2J.