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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
106
Решение задачи 3* достигается в тех же точках
0
vV
Î
, что и
решение задачи 3. При этом
(
)
(
)
00
ДД
IvIv
*
=-
. Выпишем функцию Лагранжа
для задачи 3*. Имеем
()
()
1
,,,,
l
i
iTTT
Д i
i
*************
=
éù
=-++--+-+
êú
ëû
å
()
1
n
i
iTTT
i
il
uAvAvAvc
******
=+
éù
+-+--
êú
ëû
å
,,,,,
TTT
bvbvbvuAvAvAvcu
************
=-+--+-=
,,,,,,,
TTT
bvbvbvuAvuAvuAvcu
************
=-+-+--=
,,,,,,,
bvbvbvAuvAuvAuvcu
************
=-+-+--=
(
)
,,,,,
AubvAubvAubvcuLuv
*********
=----+---=-
,
,
uUvV
ÎÎ
%%
.
Пусть
0
uU
Î
- решение задачи 1. Тогда по теореме 5 существует
седловая точка
(
)
00
,
uvUV
δ
%%
функции Лагранжа для этой задачи. Это
означает, что для всех
(
)
,
uvUV
δ
%%
справедливо двойное неравенство
(
)
(
)
(
)
(
)
(
)
(
)
00000000
,,,,,,
ДДД
LuvLuvLuvLvuLvuLvu
***
££Þ-£-£-Þ
(
)
(
)
(
)
(
)
(
)
(
)
00000000
,,,,,,
ДДДДДД
LvuLvuLvuLvuLvuLvu
******
³³Þ££
. (1)
Таким образом, пара
(
)
00
,
vuVU
δ
%%
является седловой точкой функции
Лагранжа для задачи 3*. Тогда по теореме 4 точка
0
v
является решением
задачи 3* и, следовательно, задачи 3. При этом
(
)
(
)
(
)
(
)
(
)
000000
,,
ДДД
IvIvLvuLuvIu
**
=-=-==
(2)
Обратно, если
0
vV
Î
является решением задачи 3*, то справедливо
последнее двойное неравенство в (1). Рассматривая цепочку неравенств (1) в 
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


      Решение задачи 3* достигается в тех же точках v0 Î V , что и
решение задачи 3. При этом I *Д ( v0 ) = -I Д (v0 ) . Выпишем функцию Лагранжа
для задачи 3*. Имеем

       L*Д (v, u ) = b* , v * - b** , v ** + b , v + å u i éê-( A*T v * - A**T v ** + AT v ) - ci ùú +
                                                                l
                                                                                            i

                                                     i =1   ë                                      û


                                 + å u i éê(- A*T v * + A**T v ** - AT v ) - ci ùú
                                      n
                                                                          i

                                  i =l +1 ë                                      û

               = b* , v * - b** , v ** + b , v - u, A*T v * - A**T v ** + AT v - c, u =

         = b* , v * - b** , v** + b , v - u , A*T v* + u, A**T v ** - u, AT v - c, u =


           = b* , v * - b** , v ** + b , v - A*u, v* + A**u , v ** - Au, v - c, u =

            = - A*u - b* , v * - - A**u + b** , v ** - Au - b , v - c, u = -L (u, v ) ,

                                                   u Î U% , v Î V% .

      Пусть u0 Î U - решение задачи 1. Тогда по теореме 5 существует

седловая точка (u0 , v0 ) Î U% ´V% функции Лагранжа для этой задачи. Это

означает, что для всех (u, v ) Î U% ´V% справедливо двойное неравенство

         L (u0 , v ) £ L (u0 , v0 ) £ L (u, v0 ) Þ - L*Д (v, u0 ) £ -L*Д (v0 , u0 ) £-L*Д (v0 , u ) Þ

        L*Д (v, u0 ) ³ L*Д (v0 , u0 ) ³ L*Д (v0 , u ) Þ L*Д ( v0 , u ) £ L*Д (v0 , u0 ) £ L*Д (v, u0 ) .   (1)

      Таким образом, пара ( v0 , u0 ) Î V% ´U% является седловой точкой функции

Лагранжа для задачи 3*. Тогда по теореме 4 точка v0 является решением
задачи 3* и, следовательно, задачи 3. При этом

                             I Д ( v0 ) = -I *Д ( v0 ) = -L*Д (v0 , u0 ) = L (u0 , v ) = I (u0 )           (2)

    Обратно, если v0 Î V является решением задачи 3*, то справедливо
последнее двойное неравенство в (1). Рассматривая цепочку неравенств (1) в




                                                          106

Страницы