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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

96
Теорема 2
Если линейная функция цели любой из пары задач не ограничена
(ЗЛП не имеет оптимального решения), то другая задача не имеет решения.
Теорема 3 (о дополнительной нежёсткости)
Если
njx
j
,1, = – решение исходной задачи ЛП, а miz
i
,1, = –
решение двойственной задачи, то оба решения являются оптимальными
тогда и только тогда, когда выполняются соотношения
,,1,0)(
1
00
mibxaz
n
j
ijiji
==−
∑
=
(2.58)
.,1,0)(
1
00
njCzax
m
i
iiijj
==−
∑
=
(2.59)
Если при подстановке компонент оптимального решения x
j
в систему
ограничений исходной задачи i-е ограничение обращается в неравенство,
то 0
0
=
i
z , а если 0
0
>
i
z , то i-е ограничение исходной задачи
удовлетворяется оптимальным решением
0
j
x как строгое равенство.
2.12. Поиск оптимального решения двойственной задачи
Решение двойственной задачи (оптимальное, если оно существует)
содержится в последней симплекс-таблице, полученной при решении
исходной задачи ЛП.
Пример 14
Найти min
321
23 xxxW
+
+−= при ограничениях
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥
≤+−
≤+−
−≥++
.0
,5652
,332
,52
3,2,1
321
321
321
х
ххх
ххх
ххх
Перепишем условия исходной задачи в виде
321
23 xxxW
+
+
−
=
→ min
при
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥
−−≤−+−
−−≤−+−
−−≥++
.0
,5652
,332
,52
3,2,1
3321
2321
1321
х
zххх
zххх
zххх
Тогда двойственная задача будет иметь вид
max535
321
→
−
−
−= zzzF
;
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥
≥≤−−
≥≤++
≥−≤−−
.0
,0262
,0353
,0122
3,2,1
3321
2321
1321
z
vzzz
vzzz
vzzz

Страницы