Основы теории систем и системного анализа. Матвеев Ю.Н. - 74 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

74
где y
1
, y
2
, …, y
m
– новые переменные, которые называются
дополнительными.
Из системы (2.29) следует, что дополнительные y
i,
mi ,1= , так же как
и основные x
j
, nj ,1= , должны быть неотрицательными.
Появилась новая постановка задачи ЛП: определить такие
неотрицательные значения n+m переменных x
j
, nj ,1= и y
i,
mi ,1= ,
которые удовлетворяли бы системе уравнений (2.29) и обращали бы в
минимум линейную функцию
.0...00....
212211 mnn
yyyxcxcxcW ⋅
+
+
⋅
+
⋅
+
+
++=
Это ОЗЛП. Уравнения в системе заданы в виде, когда базисные
переменные y
i
mi ,1= уже выражены через свободные x
j
, nj ,1= . Общее
количество переменных увеличилось на m, но задача сведена к ОЗЛП.
Пример 4
Определить минимум
321
32 xxxW
−
−
=
при ограничениях
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
=≥
≤−
−≥+−
−≤−
≤+−
.,1,0
,0
,12
,13
,632
15
145
23
321
njx
xx
xxx
xx
xxx
j
(2.30)
Привести эту задачу к ОЗЛП.
Решение
Приведем неравенства (2.30) к стандартной форме:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥+−
≥++−
≥−+−
≥
+
−
+
−
.0
,012
,013
,0632
15
145
23
321
xx
xxx
xx
xxx
Введем дополнительные переменные:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
−=
++−=
−−=
+
−
+
−
=
.
,12
,13
,632
514
5413
322
3211
xxy
xxxy
xxy
xxxy
(2.31)
Задача ЛП сводится к поиску x
j
≥ 0, 5,1=j , y
i
≥ 0, 4,1=i , которые бы
удовлетворяли (2.31) и приводили бы к минимуму
321
32 xxxW −
−
=
.
Переход от уравнений-ограничений к неравенствам может быть
произведен следующим образом:

Страницы