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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
100
Очевидно, что
ˆ
vV
Î
%
. Тогда из неравенства (7) следует
(
)
(
)
{
}
000
01,,
ii
AubAubiksAub
--×-³Î+Þ=
L .
Таким образом,
0
Î
. Покажем выполнение условий 3)-5).
Возьмем точку
ˆ
s
vR
Î
такую, что
{
}
{
}
0
01,,,
ˆ
1,,
i
i
принекоторм im
v
v
длявсехостальных is
ì
Î
ï
ï
=
í
ï
Î
ï
î
L
L
.
Очевидно, что
ˆ
vV
Î
%
. Тогда из неравенства (7) следует
(
)
{}
00
0,1,,
i
i
vAubim
**
×-³ÎL.
С другой стороны, в силу
(
)
00
0,0,
i
i
vAub
**
³-£
имеем
(
)
{}
00
0,1,,
i
i
vAubim
**
×-£ÎL.
Таким образом,
(
)
00
0
i
i
vAub
**
×-=
{
}
1,,
im
Î
L
,
и условия (3) имеют место.
Возьмем точку
ˆ
s
vR
Î
, такую, что
{
}
{
}
0
01,,,
ˆ
1,,.
i
i
принекоторм imk
v
v
длявсехостальных is
ì
Î+
ï
ï
=
í
ï
Î
ï
î
L
L
Очевидно, что
ˆ
vV
Î
%
. Тогда из неравенства (7) следует, что
(
)
{}
00
0,1,,
i
i
vAubimk
***
×-+³Î+L
.
С другой стороны, в силу
(
)
00
0,0,
i
i
vAub
****
³-³
имеем
(
)
{}
00
0,1,,
i
i
vAubimk
***
×-+£Î+L.
Таким образом,
(
)
{}
00
0,1,,
i
i
vAubimk
***
×-+=Î+L 
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


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

                -( Au0 - b ) ×( Au0 - b ) ³ 0 i Î {k + 1,L, s} Þ Au0 = b .
                              i            i




     Таким образом, u0 Î U . Покажем выполнение условий 3)-5).

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

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

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

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




    С другой стороны, в силу v0i ³ 0, ( A*u0 - b* ) £ 0, имеем
                                                               i




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




    Таким образом,

                             v0i × ( A*u0 - b* ) = 0         i Î {1,L, m} ,
                                                   i




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

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

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

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

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




    С другой стороны, в силу v0i ³ 0, ( A**u0 - b** ) ³ 0, имеем
                                                                   i




                         v0i × (- A**u0 + b* ) £ 0 , i Î {m + 1,L, k } .
                                                   i




    Таким образом,

                         v0i × (- A**u0 + b* ) = 0 , i Î {m + 1,L, k }
                                                   i




                                                       100

Страницы