《运筹学2课时-第3章》由会员分享，可在线阅读，更多相关《运筹学2课时-第3章（18页珍藏版）》请在金锄头文库上搜索。
1、运筹学,主讲人：朱建明,2015 年 3 月,商务信息学院,第 3章 线性规划的灵敏度分析 与最优解的解释,灵敏度分析简介,1,单系数变化,2,多系数同时变化,3,电子通信公司问题,4,第一节 灵敏度分析简介,一、引例,Par公司是一家生产高尔夫器材的小型公司，它决定进入中 高等价位的高尔夫球袋市场。已知生产单位球袋的所需时间 、单位球袋利润等数据如下表，问如何安排生产计划使公司 利润最大？,第一节 灵敏度分析简介,一、引例,决策变量：x1、x2分别代表标准袋和高级袋的生产 数量。 目标函数： max z=10x1+9x2 约束条件： s.t. 7/10x1 + x2630切割与印染 1/2x
2、1 + 5/6x2600缝合 x1 + 2/3x2708成型 1/10x1 + 1/4x2135检查与包装 x1 ，x20,通过计算机求解可得：x1*=540, x2*=252, z*=7668,第一节 灵敏度分析简介,一、引例,问题： 1、ci变化（目标函数系数变化）(保优区域) 1）若c1=10变成7，则最优解变化吗？ 2）若c2在(5,13) 变化时最优解不变，如何评价c2=9？ 3）若仅当c2(8.9,9.25)时最优解不变，又如何评价c2=9？ 2、bi变化（右端项值变化） 1）若b1=630变成640，则最优解变化吗？最优目标函数值如何变化？ 2）b1增加1个单位时，附加工时的价值
3、是什么？对偶价格 3）附加工时的价值的有效范围是什么？右端项变化范围 3、多系数同时变化 1）若c1=10变成13且c2=9变成8，则最优解变化吗？ 2）若b1=630变成650且b3=708变成808，则最优解目标函数值如何变化？,第一节 灵敏度分析简介,二、灵敏度分析简介,LP标准型： max z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 约束条件 am1x1+am2x2+amnxn= bm x1，x2，xn0 特点： 1. Zmax 2. 约束条件为等号 3. 变量非负 4. 右端常数项大于等于零,第一
4、节 灵敏度分析简介,二、灵敏度分析简介,1、什么是灵敏度分析 在 LP求出最优解之后，要研究： 1）当 ci 发生变化时，最优解如何变化？ 2）当 bi 发生变化时，最优解是否变化？最优值变化多少？ 3）当 aij 发生变化时，最优解如何变化？ 2、为什么要进行敏感性分析？ 1）现实世界是动态变化的，如：市场变化，售价的变化将导致利润率的变化，进而导致目标函数系数的变化。 2）有些资源是可控的，如：是否加班？将导致可用工时的变化，进而导致右端项值的变化。 3）模型中的数据有些是估计的、近似的。 3、LP模型系数变化后的处理方法 1）重新求解麻烦，除了最优解外，其他额外价值信息无法获得。 2）灵
5、敏度分析简单有效。,第二节 单系数变化,一、两个变量的图解法,max z=10x1+9x2 s.t. 7/10x1 + x2630 1/2 x1 + 5/6x2600 x1 + 2/3x2708 1/10x1 + 1/4x2135 x1 ，x20,通过计算机求解可得： x1*=540, x2*=252, z*=7668,1）若c1=10变成7，则最优解变化吗？新最优目标函数值是？,问题1：,2）若c2=9变成10，则最优解变化吗？新最优目标函数值是？,3）c1 与 c2 的保优区域是？,第二节 单系数变化,四约束之截距分别是： （900，630） （1200，700） （708，1062）（1
6、350，540） 约束一直线之斜率= - 7/10 约束三直线之斜率= - 3/2 约束四直线之斜率= - 2/5,3,1,of,2,4,(300,420),(540,252),第二节 单系数变化,一、两个变量的图解法,max z=10x1+9x2 s.t. 7/10x1 + x2630 1/2 x1 + 5/6x2600 x1 + 2/3x2708 1/10x1 + 1/4x2135 x1 ，x20,通过计算机求解可得： x1*=540, x2*=252, z*=7668,1）若b1=630变成640，则最优解变化吗？目标函数值变化了多少？,问题2：,2） b2=600变成610呢？b3=7
7、08变成718呢？b4=135变成145呢？,3） 若考虑加班，则应该优先考虑哪个部门？,第二节 单系数变化,一、两个变量的图解法,问题2：,1）b1由630增加到640 新最优解：x1=527.5, x2=270.75 新目标函数值：z=7711.75 目标函数值增加：7711.75 - 7668 = 43.75 单位利润增加：4.375/工时 （对切割工序来说）,第二节 单系数变化,一、两个变量的图解法,1、对偶价格的定义（dual price） 对偶价格：约束条件右端项值每增加一个单位时, 目标函数值的改 进量 2、对偶价格的意义 （1）加班费的依据4.375 是车间3支付加班费的上限
8、（2）外包或对外揽活的依据若对外加工的报酬在4.375 之上，可 以考虑节约出部分工时搞外加工，反之可考虑外包 3、注意： （1）有些bi变化对目标函数值没有影响，故松弛变量值大于0时， 对偶价格 0； （2）对偶价格仅当bi变化不大时有效，若bi不断变化，则该约束 条件可能变成冗余约束。 问题：对偶价格有意义的范围是？,第二节 单系数变化,二、计算机输出结果的解释,2、保优区域,3、对偶价格,4、对偶价格有效范围,5、松弛变量和剩余变量,1、最优解和最优目标函数值,6、递减成本,第二节 单系数变化,二、计算机输出结果的解释,递减成本：对每个决策变量，要使其由零变成正数，所对应的目标 函数系数
9、所需要改进的值。,修改的Par公司问题：假设管理者希望生产一种轻便、球手可以随身携带 的高尔夫球袋。设计部门估计每个新型球袋将需要0.8小时的切割与印染 时间，1小时的缝合时间，1小时的成型时间和0.25小时的检查与包装时间。,max z=10x1+9x2+12.85 x3 s.t. 7/10x1 + x2+0.8x3630 1/2 x1 + 5/6x2+ x3600 x1 + 2/3x2+ x3708 1/10x1 + 1/4x2+1/4x3135 x1 ，x2, x30,第三节 多系数同时变化,一、100%法则,2、方法 允许增加量：系数可能增加的最大量 允许减少量：系数可能减少的最大量
10、100%法则：若所有变化的目标函数系数（或右端项值），计算其占允 许增加量和允许减少量的百分比之和。如果和小于100%，最优解不会 改变(或对偶价格有效)。,1、问题 1）若c1=10变成13且c2=9变成8，则最优解变化吗？ 2）若b1=630变成650且b3=708变成808，则最优解目标函数值如何变化？,3、注意,100%法则只允许目标函数系数中多系数同时变化或者右端项值中多个值同时变化，但不能发生交叉同时变化。,第四节 电子通信公司问题,一、例1,电子通信公司主要生产双向便携式无线电报话机。该公司最 近开发了一种新产品，有关数据如下表所示。,假设：公司的广告费用预算是5000美元，最大销售时间为1800小时，全国连锁零售店要求至少销售150件该产品。公司决定制造的该产品数量为600件。 问：如何分配各销售渠道的销售数量能使得总利润最大？,二、例1的LP模型,决策变量：x1、x2，x3，x4分别表示通过四种不同渠道销 售的产品数量。 max z=90x1+84x2+70x3+60x4 s.t. 10x1+8x2+9x3+15x4 5000广告预算 2x1+3x2+3x3 1800可用销售时间 x1+ x2+ x3+ x4 =600产量 x3 150零售合同约束 x1，x2，x3，x4 0,三、计算机求解,第四节 电子通信公司问题,Thank You !,
