《灵敏度分析(第三章线性规划).ppt》由会员分享，可在线阅读，更多相关《灵敏度分析(第三章线性规划).ppt（46页珍藏版）》请在三一文库上搜索。
1、一、灵敏度分析概述,Max f =CX AX=b X 0,系数矩阵A、约束条件右端项b和价值系数C给定以后，这个线性规划问题就确定了。,1. 当这些系数中的一个或几个发生变化时，已求得的最优解 会有什么变化； 2. 这些系数在什么范围内变化时，线性规划问题的最优解或 最优基不变； 3. 若最优解变化，如何用最简便的方法找到新的最优解。,为了回答这些问题，可以在变化了的条件下重新求解线性规划问题。但是这样做太麻烦，也不必要。本节的目的是讲，如何在已经得到的最优解的基础上，进行适当的修改计算，即可回答上面的问题。这就是灵敏度分析的基本内容。,二、灵敏度分析的定义,灵敏度分析就是研究cj、bi、ai
2、j等参数在什么范围内变化时最优解不变，若最优解发生变化，如何用简便的方法求出新的最优解。,三、灵敏度分析的内容,价值系数cj的变化的分析 约束条件右端项bi变化的分析 系数矩阵A变化的分析 系数列向量Pk变化的分析 增加新约束条件的分析 增加新变量的分析,实例1,实例1的数学模型,设产品A、B、C 的产量分别为x1、x2、x3，则该问题的数学模型为：,用单纯形法求解结果,1.价值系数cj变化的分析,cj 变动可能由于市场价格的波动，或生产成本的变动。,cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围。,cj 的变化会引起检验数的变化，有两种情况：,非基变量对应的价
3、值系数变化，不影响其它检验数,基变量对应的价值系数变化，影响所有非基变量检验数,1.1非基变量 对应的价值系数c3的变化,在实例1中，分析产品丙的利润C3的变化对最优解的影响。,由上表可知：当C3-8 0 ，即 0 C38时，最优解不变。,5 8 6 0 0,5 8,C3,C3-8,1.2基变量对应价值系数变化,(1)基变量对应的价值系数C1的变化,5 8 6 0 0,5 8,C1,C1,-2 8-2C1 C1-8 -(64+4C1),由上表可知：当 8-2C1 0 ，同时 C1-8 0 ， 即 4 C18时，最优解不变。,(2)基变量对应的价值系数C2的变化,5 8 6 0 0,5 8,C2
4、,C2,6-C2 C2-10 5-C2 -(20+8C2),由上表可知：当 6-C2 0 ， C2-10 0，同时 5-C2 0 ， 即 6 C210时，最优解不变。,价值系数cj变化的分析总结,cj 的变化会引起检验数的变化，有两种情况：,（1）非基变量对应的价值系数变化，不影响其它检验数,（2）基变量对应的价值系数变化，影响所有非基变量检 验数。,要使原来的最优解不变，新的检验数均0,2.约束条件右端项bi变化的分析(1),设XB=B1b是最优解，则有XB=B1b 0 b的变化不会影响检验数 b的变化量b可能导致原最优解变为非基可行解,设b=b+ b,为保证最优基不变，必须满足XB=B-1
5、b 0,16 20,12 4 -92,1. 分析b1=16和b2=20时，最优基和最优解的变化,当b1=16,b2=20时， 最优基不变， 最优解变为：x1=12，x2=4,结论,22 20,24 -2,2. 分析b1=22和b2=20时，最优基和最优解的变化,5 8,0 0,-104,当b1=22,b2=20时， 最优基改变，最优解变为： x1=20，x4=2,结论,解之得：10b120,即:当10b120时，最优基不变,保持b2=20,分析b1在什么范围内 变化时，最优基不变?,b1 20,2b1-20 -b1+20 ?,5 8,0 0,解之得：12b224,即:当12b224时，最优基不
6、变,保持b1=12,分析b2在什么范围内 变化时，最优基不变?,12 b2,24-b2 -12+b2 ?,5 8,0 0,练习,最优单纯形表为：,求： （1）b1、b2的值； （2）对偶问题的最优解； （3）表中f、g、h、d、e的值； （4）在不破坏最优基的情况下，能否单独增加b1、b2来增加目标函数f的值，最多能增加到多少？,3.系数矩阵A变化的分析,系数矩阵A变化的分析包括 系数列向量Pk变化的分析 增加新约束条件的分析 增加新变量的分析,3.1系数列向量Pk变化的分析,在初始单纯形表上，变量xk的系数列向量Pk变为Pk，经过迭代后，在最终单纯形表上， xk是非基变量。这时最终单纯形表上
7、xk的系数列就变成B-1 Pk。新的判别数为,若 ，原最优解不变； 若 ，则最优解改变，继续迭代可以求出新的最优解。,实例1,在实例1中，假设产品C 的资源消耗量由 变为 ，试分析最优解的变化情况。,所有的判别数都非正，故最优解不变。,2 1,3 -1,5 8 6 0 0,5 8,-1,在实例1中，假设产品C 的资源消耗量由 变为 ，试分析最优解的变化情况。,判别数有正，故最优解变化。,1 1,1 0,5 8 6 0 0,5 8,1,初始表,最优表,最优单纯形表如下：,3.2 增加新约束条件的分析,用单纯形法求解结果,将原最优解x1=4，x2=8代入上式知，原最优解不满足该约 束条件，因而原最
8、优解不再是增加约束条件以后的最优解。,这个问题相当于在原问题的基础上增加约束条件,在新的约束条件中引入松驰变量x6，则有,将该条件填入最优单纯形表中：,将该单纯形表标准化：,将 填入最优单纯形表中,1 2 2 0 0 1 18,0 0,0,用对偶单纯形方法迭代一次得：,增加约束条件以后的最优解为：,x1=6，x2=6,增加新约束条件的分析总结,1、将最优解代入新的约束条件，若满足，则最优解不变。,2、若不满足，则当前最优解要发生变化；将新增约束条 件加入最优单纯形表，并变换为标准型。,3、利用对偶单纯形法继续迭代。 为什么可以利用对偶单纯形法?,3.3增加新的决策变量的分析,假如要增加一个新的
9、决策变量xn+1，其对应的系数列向量为Pn+1，价值系数为cn+1。在原最优单纯形表中xn+1对应的检验数为,若 ，则原最优解不变。从经济学的观点来看，增加该项活动（或产品）是不利的。,若 ，则原来的最优解不再是最优解，表明增加该活动是有利的。,这时把xn+1对应于原最优基B的系数列向量 加入到原最优表中，并以xn+1作为换入变量按单纯形法进行迭代，即可得到新的最优解。,在实例1中，如果该厂还计划生产一种 新产品D，问生产产品D是否有利？,用单纯形法求解结果,初始表,原最优表变成,5 8 6 0 0 8,5 8,3 -1,1,新的最优解为X=(0 28/3 0 0 0 4/3)T,继续迭代，找
10、到新的最优解,课后习题36(1、2),最优单纯形表：,3 1 4 0 0,0 4,C1,C1-24/5,课后习题36(3),最优单纯形表：,3 1 4 0 0 3,0 4,6 2/5,7/5,课后习题37,最优单纯形表：,10 6 4 0 0 0,6 10 0,C3,C3-20/3,课后习题37（续）,最优单纯形表：,10 6 4 0 0 0,6 10 0,25/3,5/3,课后习题37(续）,10 6 4 0 0 0,6 10 0,0 x7 O 0 - 1 0 0 0 1 -10,X7 0 0 0,0,课后习题37(续）,10 6 4 0 0 0 0,6 10 0 4,作业,线性规划问题 maxf=2X1+3X2+X3 X1+ X2 +X33 X1+3X2 +5X37 X1，X2 ,X20 （1）用单纯形方法求出最优解和最优目标函数值； （2）写出上述问题的对偶问题，并求对偶规划的最优解和最优目标函数值； （3）保持X1的系数C1=2，X3的系数C3=1不变，确定X2的 系数C2的变化范围，使原最优解保持最优； （4）求出要使原来的最优基不变的b1的变化范围， （5）若b13，b2=11，求出新的最优解。,