对偶理论和影子价格.ppt

1
第六节对偶理论与影子价格
对偶问题的提出
对偶问题的形式
对偶问题的基本性质
影子价格
2
对偶问题的提出
例1:某工厂拥有A、B、C三种类型的设备,生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:问题:工厂应如何安排生产可获得最大的总利润?
产品甲
产品乙
设备能力
设备A
3
2
65
设备B
2
1
40
设备C
0
3
75
利润
1500
2500
现在从另一个角度来讨论该问题:
如果工厂考虑不安排生产,而准备把所有设备出租(或用于外协加工),工厂收取租金(或加工费)。试问:设备 A、B、C 每工时各如何收费(租金或加工费)才最有竞争力?
工厂为了获得最大利润,在为设备定价时,应保证生产某产品的设备工时所收取的费用不低于生产该产品的利润;同时,为了提高竞争力,应该使定价尽可能低。
目标函数
设x1,x2分别为生产甲乙两种产品的件数
约束条件
设 y1 ,y2 ,y3 分别为每工时设备 A、B、C 的收费。
目标函数
约束条件
4
解: 可以建立如下的线性规划模型:

目标函数 
约束条件 


化为标准型,利用单纯形法进行求解。
最优解X=(5, 25, 0, 5, 0),
最优值(利润)为70000。
5
解: 设 y1 ,y2 ,y3 分别为每工时设备 A、B、C 的收费。可以建立以下线性规划模型:
化为标准型,利用单纯形法进行求解。
最优解Y=(500, 0, 500, 0, 0)
最优值(收费)为70000。
6
原问题
对偶问题
7
原问题
对偶问题
目标函数
Max
Min
约束条件
≤
≥
系数矩阵
A
AT
资源常数
b
c
目标系数
c
b
2个变量
2个约束
3个约束
3个变量
解
检验数
检验数
解
可以看到,这两个问题关系密切,用同样的原始数据:
线性规划有一个有趣的特性,就是对于任何一个求极大的线性规划问题都存在一个与其匹配的求极小的线性规划问题,并且这一对线性规划问题的解之间还存在着密切的关系。线性规划的这个特性称为对偶性。 对这两个线性规划问题,一般称前者为原问题,后者是前者的对偶问题
8
对偶问题的形式
9
如果线性规划问题的变量均具有非负约束,其约束条件当目标函数求极大值时均取“≤”,当目标函数求极小值时均取“≥”,则称具有对称形式。
对称形式下原问题和对偶问题的形式:
(LP)
“Max——≤”
.
(DP)
“Min——≥”
.
一对对称形式的对偶规划之间具有下面的对应关系: “极大”,约束为“小于等于”的不等式,则它的对偶模型为目标求“极小”,约束是“大于等于”的不等式。即“max,≤”和“min,≥”相对应。 :一个模型中为A,则另一个模型中为AT。一个模型是m个约束,n个变量,则它的对偶模型为n个约束,m个变量 、C的位置看:在两个规划模型中,b和C的位置对换
10