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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
103
(
)
()
(
)
(
)
(
)
000
,0
iiii
ii
iIAubAuteAutAebt
**************
ÎÞ=Þ+=+³"³
,
0
0,0
jjj
jJutetet
ÎÞ+=³"³
%
,
{
}
(
)
(
)
(
)
(
)
(
)
000
iiii
ii
imIAubAuteAutAebt
e
*******
ÎÞ<Þ+=+£ÎL ,
{
}
(
)
(
)
(
)
(
)
(
)
000
1,,\,[0,]
iiii
ii
imkIAubAuteAutAebt
e
**************
Î+Þ>Þ+=+³ÎL ,
{
}
0
1,,\0,[0,]
jj
jlJutet
e
ÎÞ+³Î
%
L
,
где
0
e
>
достаточно мало. Таким образом,
0
uteU
+Î
.
В силу того, что точка
0
uU
Î
является решением задачи 1, для нее
справедливо неравенство
0
,0,
cuuuU
-³"Î
.
В частности, для точек
0
uteU
+Î
, где
0
t
³
достаточно мало, имеем
00
,,0cuteutce
+-=³Þ
,0,
ceeK
-£"Î
.
Множество
K
перепишем в эквивалентной форме
1
0,0;0;0
n
J
II
n
e
KeRAeAeAeEe
e
***
***
ìü
æö
ïï
ïï
÷
ç
÷
ïï
ç
÷
ïï
ïï
ç
÷
==Σ³=³
ç
íý
÷
ç
÷
ïï
ç
÷
ïï
ç÷
÷
ç
ïï
÷
çèø
ïï
ïï
îþ
%
%
L .
Здесь символами
I
A
*
*
и
I
A
**
**
обозначены матрицы, которые получаются из
матриц
A
*
и
A
**
путем замены в них всех элементов строк с номерами,
соответственно,
{
}
1,,\
jmI
*
Î
L
и
{
}
1,,\
jmkI
**
Î+
L
на нули. Матрица
J
E
%
%
получается из единичной матрицы
n
-го порядка путем замены ее
диагональных элементов, не находящихся на пересечении строк и столбцов с
номерами
jJ
Î
%
, на нули. Применим теорему 1.28 по отношению к
множеству
K
и вектору
c
-
. Из указанной теоремы следует существование
векторов
0
,0,,0,,0,
mkmnsk
vRvvRvRvR
mm
****-**-
γγγÎ
%%
таких, что
0
TTTT
J
II
cAvAvAvE
m
***
******
-=-+-
%
%
%
. (13) 
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


           i Î I ** Þ ( A**u0 ) = b**i Þ ( A** (u0 + te)) = ( A**u0 ) + t ( A**e) ³ b**i , "t ³ 0 ,
                              i                                     i              i           i




                                        j Î J% Þ u0j + te j = te j ³ 0, "t ³ 0 ,

       i Î {1,L, m} \ I * Þ ( A*u0 ) < b*i Þ ( A* (u0 + te)) = ( A*u0 ) + t ( A* e) £ b* i , t Î [0, e] ,
                                        i                                 i            i           i




  i Î {m + 1,L, k } \ I ** Þ ( A**u0 ) > b**i Þ ( A** (u0 + te)) = ( A**u0 ) + t ( A** e) ³ b**i , t Î [0, e] ,
                                            i                                 i            i           i




                                   j Î {1,L, l } \ J% Þ u0j + te j ³ 0, t Î [0, e] ,

где e > 0 достаточно мало. Таким образом, u0 + te Î U .

        В силу того, что точка u0 Î U является решением задачи 1, для нее
справедливо неравенство

                                                     c, u - u0 ³ 0, "u Î U .

        В частности, для точек u0 + te Î U , где t ³ 0 достаточно мало, имеем

                          c, u0 + te - u0 = t c, e ³ 0 Þ -c, e £ 0, "e Î K .

        Множество K перепишем в эквивалентной форме

                          ïìï    æ e1 ö÷                                                 ïüï
                            ïï   çç ÷                                                      ï
                                         ÷
                      K = íe = çççL÷÷ Î R n AI** e £ 0, AI**** e ³ 0; Ae = 0; E%J% e ³ 0ïý .
                             ïï   çç n ÷÷                                                  ïï
                              ï    ççèe ÷ø                                                  ï
                              îï                                                            þï

      Здесь символами AI* и AI** обозначены матрицы, которые получаются из
                                    *           **




матриц A* и A** путем замены в них всех элементов строк с номерами,
соответственно, j Î {1,L, m} \ I * и j Î {m + 1,L, k } \ I ** на нули. Матрица E%J%
получается из единичной матрицы                                         n -го     порядка путем замены ее
диагональных элементов, не находящихся на пересечении строк и столбцов с
номерами         j Î J% , на нули. Применим теорему 1.28 по отношению к

множеству K и вектору -c . Из указанной теоремы следует существование
векторов v* Î R m , v * ³ 0, v ** Î R k-m , v ** ³ 0, m% Î R n , m% ³ 0, v0 Î R s-k таких, что

                                  -c = AI**T v * - AI****T v ** + AT v0 - E%JT% m% .                        (13)


                                                              103

Страницы