1、管理运筹学华国伟Email:北京交通大学经管学院物流管理系第二章 灵敏度分析 密码 : 123456 本节重点:线性规划问题的各个参数发生变化时 ,对最优解的影响情况 .如果最优解发生变化 ,如何求新的最优解7 灵敏度分析提 纲 灵敏度分析 (Sensitivity Analysis) 资源数量 b变化的分析 目标函数中价值系数 cj的变化分析 技术系数 aij变化分析问题 1:为什么要进行分析?问题 2:分析什么? 参数估计可能出现误差 客观环境发生变化引起 b、 c、 A问题 1:为什么要进行分析? 参数发生变化后 ,原问题的最优解还是不是最优 ?或者每个参数发生多大的变化不会破坏最优解或
2、最优基 ? 参数发生变化后 ,如果原来的结果发生变化 ,如何求新的最优解 ?问题 2:分析什么?原问题 对偶问题 结论或继续计算的步骤可行解 可行解 表中的解仍为最优解可行解 非可行解 用单纯形法继续迭代求最优解非可行解 可行解 用对偶单纯形法继续迭代求最优解非可行解 非可行解 引入人工变量,编制新的单纯形表 ,求最优解参数发生变化后 ,原来的结果发生变化后 ,如何求新的最优解?max Z = CBB-1b +( CN - CBB-1N) XN XB + B-1NXN = B-1bXB 0, XN 0s.t.若 XB 是最优解 , 则 必 有CN - CBB-1N 0B-1b 0 ( 可行性
3、)( 正则性 ) 若 bi 变化 ,可能影响解的可行性 . 若 cj 变化 ,可能影响解的 正则性 . 若 aij 变化 ,可行性和 正则性都会受到 影响 .基本原理:7.1 bj 的变化 设 XB=B1b是最优解 , 则有 XB=B1b0; b的变化不会影响检验数 ; b的变化量 b可能导致原最优解变为非可行解 ;( B-1b 会发生变化)7.1 约束常数 bi 变化的分析设线性规划的基逆矩阵为 B-1, 初始右端向量为b =( b1, b2, , bk , , bm) T如果第 k 个约束常量取得 bk 的增量 ,那么右端向量此时 ,新的解向量为b =( b1, b2, , bk+bk , , bm) TXB =B-1 b =B-1( b1, b2, , bk+bk , , bm )T记 B-1的第 k列为