文章目录
一、原问题与对偶问题标准形式
二、互补松弛定理
三、互补松弛定理示例说明
一、原问题与对偶问题标准形式
原问题 P \rm PP : m a x Z = C X s . t { A X ≤ b X ≥ 0
maxZ=CXs.t⎧⎩⎨AX≤bX≥0
maxZ=CXs.t{AX≤bX≥0
maxZ=CX
s.t
⎩
⎪
⎨
⎪
⎧
AX≤b
X≥0
; \ \ \ \ \ \ \ \ \ \ \, 对偶问题 D \rm DD : m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0
minW=bTYs.t⎧⎩⎨ATY≥CTY≥0
minW=bTYs.t{ATY≥CTY≥0
minW=b
T
Y
s.t
⎩
⎪
⎨
⎪
⎧
A
T
Y≥C
T
Y≥0
等价方法 :
生产 : 目标函数追求 利润最大化 , 约束方程设备的使用时长受约束 , 小于等于 某个时间值 ;
出租设备 : 目标函数追求 租金最小化 , 约束方程设备产生的利润要 大于等于 生产的利润 , 不能亏钱 ;
二、互补松弛定理
X 0 \rm X^0X
0
和 Y 0 \rm Y^0Y
0
分别是 原问题 P \rm PP 问题 和 对偶问题 D \rm DD 的 可行解 ,
这两个解各自都是对应 线性规划问题 的 最优解
的 充要条件是 : { Y 0 X s = 0 Y s X 0 = 0
⎧⎩⎨Y0Xs=0YsX0=0
{Y0Xs=0YsX0=0
⎩
⎪
⎨
⎪
⎧
Y
0
X
s
=0
Y
s
X
0
=0
其中 X s , Y s \rm X_s , Y_sX
s
,Y
s
是 松弛变量 或 剩余变量 ;
三、互补松弛定理示例说明
原问题与对偶问题的对应关系 :
生产问题 ( 原问题 ) :
m a x Z = 2 x 1 + 3 x 2 s . t { 2 x 1 + 2 x 2 ≤ 12 x 1 + 2 x 2 ≤ 8 4 x 1 ≤ 16 4 x 2 ≤ 12 x 1 , x 2 ≥ 0
maxZ=2x1+3x2s.t⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1,x2≥0
maxZ=2x1+3x2s.t{2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1,x2≥0
maxZ=2x
1
+3x
2
s.t
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎧
2x
1
+2x
2
≤12
x
1
+2x
2
≤8
4x
1
≤16
4x
2
≤12
x
1
,x
2
≥0
上述线性规划的最优解是 : ( 4 2 )
(42)
(42)
(
42
) ;
甲产品生产 4 44 个单位 , 乙产品生产 2 22 个单位 ;
设备出租问题 ( 对偶问题 ) :
m i n W = 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 s . t { 2 y 1 + y 2 + 4 y 3 + 0 y 4 ≥ 2 2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 ≥ 3 y 1 , y 2 , y 3 , y 4 ≥ 0
minW=12y1+8y2+16y3+12y4s.t⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪2y1+y2+4y3+0y4≥22y1+2y2+0y3+4y4≥3y1,y2,y3,y4≥0
minW=12y1+8y2+16y3+12y4s.t{2y1+y2+4y3+0y4≥22y1+2y2+0y3+4y4≥3y1,y2,y3,y4≥0
minW=12y
1
+8y
2
+16y
3
+12y
4
s.t
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎧
2y
1
+y
2
+4y
3
+0y
4
≥2
2y
1
+2y
2
+0y
3
+4y
4
≥3
y
1
,y
2
,y
3
,y
4
≥0
上述线性规划最优解是 : ( 1 2 1 0 0 )
(12100)
(12100)
(
2
1
100
) , 或 ( 0 2 3 1 8 0 )
(023180)
(023180)
(
0
3
2
8
1
0
)
将上面两个线性规划的最优解代入目标函数 , 得到的值都是 14 1414 ;
互补松弛定理 :
" X 0 \rm X^0X
0
和 Y 0 \rm Y^0Y
0
分别是 原问题 P \rm PP 问题 和 对偶问题 D \rm DD 的 最优解 " ⇔ \Leftrightarrow⇔ { Y 0 X s = 0 Y s X 0 = 0
⎧⎩⎨Y0Xs=0YsX0=0
{Y0Xs=0YsX0=0
⎩
⎪
⎨
⎪
⎧
Y
0
X
s
=0
Y
s
X
0
=0
其中 X s , Y s \rm X_s , Y_sX
s
,Y
s
是 松弛变量 或 剩余变量 ;
( 4 2 )
(42)
(42)
(
42
) 是原问题 P \rm PP 的最优解 , 是 X 0 \rm X^0X
0
,
Y s \rm Y_sY
s
是对偶问题 D \rm DD 的剩余变量 , { 2 y 1 + y 2 + 4 y 3 + 0 y 4 − y 5 = 2 2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 − y 6 = 3
⎧⎩⎨2y1+y2+4y3+0y4−y5=22y1+2y2+0y3+4y4−y6=3
{2y1+y2+4y3+0y4−y5=22y1+2y2+0y3+4y4−y6=3
⎩
⎪
⎨
⎪
⎧
2y
1
+y
2
+4y
3
+0y
4
−y
5
=2
2y
1
+2y
2
+0y
3
+4y
4
−y
6
=3
, 两个剩余变量是 ( y 5 y 6 )
(y5y6)
(y5y6)
(
y
5
y
6
) , 是 Y s \rm Y_sY
s
,
根据互补松弛定理 , Y s X 0 = 0 \rm Y_sX^0 = 0Y
s
X
0
=0 , 将真实值代入 :
Y s X 0 = ( 4 2 ) × ( y 5 y 6 ) = 4 y 5 + 2 y 6 = 0 \rm Y_sX^0 =
(42)
(42)
\times
(y5y6)
(y5y6)
=4 y_5 + 2y_6 = 0Y
s
X
0
=(
42
)×(
y
5
y
6
)=4y
5
+2y
6
=0
y 5 , y 6 \rm y_5 , y_6y
5
,y
6
都是大于等于 0 00 的 , 如果要满足 4 y 5 + 2 y 6 = 0 \rm 4 y_5 + 2y_6 = 04y
5
+2y
6
=0 , 则得到 y 5 = 0 , y 6 = 0 \rm y_5 = 0, y_6 = 0y
5
=0,y
6
=0 结论 ;
