*
第二章
线性规划的对偶理论与灵敏度分析
*
第一节 LP 的对偶理论
一、对偶问题的提出
Ⅰ Ⅱ 每天可用能力
设备A 0 5 15
设备B 6 2 24
调试工序 1 1 5
利润 2 1
①两种家电各生产多少, 可获最大利润?
*
解:设两种家电产量分别为变量x1 ， x2
5x2 15
6x1 + 2x2 24
x1 + x2 5
x1，x2 0
max Z= 2x1 +x2
*
②另一家公司至少应付出多少代价才能使美佳公司愿意出让自己的资源而不组织两种产品的生产？
解：设 y1 , y2 , y3 分别为A, B设备和调试工序工时出让的单价。
minW=15y1+24y2 +5y3
6y2 +y3 2
5y1 +2y2 +y3 1
y1 … y3 0
*
二、对偶问题与原问题的关系
1. “对称型” (P)
MaxZ=C1X1+ C2X2+…+CnXn
a11X1+ a12X2+…+ a1nXn b1
a21X1+ a22X2+…+ a2nXn b2
… … …
am1X1+ am2X2+…+ amnXn bm
Xj 0(j=1,…,n)
*
MinW=b1Y1+ b2Y2+…+bnYn
a11Y1+ a21Y2+…+ am1Ym c1
a12Y1+ a22Y2+…+ am2Ym c2
… … …
a1nY1+ a2nY2+…+ amnYm cn
Yi 0(i=1,…,m)
(D)
*
例1：写出下面问题的对偶规划
maxZ= 5X1 +6X2
3X1 -2X2 7
4X1 +X2 9
X1 , X2 0
minW=7y1 +9y2
3y1+4y2 5
-2y1 +y2 6
y1, y2 0
*
例1：写出下面问题的对偶规划
maxZ= 5X1 +6X2
3X1 -2X2 =7
4X1 +X2 9
X1 , X2 0
2. “非对称型” (P)
*
对偶问题
minW=7y1 +9y2
3y1+4y2 5
-2y1 +y2 6
y1自由 , y2 0
*
例2：写对偶规划
minZ= 4X1 +2X2 -3X3
-X1+2X2 6
2X1 +3X3 9
X1 +5X2 -2X3 = 4
X2 , X3 0
*
maxW= 6y1 +9y2 +4y3
-y1+2y2 + y3 = 4
2y1 +5y3 2
3y2 -2y3 -3
y1 0 , y2 0 , y3自由
*
minZ= 4X1 +2X2 -3X3
X1 -2X2 - 6
2X1 +3X3 9
X1 +5X2 -2X3 = 4
X2 , X3 0
或将原问题变形为
*
观察结论:
① 一对对偶问题都有最优解，且目标函数值相等。
② 最优表中有两个问题的最优解。
*
第二节 对偶问题的基本性质
一、单纯形法计算的矩阵描述
maxZ=CX
AX≤ b
X0
(P)
maxZ=CX
AX+IXS =b
X, XS0
*
（初始单纯形表）
非基变量
基变量
XB
XN
XS
0
XS
b
B
N
I
σ
CB
CN
0
*
（迭代中的单纯形表）
基变量
非基变量
XB
XN
XS
0
XB
B-1 b
I
B-1 N
B-1
σ
0
CN- CB B-1 N
- CB B-1
*
二、对偶问题的基本性质
1.对称性：对偶问题的对偶问题是原问题
2.定理1 (弱对偶定理)若 , 分别是原问题和对偶问题的可行解，则存在
推论：1.原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。
*
推论：2.若原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，对偶问题有无界解，原问题无可行解。（但逆向不成立）
推论：3.若原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，而原问题无可行解，则对偶问题的目标函数值无界。
*
3.定理2
y
X
,
分别为(P), (D)的可行解，且
X
y
C
=
b
, 则它们是(P), (D) 的最优解。
4.定理3（对偶定理）若原问题有最优解，对偶问题也有最优解，且目标函数值相等。或若原问题与对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。
5.互补松弛性： ， 分别是原问题和对偶问题的可行解，则 当且仅当 为最优解。
*
例： min = 2x1+3x2+5x3+2x4+3x5
其对偶解 y1﹡ =4/5 y2﹡ =3/5 Z﹡ =5
用对偶理论求(P)的最优解
x1+x2+2x3+x4+3x5 4
2x1 -x2+3x3+x4+x5 3
xi 0 ( i =1 … 5 )
(P)
在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，该约束条件取严格等式。反之，若约束条件取严格不等式，则其所对应的对偶变量一定为0。
*
第四节 对偶单纯形法
minZ=2X1 +3X2 +4X3
X1+2X2 + X3 3
2X1 - X2 +3X3 4
X1 , X2 , X3 0
*
初始单纯形表为
CB
XB
b
x1
x2
x3
x4
x5
-2
-3
-4
0
0
0
x4
-3
-1
-2
-1
1
0
0
x5
-4
-2
1
-3
0
1
σ
-2
-3
-4
0
0
*
思路：(max型)
单纯形法：找基B，满足B-1b0，即先找到基可行解，当 C - CBB-1 A不全 0，（即检验数）。
迭代
保持B-1b0，使C -CBB-1 A 0，即CBB-1 A C，（保持原问题的为基可行解，寻找对偶问题的可行解）
*
一、对偶单纯形法的基本思路：
找基B，满足C - CBB-1 A 0（检验数），即找到对偶问题的可行解。
如果B-1b不全0，即原问题的基解为非可行解，则
迭代
保持C -CBB-1 A 0，使B-1b0。
即保持对偶问题的解为可行解，使原问题的基解逐渐转换为基可行解。
*
二、对偶单纯形法基本步骤 max型(min型)
(1) 作初始表，要求全部σj 0 (0)
(2) 判定： B-1 b全0，停。否则，取
max{ B-1 b }=(B-1 b)l
B-1 b<0
令第 l 行的Xj l为换出变量.
*
(3)确定换入变量
① 若Xi l行的alj 全0 ，停，原问题无可行解。
② 若Xi l行的alj 有alj <0 ,
则求
σj
σk
θ=min{ }=
alj
alk
alj <0
Xk为换入变量
σk
alk
(4) 以alk 为主元，换基迭代
*
CB
XB
b
x1
x2
x3
x4
x5
-2
-3
-4
0
0
0
x4
-3
-1
-2
-1
1
0
0
x5
-4
-2
1
-3
0
1
σ
-2
-3
-4
0
0
θ
1
-
4/3
-
-
*
CB
XB
b
x1
x2
x3
x4
x5
-2
-3
-4
0
0
0
x4
-1
0
-5/2
1/2
1
-1/2
-2
x1
2
1
-1/2
3/2
0
-1/2
σ
0
-4
-1
0
-1
θ
-
8/5
-
-
2
*
CB
XB
b
x1
x2
x3
x4
x5
-2
-3
-4
0
0
-3
x2
2/5
0
1
-1/5
-2/5
1/5
-2
x1
11/5
1
0
7/5
-1/5
-2/5
σ
0
0
-9/5
-8/5
-1/5
*
练习1：
maxZ=-X1 -4X2 -3X4
X1+2X2 - X3 +X4 3
-2X1 - X2 +4X3 +X4 2
X1 … X4 0
*
最优解：X=(7,0,4,0)T Z= -7
-1 -4 0 -3 0 0
CB XB b X1 X2 X3 X4 X5 X6
0 X5 -3 (-1) -2 1 -1 1 0
0 X6 -2 2 1 -4 -1 0 1
0 σ -1 -4 0 -3 0 0
-1 X1 3 1 2 -1 1 -1 0
0 X6 -8 0 -3 (-2) -3 2 1
- 3 σ 0 -2 -1 -2 -1 0
-1 X1 7 1 7/2 0 5/2 -2 -1/2
0 X3 4 0 3/2 1 3/2 -1 -1/2
-7 σ 0 -1/2 0 -1/2 -2 -1/2
*
maxZ=-X1 -X2
2X1 -X2 2
-X1 + 1/2X2 1
X1 , X2 0
练习2：
*
第五节 灵敏度分析
CBB-1b C - CBB-1 A
B-1 b B-1 A
原始数据A，b，C
A=(P1 P2 … Pn )
aij ,bj, cj
一、灵敏度分析的概念
对系统或事物（线性规划问题）因周围条件的变化（如aij ,bj, cj 的变化）显示出来的敏感程度的分析。
*
(1) 参数A，b，C在什么范围内变动，对当前方案无影响？
(2) 参数A，b，C中的一个(几个)变动，对当前方案影响？
(3) 如果最优方案改变，如何用简便方法求新方案？
二、灵敏度分析所解决的问题
*
原问题
对偶问题
结论或继续计算的步骤
可行解
可行解
问题的最优解或最优基不变
可行解
非可行解
用单纯形法继续迭代求最优解
非可行解
可行解
用对偶单纯形法继续迭代求最优解
非可行解
非可行解
引进人工变量，编制新的单纯形表重新计算
*
一、分析 cj 的变化
cj 的变化首先影响检验数
① XB= B-1b
② σA = C - CBB-1 A = C - Y A
σN = CN - CBB-1 N = CN - Y N
σj = Cj - CBB-1 Pj = Cj - Y Pj
*
maxZ=2X1 +X2
5X2 + X3 =15
6X1 +2X2 + X4 =24
X1 + X2 + X5 =5
Xj 0
设备A
设备B
调试工序
*
CB
XB
b
x1
x2
x3
x4
x5
θ
2
1
0
0
0
0
x3
15/2
0
0
1
5/4
-15/2
2
x1
7/2
1
0
0
1/4
-1/2
1
x2
3/2
0
1
0
-1/4
3/2
σ
0
0
0
-1/4
-1/2
1.若家电1的利润降至元/件，而家电2的利润增至2元/件时，美佳公司最优生产计划有何变化？
*
2.若家电1的利润不变，则家电2的利润在什么范围内变化时则该公司的最优生产计划将不发生变化。
CB
XB
b
x1
x2
x3
x4
x5
θ
2
1+λ
0
0
0
0
x3
15/2
0
0
1
5/4
-15/2
2
x1
7/2
1
0
0
1/4
-1/2
1+λ
x2
3/2
0
1
0
-1/4
3/2
σ
0
0
0
-1/4+
1/4 λ
-1/2-
3/2 λ
*
-1/4+1/4 λ≤0
-1/2- 3/2 λ≤0
- 1/3 ≤λ≤1
2/3 ≤c2≤2
*
二、分析 bi的变化
bi 的变化首先影响XB= B-1b
① XB= B-1b
② σA = C - CBB-1 A = C - Y A
σN = CN - CBB-1 N = CN - Y N
σj = Cj - CBB-1 Pj = Cj - Y Pj
*
3.若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化。
∵XB= B-1b ，b b’=b+△b
∴ XB= B-1b’= B-1(b+ △b)
= B-1b+ B-1 △b
B-1 △b=
5/4 –15/2 0 10
0 1/4 -1/2 8 = 2
0 -1/4 3/2 0 -2
*
CB
XB
b
x1
x2
x3
x4
x5
θ
2
1
0
0
0
0
x3
35/2
0
0
1
5/4
-15/2
2
x1
11/2
1
0
0
1/4
-1/2
1
x2
-1/2
0
1
0
-1/4
3/2
σ
0
0
0
-1/4
-1/2
*
CB
XB
b
x1
x2
x3
x4
x5
θ
2
1
0
0
0
0
x3
35/2
0
0
1
5/4
-15/2
2
x1
11/2
1
0
0
1/4
-1/2
1
x2
-1/2
0
1
0
-1/4
3/2
σ
0
0
0
-1/4
-1/2
0
x3
15
0
5
1
0
0
2
x1
5
1
1
0
0
1
0
x4
2
0
-4
0
1
-6
σ
0
-1
0
0
-2
*
4.若设备A和B每天能力不变，而调试工序在什么范围内变化，问题的最优基不变。
B-1 △b=
5/4 –15/2 0 -15/2λ
0 1/4 -1/2 0 = -1/2λ
0 -1/4 3/2 λ 3/2λ
*
CB
XB
b
x1
x2
x3
x4
x5
θ
2
1
0
0
0
0
x3
15/2 -15/2λ
0
0
1
5/4
-15/2
2
x1
7/2 -1/2λ
1
0
0
1/4
-1/2
1
x2
3/2 +3/2λ
0
1
0
-1/4
3/2
σ
0
0
0
-1/4
-1/2
1 ≤λ≤1
4 ≤ b3≤6
*
三、增加一个决策变量xj 的分析
5.公司计划推出新产品3，生产一件所需设备A,B及调试工序的时间分别为3小时、4小时、2小时，预期盈利3元/件，试分析该种产品是否值得投产，如投产，对该公司的最优生产计划有何影响。
*
σ6 = C6 - CBB-1 P6 = C6 - Y P6
3
=3-( 0, 1/4 , 1/2) 4 = 1
2
P6 =B-1 P6 =
~
5/4 -15/2 3 -7
0 1/4 -1/2 4 = 0
0 -1/4 3/2 2 2
*
CB
XB
b
x1
x2
x3
x4
x5
x6
2
1
0
0
0
3
0
x3
15/2
0
0
1
5/4
-15/2
-7
2
x1
7/2
1
0
0
1/4
-1/2
0
1
x2
3/2
0
1
0
-1/4
3/2
2
σ
0
0
0
-1/4
-1/2
1
*
CB
XB
b
x1
x2
x3
x4
x5
x6
2
1
0
0
0
3
0
x3
15/2
0
0
1
4/5
-15/2
-7
2
x1
7/2
1
0
0
1/4
-1/2
0
1
x2
3/2
0
1
0
-1/4
3/2
2
σ
0
0
0
-1/4
-1/2
1
0
x3
51/4
0
7/2
1
3/8
-9/4
0
2
x1
7/2
1
0
0
1/4
-1/2
0
3
x6
3/4
0
1/4
0
-1/8
3/4
1
σ
0
-1/2
0
-1/8
-5/4
0
*
四、分析 aij的变化
① XB= B-1b
② σj = Cj - CBB-1 Pj = Cj - Y Pj
③ Pj =B-1 Pj
~
*
CB
XB
b
x1
x2
x3
x4
x5
x2’
2
1
0
0
0
3
0
x3
15/2
0
0
1
5/4
-15/2
2
x1
7/2
1
0
0
1/4
-1/2
1
x2
3/2
0
1
0
-1/4
3/2
σ
0
0
0
-1/4
-1/2
*
σ2’ = C2’ - CBB-1 P2’ = C2’ - Y P2’
8
=3 - ( 0, 1/4 , 1/2) 4 = 3/2
1
P2 =B-1 P2’ =
~
5/4 -15/2 8 11/2
0 1/4 -1/2 4 = 1/2
0 -1/4 3/2 1 1/2
*
CB
XB
b
x1
x2’
x3
x4
x5
x6
2
3
0
0
0
-M
-M
x6
9
0
0
-1
-4
24
1
2
x1
2
1
0
0
1/2
-2
0
3
x2’
3
0
1
0
-1/2
3
0
σ
0
0
-M
1/2-1/4M
-5+24M
0
0
x5
3/8
0
0
-1/24
-1/6
1
1/24
2
x1
11/4
1
0
-1/12
1/6
0
1/12
3
x2’
15/8
0
1
1/8
0
0
-1/8
σ
0
0
-5/24
-1/3
0
-M+5/24
*
7.若美佳公司家电产品还需一道环境试验工序，家电1每件需环境试验3小时，家电2每件需环境试验2小时，环境试验工序每天的生产能力为12小时，试重新确定该公司的最优生产计划。
maxZ=2X1 +X2
5X2 + X3 =15
6X1 +2X2 + X4 =24
X1 + X2 + X5 =5
3X1 +2X2 + X6 =12
Xj 0
设备A
设备B
调试工序
*
3X1 +2X2 + X6 =12
CB
XB
b
x1
x2
x3
x4
x5
θ
2
1
0
0
0
0
x3
15/2
0
0
1
5/4
-15/2
2
x1
7/2
1
0
0
1/4
-1/2
1
x2
3/2
0
1
0
-1/4
3/2
σ
0
0
0
-1/4
-1/2
将原最优解代入新约束条件
3×7/2+2×3/2=27/2>12,原最优解失效
*
CB
XB
b
x1
x2
x3
x4
x5
x6
2
1
0
0
0
0
0
x3
15/2
0
0
1
5/4
-15/2
0
2
x1
7/2
1
0
0
1/4
-1/2
0
1
x2
3/2
0
1
0
-1/4
3/2
0
0
x6
-3/2
0
0
0
-1/4
-3/2
1
σ
0
0
0
-1/4
-1/2
0
0
x3
15
0
0
1
5/2
0
-5
2
x1
4
1
0
0
1/3
0
-1/3
1
x2
0
0
1
0
-1/2
0
1
0
x5
1
0
0
0
1/6
1
-2/3
σ
0
0
0
-1/6
0
-1/3
