第2章 线性规划(灵敏度分析)精选PPT.ppt

《第2章 线性规划(灵敏度分析)精选PPT.ppt》由会员分享，可在线阅读，更多相关《第2章 线性规划(灵敏度分析)精选PPT.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 线性规划线性规划(灵灵敏度分析敏度分析)第1页，此课件共35页哦知识点知识点熟悉灵敏度分析概念和内容；熟悉灵敏度分析概念和内容；分别掌握限制常数、价值系数、约束条件系分别掌握限制常数、价值系数、约束条件系数的变化对原最优解的影响；数的变化对原最优解的影响；掌握增加新变量和增加新约束条件对原最优掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围。解的影响，并求出相应因素的灵敏度范围。第2页，此课件共35页哦灵敏度分析灵敏度分析问题的提出：问题的提出：系数（系数（aij,bi,cj）往往是估计值和预测值，且不）往往是估计值和预测值，且不是稳定的。是稳定的。当系数

2、中的一个或几个发生变化时，已求得的当系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化？如果最优规划问题的最优解会发生什么变化？如果最优解发生了变化，又怎样用最简便的方法找到新解发生了变化，又怎样用最简便的方法找到新的最优解？解决这些问题就是灵敏度分析的任的最优解？解决这些问题就是灵敏度分析的任务。务。第3页，此课件共35页哦价值系数价值系数c的变化的变化对于对于LP：max Z=CTX S.t.AX=b,X 0当从最终的单纯形表上得到最优基当从最终的单纯形表上得到最优基B时，其时，其最优结果为：最优结果为：(XBT,XRT)=(B-1bT,0T)Max Z=CBTB-1b第

3、4页，此课件共35页哦相应的检验数为：相应的检验数为：=(z-c)=CBTB-1A-C 其中：其中：基变量的检验数为基变量的检验数为0，非基变量的检验数为：非基变量的检验数为：R=CBTB-1R-CRT第第j个为：个为：j=(zj-cj)=CBTB-1Pj-cj第5页，此课件共35页哦(1)非基变量系数非基变量系数cj的变化的变化设设cj=cj+c，则有：，则有：j=CBTB-1Pj-(cj+cj)=j-cj这时，这时，若若 cj j ，原最优解保持不变。，原最优解保持不变。若若 cj j,则原最优解就不再是最优的了，这则原最优解就不再是最优的了，这时要以为时要以为xj换入变量，把最终单纯形表

4、上的换入变量，把最终单纯形表上的 j换换成成 j，cj 换成换成cj，继续迭代，以求最优解。，继续迭代，以求最优解。第6页，此课件共35页哦例：例：P6，例中，最终单纯形表为：，例中，最终单纯形表为：cj4 3 0 0 0CBXBbx1 x2 x3 x4 x5034x5x2x12006002000 0 0.5 -0.4 10 1 1 -0.4 01 0 -0.5 0.4 0 zjzj-cj26004 3 1 0.4 00 0 1 0.4 0 x（剩余工时）的价值系数（剩余工时）的价值系数c4的变化范围为：的变化范围为：00.4。当。当c4的变化超过的变化超过0.4时，就要重新计算。时，就要重新

5、计算。第7页，此课件共35页哦(2)基变量的价值系数基变量的价值系数cl的变化：的变化：这种情形下，这种情形下，cl是是CB的一个分量，当的一个分量，当cl变化变化了了 cl后，就会引起后，就会引起CB改变改变 CB，从而引起，从而引起最终单纯形表中全部非基变量的检验数和目最终单纯形表中全部非基变量的检验数和目标函数值的变化。改变以后的非基变量的检标函数值的变化。改变以后的非基变量的检验数为：验数为：j=(CB+CB)TB-1Pj-cj=j+CBTB-1Pj =j+clalj其中，其中，alj是非基变量是非基变量xj在基变量为在基变量为xl时该行时该行的系数。的系数。第8页，此课件共35页哦若

6、：若：则所有的则所有的 j 0，即最优解不变。，即最优解不变。第9页，此课件共35页哦例：在汽车生产的例子中，如果例：在汽车生产的例子中，如果x2的价值系的价值系数由数由3变成变成3+c2，要使最优解不变，求，要使最优解不变，求 c2的取值范围。的取值范围。第10页，此课件共35页哦1+c2 00.4-0.4 c2 0从而：从而：-1 c2 1cj4 3+c2 0 0 0CBXBbx1 x2 x3 x4 x503+c2 4x5x2x12006002000 0 0.5 -0.4 10 1 1 -0.4 01 0 -0.5 0.4 0 zjzj-cj2600+600c24 3+c2 1+c2 0.

7、4-0.4c2 00 0 1+c2 0.4-0.4c2 0第11页，此课件共35页哦直接按公式：直接按公式：第12页，此课件共35页哦约束方程常数项约束方程常数项b的变化的变化设第设第k个约束方程的右端常数项由原来的个约束方程的右端常数项由原来的bk变为变为bk=bk+bk，其它系数不变。，其它系数不变。设原最优解为：设原最优解为：XB=B-1b=(XB1,XBm)T若原最优基若原最优基B仍是最优的，则新的最优解满足：仍是最优的，则新的最优解满足：XB=B-1b=B-1b+B-1b=XB+bkDk 0式中，式中，Dk是是B-1的第的第k列，有：列，有：Dk=(d1k,dmk)T第13页，此课件

8、共35页哦从而最优解可写成：从而最优解可写成：XBi+bkdik 0因此，因此，bk的允许变动范围是：的允许变动范围是：第14页，此课件共35页哦如果如果 bk超过上述范围，则新得到的解为不超过上述范围，则新得到的解为不可行解。但由于可行解。但由于bk的变化不影响检验数的变化不影响检验数，故，故仍保持所有的检验数仍保持所有的检验数 I 0，即满足，即满足对偶可对偶可行性行性，这时，可在原最优表的基础上，换上，这时，可在原最优表的基础上，换上改变后的常数及相应的改变后的常数及相应的Z值，用对偶单纯形值，用对偶单纯形法迭代，以求出新的最优解。法迭代，以求出新的最优解。第15页，此课件共35页哦例：

9、生产汽车用的钢材由例：生产汽车用的钢材由1600吨变成吨变成1600+b1吨，则问题变为：吨，则问题变为：0.5 -0.4 1 1600+b1 200 0.5 X=B-1b=1-0.40 2500 =600 +1 b1 -0.5 0.4 0 400 200 -0.5 为了使最后的解仍为可行解，应满足各分量为了使最后的解仍为可行解，应满足各分量为正。为正。200+0.5b1 0 600+b1 0 200-0.5b1 0 从而：从而：-400 b1 400第16页，此课件共35页哦根据公式：根据公式：k:B-1的第k列i:第k列的第i个元素第17页，此课件共35页哦如果如果b1=1800；最优解不

10、变，直接求；最优解不变，直接求XB XB=B-1b如果如果b1=2200cj4 3 0 0 0CBXBbx1 x2 x3 x4 x5034x5x2x15001200-1000 0 0.5 -0.4 10 1 1 -0.4 01 0 -0.5 0.4 0 zjzj-cj32004 3 1 0.4 00 0 1 0.4 0第18页，此课件共35页哦用对偶单纯形法求解得用对偶单纯形法求解得cj4 3 0 0 0CBXBbx1 x2 x3 x4 x5030 x5x2x340010002001 0 0 0 12 1 0 0.4 0-2 0 1 -0.8 0 zjzj-cj30006 3 0 1.2 02

11、 0 0 1.2 0第19页，此课件共35页哦技术系数变化的影响技术系数变化的影响当当aij是非基变量的系数时，它的变化不会引是非基变量的系数时，它的变化不会引起起B-1的变化，所以计算相对容易；的变化，所以计算相对容易；当当aij是基变量的系数，它的变化会引起是基变量的系数，它的变化会引起B-1的变化，所以最终单纯形表也要发生变化。的变化，所以最终单纯形表也要发生变化。第20页，此课件共35页哦例：假定生产大轿车所用的钢材由例：假定生产大轿车所用的钢材由2吨吨/辆变成辆变成3吨吨/辆，求最优解的变化。辆，求最优解的变化。解：解：a11由由2变成变成3，x1的系数列向量为：的系数列向量为：B-

12、1P1第21页，此课件共35页哦0.5-0.4131-0.405-0.50.4010.510.5第22页，此课件共35页哦cj4 3 0 0 0CBXBbx1 x2 x3 x4 x5034x5x2x12006002000.5 0 0.5 -0.4 1 1 1 1 -0.4 0 0.5 0 -0.5 0.4 0 cj4 3 0 0 0CBXBbx1 x2 x3 x4 x5034x5x2x102004000 0 1 -0.8 1 0 1 2 -1.2 0 1 0 -1 0.8 0 zjzj-cj22004 3 2 -0.4 0 0 0 2 -0.4 0 行变换行变换(这里并没有进行换基迭代这里并没

13、有进行换基迭代)第23页，此课件共35页哦新的最优解是：新的最优解是：X=(0,800,0,500,400)TZmax=2400cj4 3 0 0 0 CBXBbx1 x2 x3 x4 x5030 x5x2x44008005001 0 0 0 1 1.5 1 0.5 0 0 1.25 0 -1.25 1 0 zjzj-cj24004.5 3 1.5 0 0 0.5 0 1.5 0 0 第24页，此课件共35页哦问题：在前例中，要求保持最优解不变的技术消问题：在前例中，要求保持最优解不变的技术消耗系数的变化范围？耗系数的变化范围？关键：理解技术消耗系数的变化会引起什么发生变，关键：理解技术消耗系

14、数的变化会引起什么发生变，什么不变？什么不变？第25页，此课件共35页哦决策变量增减的分析决策变量增减的分析决策变量的增减，相对于在原约束方程中增决策变量的增减，相对于在原约束方程中增加或减少一个列向量：加或减少一个列向量：B-1Pn+1。在增加一个非负变量在增加一个非负变量xn+1后，相应增加的系后，相应增加的系数列向量为数列向量为Pn+1，目标函数的系数为，目标函数的系数为cn+1，如果原问题的最优基是如果原问题的最优基是B，那么增加这个新，那么增加这个新变量后，对原最优解的可行性没有影响，而变量后，对原最优解的可行性没有影响，而新变量的检验数为：新变量的检验数为：n+1=CBTB-1Pn

15、+1-cn+1第26页，此课件共35页哦如果如果 n+1 0，则原最优解就是新问题的最，则原最优解就是新问题的最优解；优解；如果如果 n+1 0，则原最优解不再是最优解，则原最优解不再是最优解，这时，要把加入到原最终表内，并以新变量这时，要把加入到原最终表内，并以新变量作为换入变量，按单纯形法继续迭代，即可作为换入变量，按单纯形法继续迭代，即可得到新的最优解。得到新的最优解。第27页，此课件共35页哦例：工厂研制出小型旅行车，每辆旅行车用例：工厂研制出小型旅行车，每辆旅行车用钢材钢材1.5吨，工时吨，工时1.25吨，座椅吨，座椅0.25套。利套。利润也是润也是3千元。问新产品该不该投产，生产千

16、元。问新产品该不该投产，生产计划应当如何安排。计划应当如何安排。第28页，此课件共35页哦0.5-0.411.51-0.401.25-0.50.400.250.51-0.25B-1P6=第29页，此课件共35页哦cj4 3 0 0 03CBXBbx1 x2 x3 x4 x5 x6034x5x2x12006002000 0 1 -0.8 2 0.50 1 0 0.4 -2 11 0 0 0 1 -0.25200/2600/1zjzj-cj22004 3 1 0.4 0 20 0 1 0.4 0 -1第30页，此课件共35页哦cj4 3 0 0 03CBXBbx1 x2 x3 x4 x5 x633

17、4x6x2x14002003000 0 1 -0.8 2 10 1 0 0.4 -2 01 0 -0.25 0.2 0.5 0200/0.4300/0.2zjzj-cj30004 3 2 -0.4 2 30 0 2 -0.4 2 0CBXBbx1 x2 x3 x4 x5 x6304x6x4x18005002000 2 1 0 -2 10 2.5 0 1 -5 01 -0.5 -0.25 0 1.5 0zjzj-cj32004 4 2 0 0 30 1 2 0 0 0第31页，此课件共35页哦约束条件增减的分析约束条件增减的分析增加（减少）新的约束条件意味着对某种资增加（减少）新的约束条件意味着

18、对某种资源原来没有限制，现在情况发生了变化，需源原来没有限制，现在情况发生了变化，需要有所限制。要有所限制。第32页，此课件共35页哦例如，发动机的供应量每年只有例如，发动机的供应量每年只有600台，这台，这相当于增加一个约束条件：相当于增加一个约束条件：x1+x2 600加入松驰变量，得：加入松驰变量，得：x1+x2+x7=600因为因为x7是基变量，最终单纯形表中也增加一是基变量，最终单纯形表中也增加一列和一行。见下表：列和一行。见下表：第33页，此课件共35页哦cj4 3 0 0 0 0CBXBbx1 x2 x3 x4 x5 x70340 x5x2x1x72006002006000 0

19、0.5 -0.4 1 00 1 1 -0.4 0 01 0 -0.5 0.4 0 01 1 0 0 0 1cj4 3 0 0 0 0CBXBbx1 x2 x3 x4 x5x70340 x5x2x1x7200600200-2000 0 0.5 -0.4 1 00 1 1 -0.4 0 01 0 -0.5 0.4 0 00 0 -0.5 0 0 1zjzj-cj26004 3 1 0.4 0 10 0 1 0.4 0 1进行实行初等行变换，得：进行实行初等行变换，得：第34页，此课件共35页哦cj4 3 0 0 03CBXBbx1 x2 x3 x4 x5x70340 x5x2x1x302004004000 0 0 -0.4 1 00 1 0 -0.4 0 21 0 0 0.4 0 -10 0 1 0 0 -2zjzj-cj22004 3 0 0.4 0 20 0 0 0.4 0 2新的最优解是：新的最优解是：X=(400,200,400,0,0)TZmax=2200第35页，此课件共35页哦