3 Общая задача линейного
программирования и методы их решения
Формулировка
задачи. Даны линейная
функция
Z = C1x1 + C2x2
+…+ C nxn
(2.1.1)
и система линейных ограничений
a11x1
+ a12x2 +…+ a1jxj +…+ a1n xn = b1,
a21x1
+ a22x 2 +…+ a2jxj +…+ a2n xn
= b2,
… ………………………………… (2.1.2)
ai1x1 +
ai2x2 +…+ a ij xj +…+ a in xn = bi,
…………………………………………
a m1x1+
a m2x2 +…+ amjxj
+…+ amnxn =bm,
xj ≥
0 (j =1, 2,…, n),
(2.1.3)
где aij, bi и Cj – заданные постоянные величины.
Найти такие неотрицательные
значения х1, х2,…, xn которые
удовлетворяют системе ограничений (2.1.2) и доставляют линейной функции (2.1.1)
минимальное значение.
Как отмечалось ранее, в системе ограничений
(2.1.2) все bi, (i=1,2,…,m) можно
считать неотрицательными. Общая задача имеет несколько форм записи.
Векторная форма записи. Минимизировать линейную функцию
Z= CX при ограничениях A1x1
+ A2x2 +…+ A nxn = A0, X ≥
0 (2.1.4)
где С = (с1, с2,…
, сn); X = ( x1, x2,…, xn); СХ- скалярное
произведение; векторы




a 11 a 12 a1n b1
A1= a21 , A2= a 22 , … , An= a2n ,
A0= b2 ,
….. ….. ….. ……
a m1 am2 amn bm
состоят соответственно из коэффициентов при неизвестных и свободных членов.
Матричная форма записи. Минимизировать
линейную функцию
Z = CX при ограничениях
AX = A0, X ≥
0, где С = (с1, с2,…. , cn )-
матрица-строка; А = ( a ij ) -
матрица системы;


x1
b1
Х= x2 -
матрица-столбец, A0= b2 -
матрица-столбец.
… …
xn bm
Запись с помощью знаков суммирования. Минимизировать линейную функцию Z =
, при
ограничениях
aij
x j = b i, i = 1, 2, …, m; x
j ≥ 0 , j = 1, 2, …, n.
Определение 1. Планом или допустимым
решением задачи линейного программирования называется вектор Х = ( x1, x2,… ,xn);
удовлетворяющий условиям (2.1.2) и (2.1.3) .
Определение 2. План Х = ( x1, x2,… , xn) называется опорным, если векторы Аi (i = 1, 2,…, m), входящие в разложение (2.1.4) с положительными коэффициентами
xi,
являются линейно независимыми.
Так как векторы Аi являются m-
мерными, то из определения опорного плана следует, что число его положительных
компонент не может превышать m.
Определение 3. Опорный план называется
невырожденным, если он содержит m
положительных компонент, в противном случае опорный план называется
вырожденным.
Определение 4. Оптимальным планом или
оптимальным решением задачи линейного программирования называется план,
доставляющий наименьшее (наибольшее) значение линейной функции.
В
дальнейшем рассмотрено решение задач линейного программирования, связанных с
нахождением минимального значения линейной функции. В тех задачах, где
необходимо найти максимальное значение линейной функции, достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней функции. Заменяя на противоположный знак полученного минимального
значения, определяем максимальное значение исходной линейной функции. Свойства
решений задачи линейного программирования тесно связаны со свойствами выпуклых
множеств.