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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Пример 2. Дан вектор )3;1;0;3(
=
x
. Определить, является ли он
оптимальным решением следующей задачи
max2
4321
→
+
+−−= xxxxZ
;
22
4321
=
−
+− xxxx
;
632
4321
=
+
−
+
xxxx
;
223
4321
−=
−
−− xxxx
;
0,,
41
≥xx L
, (6.14)
Заметим, что вектор
−
x
допустимое решение задачи (6.14). Построим
двойственную задачу.
min262
321
→
−
+= yyyW
;
22
321
−≥++ yyy ; 13
321
−
≥
−
+
− yyy ; 1232
321
≥
−
−
yyy ;
1
321
≥−+− yyy . (6.15)
Запишем условия дополняющей нежесткости и по ним найдем
значения
321
,, yyy . Если окажется, что найденные значения переменных
удовлетворяют всем ограничениям задачи (6.15), то данный вектор
x
и
найденный вектор
y = (
321
,, yyy ) являются не только допустимыми, но
и оптимальными решениями своих задач. Если же вектор
y
не будет
допустимым решением своей задачи, то вектор
x
не оптимален.
3( )2(2
321
−−++ yyy ) = 0; 0( )1(3
321
−
−
−
+
−
yyy ) = 0;
1( 1232
321
−−− yyy ) = 0; 3( 1
321
−
−
+
−
yyy ) = 0. (6.16)
Чтобы удовлетворить условиям (6.16), нужно превратить в равенства
первое, третье, четвертое ограничения задачи (6.15). Получится такая
система линейных уравнений
22
321
−
=
++ yyy ; 1232
321
=
−
− yyy ; 1
321
=
−
+
−
yyy .
Решение системы таково: 3/1;3/2
231
−
=
−
=
=
yyy .
Если подставить эти числа во второе, пропущенное нами ограничение
задачи (6.16), получится верное неравенство, так как
13
/
723
/
13
/
2 −>=+− . Итак, данный вектор
x
− оптимальное решение
задачи (6.14); вектор
y − оптимальное решение задачи (6.1);
minmax
WZ = =
−2.
Пример 3. Сформулируем условия дополняющей нежесткости для
симметричной пары двойственных задач.
max),( →=
x
c
Z
; min),(
0
→= yAW ;
0
AxA ≤ (6.17)
cyA
T
≥
(6.18)
0≥
x
0≥y

Страницы