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



Pdf көрінісі
бет56/70
Дата22.11.2022
өлшемі6,77 Mb.
#159284
түріАнализ
1   ...   52   53   54   55   56   57   58   59   ...   70


1 (вектор переменных);
b
– вектор-столбец размерности 


1 (вектор ресурсов);
c
– вектор-строка размерности 


n
(вектор оценок задачи линейного 
программирования).
Рассмотрим применение симплекс-метода на примерах. 
Электронный
архив
УГЛТУ


105 
Приведение задач линейного программирования
к стандартной форме 
При решении задач линейного программирования симплекс-методом 
требуется, чтобы задача была представлена в стандартной форме, т.е. все 
неравенства должны быть представлены равенствами, а все отрицательные 
переменные преобразованы в неотрицательные. На практике задачи ли-
нейного программирования чаще не имеют стандартной формы. Часто 
ограничения имеют вид неравенств. В некоторых задачах не все перемен-
ные неотрицательные. Первый этап решения задачи линейного програм-
мирования состоит в приведении ее к стандартной форме.
Ограничения в виде неравенств преобразуются в равенства при по-
мощи введения остаточных или избыточных переменных. 
Например, неравенство вида 
x

+ 2
x

+ 5
х
3
≤ 25 можно преобразовать 
в равенство путем введения остаточной переменной 
х
4
:
х

+ 2
x

+ 5
х


х

= 25. 
Переменная 
х
4
неотрицательна и соответствует разности правой и 
левой частей.
Неравенство вида 2
х
1

2
− 3
х

≤ 12 преобразуется в равенство путем 
введения избыточной переменной 
х
5
:
2
х


х
2
− 3
х
3
− 
х

= 12. 
В тех случаях, когда переменные принимают как положительные, 
так и отрицательные значения, т.е. не ограниченные по знаку, неограни-
ченные переменные заменяются разностью двух неотрицательных пере-
менных. 
Рассмотрим пример приведения задачи к стандартной форме.
Максимизировать 
Z = x
1
− 2
x

+ 3
x
3
при ограничениях: 
х


х


х

≤ 7;
х
1
− 
х


х

≥ 2;
3
х

− 
х


х

= -5;
х
1
≥ 0,
х

≥ 0; 
х
3
– переменная, не ограниченная по знаку.
Последовательность приведения:
1) заменим
х
3
на
х

− 
х
5
, где 
х

≥ 0, 
х

≥ 0;
2) умножим обе части ограничений на (-1);
3) введем дополнительные переменные 
х
6
и 
х
7
во втором и третьем 
ограничениях соответственно;
4) припишем в целевой функции нулевой коэффициент переменным 
х
6
и
х
7
, целевая функция при этом не меняется.
Электронный
архив
УГЛТУ


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


Достарыңызбен бөлісу:
1   ...   52   53   54   55   56   57   58   59   ...   70




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет