Введение в линейное программирование. Палий И.А. - 40 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

jmmjjj
cyayaya
−
+
+
+ L
2211
, n
j
,,1 L
=
.
Следовательно, скалярное произведение векторов
x
и
cyA
T
−
равно
нулю тогда и только тогда, когда выполняются следующие
n условий
j
x (
jmmjjj
cyayaya
−
+++ L
2211
) = 0, n
j
,,1 L
=
(6.10)
Условия (6.10) называются
условиями дополняющей нежесткости.
Другими словами,
если переменная
j
x задачи (6.3) отлична от нуля,
соответствующее ей
j
-е ограничение двойственной задачи обращается в
строгое равенство
Приведенные рассуждения легко обратить (провести их в обратном
порядке). Тогда из условий (6.10) вытекает равенство целевых функций
Z и
W задач (6.3) и (6.4).
Пример 1. Найти оптимальное решение ЗЛП.
max5
4321
→+++= xxxxZ ;
164
431
=
++ xxx ; 446
4321
=
+
−
− xxxx ; 0,,
41
≥xx L , (6.11)
если известно оптимально решение двойственной задачи:
625,1
1
=y ;
2
y = −0,25.
Составим двойственную задачу
min416
21
→+= yyW ;
564
21
≥+ yy ; 14
2
≥
−
y 1
21
≥
−
yy ; 1
21
≥
+
yy . (6.12)
Запишем условия дополняющей нежесткости.
x
1
(564
21
−+ yy ) = 0; x
2
(14
2
−
− y ) = 0;
x
3
(1
21
−− yy ) = 0; x
4
(1
21
−
+
yy ) =0 (6.13)
Если
625,1
1
=y
;
2
y
= −0,25, то выражения в скобках обращаются в 0 в
первом и втором случаях (первое и второе ограничения двойственной
задачи обращаются в равенства при указанных значениях переменных
1
y и
2
y ). Выражения в скобках отличны от 0 для третьего и четвертого условий
(третье и четвертое ограничения двойственной задачи превращаются в
строгие неравенства, так как
=
+
=
−
25,0625,1
21
yy =
1875,1 >
;
=
+
21
yy
=
1375,125,0625,1 >=−
).
Для выполнения условий (6.13) необходимо положить
3
x =
4
x = 0.
Тогда
1
x и
2
x можно найти из (6.11), подставляя в качестве значений
переменных
3
x и
4
x нули. Имеем: 5;4446;164
21211
=
=⇒
=
−
=
xxxxx ;
minmaxminmax
;2525,04625,116;25545 WZWZ =
=
×
−
×
=
=+×= .

Страницы