7灵敏度分析.ppt

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

1、3.5.5灵敏度分析一、灵敏度分析的含义和内容1、什么是灵敏度分析？研究线性规划模型某些参数（A,b,c）或限制量(x,约束条件)的变化对最优解的影响及其程度的分析过程称为灵敏度分析或（优化后分析）。2、灵敏度分析的内容：目标函数的系数c变化对最优解的影响；约束方程右端系数b变化对最优解的影响；约束方程组系数阵A变化对最优解的影响；回答两个问题：①这些系数在什么范围内发生变化时，最优基不变（即最优解或最优解结构不变）？②系数变化超出上述范围时，如何用最简便的方法求出新的最优解？两个问题cTcBTcNTcsTcB

2、xBbxBTxNTxSTcsxSbBNIz0cBTcNT0TcTcBTcNTcsTcBxBbxBTxNTxSTcBxBB-1bB-1BB-1NB-1IzcBTB-1b0TcBTB-1N-cNTcBTB-1初始单纯形表最优单纯形表二、进行灵敏度分析的基本原则1、在最优表格的基础上进行；2、尽量减少附加计算工作量；三、灵敏度分析的步骤:将参数的改变通过计算反映到最终单纯形表上来.检查是否仍为原问题的可行解.检查是否仍为对偶问题的可行解.4.依据不同情况决定继续计算或得到结论.原问题对偶问题结论或继续计算的步骤可行解可行解

3、非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算原问题和对偶问题同时可行时，同时达到最优主要内容一.分析cj的变化二.分析bj的变化一.分析cj的变化cTcBTcNTcsTcBxBbxBTxNTxSTcBxBB-1bB-1BB-1NB-1IzcBTB-1b0TcBTB-1N-cNTcBTB-1c仍为最优解，但最优值可能已变不是最优解，用单纯形法继续迭代将cj看作待定参数，令解这n-m个不等式，可算出保持最

4、优解不变时cj的变化范围！（1）当cj是非基变量的价值系数——它的变化只影响一个检验数（2）当cj是基变量的价值系数——它的变化将影响所有非基变量的检验数例3.20给定线性规划问题试讨论c1,c2,c3分别在什么范围内变化时，最优解不变？最优表1-1/301/30-2/31/3020011602/311/301/313/30-40-10-2-17x5x1x3二.分析bj的变化cTcBTcNTcsTcBxBbxBTxNTxSTcBxBB-1bB-1BB-1NB-1IzcBTB-1b0TcBTB-1N-cNTcBTB-1

5、b仍为最优解，但最优解、最优值可能已变是正则解，用对偶单纯形法继续迭代①保持B-1b≥0,当前的基仍为最优基，最优解的结构不变（取值改变）；②（B-1b）i<0,当前基为非可行基,但是仍保持为对偶可行基，可用对偶单纯形法求出新的最优解；③如何求出保持最优基不变的bi的范围?把bi看作待定参数,令B-1b≥0,求解该不等式组即可；例3.21给定线性规划问题试讨论b1,b2在什么范围内变化时，最优基保持不变？1111063011110-30-1-20-12x2x5最优表作业P14820§3.5.3退化与循环例：退化与循环

6、的问题在非退化情形下，用单纯形方法经过有限次迭代一定可达到最优解。在退化情形下，用单纯形方法进行迭代可能得不到最优解。基迭代经过若干次后又回到先前的可行基B1B2...B1循环为避免循环，伯兰特(Bland)规则：1.当存在多个，始终选取下标值为最小的变量作为进基变量。2.当出现两个以上相同的最小比值时，始终选取下标值为最小的变量为离基变量3.3.2摄动法四个定理利用单纯形法求解摄动问题时，不会出现循环现象。判别数相同通过求解摄动问题，能给出原问题的解。两个问题：怎样找到摄动问题的初始基本可行解?如何处理?基列下标小

7、于非基列下标进行列调换，把基列排在非基列的左边，并相应地改变变量的下标，使其从1开始按递增顺序排列。问题1的解决方案：问题2的解决方案(确定主行)：摄动法与一般单纯形法的差别主要在于主行的选择。