运筹学灵敏度分析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《运筹学灵敏度分析课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 灵敏度 分析 课件
- 资源描述:
-
1、第六节 线性规划应用举例 例1:某工厂生产A,B两种产品,均需经过两道工序, 每种产品需各工序加工的时间及各工序可提供的时间如下表。生产产品B同时生产出副产品C,每生产一吨产品B可同时得到2吨产品C,无需费用。出售一顿A盈利400元,B盈利1000元,C盈利300元,而生产要报废的C每吨损失200元,经预测C最大销量为5吨,列模型决定A,B产量,使工厂总盈利最大。 A B C工时限量一工序二工序 2 3 3 4 12 24盈利损失400 1000 300 -200可控变量:设X1为A产量,X2为B产量,X3为C销售量,X4为C报废量目标为总盈利,约束为资源限制等 maxZ=4X1+10X2+3
2、X3-2X4 2X1+3X212 3X1+4X224 X3+X4=2X2 X35 X1,X2,X3,X40 例2:某工厂生产的一种产品由四个零件一和三个零件二组成,这两种零件要用两种原材料,由于三个车间拥有的设备和工艺不同,每个工班原材料耗用量和零件产量不同,问三个车间应各开多少工班,才能使该产品的配套数达到最大。 分析:可控变量是什么,目标和约束是什么每班用料数(公斤)每班产量(件数)A材料B材料零件一零件二一车间二车间三车间853698768594资源限量300500可控变量:三个车间工班数,目标:产品配套数,约束资源约束 目标为两目标取小,要转化为一个目标时的方法。Z=min( (7x1
3、+6x2+8x3)/4 ,(5x1+9x2+4x3)/3)可令y= min( (7x1+6x2+8x3)/4 ,(5x1+9x2+4x3)/3)则上目标转化为maxZ=y (7x1+6x2+8x3)/4y(5x1+9x2+4x3)/3y maxZ=y (7x1+6x2+8x3)/4y (5x1+9x2+4x3)/3y 8x1+5x2+3x3300 6x1+9x2+8x3500 x1,x2,x3,y0 解 先看有多少种裁料方案,再进行组合和选择。方案: 例3 合理利用线材问题 现要做一百套钢管, 每套要长为2.9m、2.1m和1.5m的钢管各一根。已知原料长7.4m,问应如何下料,使用的原料最省
4、。 2 .9 m 2 .1 m 1 .5 m 2 0 1 1 2 0 1 1 1 1 0 3 0 3 0 0 2 2 0 1 3 0 0 4 料料 头头 0 .1 0 .3 0 .9 0 1 .1 0 .2 0 .8 1 .4 设用方案设用方案,分别裁原料分别裁原料钢管钢管x1,x2, ,x8根根, 则:则:Min z= x1+ x2+ x3+x4+ x5+x6+x7+x8 2x1+ x2+x3 + x4 100 2x2+x3+ 3x5 +2x6+ x7 100 x1+ x3 +3x4 +2x6+3x7+4x8 100 x1, x2, x3, x4, x5 ,x6, x7, x8 0 例例4
5、4 某工厂要用三种原材料某工厂要用三种原材料C,P,HC,P,H混合调配出混合调配出三种不同规格的产品三种不同规格的产品A,B,DA,B,D。已知产品的规格要。已知产品的规格要求、单价和原料的供应量、单价如下表。该厂应求、单价和原料的供应量、单价如下表。该厂应如何安排生产,能使利润最大?如何安排生产,能使利润最大? 产产品品名名规规格格要要求求单单价价A原原料料 C 不不少少于于 50%原原料料 P 不不超超过过 25%50 元/KGB原原料料 C 不不少少于于 25%原原料料 P 不不超超过过 50%35 元/KGD不不限限25 元/KG原原料料名名每每天天最最多多供供应应量量单单价价CPH
6、100KG100KG60KG65 元/KG25 元/KG35 元/KG根据产品要求有:根据产品要求有: AC0.5A, AP0.25A BC0.25B, BP0.5B AC+AP+AH=A BC+BP+BH=B根据原料供应量有:根据原料供应量有: AC+BC+DC100 AP+BP+DP100 AH+BH+DH60设设AC,AP,DH分别为分别为x1,x2,x9,有,有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+ x2+ x3) x2
7、0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x4+ x5+ x6) x1+ x4+ x7100 x2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9解:记产品解:记产品A,B,DA,B,D中中C,P,HC,P,H的含量分的含量分别为别为AC,AP,AH,BC,BP,BH,DC,DP,DH。 例例5 连续投资问题。某单位有资金连续投资问题。某单位有资金10万元,在万元,在今后今后5年内可考虑下列投资项目,已知:年内可考虑下列投资项目,已知: 项目项目A:从第:从第1到第到第4年每年初可投资,并于次年每年
8、初可投资,并于次年末回收本利年末回收本利115%; 项目项目B:第:第3年初需要投资,到第年初需要投资,到第5年末回收本年末回收本利利125%,但最大投资额不超过,但最大投资额不超过4万元;万元; 项目项目C:第:第2年初需要投资,到第年初需要投资,到第5年末能回收年末能回收本利本利140%,但最大投资额不超过,但最大投资额不超过3万元;万元; 项目项目D:5年内每年初可购买公債,当年末回年内每年初可购买公債,当年末回收本利收本利106%。 问它应该如何安排每年的投资,使到问它应该如何安排每年的投资,使到5年末年末拥有的资金最多?拥有的资金最多? 年份年份项目项目 一一 二二 三三 四四 五五
9、 A X1AX2AX3AX4A B X3B CX2C D X1DX2DX3DX4DX5D x2A+x2C+x2D=1.06x1D解:每年的投资额解:每年的投资额应不超过手中的资应不超过手中的资金。由于项目金。由于项目D每每年都可投资,且当年都可投资,且当年末就可收回。所年末就可收回。所以该单位每年必然以该单位每年必然把资金全部投出去,把资金全部投出去,即投资额等于手中即投资额等于手中的资金数。的资金数。 设第设第i年投资各项目的资金年投资各项目的资金为为xiA,xib,xiC,xiD 。数学模型为:。数学模型为: x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2Dx4
10、A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D第二章第二章 线性规划的对偶理论线性规划的对偶理论与灵敏度分析与灵敏度分析改进单纯型法对偶问题 对偶理论 目标函数值之间的关系 最优解之间的互补松弛关系 对偶单纯形法对偶的经济解释灵敏度分析DUAL第一节 改进单纯型法 需要求的几个重要指标需要求的几个重要指标 ,不需要完全的矩阵,不需要完全的矩阵变换就可求得。变换就可求得。需要求的:基可行解,需要求的:基可行解,非基变量,非基变量,XBB-1b B-1B-1P
11、k初始表为单位阵(初始基)确定主元素 -Y=-CBB-1 k 求求,确定换入变确定换入变量量xk ,计算计算B-1Pk ,计计算算,确定主元素确定主元素,对简化单纯型表作对简化单纯型表作旋转变换旋转变换简化单纯形表简化单纯形表Cj CCB XB B-1b X b A B-1b B-1ACCB B-1A Cj CB CS CN1CB XB B-1b XB XS XN1 CS XS b B E N1 CB XB B-1b E B-1 B-1N1 0 CSCB B-1 CN1CB B-1N1初始表初始表以以B为基的为基的单纯形表单纯形表当XS为松弛变量时CS=0,松弛变量检验数为Cj CB CNCB
12、 XB B-1b XB XN b B N B-1b E B-1N 0 CNCB B-1N c1cn00CBXBx1xnxn+1xn+mi0 xn+1b1a11a1n1010 xn+2b2a21a2n0020 xn+mbmam1amn01m-zfc1cn00c1 cn cn+1 cn+m CB XB x1 xn xn+1 xn+m i ci1 xi1 b1 a11 a1n a1n+1 a1n+m 1 ci2 xi2 b2 a21 a2n a2n+1 a2n+m 2 Cim xim bm am1 amn amn+1 amn+m m -z f 1 n n+1 n+m 最优单纯形表最优单纯形表B-1c
13、B B -1EO 第二节 对偶问题 产品产品资源资源 I II 总总量量原料原料工时工时 2 3 4 6 100 120利润利润 6 4原问题:确定获利最大的生产方案原问题:确定获利最大的生产方案对偶问题:确定资源最低可接受对偶问题:确定资源最低可接受 出让价格出让价格建立两问题的模型,对比其最优解,最优目标函数建立两问题的模型,对比其最优解,最优目标函数值的关系。值的关系。 两规划最优目标函数值相等 为Z=CB B-1b 此时最优解XB= B-1b, Y= CB B-1(为原规划松弛变量在最终表 中的检验数,即单纯形乘子)原始问题max z=C Xs.t.AXbX 0对偶问题min =Ybs
14、.t. YACY 0maxbAC CTATbTminmnmn 0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn12121112222111、原始问题是利润最大化的生产计划问题单位产品的利润(元/件)产品产量(件)总利润(元)资源限量(吨)单位产品消耗的资源(吨/件)剩余的资源(吨)消耗的资源(吨)2、对偶问题0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacy
15、yayayat sybybybw资源限量(吨)资源价格(元/吨)总利润(元)对偶问题是资源定价问题,对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格(Shadow Price)原始和对偶问题都取得最优解时,最大利润 max z=min y对偶问题是资源定价问题,对偶问题的最优解对偶问题是资源定价问题,对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格(影子价格(Shadow Price)影子价格为当影子价格为当bi有单位增量,有单位增量,若原最终优基不变若原最终优基不变,总收益总收益Z的变化,也可以说的变化,也可以说yi是对第是对第i种资源的一种种资源的一种价格估
16、计,由于影子价格是指资源增加时对最优收价格估计,由于影子价格是指资源增加时对最优收益的贡献,所以又称它为资源的机会成本或者边际益的贡献,所以又称它为资源的机会成本或者边际产出产出当市场价格低于影子价格时,企业应该买进资源用当市场价格低于影子价格时,企业应该买进资源用于扩大生产,高于影子价格时,企业应该将已有资于扩大生产,高于影子价格时,企业应该将已有资源卖掉。源卖掉。影子价格的计算影子价格的计算 例子:两种产品由三种原料混合而成,A包括原料一60%,原料二40%,B包括原料一50%,原料二10%,原料三40%,原料一、二、三限量为11250,4000,6000(吨).试建立模型,求解。A每吨2
17、5美元,B每吨10美元maxZ=25x1+10 x20.6x1+0.5x2120000.4x1+0.1x240000.4x26000 x1,x20原料原料2的约束的约束原料原料1的约束的约束原料原料3的约束的约束 当市场价格低于影子价格时,企业应该买进资源用于扩大生产,高于影子价格时,企业应该将已有资源卖掉。 一个不起作用约束的影响价格总为0,一个起作用约束的影子价格在资源在一定范围内变化时是不变的。这个变化范围就是关于资源限量bi的灵敏度不起作用的约束是对最优解而言,该约束的松弛变量 的值不为0起作用的约束是是对最优解而言,该约束的松弛变量 的值为0 x2=0 x1=0 x3=0 x4=0O
展开阅读全文