ВУЗ:
Составители:
Рубрика:
3
1. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
1.1 Правила построения двойственных задач
1. Рассмотрим задачу линейного программирования следующего вида:
max®xc
T
(1)
bAx
£
(2)
0
³
x
(3)
где
(
)
(
)
(
)
(
)
.,1,,1,,,....,,,....,,,....,
111
mjniaAbbbxxxccc
ijn
T
n
T
n
T
======
Функция Лагранжа для задачи (1) - (3) записывается в виде:
( ) ( ) ( )( )
0,0,, ³³-+=-+=
å
yxAxbyxcAxbyxcyxL
i
ii
TTT
.
Задачу (1) – (3) можно эквивалентно переписать следующим образом:
(
)
,,minmax
0
0
yxL
y
x
³
³
так как для любого фиксированного 0
€
³
x имеет место равенство
(
)
min,
TT
ii
i
cxybAxcx
éù
æö
êú
ç÷
+-=
êú
ç÷
êú
èø
ëû
å
)))
при
(
)
i
i
xAb
€
³
.
Двойственная задача по определению записывается в виде:
(
)
,,maxmin
0
0
yxL
x
y
³
³
где
(
)
(
)
0,0,, ³³-+= yxyAcxybyxL
TTT
.
Зафиксируем произвольное
0
³
y
. Тогда имеют место равенства
(
)
(
)
(
)
(
)
00
,:0
max,max.
,:0
T
j
j
TTT
xx
TTT
j
j
если jcAy
LxybyxcAy
by
если jcAy или Ayc
³³
ì
ï
+¥$->
ï
éù
ï
êú
=+-=
í
êú
ï
êú
ëû
"-£³
ï
ï
î
Таким образом, двойственную задачу можно записать следующим об-
разом:
1. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
1.1 Правила построения двойственных задач
1. Рассмотрим задачу линейного программирования следующего вида:
c T x � max (1)
Ax � b (2)
x�0 (3)
где c T � �c1 ,...., cn �, x T � � x1 ,...., xn �, b T � �b1 ,...., bn �, A � �aij �, i � 1, n, j � 1, m.
Функция Лагранжа для задачи (1) - (3) записывается в виде:
L�x, y � � c T x � y T �b � Ax � � c T x � � yi �bi � � Ax �i �, x � 0, y � 0 .
Задачу (1) – (3) можно эквивалентно переписать следующим образом:
max min L� x, y �,
x�0 y �0
так как для любого фиксированного x€ � 0 имеет место равенство
� � �
� �� �
� T�
�
�
� i
� �
� ��
�
min � c x �� yi � bi � Ax � � � cT x , при bi � � Ax€�i .
�
Двойственная задача по определению записывается в виде:
min max L� x, y �,
y �0 x �0
где L�x, y � � b T y � x T �c � AT y �, x � 0, y � 0 .
Зафиксируем произвольное y � 0 . Тогда имеют место равенства
� �
�
� ��, если �j : c � AT y � 0
�
� �
� �
� �
j
�
max L x, y � max�� bT y � xT c � AT y ��
j
�� .
x� 0 x� 0 � � � T
� �
� b y, если�j : c j � A y � 0 или A y � c
�
�
T
j
T
Таким образом, двойственную задачу можно записать следующим об-
разом:
3
