灵敏度分析

15.093 最优化方法 第 7课：灵敏度 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 1 导学 1.1 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 幻灯片 1 0 ' min ≥ = = x b Ax s.t. xcz z 目标函数中的价值系数 的变化与目标函数值 的关系？资源数量 的变化与目 标函数值 的关系？ c z b z z 改变 中的任意一个， 会有什么变化？ , ,b c A z z 如果加入新的约束条件，引入新的变量， 会有什么变化？ z z 重要性：找到线性优化与实际应用之间的相关性 2 概述 幻灯片 2 1．全局灵敏度分析 2．局部灵敏度分析 （a）改变 的值 b （b）改变c的值 （c）增加一个变量 （d）增加一个约束条件 （e）改变 A的值 3．具体例子 3 全局灵敏度分析 3.1 依赖于 幻灯片 3 c 0 min)( ≥ = = x bAx s.t. c'xcG 是 的一个凹函数 c 3.2 依赖于b 幻灯片 4 原函数 对偶函数 0 max)( min)( ≥ ≤= == x c'As.t. p'b Ax s.t. p'bbFc'xbF 是 的一个凸函数 b 4 局部灵敏度分析 幻灯片 5 0 min ≥ = = x b. Ax s.t c'xz 基 B最优的含义？ 1． 可行性条件： 0 1 ≥− bB 2． 最优性条件： 'AB c'-c'B 0 1 ≥− 幻灯片 6 z 以假设改变b或c为例 z 如何确定基 B仍然是最优的？ z 需要检查是否符合可行性条件和最优性条件 5 局部灵敏性分析 5.1 改变 的值 幻灯片 7 b ib 发生变化，变为 ib + ∆ 00 min )( min )( ≥≥ ∆+=→= x x eb Ax s.t. b t. Ax s. c'xP'c'xP i z B是 ( 的最优基 )P z B是 ( 的最优基吗？ )'P 需要进行检查： 幻灯片 8 1． 可行性： 01 ≥∆+− )e(bB i 2． 最优性： 'ABc'-c'B 01 ≥− 观察得到： 1． 改变b的值将影响可行性 2． 但不会改变最优性条件 幻灯片 9 [ ] [ ] ⇒≥∆+⇒≥∆+ = = ≥∆+ −− − − − 00)()( Thus, 0 11 1 1 1 jijjij jj ijij i beBbB bBb B )e(bB β β 因此， 幻灯片 10 ∆≤∆≤∆ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛−≤∆≤⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛− <> minmax 00 ji j ij j bb jiij ββ ββ 在这个范围内： z 现有的基 B是最优的 z iBiB pbBceBBcz ∆+=∆+= −− 1'1' )( z 如果∆ = ∆呢？ z 如果∆ > ∆呢？ 现有的解不可行，但满足最优性条件 采用对偶单纯形法 → 5.2 改变 的值 幻灯片 11 c 现有的基 B是否最优？ 需要进行检查： 1．可行性： ，不受影响 01 ≥∆+− )e(bB i 2．最优性： ，受影响 'ABc'-c'B 01 ≥− 存在两种情况： z jx 为基变量 z jx 为非基变量 5.2.1 jx 为非基变量 幻灯片 12 Bc 不受影响 00)( 1' ≥∆+⇒≥−∆+ − jjBj cABcc 如果 jc∆ ≥ − ，解最优 如果 jc∆ = − 呢？ 如果 jc∆ < − 呢？ 5.2.2 jx 为基变量 幻灯片 13 jBBB eccc ∆+=← ˆ 那么， [ ] [ ] 0'0ˆ' 11' ≥∆+−⇒≥− −− jjBiiB ABeccABcc [ ] jiji aAB =−1 ji i a ji i ajii a c a cac jiji 00 minmax0 >< ≤∆≤⇒≥∆− 如果 的值超出了这个范围呢？采用原来的单纯形 ∆ 5.3 加入一个新的变量 幻灯片 14 00 min min 11 11 ≥≥ =+→= + ++ ++ x x bxAt. Ax s.b x s.t. A xc c'xc'x nn nn 在新的问题中 1 0nx + = 还是 （i.e，这一改变是否有益处？） 幻灯片 15 1 0nx + > 现有的基为 B。解 是最优吗？ z 满足可行性条件 z 满足最优性条件： ?0'0 111 1' 1 ≥−⇒≥− +++−+ nnnBn ApcABcc z 如果满足，则解 为最优解 z 否则，采用原单纯形 5.4 增加一个约束条件 幻灯片 16 0 0 minmin 11 ≥ =≥ =→= ++ x bx a x b.t. Ax sb x s.t. A c'x c'x m ' m 如果现有的解可行，即为最优解；否则，应用对偶单纯形。 5.5 改变 A的值 幻灯片 17 z 假设 ∆+← ijij aa z 假定 jA 不属于基 z 可行性条件： 不受影响 01 ≥− bB z 最优性条件： 不受影响 jlABcc lBl ≠≥− − ,01' z 最优性条件： 00)(' ≥∆−⇒≥∆+− ijijj pceApc z 如果 jA 是基呢？ , .5.BT Exer 3 6 例题 6.1 一个家具公司 幻灯片 18 z 一个家具公司制造书桌，餐桌和椅子 z 生产这些产品需要木材，修整工，木匠 书桌 餐桌（ft） 椅子 可得性 利润 60 30 20 - 木材（ft） 8 6 1 48 修整工 hrs. 4 2 1.5 20 木匠 hrs. 2 1.5 0.5 8 6.2 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式 幻灯片 19 决策变量： 椅子数餐桌数书桌数 === 321 ,# , # xxx 0 850512 20512 4 48 6 8 203060max 321 321 321 321 321 ≥ ≤++ ≤++ ≤++ ++ ,x,xx x.x.x x.xx xxxs.t. xxx 6.3 单纯形表 幻灯片 20 初始表： 5.05.121 8 5.124 1 20 168 148 2030600000 3 2 1 321321 = = = −−− s s s xxxsss 最终表： 025.115.1 0.5-0 2 1204- 20 8 0208- 2 124 05010100280 1 3 1 321321 = −= −= x x s xxxsss 6.4 表中的信息 幻灯片 21 z 基 B的值？ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = 25.00 45.10 811 B z 1B− 的值？ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ − − − =− 5.15.00 420 821 1B 幻灯片 22 z 最优解为多少？ z 最优解的函数值为多少？ z 结果是否符合常规？ z 对偶问题的最优解是多少？ z 木材这个约束条件的影子价格是多少？ z 整修时间这个约束条件的影子价格是多少？ z 2x 减少的成本是多少？ 6.5 影子价格 幻灯片 23 整修时间这个约束条件的对偶价格为何为 10？ z 假设整修时间从 20调整为 21 z 现在只生产书桌（ 1x ）和椅子（ 3x ） z 整修时间和木匠时间为严格约束条件 z 这样改变后还存在最优解吗？ 幻灯片 24 新的解： 8 10 x 8 5.02 2 1.5 x 21 5.14 24 26s 48 8 331 131 1131 ==+ =⇒=+ ==++ xx xx sxx 解的改变： 10)8*202*60()10205.1*60(' +−++=−zz 幻灯片 25 z 假如你能以$7每小时的价格雇用修整工加班，你会采用这样的方式吗？ z 检查 ( ) ( )10,10,0 5.15.00 420 821 60,20,01' −−= ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − − − −−=−BcB 6.6 减少的成本 幻灯片 26 z 2x 减少的成本是 5的含义？ z 假设你必须生产一张餐桌（ 2x ＝１） z 将会减少多少利润？ 10 x 8 1*1.5 0.5x2x 0.75 x 201*2 1.5x4x 26 s 481*6 8 331 131 1131 ==++ =⇒=++ ==+++ sxx 幻灯片 27 可以用另一种方法计算：如果 2 1x = 来自餐桌的直接利润为 30+ 用去木材的费用 00*6 =− 整修所花的费用 2010*2 −=− 木匠工作所花的费用 1510*5.1 −=− 合计 5− 假设生产餐桌的收益从$30上升到$34，应该生产餐桌吗？如果上升到$35，$36呢？ 6.7 成本范围 幻灯片 28 假设来自书桌的收益变为 60+∆。∆为什么值时，现有的基仍是最优的？ 最优性条件： ⇒≥− − 01' jBj ABcc [ ] [ ]∆+∆−−= ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ − − − ∆+−−=−= 5.110,5.010,0 5.15.00 420 821 )60(,20,01' ' Bcp B 幻灯片 29 131 ,, xxS 是基 非基变量的减少的成本 [ ] ∆−= ∆−= ∆+= ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ∆+∆−+−=−= 5.110 5.010 25.15 5.1 2 6 5.110,5.010,030' 3 2 222 s s c c Apcc 现有的基为最优： 5 1.25 0 10 0.5 0 4 20 10 1.5 0 + ∆ ≥ ⎫⎪− ∆ ≥ − ≤ ∆ ≤⎬⎪+ ∆ ≥ ⎭ 解仍为最优。 如果 ，或 现有的基不是最优。 561 c 假设 )40(1001 =∆=c 该怎么做？ 6.8 Rhs范围 幻灯片 30 假设修整时间变化一个小的量 ，变为（20+∆ ∆），会有什么变化？ 44 0 5.02 28 224 8 20 48 5.15.00 420 821 8 20 48 1 ≤∆≤−⇒ ≥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ∆− ∆+ ∆+ = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ∆+ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ − − − = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ∆+−B 现有的基最优 幻灯片 31 注意：即使现有的基是最优，最优解也会发生改变： ∆+=∆++∆−= ∆−= ∆+= ∆+= 10280)28(20)5.02(60 5.02 28 x 224s 1 3 1 z x 幻灯片 32 假设 =10，则 ∆ （采用对偶单纯形） ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 3 25 44 1 3 1 x x s inf .← 6.9 新的措施 幻灯片 33 假设这家公司有机会生产利润为$15的凳子；每生产一张凳子需要 1ft的木材，1 小时的整修时间，1小时的木工时间。则该公司应该生产凳子吗？ 0 850 512 20 51 24 4868 15203060max 34321 24321 14321 4321 ≥ =++++ =++++ =++++ +++ ix s xx.x.x s xx.x x sx x x x xxxx ( ) 05 1 1 1 10,10,015414 ' ≥= ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −−−−=−− ABcc B 现有的基仍为最优。不应生产凳子。