Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 99 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
99
(
)
00
0,1,,,
i
i
vAubimk
****
-+==+L (4)
(
)
00
0,1,,
i
i
vAubiks
-==+
L
. (5)
0
uU
. (6)
Доказательство. Необходимость. Пусть
(
)
00
,
uvUV
δ
%%
- седловая
точка. В силу (1) условие (2) выполнено автоматически. Перепишем левое
неравенство (1) с учетом определения функции Лагранжа
(
)
0000
,,,IuvAubvAubvAub
*********
+-+-++-£
(
)
0000000
,,,IuvAubvAubvAub
*********
£+-+-++-Þ
000000
0,,,
vvAubvvAubvvAubvV
************
£--+--++--"Î
%
. (7)
Покажем, что точка
0
uU
Î
%
принадлежит множеству
U
(условие(6)),
т.е. что точка
0
u
является допустимой. Возьмем точку
ˆ
s
vR
Î
, такую, что
{
}
{}
0
0
11,,,
ˆ
1,,
i
i
i
v принекоторм im
v
v
длявсехостальных is
ì
ï
+Î
ï
=
í
ï
Î
ï
î
L
L
.
Очевидно, что
ˆ
vV
Î
%
. Тогда из неравенства (7) следует
()
(
)
{}
00
10,1,,
i
AubimAub
****
--³ÎÞ£
L .
Возьмем точку
ˆ
s
vR
Î
такую, что
{
}
{}
0
0
11,,,
ˆ
1,,.
i
i
i
v
принекоторм imk
v
v
длявсехостальных is
ì
ï
+Î+
ï
=
í
ï
Î
ï
î
L
L
Очевидно, что
ˆ
vV
Î
%
. Тогда из неравенства (7) следует
(
)
(
)
{
}
00
101,,
i
AubimkAub
********
--+³Î+Þ³L .
Возьмем точку
ˆ
s
vR
Î
такую, что
(
)
{}
{}
00
0
1,,,
ˆ
1,,.
i
i
i
i
vAub
принекоторм iks
v
v
длявсехостальных is
ì
ï
+-Î+
ï
ï
=
í
ï
Î
ï
ï
î
L
L
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


                            v0i (- A**u0 + b** ) = 0, i = m + 1,L, k ,
                                                   i
                                                                                               (4)

                        v0i ( Au0 - b ) = 0, i = k + 1,L, s .
                                      i
                                                                                               (5)

                                              u0 Î U .                                         (6)

     Доказательство. Необходимость. Пусть (u0 , v0 ) Î U% ´V%                        - седловая
точка. В силу (1) условие (2) выполнено автоматически. Перепишем левое
неравенство (1) с учетом определения функции Лагранжа

                I (u0 ) + v* , A*u0 - b * + v** , - A**u0 + b** + v , Au0 - b £


             £ I (u0 ) + v0* , A*u0 - b* + v0** ,- A**u0 + b** + v0 , Au0 - b Þ

       0 £ v0* - v* , A*u0 - b* + v0** - v** , - A**u0 + b** + v0 - v , Au0 - b    "v Î V% .   (7)

     Покажем, что точка u0 Î U% принадлежит множеству U (условие(6)),
т.е. что точка u0 является допустимой. Возьмем точку vˆ Î R s , такую, что

                              ìïvi + 1   при некоторм i Î {1,L, m},
                       vˆi = ïí 0 i                                       .
                               ïï v0
                                î      для всех остальных i Î {1, L , s }

    Очевидно, что v̂ Î V% . Тогда из неравенства (7) следует

                      (-1)( A*u0 - b* ) ³ 0, i Î {1,L, m} Þ A*u0 £ b* .
                                          i




     Возьмем точку vˆ Î R s такую, что

                             ìïv i + 1 при некоторм i Î {m + 1,L, k } ,
                      vˆi = ïí 0 i
                              ïï v0
                               î       для всех остальных i Î {1,L, s}.

    Очевидно, что v̂ Î V% . Тогда из неравенства (7) следует

                 (-1)(- A**u0 + b** ) ³ 0 i Î {m +1,L, k } Þ A**u0 ³ b** .
                                      i




     Возьмем точку vˆ Î R s такую, что

                      ìïv i + Au - b i
                       ï
                 vˆ = í 0
                  i          ( 0 )               при некоторм i Î {k + 1,L, s} ,
                       ïï     v0i               для всех остальных i Î {1,L, s}.
                        ïî


                                                       99

Страницы