第三章 对偶问题与灵敏度分析.ppt

第三章对偶问题与灵敏度分析
要求:
了解LP对偶问题的实际背景
了解对偶问题的建立规则与基本性质
掌握对偶最优解的计算及其经济解释
掌握LP的灵敏度分析
理解计算机输出的影子价格与灵敏度分析的内容
OR1
1
对偶问题
对偶问题的提出
回顾例题1: 现在A、B两产品销路不畅,可以将所有资源出租或外卖,现在要谈判,我们的价格底线是什么?
产品A
产品B
资源限制
劳动力
设备
原材料
9
4
3
4
5
10
360
200
300
单位利润
70
120
OR1
2
对偶模型
设每个工时收费Y1元,设备台时费用Y2元,原材料附加费Y3元。
出租收入不低于生产收入:
9y1+4y2+3y3 ≥70
4y1+5y2+10y3 ≥120
目标:ω=360y1+200y2+300y3
出租收入越多越好?至少不低于某数
OR1
3
原问题与对偶问题之比较
原问题: 对偶问题:
maxZ=70X1+120X2 minω=360y1+200y2+300y3
9X1+4X2≤360 9y1+4y2+3y3 ≥70
4X1+5X2 ≤200 () 4y1+5y2+10y3 ≥120 ()
3X1+10X2 ≤300 y1 ≥0, y2 ≥0, y3 ≥0
X1≥0 X2≥0
OR1
4

原问题一般模型: 对偶问题一般模型:
maxZ=CX min ω=Yb
AX ≤b YA ≥C
X ≥0 Y ≥0
OR1
5
对偶规则
原问题有m个约束条件,对偶问题有m个变量
原问题有n个变量,对偶问题有n个约束条件
原问题的价值系数对应对偶问题的右端项
原问题的右端项对应对偶问题的价值系数
原问题的技术系数矩阵转置后为对偶问题系数矩阵
原问题的约束条件与对偶问题方向相反
原问题与对偶问题优化方向相反
OR1
6
对偶规则
.
原问题
对偶问题
目标函数 max
min 目标函数
约束条件≤
≥
=
≥变量
≤
无约束
≥
变量符号≤
无约束
≥
≤约束条件
=
OR1
7
对偶规则简捷记法
原问题标准则对偶问题标准
原问题不标准则对偶问题不标准
例题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
8

对称性:对偶问题的对偶问题是原问题
弱对偶性:极大化原问题的任一可行解的目标函数值,不大于其对偶问题任意可行解的目标函数值(鞍型图)
无界性:原问题无界,对偶问题无可行解
对偶定理:若一个问题有最优解,则另一问题也有最优解,且目标函数值相等。若原问题最优基为B,则其对偶问题最优解Y*=CBB-1
OR1
9
—影子价格
Z= ω=CX=Yb Z/  b=(Yb)’=Y
Z=Yb= ∑yibi的意义:Y是检验数的反数。在Y确定的前提下,每增加一个单位的i种资源,对目标函数的贡献。
结合例题1讲解影子价格:y1=0:第一种资源过剩
y2=:设备台时最紧张,每增加一个台时, 。y3=…
影子价格所含有的信息: 1、资源紧缺状况
2、确定资源转让基价
参见:P40 3、取得紧缺资源的代价
OR1
10