Н. В. Куцубина системный анализ при принятии решений

105 
Приведение задач линейного программирования
к стандартной форме 
При решении задач линейного программирования симплекс-методом 
требуется, чтобы задача была представлена в стандартной форме, т.е. все 
неравенства должны быть представлены равенствами, а все отрицательные 
переменные преобразованы в неотрицательные. На практике задачи ли-
нейного программирования чаще не имеют стандартной формы. Часто 
ограничения имеют вид неравенств. В некоторых задачах не все перемен-
ные неотрицательные. Первый этап решения задачи линейного програм-
мирования состоит в приведении ее к стандартной форме.
Ограничения в виде неравенств преобразуются в равенства при по-
мощи введения остаточных или избыточных переменных. 
Например, неравенство вида 
x
1 
+ 2
x
2 
+ 5
х
3
≤ 25 можно преобразовать 
в равенство путем введения остаточной переменной 
х
4
:
х
1 
+ 2
x
2 
+ 5
х
3 
+ 
х
4 
= 25. 
Переменная 
х
4
неотрицательна и соответствует разности правой и 
левой частей.
Неравенство вида 2
х
1
+х
2
− 3
х
3 
≤ 12 преобразуется в равенство путем 
введения избыточной переменной 
х
5
:
2
х
1 
+ 
х
2
− 3
х
3
− 
х
5 
= 12. 
В тех случаях, когда переменные принимают как положительные, 
так и отрицательные значения, т.е. не ограниченные по знаку, неограни-
ченные переменные заменяются разностью двух неотрицательных пере-
менных. 
Рассмотрим пример приведения задачи к стандартной форме.
Максимизировать 
Z = x
1
− 2
x
2 
+ 3
x
3
при ограничениях: 
х
1 
+ 
х
2 
+ 
х
3 
≤ 7;
х
1
− 
х
2 
+ 
х
3 
≥ 2;
3
х
1 
− 
х
2 
+ 
х
3 
= -5;
х
1
≥ 0,
х
2 
≥ 0; 
х
3
– переменная, не ограниченная по знаку.
Последовательность приведения:
1) заменим
х
3
на
х
4 
− 
х
5
, где 
х
4 
≥ 0, 
х
5 
≥ 0;
2) умножим обе части ограничений на (-1);
3) введем дополнительные переменные 
х
6
и 
х
7
во втором и третьем 
ограничениях соответственно;
4) припишем в целевой функции нулевой коэффициент переменным 
х
6
и
х
7
, целевая функция при этом не меняется.
Электронный
архив
УГЛТУ

106 
Таким образом, стандартная задача будет выглядеть следующим
образом:
максимизировать 
Z = х
1
− 2

жүктеу/скачать 6,77 Mb.

Достарыңызбен бөлісу: