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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

7
1.2 Свойства пары двойственных задач
Обозначим через
W
и
Q
соответственно допустимые множества ис-
ходной задачи (1) – (3) и двойственной задачи (4) – (6).
{
}
0,:
³
£
=
W
xbAxx
{
}
0,: ³³= ycyAyQ
T
.
1. Задача двойственная к двойственной является исходной.
Запишем задачу (4)-(6) в виде
max®- yb
T
cyA
T
-£-
0
³
y
,
двойственная к которой по определению имеет вид
min®- xс
T
max®xc
T
bxA
T
-³-
или
bxA
T
£
0
³
x
0
³
x
.
2. Для любых
W
x
и
Q
y
имеет место неравенство ybxc
TT
£
.
Действительно, всегда справедливы соотношения:
ybbyAxyyAxcxxc
T
x
TT
Qy
TTTT
=£=£=
WÎÎ"
3. Если в одной из задач (исходной или двойственной) отсутствует
решение из-за неограниченности целевой функции на допустимом множе-
стве, то в двойственной к ней допустимое множество пусто.
Например, если
+¥=
W
xc
T
sup
, то
Æ
=
Q
.
Доказательство.
Предположим противное. Пусть
Æ
¹
Q
, тогда
yQ
$Î
)
.
Используя свойство 2, запишем неравенство
TT
cxby
£
)
,
W
x
, что
противоречит неограниченности целевой функции xc
T
на множестве
W
.
4. Если x
$ÎW
)
и
yQ
$Î
)
такие, что
TT
cxby
=
))
, то
x
)
– решение исходной
задачи,
y
)
– решение двойственной задачи. 
                  1.2 Свойства пары двойственных задач

    Обозначим через � и Q соответственно допустимые множества ис-
ходной задачи (1) – (3) и двойственной задачи (4) – (6).
                                   � � �x : Ax � b, x � 0�
                                   Q � �y : AT y � c, y � 0�.
    1. Задача двойственная к двойственной является исходной.
   Запишем задачу (4)-(6) в виде

                                     � b T y � max
                                          � AT y � �c
                                            y � 0,
   двойственная к которой по определению имеет вид
                   � с T x � min                                   c T x � max
                   � A T x � �b                или                   AT x � b
                      x�0                                             x �0.


    2. Для любых x � � и y � Q имеет место неравенство c T x � b T y .
   Действительно, всегда справедливы соотношения:
                     c T x � x T c � x T AT y � y T Ax � y T b � b T y
                                   �y�Q                  x��




     3. Если в одной из задач (исходной или двойственной) отсутствует
решение из-за неограниченности целевой функции на допустимом множе-
стве, то в двойственной к ней допустимое множество пусто.
      Например, если sup c T x � �� , то Q � � .
                         �

     Доказательство.
                                                �
    Предположим противное. Пусть Q � � , тогда �y � Q .
                                                                                 �
    Используя свойство 2, запишем неравенство cT x � bT y , �x � � , что
противоречит неограниченности целевой функции c T x на множестве � .

              �          �                           �         �      �
    4. Если �x � � и �y � Q такие, что cT x � bT y , то x – решение исходной
        �
задачи, y – решение двойственной задачи.

                                              7

Страницы