运筹学2课时-第3章

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

2、查与包装 7/107/10 1/21/2 1 1 1/101/10 1 1 5/65/6 2/32/3 1/41/4 630630 600600 708708 135135 单位利润单位利润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, x

3、2*=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、多系数同时变化 1）若c1=10变成13且c2=9变成8，则最优解变化

4、吗？ 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. 右端常数项大于等于零 第一节第一节 灵敏度分析简介灵敏度分析简介 二、灵敏度分析简介 1、什么是灵敏度分析 在 LP求出最优解之后，要研究： 1）当

5、c ci i 发生变化时，最优解最优解如何变化？ 2）当 b bi i 发生变化时，最优解最优解是否变化？最优值最优值变化多少？ 3）当 a aij ij 发生变化时，最优解 最优解如何变化？ 2、为什么要进行敏感性分析？ 1）现实世界是动态变化动态变化的，如：市场变化，售价的变化将导致利润率的 变化，进而导致目标函数系数目标函数系数的变化。 2）有些资源是可控可控的，如：是否加班？将导致可用工时的变化，进而导 致右端项值右端项值的变化。 3）模型中的数据有些是估计的、近似近似的。 3、LP模型系数变化后的处理方法 1）重新求解麻烦，除了最优解外，其他额外价值信息无法获得。 2）灵敏度分析简单

6、有效。 第二节第二节 单系数变化单系数变化 一、两个变量的图解法 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*=7668 1）若c1=10变成7，则最优解变化吗？新最优目标函数值是？ 问题1： 2）若c2=9变成10，则最优解变化吗？新最优目标函数值是？ 3）c1 与 c2 的保优区域是？ 四约束之截距分别是： （900，630） （1200，700） （708，1062）（1350，5

7、40） 约束一直线之斜率= - 7/10 约束三直线之斜率= - 3/2 约束四直线之斜率= - 2/5 3 1 of 2 1 . c c fo直线之斜率 2 4 (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*=7668 1）若b1=630变成640，则最优解变化吗？目标函数值变化了多少？ 问

8、题2： 2） b2=600变成610呢？b3=708变成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） 对偶价格：

9、约束条件右端项值每增加一个单位时, 目标函数值的改 进量 2、对偶价格的意义 （1）加班费的依据4.375 是车间3支付加班费的上限 （2）外包或对外揽活的依据若对外加工的报酬在4.375 之上，可 以考虑节约出部分工时搞外加工，反之可考虑外包 3、注意： （1）有些bi变化对目标函数值没有影响，故松弛变量值大于大于0 0时， 对偶价格 0； （2）对偶价格仅当bi变化不大时有效，若bi不断变化，则该约束 条件可能变成冗余约束。 问题：对偶价格有意义的范围是？ 第二节第二节 单系数变化单系数变化 二、计算机输出结果的解释 2、保优区域 3、对偶价格 4、对偶价格有效范围 5、松弛变量和剩余变量

10、 1、最优解和最优目标函数值 6、递减成本 第二节第二节 单系数变化单系数变化 二、计算机输出结果的解释 递减成本：对每个决策变量，要使其由零变成正数，所对应的目标 函数系数所需要改进的值。 修改的Par公司问题：假设管理者希望生产一种轻便、球手可以随身携带 的高尔夫球袋。设计部门估计每个新型球袋将需要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

11、 + 1/4x2+1/4x3135 x1 ，x2, x30 第三节第三节 多系数同时变化多系数同时变化 一、100%法则 2、方法 允许增加量：允许增加量：系数可能增加的最大量 允许减少量：允许减少量：系数可能减少的最大量 100%100%法则：法则：若所有变化的目标函数系数目标函数系数（或右端项值右端项值），计算其占允 许增加量和允许减少量的百分比之和。如果和小于小于100%，最优解最优解不会 改变(或对偶价格对偶价格有效)。 1、问题 1）若c1=10变成13且c2=9变成8，则最优解变化吗？ 2）若b1=630变成650且b3=708变成808，则最优解目标函数值如何变化？ 3、注意 1

12、00%法则只允许目标函数系数中多系数同时变化或者右端项值中 多个值同时变化，但不能发生交叉同时变化。 第四节第四节 电子通信公司问题电子通信公司问题 一、例1 。 分销渠道 单位利润 （美元） 单位广告费用 （美元） 单位销售时间 （小时） 航海器材经销店 商用器材经销店 全国连锁零售店 直接邮购 90 84 70 60 10 8 9 15 2 3 3 0 假设：公司的广告费用预算是5000美元，最大销售时间为 1800小时，全国连锁零售店要求至少销售150件该产品。公 司决定制造的该产品数量为600件。 问：问：如何分配各销售渠道的销售数量能使得总利润最大？ 二、例1的LP模型 决策变量：x1、x2，x3，x