Элементы теории двойственности. Чернышова Г.Д - 10 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

10
Для задачи (1) – (3) аналогичная система имеет вид:
ï
ï
ï
î
ï
ï
ï
í
ì
=
³
³
³
£
ybxc
y
cyA
x
bAx
TT
T
0
0
.
Вторая теорема двойственности.
Пусть решается задача (1) – (3). Для того, чтобы Qyx ÎWÎ
00
, были
решениями исходной и двойственной задач, необходимо и достаточно вы-
полнение условий дополняющей нежёсткости:
(
)
0
00
=- yAcx
TT
(
)
(
)
0
00
=-
i
T
ii
yAcx , ni ,1="
(
)
0
00
=- xAby
TT
(
)
(
)
0
00
=-
j
T
jj
xAby , mj ,1="
Доказательство
1. Необходимость
Пусть WÎ
0
x – решение исходной задачи, Qy Î
0
– решение двойст-
венной задачи. Тогда по первой теореме двойственности
( )
.0
,
00
00000
³-
³==
yAcx
Axybyybxc
TT
TTTT
С другой стороны, 0,0
00
£-³ yAcx
T
. Значит,
(
)
0
00
£- yAcx
TT
. Полу-
чаем, что
(
)
0
00
=- yAcx
TT
.
Аналогичные рассуждения проводятся для второго равенства.
2. Достаточность
Пусть в некоторых точках
00
,
xyQ
ÎWÎ
выполняются условия допол-
няющей нежёсткости, покажем, что они являются оптимальными точками.
Заметим, что
(
)
(
)
0000
AxbyyAcx
TTT
-=- .
Тогда
(
)
(
)
000000
xyAybxyAxc
T
TT
T
TT
-=- . Откуда следует равенство
00
ybxc
TT
= .
Из свойства 3 следует, что
0
x
– решение исходной задачи, а
0
y – ре-
шение двойственной задачи.
Теорема доказана. 
      Для задачи (1) – (3) аналогичная система имеет вид:
                                                  � Ax � b
                                                  �x � 0
                                                  �
                                                  � T
                                                  �A y � c .
                                                  �y � 0
                                                  �
                                                  ��c T x � b T y
      Вторая теорема двойственности.
      Пусть решается задача (1) – (3). Для того, чтобы x 0 � �, y 0 � Q были
решениями исходной и двойственной задач, необходимо и достаточно вы-
полнение условий дополняющей нежёсткости:

           x 0 T �c � AT y 0 � � 0                   xi0 �ci � �AT y 0 �i � � 0 , �i � 1, n
            y 0 T �b � AT x 0 � � 0                  y 0j �b j � �AT x 0 � j � � 0 , �j � 1, m


      Доказательство
           1. Необходимость
      Пусть x 0 � � – решение исходной задачи, y 0 � Q – решение двойст-
венной задачи. Тогда по первой теореме двойственности
                                      c T x 0 � b T y 0 � y 0 T b � y 0 T Ax 0 ,
                                      x 0 T �c � AT y 0 � � 0.
      С другой стороны, x 0 � 0, c � AT y 0 � 0 . Значит, x 0 T �c � AT y 0 � � 0 . Полу-
чаем, что x 0 T �c � AT y 0 � � 0 .
      Аналогичные рассуждения проводятся для второго равенства.
          2. Достаточность
      Пусть в некоторых точках x 0 � �, y 0 � Q выполняются условия допол-
няющей нежёсткости, покажем, что они являются оптимальными точками.
   Заметим, что x 0 T �c � AT y 0 � � y 0 T �b � Ax 0 � .
      Тогда c T x 0 � �AT y 0 � x 0 � b T y 0 � �AT y 0 � x 0 . Откуда следует равенство
                                      T                          T



c T x 0 � bT y 0 .
      Из свойства 3 следует, что x 0 – решение исходной задачи, а y 0 – ре-
шение двойственной задачи.
   Теорема доказана.

                                                         10

Страницы