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

《线性规划问题的灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章线性规划问题的灵敏度分析(又称为后优化分析)线性规划是静态模型参数发生变化，原问题的最优解还是不是最优哪些参数容易发生变化:C,b,A每个参数发生多大的变化不会破坏最优解灵敏度越小，解的稳定性越好5.1灵敏度分析的概念与内容灵敏度分析概念：(1)当线性规划有关参数和条件发生变化时，分析其最优基/最优解/最优值的变化情况；(2)分析线性规划相关参数和条件在什么范围内变化，其最优基/最优解/最优值不变。灵敏度分析内容：(1)参数Cj,bi,aij的影响分析;(2)增加约束或变量的影响分析；25.2灵敏度分析工具与原理Pj’=B-1Pjb’=B-1bσj=Cj-CBB-1Pj=C

2、j-CBPj’Z0=CBTB-1b=CBb’（LP）最优基保持不变σj≤0b’≥0(1)灵敏度分析工具(2)灵敏度分析原理3(3)分析结论原问题对偶问题结论或继续计算的步骤可行可行仍为最优解可行不可行迭代求出最优（单纯形法）不可行可行迭代求出最优（对偶单纯形法）不可行不可行引入人工变量，编制新单纯形表进行求解45.3价值系数cj的灵敏度分析cj变动可能由于市场价格的波动，或生产成本的变动cj的灵敏度分析是在保证最优基变量不变的情况下，分析cj允许的变动范围cjcj的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非

3、基变量检验数（1）非基变量对应的价值系数的灵敏度分析5例5.16（2）基变量对应的价值系数的灵敏度分析由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数只有一个基变量的cj发生变化，变化量为cj令cj在CB中的第k行，研究非基变量xj机会成本的变化不考虑ark=0的情况，因为当ark=0时，cj的变化不影响zk，同时因为基变量检验数始终为0，不考虑其变化。7设x4的价值系数增加c4，对应k=2（第二行）有一边为空集如何处理为什么akj=0不出现在任何一边的集合中与对偶单纯型法找入变量的公式一样8试求价值系数变化范围为多少时原问题最优解不变9上例题的最

4、优单纯形表为：10约束条件右端项bi的变化在实际问题中反映为可用资源数量的变化。由对偶单纯形法可看出b变化反映到最终单纯形表上将引起右边系数列数字的变化,结论可能出现第一或第三的两种情况。出现第一种情况时，问题的最优基不变，变化后的b列值为最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解。原问题对偶问题结论或继续计算的步骤可行可行仍为最优解可行不可行迭代求出最优（单纯形法）不可行可行迭代求出最优（对偶单纯形法）不可行不可行引入人工变量，编制新单纯形表进行求解5.4右端项bi的灵敏度分析11设XB=B1b是最优解，则有XB=B1b0b的变化不会影响检验数b的变化量

5、b可能导致原最优解变为非可行解121314以b2为例,x6是对应的初始基变量，所以有15试求右边系数变化范围为多少时原问题最优基不变16上例题的最优单纯形表为：175.6新增决策变量的分析若新增产品x6，问是否生产？已知c6=4,p6=(2,4,5)计算x6的检验数可知生产是否有利185.7技术系数aij的变化约束矩阵A随之变化若xj在最终表中为非基变量，其约束条件中系数aij的变化分析步骤参考增加一个变量时的情形若xj在最终表中为基变量，则aij的变化将使相应的基矩阵B和B-1发生变化，可能出现原问题和对偶问题均为非可行解的情况，需引进人工变量将原问题化为可行解，再用单纯形法1

6、9例3分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品Ⅰ的工艺结构有了改进，这时有关它的技术系数向量变为P1′=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?原问题最优单纯形表如下：20x1′的检验数为c1′-CBB-1P1′=4-(1.5,0.125,0)(2,5,2)T=0.375解把改进工艺结构的产品Ⅰ看作产品Ⅰ′，设x1′为其产量。参照增加一个变量时的计算步骤21可见x1′为换入变量，x1为换出变量，替换后，不再保留x1列，经过迭代，得到反映到最终单纯形表中22找新的最优解：23表明原问题和对偶问题的解都是可行解。所以表中的结果

7、已是最优解。即应当生产产品Ⅰ′，3.2单位；生产产品Ⅱ，0.8单位。可获利15.2元。注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。24例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。反映到最终表中，得到25x1′变换为基变量，替换x1，得26可见原问题和对偶问题都