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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

4
min®yb
T
(4)
cyA
T
³ (5)
0
³
y
(6)
2. Аналогичные рассуждения проведём для задачи, записанной в ка-
нонической форме:
max®xс
T
bAx
=
0
³
x
.
Перепишем задачу в виде (1) – (3)
max®xс
T
bAx
£
bAx
-
£
-
0
³
x
.
Функция Лагранжа в этом случае будет выглядеть следующим образом:
(
)
(
)
(
)
(
)
(
)
AxbvuxcAxbvAxbuxcvuxL
T
TTTT
--+=+-+-+=,,
.
0
,
0
,
0
³
³
³
v
u
x
Обозначим переменную
v
u
-
через переменную
y
. Тогда функцию
Лагранжа можно записать:
(
)
(
)
AxbyxcyxL
TT
-+=, ,
0
³
x
,
y
любого знака.
По определению двойственная задача к канонической записывается в
виде:
(
)
[
]
ybyAcxyb
T
yA
TTT
x
y
T
0
0
minmaxmin
³
³
"-
=-+ .
Таким образом, двойственную задачу к канонической можно записать
следующим образом:
min®yb
T
xyA
T
³
y
"
-
                                            b T y � min                                            (4)
                                              AT y � c                                             (5)
                                                y�0                                                (6)

    2. Аналогичные рассуждения проведём для задачи, записанной в ка-
нонической форме:

                                            с T x � max
                                                Ax � b
                                               x �0.
     Перепишем задачу в виде (1) – (3)

                                            с T x � max
                                                Ax � b
                                             � Ax � �b
                                               x �0.
     Функция Лагранжа в этом случае будет выглядеть следующим образом:

             L� x, u, v � � c T x � u T �b � Ax � � v T �� b � Ax � � c T x � �u � v � �b � Ax �
                                                                                    T




                                            x � 0, u � 0, v � 0.

     Обозначим переменную u � v через переменную y . Тогда функцию
Лагранжа можно записать: L�x, y � � c T x � y T �b � Ax � , x � 0 , y любого знака.

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

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



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

                                            b T y � min
                                              AT y � x
                                            y � � знака



                                                  4

Страницы