[教育]第五章 线性规划问题的灵敏度分析.ppt

第五章 线性规划问题的灵敏度分析 (又称为后优化分析) 5.3 价值系数 cj 的灵敏度分析 cj 变动可能由于市场价格的波动，或生产成本的变动 cj 的灵敏度分析是在保证最优基变量不变的情况下，分析cj 允许的变动范围?cj cj 的变化会引起检验数的变化，有两种情况 非基变量对应的价值系数变化，不影响其它检验数 基变量对应的价值系数变化，影响所有非基变量检验数 （1）非基变量对应的价值系数的灵敏度分析 例5.1 （2）基变量对应的价值系数的灵敏度分析 由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数 只有一个基变量的 cj? 发生变化，变化量为? cj? 令 cj? 在CB中的第k行，研究非基变量xj 机会成本的变化 5.6 新增决策变量的分析 若新增产品 x6，问是否生产？ 已知 c6=4, p6=(2,4,5) 计算 x6 的检验数可知生产是否有利 例3 分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品Ⅰ的工艺结构有了改进，这时有关它的技术系数向量变为P1′=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响? 原问题最优单纯形表如下： 例4 假设例3的产品Ⅰ′的技术系数向量变为P1′=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案? 5.8对偶单纯形法的应用（新增约束条件的分析) 将最优解代入新的约束条件，若满足，则最优解不变 若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型 利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法 * * * 线性规划是静态模型 参数发生变化，原问题的最优解还是不是最优 哪些参数容易发生变化:C, b, A 每个参数发生多大的变化不会破坏最优解 灵敏度越小，解的稳定性越好 5.1 灵敏度分析的概念与内容 灵敏度分析概念： (1)当线性规划有关参数和条件发生变化时，分析其最优基/最优解/最优值的变化情况； (2)分析线性规划相关参数和条件在什么范围内变化，其最优基/最优解/最优值不变。 灵敏度分析内容： (1)参数 Cj,bi,aij的影响分析; (2) 增加约束或变量的影响分析； 5.2 灵敏度分析工具与原理 Pj’ =B-1Pj b’=B-1b σj =Cj-CBB-1Pj=Cj-CBPj’ Z0=CBTB-1b=CBb’ （LP）最优基保持不变 σj ≤0 b’≥0 (1)灵敏度分析工具 (2)灵敏度分析原理 (3)分析结论 引入人工变量，编制新单纯形表进行求解 不可行 不可行 迭代求出最优（对偶单纯形法） 可行 不可行 迭代求出最优（单纯形法） 不可行 可行 仍为最优解 可行 可行 结论或继续计算的步骤 对偶问题 原问题 不考虑ark=0的情况，因为当ark=0时，cj的变化不影响zk，同时因为基变量检验数始终为0，不考虑其变化。 设x4的价值系数增加?c4，对应k=2（第二行） 有一边为空集如何处理 为什么akj=0不出现在任何一边的集合中 与对偶单纯型法找入变量的公式一样 试求价值系数变化范围为多少时原问题最优解不变 上例题的最优单纯形表为： 约束条件右端项bi的变化在实际问题中反映为可用资源数量的变化。由对偶单纯形法可看出b变化反映到最终单纯形表上将引起右边系数列数字的变化,结论可能出现第一或第三的两种情况。出现第一种情况时，问题的最优基不变，变化后的b列值为最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解 。 引入人工变量，编制新单纯形表进行求解 不可行 不可行 迭代求出最优（对偶单纯形法） 可行 不可行 迭代求出最优（单纯形法） 不可行 可行 仍为最优解 可行 可行 结论或继续计算的步骤 对偶问题 原问题 5.4 右端项 bi 的灵敏度分析 设XB=B?1b是最优解，则有XB=B?1b?0 b的变化不会影响检验数 b的变化量?b可能导致原最优解变为非可行解 以b2为例, x6是对应的初始基变量，所以有 试求右边系数变化范围为多少时原问题最优基不变 上例题的最优单纯形表为： 5.7 技术系数aij的变化 约束矩阵A随之变化 若xj在最终表中为非基变量，其约束条件中系数aij的变化分析步骤参考增加一个变量时的情形 若xj在最终表中为基变量，则aij的变化将使相应的基矩阵B和B-1发生变化，可能出现原问题和对偶问题均为非可行解的情况，需引进人工变量将原问题化为可行解，再用单纯形法 x1′的检验数为 c1′-CBB-1P1′=4-(1.5,0.125,0)(2,5,2)T=0.375 解 把改进工艺结构的产品Ⅰ看作产品Ⅰ′，设x