25灵敏度分析.ppt

运 筹 学; 灵敏度分析 在线性规划问题中，目标函数、约束条件的系数以及资源的限制量等都当作确定的常数，并在这些系数值的基础上求得最优解。但是实际上，这些系数或资源限制量并非一成不变的，它们是一些估计或预测的数字，比如价值系数随着市场的变化而变化，约束系数随着工艺的变化或消耗定额的变化而变化，计划期的资源限制量也是经常变化的。当这些系数发生变化时，最优解会受到什么影响？最优解对哪些参数的变动最敏感？搞清这些问题会使我们在处理实际问题时，具有更大的主动性和可靠性。 分析线性规划模型的某些系数或限制数的变动对最优解的影响，被称作灵敏度分析。 灵敏度分析主要解决两个问题： ⑴这些系数在什么范围内变化时，原先求出的最优解或最优基不变？即最优解相对参数变化的稳定性。 ⑵如果系数的变化引起了最优解的变化，如何用最简便的方法求出新的最优解。 ;下面分别介绍各类参数变化的灵敏度分析。 5.1 目标函数中价值系数C的分析 分别就非基变量和基变量的价值系数两种情况来讨论： ⒈设非基变量xj的价值系数cj,有增量△cj,其它参数不变，求△cj的范围使原最优解不变。 由于cj是非基变量的价值系数，因此它的改变仅仅影响检验数σj的变化，而对其它检验数没有影响。 由 σj+△cj≤0 知，当△cj≤-σj 时，原最优解不变。 ⒉设基变量XBr的价值系数CBr有增量△CBr，其它参数不变，求△CBr的范围使原最优解不变。 由于CBr是基变量的价值系数，因此它的变化将影响所有非基变量检验数的变化。 由新的非基变量检验数： =σj-（0…△CBr…0）B-1Pj=σj-arj△CBr≤0，可知，当 max｛σj/arj│arj＞0｝≤△CBr≤min｛σj/arj│arj＜0｝时，原最优解不变。; 例3 已知某LP问题的最优解及最优值如下：; ⑵将C1=12代入原最优表，重新计算检验数，原最优解不 再是最优解，用单纯形法继续运算，结果如下：; 5.2 资源系数b的分析 设bi有增量△bi，其它参数不变，则bi的变化将影响基变量所取的值，但对检验数没有影响，记新的基变量为 ，则 这里 是原最优基逆阵B-1的第i列。如果变化后仍有 ≥0，则原最优基不变。由此可知，当△bi满足 ≤△bi≤ 时，原最优基不变。 结果说明 ，△bi的变化范围是由原基变量的相反数与B-1的 第i列元素的比值所确定的。 如果△bi不在上述范围变动，则变化后的基变量所取值 肯定会出现负分量，但由于△bi不影响检验数的变化，因此可以用 取代原最优解XB=B-1b ，以该解为初始解，用对偶单纯形法继续求解。; 例4 已知线性规划问题的初始解及最优解见例3。 ⑴求△b1的范围，使原最优基不变； ⑵若b1变为200，试求新的最优解。;; 5.3 系数矩阵A的分析 以下分4 种情况讨论系数矩阵的变化。 1.增加一个新变量的分析 设xn+1是新增加的变量，其对应的系数列向量为Pn+1，价值系数为Cn+1，试讨论原最优解有无改变？及如何尽快地求出新的最优解。 如果原问题增加一个新变量，则系数矩阵增加一个列，注意到新增加的列在以B为基的单纯形表中应变为B-1Pn+1 ，所以可先计算B-1Pn+1及σn+1=Cn+1-CBB-1Pn+1，若σn+1≤0，则原最优解不变，反之可将B-1Pn+1增填到原最优表的后面，用单纯形法继续迭代。; 解：设生产Ⅲ型计算机x3′台，由原最优基的B-1逆可得： B-1P3′= σ3′=C3′-CBB-1P3′=8-（4，6） 因为σ3′＞0，所以安排生产Ⅲ型计算机有利，将B-1P3′增填到原最优表的后面，并用单纯形法继续计算，结果如下：;第二章 线性规划的对偶理论 与灵敏度分析; 2.增加一个新约束条件的分析 设am+1，1x1+am+1，2x2+‥‥+am+1，nxn≤bm+1是新增加的约束条件，试分析原问题最优解有无变化？