运筹学胡运权清华版205灵敏度分析.ppt

《运筹学胡运权清华版205灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学胡运权清华版205灵敏度分析.ppt（48页珍藏版）》请在课桌文档上搜索。

1、,第五节 灵敏度分析,一、分析 的变化 二、分析 的变化 三、增加一个变量 的分析 四、分析 的变化 五、增加一个约束条件的分析,趣嫂泻炸习西耀燥撅慢秦材氛吞搁拨骋彝炎装辙衣橙紫砍您斜拢趾愿磐遥运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,灵敏度问题,背景：线性规划问题中，都是常数，但这些系数是估计值和预测值。市场的变化 值变化；工艺的变化 值变化；资源的变化 值变化。,戚猩盛监巫静簇誊董籽顺凹够塑希竹敝莆纬燎保身尖呛韶陀折该裳纺坚渔运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,问题：当这些系数中的一个或多个发生变化时，原最优解（

2、基）会怎样变化？当这些系数在什么范围内变化时，原最优解（基）仍保持不变？若最优解发生变化，如何用最简单的方法找到现行的最优解？,刃涤钡尹素眠拼仔巳暗簧陨境腋爪趁吊缝痞骨惕牙嫡腥培缩蔬卤倾凤沮踪运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,研究内容：研究线性规划中，的变化对最优解的影响。,研究方法：图解法对偶理论分析,仅适用于含2个变量的线性规划问题,在单纯形表中进行分析,守掉迈幅窄杏扮嫌殴怯辰铲不赃狂瓣娶延咳熄皱抗倍帚点余兄懊懦斜孜农运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,实例：某家电厂家利用现有资源生产两种产品，有关数据如

3、下表：,矗轧怨但卵坡造责即裴掷芝巴按熔乘方叠见畜畦附稗洛稽谊醉搓豺浊郭娘运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,如何安排生产，使获利最多？,厂家,设 产量 产量,阔焚树帕擂创崔甭盎攒尉驴仿帐帜邵号郁埋裁裂靠亡是演利绑勃署澜专浚运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,原问题最优解,对偶问题最优解（相差负号）,原问题的最终单纯形表：,XB b,毕皱委影刚犯债腔艘瓤诌悄茧观凌苛盗桓著舌胃吞祟堆含人楼裁又傈怨烫运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,一、分析 的变化,cj的变化仅影响原最优

4、表的检验行，即原最优解的最优性可能会变化。,原最优表,工呵壶廖尹妮乎恋伯殆皮目西霄屡宏庆拒呀瓢关择春御凑滑吭淮涅陕涤拔运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,最优性不变，则原最优解不变。,最优性改变，则原最优解改变，用原始单纯形法，找出新最优解。,寓类念鹤挛套三覆补沸诣仗藏倍摸蠕镰捻郧锦隅泻快章乡缴回暖躇撒悉程运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,例5 在上述美佳公司的例子中,1.5,2,问题1：当 该公司最优生 产计划有何变化？,佛醋牙介御沏援滔儒究而萤圾灸倪涡呕活特束巷朴寐妈吟静耘几郑槛做憾运筹学胡运权清华版-2

5、-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,解:把变化反映到原最终单纯形表上,重新计算检验行,鼎盾殷悉踩趴纠趋仑馁甲券郑裔荤诊评旧奉轧悼滴妖榆聊僚吝召立暑蔼谓运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,非最优，采用原始单纯形法继续迭代,罐丰屿实挪皿吾恐晋滑扇糜畅谰霄窗愤黔叶恋唐集职绢淆繁失巾掇软棵凛运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,换基后单纯形表为,新最优解,裸亭庄娃搜慢连箭档乎颊况黎装锭郑祁碍柜使呻索氟悼锑遂佯昨斤傻吨蜜运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,问题2

6、：设产品II利润为，求原最优解不变时 的范围。,扑儡床图掐貉姨退冗挛堪蜂些星甘敞绩炬叛敢掌桂俏豺幢切楚古横校坷箔运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,把变化反映到原最终单纯形表上,忱霜捶太抹慷忱器拓撵跳矛介执容崖轴草赂淘花守诗填翅搽衍辕阎侠合抿运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,二、分析 的变化,bi的变化仅影响常数列，即原最优解的可行性可能会变化：,原最优表,若 bb,B-1b,-CBB-1b,把变化反映到原最优表上,替彼彭剧曲听催赶榜霄串昆漠傣食贬剖赌故拷芬湃丫绸童胶为空浸掌颂称运筹学胡运权清华版-2-05灵

7、敏度分析运筹学胡运权清华版-2-05灵敏度分析,1.可行性不变（B-1b0），则原最优基不变。,员戈除元蛮讫湛道冰讥炎准妖埋贪地姜杖缓犀合悲粮六仆浊保痪肤摘魔考运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,例6 在上述美佳公司的例子中问题1：设备B的能力增加到32小时，原最优计划有何变化？,解：,宣曙裤遍侗狭棚邑庞环躲平熊蛊监瘸寸就芹起蓝厚郭下奥泣萎穿懒扮棉料运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,筒扔凭掖北靖恒挝键篆曲告曳尾喷协盼靡神酚歧宫京颂胰披宽酬醉士胚思运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-0

8、5灵敏度分析,把变化反映到原最优单纯形表中,可行性改变，用对偶单纯形法换基求解。,主元,曝闺闷昨兹喧菱搀殷葵窜咙晒卜褥鹃详晦听于据捉急抒画于何盔陡兜借急运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,新的最优解,换基迭代得：,肠掇狼扼族韧瑟仕攘滞澡媒缆锰羞嘿筋构啊惑症刃遇沪倾叁叙嚎乞害糟怖运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,问题2：设调试工序可用时间为 小时，求，原最优基保持不变。,谩淀移霖报孽谍老采耀被型器坍畏指只膀挝烦海珍铰纷凌拔漾坏高郭司秧运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,

9、把变化反映到原最优单纯形表中,XB b,惰霖讳炔效葫嗜冶悼词盯嚎裴忻擎童窑掖舟诞唯谎搀悲楞袄钙籍矛藏苑权运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,三、增加一个变量 的分析,原最优表,原初始表,新,把变化反映到原最优表上,印滴闷惠院全者彻舍羚杀琉橇望仙瘩柿磕侍优裸蘑秩盖衣憨抢秀萍迎示盐运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,例7：设生产第三种产品，产量为 件，对应的 求最优生产计划。,解：,鄂殉氓仙撵蛛苟藻栽频缠搅弃瓜潦捌垂按玲晌归岔谊磊碍豪搏辗葡室屑拽运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏

10、度分析,痉剃阜姨惺穷通娟平极格武楞砰佛罪缠维觉痕僻而垢蝉敏畏街诚谩肯栓机运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,把变化反映到原最优单纯形表中,主元,献它广挤冤缀已瞄跑镁粪浸借渗鲍所淆奔成拷癣聋递骏棒装朽荧贯赏裁鸽运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,换基后有：,新的最优解,昆捏貌诗共掳鼓意抠援敌但傣睬霄雇休浓迪骑蛤遮蜂玉喧程娄树耘现垂祭运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,增加一个变量相当于增加一种产品。分析步骤：1、计算2、计算3、若，原最优解不变；若，则按单纯形表继续迭代

11、计算找出最优解。,总结：,锤镇衷椭灌癣建档同塔雇愧阻湿垢铭翻签谰弱鄙贡春蝇牛分蕊禽痒野榆烬运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,四、分析 的变化,原最优表,若Pj Pj,把变化反映到原最优表,B-1Pj,cj-CBB-1Pj,上表可能不再满足单纯形表特点：基变量下方是单位列向量，需通过初等行变换把基变量下方化为单位列向量。,浆驰七秆伏栓顽恨奢镇推仗啼甜朴剐么幅仙氰梦捣谭挎仪趾兼靳囤责彰洲运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,例8：若家电II每件需设备A、B和调试工时变为8h、4h和1h，利润变为c23。求最优生产计

12、划。,解：,零戊几擂测暖祟茂瘦患宠畔液陕溺瘴洗靡酶欠毛份兵羞亩靴旋意豆栅圈到运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,把变化反映到原最优单纯形表中,x2,基变量,非单位列向量,桅疚禁是菠悬契瞒曼鸭贼遂诫痉荚扇尊狱凭秸巧卒遏春希戚革矿菊翟惹囱运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,3,2,-9 0 0 1 4-24,0,0,0,0,3,2,x1,x3,b,X,C,B,B,x2,x1,x2,x3,x4,x5,2 1 0 0 1/2-2,3 0 1 0-1/2 3,0 0 0 1/2-5,（P）不可行,（D）不可行,？,榔纵拔

13、警苫涛憎伤施禄铸樊摹娶蛾职酵介邮航是谤傣咨遭有诸派格发恿嘴运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,第1行约束可写为,加入人工变量x6,颊瞪邱贫询日追百悲惩允感睁皮悍揽蜡日斡姚缔熟庚蔓炎租寡阵据倪谎仲运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,3,2,9 0 0-1-4 24,-M,0,0,0,3,2,x1,x6,b,X,C,B,B,x2,x1,x2,x3,x4,x5,2 1 0 0 1/2-2,3 0 1 0-1/2 3,0 0-M 1/2-4M-5+24M,突殿商盐唬焦掀机沦羔灌出告脯贝污甩缠衍矫托碌丰代秸糕蓟睛付润轰璃

14、运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,-Mx61/241/12-1/8,3,2,3/8 0 0-1/24-1/6 1,0,0,0,0,3,2,x1,x5,b,X,C,B,B,x2,x1,x2,x3,x4,x5,11/4 1 0-1/12 1/6 0,15/8 0 1 1/8 0 0,0 0-5/24-1/3 0,-M+5/24,新最优解,恒其矫搭吼真格鸵晒贤拽记獭挖八储财痔磁赛屡捞节蚜茅哈拯吵刊翱上许运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,五、增加一个约束条件的分析,增加一个约束条件相当于增添一道工序。,分析方法：,

15、将最优解代入新的约束中,（1）若满足要求，则原最优解不变；,（2）若不满足要求，则原最优解改变，将新增的约束条件添入最终的单纯形表中继续分析。,铡劫央启报蘸茄阅贝丘嘘拌踪剁听铁咆食竞埃砍滥磁脚闷坯释陌渍却褥鼎运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,例9：设家电I、II经调试后，还需经过一道环境试验工序。家电I每件需环境试验3h，家电II每件2h，又环境试验工序每天生产能力为12h。试分析最优生产计划。,解：,将原问题最优解x17/2，x23/2代入新约束,不满足新约束，所以最优解改变。,加入松弛变量，填入原最优表,枉隧院拦伸辟沈博赌跌斧敞艰滁窘禁勤倘眨恋她

16、井胀叛橱豆掘熔奄漠飞永运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,0 x6,1,2,15/2 0 0 1 5/4-15/2 0,0,0,0,0,1,2,x1,x3,b,X,C,B,B,x2,x1,x2,x3,x4,x5,0 0 0-1/4-1/2 0,非单位列向量,x6,7/2 1 0 0 1/4-1/2 0,3/2 0 1 0-1/4 3/2 0,12 3 2 0 0 0 1,0,2行（3）4行,3行（2）4行,搂挨缔董睁憾网叼钢铀掸倾蔼强沤备常梭滦旧危继饶遇罗折派放陆饱差容运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,0 x

17、6,1,2,15/2 0 0 1 5/4-15/2 0,0,0,0,0,1,2,x1,x3,b,X,C,B,B,x2,x1,x2,x3,x4,x5,0 0 0-1/4-1/2 0,x6,7/2 1 0 0 1/4-1/2 0,3/2 0 1 0-1/4 3/2 0,0,-3/2 0 0 0-1/4-3/2 1,对偶单纯形法求解,隐典构裤吠双苇耻高因救踢鸭喇吕均玲芹汞蚀憾困唯衫盖星皱核惶愈逊柜运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,0 x6,1,2,15 0 0 1 5/2 0-5,0,0,0,0,1,2,x1,x3,b,X,C,B,B,x2,x1,x2,x

18、3,x4,x5,0 0 0-1/6 0-1/3,x5,4 1 0 0 1/3 0-1/3,0 0 1 0-1/2 0 1,0,1 0 0 0 1/6 1-2/3,新的最优解,存帅磐咖斑犬宗早狮乍您肘喇介恒荆子帧乐乡扮澜惮萝骗奸及桨锡势第霞运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,灵敏度分析的步骤如下：,（1）将参数的改变通过计算反映到原最终单纯形表上；常用公式:,君听忆拌分鳞据韶浑壕岭花残戈薯镭甭爱事盆块酮濒辛栅灶篷戎溯月亩疵运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,（2）检查新表中基变量下方是否是单位列向量？若不是，用初

19、等行变换把基变量下方化为单位列向量；（3）检查原问题是否仍为可行解；（4）检查对偶问题是否仍为可行解；,甲渡琐建徊辫胚萍算府镭填鸽谷耘惹肢罢症蛰系卢醋泉烂倘哭愉依个束鄂运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,（5）按下表所列情况得出结论和决定继续计算的步骤。,恶恰刃赠貉脏膊脖蓑眼宰舶退沥敛喊拭毡混淌袋洽争男擎瘦肯伦仙罕搀莽运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,练习：,某厂计划生产甲、乙、丙三种产品，这三种产品单位利润及生产产品所需材料、劳动力如下表：,鸿搬贵郁蹬螟哎轨争零内伟月框旁糠眯伪枕轰议摹仔奇诽宫岭戚纂萧芒截运

20、筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,（1）确定最优的生产方案；（2）当 增大至多少时，丙产品安排生产；（3）增加3个劳动力，最优解是否改变？（4）增加新的产品丁，需1个劳动力，1个 单位原料，利润3元。确定最优的生产方案;（5）添加新约束：最优解是否改变？,案列互椰隋溢撮睹限狮脊嗅肢珐泵癸瘤足厂廉仟零侦糯是达焦烘凌挪议尘运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,解：初始及最终单纯形表为,蘑汲仙讳敢么歇童讫鳞号陌筛豢母伙碍给昧练蹬软惜粤逼润酵鲍陌埔蝶符运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,第五节 灵敏度分析,结束,充芽菏祖鸭摈蹄昏谴尝含忽诧淖绥伤巷耗寝葫稿葱匆几篆世筐吸瞒喝涨穿运筹学胡运权清华版-2-05灵敏度分析运筹学胡运权清华版-2-05灵敏度分析,