灵敏度分析(运筹学)课件.ppt

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

1、第五节灵敏度分析大连海事大学交通运输管理学院2.5.1单纯形法的矩阵描述2.5.2图解法灵敏度分析2.5.3单纯形法灵敏度分析第五节灵敏度分析在单纯形法的迭代中，我们注意到，迭代过程中主要应用了矩阵的行变换，如在某一行上乘以一个不等于0的乘数k,或在某一行上乘以常数k加到另一行上。这种迭代过程相当于左乘一个相应的初等阵，而初等阵及其乘积为可逆矩阵。因此，约束方程系数矩阵的迭代实际上相当于左乘相应的可逆矩阵。2.5.1单纯形法的矩阵描述Cj→x1x2x3x4XBbCB11101201230034x3x400cj-zj23001/201-1/21/2101

2、/2x3x212cj-zj1/200-3/203102-101-11x1x221cj-zj00-1-1232.5.1单纯形法的矩阵描述1.约束方程系数矩阵的变化约束方程系数矩阵，进行初等行变换，相当于左乘一个相应的初等阵。即，在A中所包含的矩阵B，左乘后，则得到。2.约束方程右端项的变化3.目标函数系数的变化由，得，两边左乘基变量的目标函数系数，得到与得到2.5.1单纯形法的矩阵描述用单纯形表表示如下：XS=bBNEXB=b'EN'B-1初始表XBXNXScj-zj0,······,0'N'S最终表XBXNXScj-zjBN0,······,0

3、表中，b'=B-1bN'=B-1N或者Pj'=B-1PjN'=CN-CBB-1N或者j'=Cj-CBB-1PjS'=-CBB-1········--第2章对偶问题----7--练习：用单纯形法解目标规划问题时，有如下二个单纯形表，试求括弧中未知数a~l的值。x1x2x3x4XBb(b)(c)(d)10-13(e)01(a)1-20061x4x5cj-zjXBbx1x2x3x4x5x1x5cj-zj···x5(g)2-11/20(h)(i)11/2107(j)(k)(l)(f)4以前讨论线性规划问题时，假定αij，bi,cj都是常数。但实际上这些系

4、数往往是估计值和预测值。如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。因此，所谓灵敏度分析，是指当线性规划问题中的参数发生变化后，引起最优解如何改变的分析。2.5.2图解法灵敏度分析例子用图解法求得的最优解为Q（4，2）点。即生产甲产品4件，乙产品2件。考虑目标函数系数变化对例题中最优产量解有什么影响。甲产品的利润为2元，乙产品的利润为3元，如果其中一种产品的利润增加，公司就会增加该产品的产量，如果其中一

5、种产品的利润减少，公司就会减少该产品的产量。但问题是，利润变化多少时，管理者才应该决定改变产量呢？每个目标函数都有一个最优范围，目标函数系数在此范围内变化，模型最优解保持不变。下面用图解法求解这个最优范围。1.目标函数系数的变化只要目标函数直线的斜率处于直线x1+2x2=8与直线4x1=16的斜率之间，Q2点就仍然是最优解的点。目标函数直线的斜率z=c1x1+c2x2的斜率-c1/c2小于等于-0.5如果甲产品的单位利润不变，乙产品的单位利润改变，可得甲产品的利润范围c1≥1.5.同理，乙产品的利润最优范围0≤C2≤4。当两个系数C1、C2都改变时，我

6、们仍然可以用目标函数斜率的变化范围来确定最优解是否改变。由于系数的改变，最优值z可能发生变化而不再是原值了。2、约束条件右端值的变化约束条件右端值每增加一个单位引起的最优值的改进量称为对偶价格。对偶价格只适用于在右端值仅发生了很小变动的情况在其他系数不变的情况下，一些参数在一定范围内变化最优解不变。但是如果一些参数的变化较大，最优解就可能发生变化。这样就要问：这些参数在什么范围内变化时，问题的最优基（或最优解）不变，或者当这些参数中的一个或几个发生变化时，问题的最优解会有何变化。这就是灵敏度分析要研究解决的问题。2.5.3单纯形法灵敏度分析当某一个参数

7、发生变化后，引起最优解如何改变的分析。可以改变的参数有：bi——约束右端项的变化，通常称资源的改变；cj——目标函数系数的变化，通常称市场条件的变化；pj——约束条件系数的变化，通常称工艺系数的变化；其他的变化有：增加一种新产品、增加一道新的工序等。1.灵敏度分析的概念：（1）借助最终单纯形表将变化后的结果按下述基本原则反映到最终表里去。①bi变化：（b+△b）´=B-1（b+△b）=B-1b+B-1△b=b´+B-1△b②pj变化：（pj+△pj）´=B-1（pj+△pj）=B-1pj+B-1△pj=pj´+B-1△pj③cj变化：直接反映到最终表中

8、，计算检验数。④增加一个约束方程：直接反映到最终表中。⑤增加新产品：仿照pj变化。2．分析原理