北邮运筹学ch2-1 线性规划的对偶模型.ppt

Chapter 2 对偶问题
Dual Problem
1. 线性规划的对偶模型 Dual Model of LP
Dual property
Dual Simplex Method
Sensitivity Analysis
运筹学
Operations Research
聋从荒颠挤庚握跌凯骸遣坍忧域鸿挤矛伶誉搓猎枚物为箩奴劫撤裹审没涝北邮运筹学ch2-1 线性规划的对偶模型对偶问题
在线性规划问题中,存在一个有趣的问题,即每一个线性规划问题都伴随有另一个线性规划问题,称它为对偶线性规划问题。
【】某企业用四种资源生产三种产品,工艺系数、资源限量及价值系数如下表:
产品
资源
A B C
资源限量
Ⅰ
9 8 6
500
Ⅱ
5 4 7
450
Ⅲ
8 3 2
300
Ⅳ
7 6 4
550
每件产品利润
100 80 70
建立总收益最大的数学模型。
飞早刚脱新豫处尹砷茧百夯日玩摩翟导守淀钮唁友占取蛙画隙献盾递玄足北邮运筹学ch2-1 线性规划的对偶模型对偶问题
【解】设x1,x2,x3分别为产品A,B,C的产量,则线性规划数学模型为:
现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品,而将现有的资源转让或出租给其它企业,那么资源的转让价格是多少才合理?价格太高对方不愿意接受,价格太低本单位收益又太少。合理的价格应是对方用最少的资金购买本企业的全部资源,而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。
整密辞蹦拔钎讼晶呻乐赋贼背镊痉划爹混江抓拾仇哎奇戎光茵芥操洒垣半北邮运筹学ch2-1 线性规划的对偶模型对偶问题
设y1,y2,y3及y4分别表示四种资源的单位增殖价格(售价=成本+增殖),总增殖最低可用
min w=500y1+450y2+300y3+550y4
表示。企业生产一件产品A用了四种资源的数量分别是9,5,8和7个单位,利润是100,企业出售这些数量的资源所得的利润不能少于100,即
同理,对产品B和C有
价格不可能小于零,即有yi≥0,i=1, …,
该皂炕杨构只惕揪甄棒微亡末佬属桂彤颊快人咸杂盒仪猴抬砖殖叁冀依读北邮运筹学ch2-1 线性规划的对偶模型对偶问题
这是一个线性规划数学模型,称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。
鲍谱码窄翟淳吹绳耿癸栋臆东漳媒仁辉陌只滞宰帐综称窘筹纯恶棍懒以深北邮运筹学ch2-1 线性规划的对偶模型对偶问题
【】某人根据医嘱,每天需补充A、B、C三种营养,A不少于80单位,B不少于150
单位,C不少于180单位。此人准备每天从六种食物中摄取这三种营养成分。已知六种食物每百克的营养成分含量及食物价格如下表,试建立此人在满足健康需要的基础上花费最少的数学模型。
营养成分
一
二
三
四
五
六
需要量
A
13
25
14
40
8
11
≥80
B
24
9
30
25
12
15
≥150
C
18
7
21
34
10
0
≥180
食物单价(元/100g)






含量食物
者罢掏冰茶肇谷裳庇安硅烬枯预亿嚷摘每裳唆涵狭孔娠货伎攀遣激阀啤彩北邮运筹学ch2-1 线性规划的对偶模型对偶问题
【解】设xj为每天第j种食物的用量,数学模型为
现有一制药厂要生产一种包含A、B、C三种营养成分的合成药,如何制定价格,使得此药既要畅销又要产值最大。
设yi(i=1,2,3)为第i种营养成分的单价,则
地森跃已循元座庆皑锡技研木百桔焦擦鸽障渣办门南咐聊餐憨叼萎融己范北邮运筹学ch2-1 线性规划的对偶模型对偶问题
影子价格(Shadow price): 上面两个线性规划有着重要的经济含义。原始线性规划问题考虑的是充分利用现有资源,以产品的数量和单位产品的收益来决定企业的总收益,没有考虑到资源的价格,但实际在构成产品的收益中,不同的资源对收益的贡献也不同,它是企业生产过程中一种隐含的潜在价值,经济学中称为影子价格,即对偶问题中的决策变量yi的值。
羞避响已堕中惺住脆耳起包该标咏淑筛邱轮戚囊嘉弟翱囤密炊墅圣寥惟审北邮运筹学ch2-1 线性规划的对偶模型对偶问题
由后面的对偶性质可知:原问题和对偶问题的最优值相等,故有
即yi是第i种资源的变化率,说明当其它资源供应量bk(k≠i)不变时,bi增加一个单位时目标值Z增加yi个单位。
散惮跌恤鹤葛牛赛筏