- 1、下载文档前请自行甄别文档内容的完整性,平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益,请联系客服反馈,我们会尽快为您处理(人工客服工作时间:9:00-18:30)。
sfsf
16
sfsf
17
例1:写出下面线性规划的对偶规划 min S x1 3x3
s.t. 2 x1 3x2 6 x3 7 16x 2 x 2 x 1 1 3 4 7 x 7 x 6 x x 0 1 2 3 4 x1 , x2 , x3 , x4 0
第三 讲 线性规划:灵敏度分析与对偶
李勇建 博士
sfsf
1
主要内容
线性规划的对偶问题 线性规划的灵敏度分析问题
sfsf
2
线性规划的对偶问题
•对偶问题的来源 •对偶问题的应用和经济解释
•对偶问题的转化
sfsf 3
对偶问题
原问题
max z 50x1 100x2
约束:
x1 x2 300 2 x1 x2 400 x2 250
sfsf
10
资源定价的决策方案
例:某厂生产甲乙产品,(1)如何安排每周的利润为最大? 甲 乙 资源成本 资源拥有量
原材料 (kg) 设备 (工时) 电力 (度)
销售价格(元)
9 4 3
390
4 5 10
352
20 50 1
360 200 300
(2)如果企业可以不生产,那资源出让如何定价?
1、最优生产决策
x1 0, x2 0
最优解:x1=50, x2=250;Z*=27500
sfsf 4
如果把三种资源分别以价格 y1 , y 2 , y3 出租或买出, 那么出 让相对于生产一单位第 j 种产品的资源消耗的价值应不低 于第 j 种产品的单位利润价值 max z 50x 100x
1
因此有
sfsf 9
影子价值的内涵
影子价格不是资源的实际价格,反映了资源配置结构,
其它数据固定,某资源增加一单位导致目标函数的增量。
对资源i总存量的评估:购进 or 出让 对资源i当前分配量的评估:增加 or 减少
第一,影子利润说明增加哪种资源对经济效益最有利 第二,影子价格告知以怎样的代价去取得紧缺资源 第三,影子价格是机会成本,提示资源出租/转让的基价 第四,利用影子价格分析新品的资源效果:定价决策 第五,利用影子价格分析现有产品价格变动的资源紧性 第六,可以帮助分析工艺改变后对资源节约的收益 第七,可以预知哪些资源是稀缺资源而哪些资源不稀缺
* y* 0, y 0 4 5
sfsf
12
阅读和自学:
参考书 P60-61,第3.3.4节
sfsf
13
想一想
产品的机会成本是什么:
j 表示减少一件产品 j 所节省的资源可以增加的 利润. 产品的差额成本是什么:
sfsf
14
对偶问题的经济解释
如果 则用这些资源来生产这种产品更为有利可图. 如果
sfsf
7
举例
原问题
Max 50x1+30x2 S.t. 4x1+3x2120 2x1+x250 x1,x20
对偶问题
Min 120y1+50y2 S.t. 4y1+2y250 3y1+y2 30 y1,y20
sfsf
8
对偶规划的应用
一般来说,线性规划问题是确定资源的最优分 配方案;对偶问题则是确定对资源的恰当估价, 以确定资源的最有效利用; 可借助资源的影子价格确定一些内部结算价格, 以便控制有限资源的使用和考核下属企业经营 的好坏; 对于一些紧缺资源,可以借助于影子价格机制 规定上交的利润额,控制一些经济效益低的公 司自觉地节约使用紧缺资源。
f min 27500 z *
sfsf 6
影子价格在原问题当中是什么意思? 设原问题的松弛变量为 s1 , s 2 , s3 , (对应资源的剩余量) ,那么原问题的 最优解为 ( x1 , x2 , sy s22,,y s3 ) = (50, 250, 50, 0, 50)。 1, 1,y 松弛变量不为 0,即有剩余的资源,其影子价格为 0。 没有剩余、比较紧缺的资源其影子价格,代表了其紧缺程度。 比如,当 x1 x2 300改为 x1 x2 301时, 最优解为 x1 51, x2 250 , 利润增加 50 元, 资源增加一个单位, 利润增加 50 元, 称为资源 1 的影子 价格。
max Z 7 x1 12x2 9 x1 4 x2 360 4 x 5 x 200 1 2 s.t. 3x1 10x2 300 x1 , x2 0
X * (20, 24,84,0,0)T
sfsf
11
资源定价的决策方案
2、资源获利决策
如果决策者考虑自己不生产甲乙两种产品,而把原拟用于生产 这两种产品的原材料、设备工时、电量资源全部出售给外单位, 或者做代加工,则应如何确定这三种资源的价格。 设原材料的单位出让获利为y1,设备工时的单位出让获利为y2, 电量的单位出让获利为y3 。 出让决策的线性规划模型:
对偶问题
决策变量:yi 收买该公司一单位 i 种资源时付给的价格 目标函数: 约束:
min f 300y1 400y2 250y3
y1 2 y2 50 y1 y2 y3 100
.
y1 , y2 , y3 0
此极小问题称为原问题的对偶问题,解是 y1 50, y2 0, y3 50 分别称为原料1,2,3的影子价格或对偶价格.
y1 2 y2 50 y1 y2 y3 100 y1 , y2 , y3 0
x1 x2 300 y2: 2 x1 x2 400 x2 250 y3 :
y1 :
2
但是买方会把价格压到最低 :
min f 300y1 400y2 250y3
sfsf 5
min w 360 y1 200 y2 300 y3 9 y1 4 y2 3 y3 7 s.t. 4 y1 5 y2 10 y3 12 y , y , y 0 1 2 3
* * y1 0 y* 1.36 y 0.52 2 3
Z * 428
表明已经在其他地方以更为有利可图的方式使用这些资源,没有必 要生产产品j . 其经济解释是:在利润最大化的生产计划中 (1)边际利润大于0的资源没有剩余; (2)有剩余的资源边际利润等于0; (3)安排生产的产品机会成本小于等于利润; (4)机会成本大于利润的产品不安排生产.
sfsf 15
对偶的一般形式