第三章线性规划敏感性分析 和计算机解法 敏感性分析: 除最优解外,为决策者提供有价值的额外信息 计算机求解: 解决两个以上变量LP.问题
Ling Xueling 第三章 线性规划敏感性分析 和计算机解法 敏感性分析： 除最优解外，为决策者提供有价值的额外信息 计算机求解： 解决两个以上变量 L.P. 问题
第一节敏感性分析介绍 概念 1、LP.一般式 maxz三max ∑ st ∑ b (i=1,2 ≥0(j=1
Ling Xueling 第一节 敏感性分析介绍 一、概念 1、L.P. 一般式 0 ( 1,2,...., ) ( 1,2,...., ) . . max max 1 1 x j n a x b i m st z c x j n j i j j i n j j j = = = = =
第一节敏感性分析介绍 概念 什么是敏感性分析 最优后分析。就是在LP求出最优解之后,要研究: 1)当C;发生变化时,对最优解x;的影响是什么? 2)当b;发生变化时,对最优解值z=o.f的影响是什么? 3、为什么要进行敏感性分析? 1)现实世界是动态变化的,所有系数都会变化,如:市场变化,售价 的变化将导致利润率的变化,进而导致目标函数之系数的变化 2)有些数据是可控的,如:是否加班?将导致可用工时的变化 3)不少模型中的数据本来就是估计的、近似的 对修正了的LP.模型不再重新求解,也要有足够的信息回答 上述变化所带来的影响一一对最优解的影响,即:动态变化 或近似估计允许的范围是什么?
Ling Xueling 第一节 敏感性分析介绍 一、概念 2、什么是敏感性分析 最优后分析。就是在L.P. 求出最优解之后，要研究： 1）当 C j 发生变化时，对最优解 x j 的影响是什么？ 2）当 b i 发生变化时，对最优解值 z ＝ o.f. 的影响是什么？ 3、为什么要进行敏感性分析？ 1） 现实世界是动态变化的，所有系数都会变化，如：市场变化，售价 的变化将导致利润率的变化，进而导致目标函数之系数的变化 2）有些数据是可控的，如：是否加班？将导致可用工时的变化 3）不少模型中的数据本来就是估计的、近似的 对修正了的 L.P. 模型不再重新求解，也要有足够的信息回答 上述变化所带来的影响－－对最优解的影响，即：动态变化 或近似估计允许的范围是什么？
凌晨: 节敏感性分析介绍 二、实例一—Par.公司问题 1、原问题及最优解 Max 10x,+9x s t 7/10x1+ X2≤630 最优解 1/2x1+5/6x2≤600 1=540 1+2/3x2≤708 252 /10x1+14x2≤135 2≥0
Ling Xueling 二、实例－－Par. 公司问题 1、原问题及最优解 Max 10x1 + 9 x2 s.t. 7/10 x1 + x2 630 最优解 1/2 x1 + 5/6 x2 600 x1 = 540 x1 + 2/3 x2 708 x2 = 252 1/10 x1 + 1/4 x2 135 x1 , x2 0 第一节 敏感性分析介绍 凌晨: 凌晨:
凌晨: 一节敏感性分析介绍 实例 2、c变化与最优解x )若c1=10变成7,问:最优解变化吗? 2)若c2在(5,13)变化时最优解不变,如何评价c2=9? 3)若仅当c2∈(8.9,9.25)时最优解不变,超出这个范围哪怕 点点,最优解就会变,又如何评价c2=9? 3、b;变化与最优解值z 1)b,变化时,z如何变化? 2)b增加时,附加工时的价值(z2-z1)是什么?
Ling Xueling 二、实例 2、cj 变化与最优解 xj 1）若 c1 = 10 变成 7，问：最优解变化吗？ 2）若 c2 在 (5, 13) 变化时最优解不变，如何评价 c2 = 9 ？ 3）若仅当 c2 (8.9, 9.25) 时最优解不变，超出这个范围哪怕 一点点，最优解就会变，又如何评价 c2 = 9 ？ 3、bi 变化与最优解值 z 1）bi 变化时，z 如何变化？ 2）bi 增加时，附加工时的价值 (z2－z1 ) 是什么？ 第一节 敏感性分析介绍 凌晨: 凌晨:
凌晨: 节敏感性分析图解法 关于c;的变化 1、保优区域的定义 使最优解不发生变化,c的允许变化区间 注意:只保最优解,不保目标函数值! 2、C;保优区域的几何求法 因为of.直线在最优解点处顺时针旋转一一下界;逆时针旋转 上界,得: 7 10 故,c的保优区域是: 6.3≤c1≤13.5 0 667≤c2≤1429(暂时不讨论联立变化)
Ling Xueling 一、关于 cj 的变化 1、保优区域的定义 使最优解不发生变化，cj 的允许变化区间 注意：只保最优解，不保目标函数值！ 2、Cj 保优区域的几何求法 因为 o.f. 直线在最优解点处顺时针旋转－－下界；逆时针旋转 －－上界，得： 故，cj 的保优区域是： 令 c2 = 9 6.3 c1 13.5 c1 = 10 6.67 c2 14.29 ( 暂时不讨论联立变化） 第二节 敏感性分析图解法 凌晨: 凌晨: 10 7 2 3 2 1 − − − c c
凌晨: 节敏感性分析图解法 关于c;的变化 3、特殊情况的讨论 18X1+9 则最优解是 708 X2=0 令C2=9从 得下界13.5≤c1 从 得上界c1≤+0O 即得C1保优区域:13.5≤C1<+00
Ling Xueling 一、关于 cj 的变化 3、特殊情况的讨论 令 z = 18 x1 + 9 x2 则最优解是 x1 = 708 x2 = 0 令 c2 = 9 从 得下界 13.5 c1 从 得上界 c1 ＋ 即得 C 1 保优区域: 13.5 C1 < + 第二节 敏感性分析图解法 凌晨: 凌晨: 2 3 2 1 − − c c − − 2 1 c c
凌晨: 节敏感性分析图解法 关于右手边值b;(资源)的变化 要研究:1)可行域如何变化? 2)最优解如何变化? 3)变化值的意义是什么? 1、实例 在Par公司问题的第一个约束式中令b1=640 则因为可行域增大,最优解变成:ⅹ1=527.5,ⅹ2=270.75 of=7711.75 即:利润增加771.75-7668=43.75=△z 也即:4.375/工时(对C&D工序来说)
Ling Xueling 二、关于右手边值 b i （资源）的变化 要研究：1）可行域如何变化？ 2）最优解如何变化？ 3）变化值的意义是什么？ 1、实例 在 Par. 公司问题的第一个约束式中令 b1 = 640 则因为可行域增大，最优解变成：x1 = 527.5, x2 = 270.75 o.f. = 7711.75 即：利润增加 7711.75 - 7668 = 43.75 = 也即：4.375 / 工时 （对 C&D 工序来说）。 第二节 敏感性分析图解法 凌晨: 凌晨: z
凌晨: 节敏感性分析图解法 关于右手边值b;(资源)的变化 2、影子价格的定义 约束条件右手边常数每增加一个单位时,目标函数of.所增加的 数值成为影子价格 3、影子价格的意义 1)加班费的依据--4.375是C&D车间支付加班费的上限 2)对外揽活的依据一一若对外加工的报酬在4.375之上,可以考 虑节约出部分工时搞外加工 3)注意:(1)有些b变化对of.没有影响,故,任何不是可行 域之限界的约束条件的影子价格=0,如S车间 (2)显然,影子价格仅仅当b;变化不大时有效,若b 不断变化,则其他约束条件可能变成限界而使o.f发生其他的变 化。问题:使影子价格有意义的范围时什么?
Ling Xueling 二、关于右手边值 b i （资源）的变化 2、影子价格的定义 约束条件右手边常数每增加一个单位时，目标函数 o.f. 所增加的 数值成为影子价格 3、影子价格的意义 1）加班费的依据－－4.375 是 C&D 车间支付加班费的上限 2）对外揽活的依据－－若对外加工的报酬在 4.375 之上，可以考 虑节约出部分工时搞外加工 3）注意：（1）有些 bi 变化对 o.f. 没有影响，故，任何不是可行 域之限界的约束条件的影子价格 ＝ 0，如 S 车间 （2）显然，影子价格仅仅当 bi 变化不大时有效，若 bi 不断变化，则其他约束条件可能变成限界而使 o.f. 发生其他的变 化。问题：使影子价格有意义的范围时什么？ 第二节 敏感性分析图解法 凌晨: 凌晨:
凌晨: 节敏感性分析图解法 关于右手边值b;(资源)的变化 4、b;允许变化的区间 1)对偶价格定义( dual price) b;每增加一个单位时,of的改善值 显然,在max问题中,dual= shadow 在min问题中,dual=- shadow 2)b;可行区间( range of feasibility)定义 使得对偶价格有效的区间称为b;的可行区间 意义:可行,要保证“对偶”有效,即:资源配置的增、减 幅度应该控制在有效、可行范围内! 问题:如何求b;的可行区间?一一下面一节解决
Ling Xueling 二、关于右手边值 b i （资源）的变化 4、b i 允许变化的区间 1）对偶价格定义（dual price） b i 每增加一个单位时，o.f. 的改善值 显然，在 max 问题中，dual = shadow 在 min 问题中，dual = － shadow 2）b i 可行区间（range of feasibility）定义 使得对偶价格有效的区间称为 b i 的可行区间 意义：可行，要保证“对偶”有效，即：资源配置的增、减 幅度应该控制在有效、可行范围内！ 问题：如何求 b i 的可行区间？－－下面一节解决。 第二节 敏感性分析图解法 凌晨: 凌晨: