线性规划问题的灵敏度分析.ppt

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