OR1 1
第三章 对偶问题与灵敏度分析
要求：
了解 LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握 LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容
OR1 2
3.1 对偶问题
3.1.1 对偶问题的提出回顾例题 1,现在 A,B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？
产品 A 产品 B 资源限制劳动力设备原材料
9
4
3
4
5
10
360
200
300
单位利润 70 120
OR1 3
对偶模型
设每个工时收费 Y1元，设备台时费用 Y2
元，原材料附加费 Y3元。
出租收入不低于生产收入：
9y1+4y2+3y3 ≥70
4y1+5y2+10y3 ≥120
目标,ω=360y1+200y2+300y3
出租收入越多越好？至少不低于某数
OR1 4
原问题与对偶问题之比较原问题,对偶问题：
maxZ=70X1+120X2 minω=360y1+200y2+300y3
9X1+4X2≤360 9y1+4y2+3y3 ≥70
4X1+5X2≤200 (3.1) 4y1+5y2+10y3 ≥120 (3.2)
3X1+10X2≤300 y1 ≥0,y2 ≥0,y3 ≥0
X1≥0 X2≥0
OR1 5
3.1.2对偶规则原问题一般模型,对偶问题一般模型：
maxZ=CX min ω=Yb
AX ≤b YA ≥C
X ≥0 Y ≥0
OR1 6
对偶规则
原问题有 m个约束条件，对偶问题有 m个变量
原问题有 n个变量，对偶问题有 n个约束条件
原问题的价值系数对应对偶问题的右端项
原问题的右端项对应对偶问题的价值系数
原问题的技术系数矩阵转置后为对偶问题系数矩阵
原问题的约束条件与对偶问题方向相反
原问题与对偶问题优化方向相反
OR1 7
对偶规则
.
原问题 对偶问题目标函数 max min 目标函数约束条件 ≤
≥
=
≥ 变量
≤
无约束
≥
变量符号 ≤
无约束
≥
≤ 约束条件
=
OR1 8
对偶规则简捷记法
原问题标准则对偶问题标准
原问题不标准则对偶问题不标准
例题 2 max ω=7y1+4y2-2y3
minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3
2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2
x1+ 2x3 -x4 ≤4 -4y1+ 2y2 ≤-6
-x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0
x1,x2,x3 ≥0; 3y1 +y3=1
x4 ≤0;x5无限制 y1 ≥ 0y2 ≤ 0y3 无约束
OR1 9
3.1.3对偶问题的基本性质
对称性：对偶问题的对偶问题是原问题
弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图 )
无界性：原问题无界，对偶问题无可行解
对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为 B，则其对偶问题最优解 Y*=CBB-1
OR1 10
3.1.4对偶最优解的经济解释 — 影子价格
Z= ω=CX=Yb?Z/? b=(Yb)’=Y
Z=Yb= ∑yibi的意义,Y是检验数的反数。在 Y确定的前提下，每增加一个单位的 i种资源，对目标函数的贡献。
结合例题 1讲解影子价格,y1=0:第一种资源过剩
y2=13.6：设备台时最紧张，每增加一个台时,利润增加
13.6元。 y3=5.2…
影子价格所含有的信息,1、资源紧缺状况
2、确定资源转让基价参见,P40 3、取得紧缺资源的代价
OR1 11
3.2灵敏度分析
为什么进行灵敏度分析？
灵敏度分析的两把尺子：
σj =Cj-CBB-1pj≤ 0；? xB= B-1b ≥0
3.2.1 价值系数的灵敏度分析
Cj变化到什么程度可以保持最优基不变？用?
（参看 P96）
例题 4,87.5 ≤ C2 ≤ 233.33； 36 ≤ C1 ≤ 96
OR1 12
灵敏度分析
右端项的灵敏度分析：
bi变化到什么程度可以保持最优基不变？用尺度?
xB= B-1b ≥0
例题 5,1 -3.12 1.16 360
B-1b= 0 0.4 -0.2 200 ≥0
0 -0.12 0.16 b3
b3的变化范围,227.586 ≤ b3 ≤ 400
OR1 13
其它形式的灵敏度分析新产品的分析：
在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。
例题 6：新增一种 C产品，单位利润 110元，使用劳动力 6工时，设备 5台时，原材料 7公斤，问要否调整产品结构？
先算检验数 σj =Cj-CBB-1pj
σ6=C6-YP6=110-（ 0,13.6,5.2）（ 6,5,7） T
= 110-104.4=5.6 大于零，有利可图，将 P6左乘 B-1，
加入到末表之中，继续迭代，直到求得最优解。
OR1 14
3.3用计算机进行灵敏度分析
例题 7 参见 P102
OR1 15
习题课：
P78—— 2.10
（ 1）唯一最优解,H3 ≤ 0,H5≤ 0,H1 ≥0
（ 2）无穷多最优解,H3=0,H1 ≥0,H5? 0,H2>0
或 H5=0,H1 ≥0,H3? 0,H4>0
（ 3）无界解,H5≥0,H4? 0,H1 ≥0,H3? 0
（ 4）退化 最优 解,H1=0,H3? 0,H5? 0
（ 5）非最优解,X1进基,X2出基：
H1 ≥0,H3>0,H2>0,5H
2
< H17
OR1 16
习题课：
P79—— 2.11
1、对 2、错，可能有最优解 3、对
4、对 5、错 6、错 7、错在“可行”
8、对 9、错
OR1 17
习题课：
P81—— 2.16
设白天电视广告 X1个，黄金时间电视广告 X2个，
广播广告 X3个，杂志广告 X4个
maxZ=40X1+90X2+50X3+2X4
8X1+15X2+6X3+3X4≤16
30X1+40X2+20X3+X4≥200
8X1+15X2 ≤10
X1 ≥3 X2 ≥2
X3 ≥5 X3 ≤10
X4 ≥5 X4 ≤10 X j≥0 j=1,2,3,4
OR1 18
习题课：
P81—— 2.17
设 A产品生产 X1单位,B产品生产 X2单位，
C产品销毁 X3单位
maxZ=5X1+10X2+3（ 2X2-X3） -1X3
2X1+3X2≤200
3X1+4X2≤240
2X2-X3≤10 X1,X2,X3 ≥0
OR1 19
习题课：
P107—— 3.2
1、对，根据若对偶性
2、对，同上
3、对，同上
4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度
5、对，根据强对偶定理
OR1 20
习题课
P107—— 3.5 注：目标函数为最大化
1、这是线性规划的逆运算
对偶问题最优解,
Y1=4,Y2=2,Y3=0,Y4=4,Y5=0
OR1 21
习题课
P109—— 3.8
1、原问题的最优解,X1=6,X5=10，其余为零 ;对偶问题最优解,Y1=2,Y2=0
C1的变化范围：以 C1代入末表,C1 ≥1
右端项变化范围,xB= B-1b ≥0
b1 ≥-6,?b2≥-10
第三章 对偶问题与灵敏度分析
要求：
了解 LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握 LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容
OR1 2
3.1 对偶问题
3.1.1 对偶问题的提出回顾例题 1,现在 A,B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？
产品 A 产品 B 资源限制劳动力设备原材料
9
4
3
4
5
10
360
200
300
单位利润 70 120
OR1 3
对偶模型
设每个工时收费 Y1元，设备台时费用 Y2
元，原材料附加费 Y3元。
出租收入不低于生产收入：
9y1+4y2+3y3 ≥70
4y1+5y2+10y3 ≥120
目标,ω=360y1+200y2+300y3
出租收入越多越好？至少不低于某数
OR1 4
原问题与对偶问题之比较原问题,对偶问题：
maxZ=70X1+120X2 minω=360y1+200y2+300y3
9X1+4X2≤360 9y1+4y2+3y3 ≥70
4X1+5X2≤200 (3.1) 4y1+5y2+10y3 ≥120 (3.2)
3X1+10X2≤300 y1 ≥0,y2 ≥0,y3 ≥0
X1≥0 X2≥0
OR1 5
3.1.2对偶规则原问题一般模型,对偶问题一般模型：
maxZ=CX min ω=Yb
AX ≤b YA ≥C
X ≥0 Y ≥0
OR1 6
对偶规则
原问题有 m个约束条件，对偶问题有 m个变量
原问题有 n个变量，对偶问题有 n个约束条件
原问题的价值系数对应对偶问题的右端项
原问题的右端项对应对偶问题的价值系数
原问题的技术系数矩阵转置后为对偶问题系数矩阵
原问题的约束条件与对偶问题方向相反
原问题与对偶问题优化方向相反
OR1 7
对偶规则
.
原问题 对偶问题目标函数 max min 目标函数约束条件 ≤
≥
=
≥ 变量
≤
无约束
≥
变量符号 ≤
无约束
≥
≤ 约束条件
=
OR1 8
对偶规则简捷记法
原问题标准则对偶问题标准
原问题不标准则对偶问题不标准
例题 2 max ω=7y1+4y2-2y3
minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3
2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2
x1+ 2x3 -x4 ≤4 -4y1+ 2y2 ≤-6
-x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0
x1,x2,x3 ≥0; 3y1 +y3=1
x4 ≤0;x5无限制 y1 ≥ 0y2 ≤ 0y3 无约束
OR1 9
3.1.3对偶问题的基本性质
对称性：对偶问题的对偶问题是原问题
弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图 )
无界性：原问题无界，对偶问题无可行解
对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为 B，则其对偶问题最优解 Y*=CBB-1
OR1 10
3.1.4对偶最优解的经济解释 — 影子价格
Z= ω=CX=Yb?Z/? b=(Yb)’=Y
Z=Yb= ∑yibi的意义,Y是检验数的反数。在 Y确定的前提下，每增加一个单位的 i种资源，对目标函数的贡献。
结合例题 1讲解影子价格,y1=0:第一种资源过剩
y2=13.6：设备台时最紧张，每增加一个台时,利润增加
13.6元。 y3=5.2…
影子价格所含有的信息,1、资源紧缺状况
2、确定资源转让基价参见,P40 3、取得紧缺资源的代价
OR1 11
3.2灵敏度分析
为什么进行灵敏度分析？
灵敏度分析的两把尺子：
σj =Cj-CBB-1pj≤ 0；? xB= B-1b ≥0
3.2.1 价值系数的灵敏度分析
Cj变化到什么程度可以保持最优基不变？用?
（参看 P96）
例题 4,87.5 ≤ C2 ≤ 233.33； 36 ≤ C1 ≤ 96
OR1 12
灵敏度分析
右端项的灵敏度分析：
bi变化到什么程度可以保持最优基不变？用尺度?
xB= B-1b ≥0
例题 5,1 -3.12 1.16 360
B-1b= 0 0.4 -0.2 200 ≥0
0 -0.12 0.16 b3
b3的变化范围,227.586 ≤ b3 ≤ 400
OR1 13
其它形式的灵敏度分析新产品的分析：
在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。
例题 6：新增一种 C产品，单位利润 110元，使用劳动力 6工时，设备 5台时，原材料 7公斤，问要否调整产品结构？
先算检验数 σj =Cj-CBB-1pj
σ6=C6-YP6=110-（ 0,13.6,5.2）（ 6,5,7） T
= 110-104.4=5.6 大于零，有利可图，将 P6左乘 B-1，
加入到末表之中，继续迭代，直到求得最优解。
OR1 14
3.3用计算机进行灵敏度分析
例题 7 参见 P102
OR1 15
习题课：
P78—— 2.10
（ 1）唯一最优解,H3 ≤ 0,H5≤ 0,H1 ≥0
（ 2）无穷多最优解,H3=0,H1 ≥0,H5? 0,H2>0
或 H5=0,H1 ≥0,H3? 0,H4>0
（ 3）无界解,H5≥0,H4? 0,H1 ≥0,H3? 0
（ 4）退化 最优 解,H1=0,H3? 0,H5? 0
（ 5）非最优解,X1进基,X2出基：
H1 ≥0,H3>0,H2>0,5H
2
< H17
OR1 16
习题课：
P79—— 2.11
1、对 2、错，可能有最优解 3、对
4、对 5、错 6、错 7、错在“可行”
8、对 9、错
OR1 17
习题课：
P81—— 2.16
设白天电视广告 X1个，黄金时间电视广告 X2个，
广播广告 X3个，杂志广告 X4个
maxZ=40X1+90X2+50X3+2X4
8X1+15X2+6X3+3X4≤16
30X1+40X2+20X3+X4≥200
8X1+15X2 ≤10
X1 ≥3 X2 ≥2
X3 ≥5 X3 ≤10
X4 ≥5 X4 ≤10 X j≥0 j=1,2,3,4
OR1 18
习题课：
P81—— 2.17
设 A产品生产 X1单位,B产品生产 X2单位，
C产品销毁 X3单位
maxZ=5X1+10X2+3（ 2X2-X3） -1X3
2X1+3X2≤200
3X1+4X2≤240
2X2-X3≤10 X1,X2,X3 ≥0
OR1 19
习题课：
P107—— 3.2
1、对，根据若对偶性
2、对，同上
3、对，同上
4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度
5、对，根据强对偶定理
OR1 20
习题课
P107—— 3.5 注：目标函数为最大化
1、这是线性规划的逆运算
对偶问题最优解,
Y1=4,Y2=2,Y3=0,Y4=4,Y5=0
OR1 21
习题课
P109—— 3.8
1、原问题的最优解,X1=6,X5=10，其余为零 ;对偶问题最优解,Y1=2,Y2=0
C1的变化范围：以 C1代入末表,C1 ≥1
右端项变化范围,xB= B-1b ≥0
b1 ≥-6,?b2≥-10
