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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
101
и условия (4) имеют место.
Условия 5) выполняются с очевидностью. Необходимость доказана.
Достаточность. Пусть для некоторой точки
(
)
00
,
uvUV
δ
%%
выполнены
условия (2)-(6). Правое неравенство в (1) следует сразу из (2). Докажем
выполнение левого неравенства в (1). Для всех ,
uUvV
ÎÎ
%
в силу (3)-(5)
справедливы равенства
()()
(
)
(
)
(
)
{}
0
,0,
0,0,
ii
i
i
ii
i
vAubAub
vvAubim
Aub
****
*
**
ì
ï
---<
ï
ï
ï
--=Î
í
ï
ï
-=
ï
ï
î
L (8)
()()
(
)
(
)
(
)
{}
0
,0,
1,,,
0,0,
ii
i
i
ii
i
vAubAub
vvAubimk
Aub
********
****
****
ì
ï
--+->
ï
ï
ï
---=Î+
í
ï
ï
-=
ï
ï
î
L
(9)
(
)
(
)
{
}
0
0,1,,
i
ii
vvAubiks
--=Î+L . (10)
Правые части всех равенств (8)-(10) неотрицательны. Тогда суммируя
эти равенства при
0
uu
=
, получим
()()()()()()
000000
111
mks
iii
iiiiii
iimik
vvAubvvAubvvAub
******
==+=+
--+--+--=
ååå
(
)
(
)
(
)
(
)
(
)
(
)
000000
,,,0
vvAubvvAubvvAub
***********
=--+--++--³Þ
0000000
,,,,cuvAubvAubvAub
*********
+-+-++-³
(
)
00000
,,,,,cuvAubvAubvAubLuv
*********
³+-+-++-=Þ
(
)
(
)
000
,,
LuvLuvvV
£"Î
%
.
Теорема доказана.
Теорема 4. Пусть
(
)
00
,
uvUV
δ
%%
- седловая точка функции Лагранжа
для задачи 1. Тогда
0
u
- является решением задачи 1 линейного
программирования и при этом справедливо равенство
(
)
(
)
000
,
LuvIu
=
. (11) 
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


и условия (4) имеют место.

      Условия 5) выполняются с очевидностью. Необходимость доказана.

      Достаточность. Пусть для некоторой точки (u0 , v0 ) Î U% ´V% выполнены

условия (2)-(6). Правое неравенство в (1) следует сразу из (2). Докажем
выполнение левого неравенства в (1). Для всех u Î U , v Î V% в силу (3)-(5)
справедливы равенства

                               ìï-v i A*u - b* i ,
                                     (        )                               ( A*u - b* ) < 0,
                                                                                            i
                                ï
        (v - v )( A u - b) = ïíï                                                                           i Î {1,L, m} ,
                             *         i
              i        i
                                                                                                                                        (8)
                                                                              ( A*u - b* ) = 0,
              0
                                ïï
                                                                                          i
                                        0,
                                 î

                                             ìï-v i - A**u + b** i ,
                                              ï (               )                ( A**u - b** ) > 0,
                                                                                                    i


    (v0i - v i )(- A**u - b** )            = ïí                                                                  i Î {m + 1,L, k } ,
                                       i
                                                                                                                                        (9)
                                                ï
                                              ïîï                                ( A**u - b** ) = 0,
                                                                                                       i
                                                        0,


                                 (v0i - v i )( Au - b ) = 0, i Î {k + 1,L, s} .
                                                           i
                                                                                                                                       (10)

      Правые части всех равенств (8)-(10) неотрицательны. Тогда суммируя
эти равенства при u = u0 , получим


       å (v           - v i )( A*u0 - b* ) +      å (v             - vi )( A**u0 - b** ) +      å (v           - vi )( Au0 - b ) =
        m                                          k                                               s
                  i                          i                 i                        i                  i                  i
                  0                                            0                                           0
       i =1                                      i = m+1                                        i = k +1



     = (v0* - v* ) , ( A*u0 - b* ) + (v0** - v* ) , (- A**u0 + b** ) + (v0 - v ) , ( Au0 - b ) ³ 0 Þ


                           c, u0 + v0* , A* u0 - b* + v0** , - A**u0 + b** + v0 , Au0 - b ³


              ³ c, u0 + v* , A*u0 - b* + v** , - A**u0 + b** + v , Au0 - b = L (u0 , v) Þ

                                                 L (u0 , v ) £ L (u0 , v0 ) "v Î V% .

      Теорема доказана.

      Теорема 4. Пусть (u0 , v0 ) Î U% ´V% - седловая точка функции Лагранжа

для задачи 1. Тогда                              u0 -          является решением задачи 1 линейного
программирования и при этом справедливо равенство

                                                       L (u0 , v0 ) = I (u0 ) .                                                        (11)

                                                                        101

Страницы