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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

5
3. Рассмотрим далее задачу линейного программирования (1) – (2)
max®xc
T
(1)
bAx
£
. (2)
Введём замену переменных 0,0,
³
¢
¢
³
¢
¢
¢
-
¢
=
xxxxx . Задача эквивалент-
но перепишется следующим образом:
(
)
max®
¢¢
-
¢
xxc
T
(
)
bxxA
£
¢
¢
-
¢
0,0
³
¢
¢
³
¢
xx .
Функция Лагранжа для задачи имеет вид:
(
)
(
)
(
)
(
)
0,0,0,,, ³³
¢¢
³
¢¢¢
-
¢
-+
¢¢
-
¢
=
¢¢¢
yxxxxAbyxxcyxxL
TT
.
Исходную задачу перепишем в виде:
(
)
yxxL
y
xx
,,minmax
0
0,
¢
¢
¢
³
³
¢¢¢
.
По определению двойственная задача запишется в виде:
(
)
yxxL
xx
y
,,maxmin
0,
0
¢
¢
¢
³
¢¢¢
³
(
)
(
)
(
)
yAcxxybyxxL
T
T
T
-
¢¢
-
¢
+=
¢¢¢
,, .
Зафиксируем произвольное
0
³
y
. Тогда справедливы равенства:
( )
( )
[ ]
(
)
( )
ï
î
ï
í
ì
==-"
¹-$¥+
=-+=
"-"-
cyAилиyAcjеслиyb
yAcjесли
yAcxybyxL
T
j
T
j
T
j
T
j
TTT
xx
0:,
0:,
max,max
(
)
[
]
.,minmaxmin
00
cyAеслиybyAcxyb
TT
y
TTT
x
y
==-+
³
"-
³
Двойственную задачу можно записать следующим образом:
min®yb
T
cyA
T
=
0
³
y
. 
        3.     Рассмотрим далее задачу линейного программирования (1) – (2)

                                                          c T x � max                                    (1)
                                                              Ax � b .                                   (2)

        Введём замену переменных x � x� � x ��, x � � 0, x �� � 0 . Задача эквивалент-
но перепишется следующим образом:

                                                 c T �x � � x��� � max
                                                     A�x � � x ��� � b
                                                         x � � 0, x �� � 0 .
        Функция Лагранжа для задачи имеет вид:

               L�x �, x��, y � � c T � x � � x ��� � y T �b � A� x � � x����, x� � 0, x�� � 0, y � 0 .

        Исходную задачу перепишем в виде:

                                                max min L� x �, x ��, y � .
                                                x � , x��� 0   y �0



        По определению двойственная задача запишется в виде:

                                                min max L� x �, x ��, y �
                                                    y � 0 x� , x ��� 0



                                L�x �, x��, y � � b T y � � x � � x��� �c � AT y � .
                                                                               T




        Зафиксируем произвольное y � 0 . Тогда справедливы равенства:

                                          ��� �, если �j : c j � �AT y � j � 0
max L� x, y � � max�b y � x �c � A y �� � � T
                          T        T            T

                                           ��b y, если�j : c j � �A y � j � 0 или A y � c
 x ��            x ��                                              T               T




min max�b T y � x T �c � AT y �� � min b T y , если AT y � c.
 y �0   x ��                             y �0



        Двойственную задачу можно записать следующим образом:

                                                           b T y � min
                                                                AT y � c
                                                                  y � 0.



                                                                         5

Страницы