运筹学2课时-第3章

1、运筹学运筹学主讲人：朱建明主讲人：朱建明 2015 年 3 月商务信息学院商务信息学院第第 3章章 线性规划的灵敏度分析线性规划的灵敏度分析与最优解的解释与最优解的解释灵敏度分析简介 1单系数变化2多系数同时变化 3电子通信公司问题4第一节第一节 灵敏度分析简介灵敏度分析简介一、引例Par公司是一家生产高尔夫器材的小型公司，它决定进入中高等价位的高尔夫球袋市场。已知生产单位球袋的所需时间、单位球袋利润等数据如下表，问如何安排生产计划使公司利润最大？ 球袋球袋部门部门标准袋标准袋高级袋高级袋工时限制工时限制切割与印染切割与印染缝合缝合成型成型检查与包装检查与包装7/107/101/21/21 1

2、1/101/101 15/65/62/32/31/41/4630630600600708708135135单位利润单位利润10109 9第一节第一节 灵敏度分析简介灵敏度分析简介一、引例决策变量：x1、x2分别代表标准袋和高级袋的生产 数量。目标函数： max z=10 x1+9x2约束条件： s.t. 7/10 x1 + x2630切割与印染 1/2x1 + 5/6x2600缝合 x1 + 2/3x2708成型 1/10 x1 + 1/4x2135检查与包装 x1 ，x20 通过计算机求解可得：x1*=540, x2*=252, z*=7668第一节第一节 灵敏度分析简介灵敏度分析简介一、引

3、例 问题： 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、多系数同时变化 1）若c1=10变成13且c2=9变成8，则最优解变化吗？ 2）若b1=630变成650且b3=708变成808，则最优解目标函数值如何变

4、化？第一节第一节 灵敏度分析简介灵敏度分析简介二、灵敏度分析简介 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. 右端常数项大于等于零第一节第一节 灵敏度分析简介灵敏度分析简介二、灵敏度分析简介 1、什么是灵敏度分析 在 LP求出最优解之后，要研究： 1）当 c ci i 发生变化时，最优解最优解如何变化？ 2）当 b bi i 发生变化时，最优解最

5、优解是否变化？最优值最优值变化多少？ 3）当 a aijij 发生变化时，最优解最优解如何变化？ 2、为什么要进行敏感性分析？ 1）现实世界是动态变化动态变化的，如：市场变化，售价的变化将导致利润率的变化，进而导致目标函数系数目标函数系数的变化。 2）有些资源是可控可控的，如：是否加班？将导致可用工时的变化，进而导致右端项值右端项值的变化。 3）模型中的数据有些是估计的、近似近似的。3、LP模型系数变化后的处理方法 1）重新求解麻烦，除了最优解外，其他额外价值信息无法获得。 2）灵敏度分析简单有效。 第二节第二节 单系数变化单系数变化一、两个变量的图解法 max z=10 x1+9x2 s.t

6、. 7/10 x1 + x2630 1/2 x1 + 5/6x2600 x1 + 2/3x2708 1/10 x1 + 1/4x2135 x1 ，x20 通过计算机求解可得：x1*=540, x2*=252, z*=76681）若c1=10变成7，则最优解变化吗？新最优目标函数值是？问题1：2）若c2=9变成10，则最优解变化吗？新最优目标函数值是？3）c1 与 c2 的保优区域是？ 四约束之截距分别是：（900，630） （1200，700）（708，1062）（1350，540）约束一直线之斜率= - 7/10约束三直线之斜率= - 3/2约束四直线之斜率= - 2/531of21.ccf

7、o直线之斜率24(300,420)(540,252)第二节第二节 单系数变化单系数变化一、两个变量的图解法 max z=10 x1+9x2 s.t. 7/10 x1 + x2630 1/2 x1 + 5/6x2600 x1 + 2/3x2708 1/10 x1 + 1/4x2135 x1 ，x20 通过计算机求解可得：x1*=540, x2*=252, z*=76681）若b1=630变成640，则最优解变化吗？目标函数值变化了多少？问题2：2） b2=600变成610呢？b3=708变成718呢？b4=135变成145呢？3） 若考虑加班，则应该优先考虑哪个部门？第二节第二节 单系数变化单系

8、数变化一、两个变量的图解法问题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支付加班费的上限（2）外包或对外揽活的依据若对外加工的报酬在4.37

9、5 之上，可 以考虑节约出部分工时搞外加工，反之可考虑外包3、注意：（1）有些bi变化对目标函数值没有影响，故松弛变量值大于大于0 0时， 对偶价格 0；（2）对偶价格仅当bi变化不大时有效，若bi不断变化，则该约束 条件可能变成冗余约束。问题：对偶价格有意义的范围是？第二节第二节 单系数变化单系数变化二、计算机输出结果的解释2、保优区域3、对偶价格4、对偶价格有效范围5、松弛变量和剩余变量1、最优解和最优目标函数值6、递减成本第二节第二节 单系数变化单系数变化二、计算机输出结果的解释递减成本：对每个决策变量，要使其由零变成正数，所对应的目标 函数系数所需要改进的值。修改的Par公司问题：假设

10、管理者希望生产一种轻便、球手可以随身携带的高尔夫球袋。设计部门估计每个新型球袋将需要0.8小时的切割与印染时间，1小时的缝合时间，1小时的成型时间和0.25小时的检查与包装时间。 max z=10 x1+9x2+12.85 x3 s.t. 7/10 x1 + x2+0.8x3630 1/2 x1 + 5/6x2+ x3600 x1 + 2/3x2+ x3708 1/10 x1 + 1/4x2+1/4x3135 x1 ，x2, x30 第三节第三节 多系数同时变化多系数同时变化一、100%法则 2、方法 允许增加量：允许增加量：系数可能增加的最大量 允许减少量：允许减少量：系数可能减少的最大量

11、100%100%法则：法则：若所有变化的目标函数系数目标函数系数（或右端项值右端项值），计算其占允 许增加量和允许减少量的百分比之和。如果和小于小于100%，最优解最优解不会 改变(或对偶价格对偶价格有效)。1、问题1）若c1=10变成13且c2=9变成8，则最优解变化吗？2）若b1=630变成650且b3=708变成808，则最优解目标函数值如何变化？3、注意100%法则只允许目标函数系数中多系数同时变化或者右端项值中多个值同时变化，但不能发生交叉同时变化。第四节第四节 电子通信公司问题电子通信公司问题一、例1。分销渠道单位利润（美元）单位广告费用（美元）单位销售时间（小时）航海器材经销店商用器材经销店全国连锁零售店直接邮购908470601089152330假设：公司的广告费用预算是5000美元，最大销售时间为1800小时，全国连锁零售店要求至少销售150件该产品。公司决定制造的该产品数量为600件。问：问：如何分配各销售渠道的销售数量能使得总利润最大？二、例1的LP模型决策变量：x1、x2，x3，x4分别表