第2章对偶理论和灵敏度分析第78节课件.ppt

《第2章对偶理论和灵敏度分析第78节课件.ppt》由会员分享，可在线阅读，更多相关《第2章对偶理论和灵敏度分析第78节课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章对偶理论和灵敏度分析第78节第1页，此课件共51页哦线性规划问题中某一个或几个系数发生变化显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况 进行处理。第2页，此课件共51页哦表 2-9下面就各种情况分别按节进行讨论。第3页，此课件共51页哦7.1 资源数量变化的分析资源数量变化是指资源中某系数br发生变化，即br=br+

2、br。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB=B-1(b+b)这 里 b=(0,，br,0,，0)T。只 要XB0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB为新的最优解。新的最优解的值可允许变化范围用以下方法确定。第4页，此课件共51页哦B-1 是最终计算表中的最优基的逆第5页，此课件共51页哦b列的元素变化第6页，此课件共51页哦例如求第1章例1中第二个约束条件b2的变化范围。解：可以利用第1章例1的最终计算表中的数据：第7页，此课件共51页哦可计算b2：由上式，可得 b2-4/0.25=-16，b2-4/0.5=-8，b22/0

3、.125=16。所以b2的变化范围是-8，16；显然原b2=16，加它的变化范围后，b2的变化范围是8，32。第8页，此课件共51页哦例7 从表1-5得知第1章例1中，每设备台时的影子价格为1.5元，若该厂又从其他处抽调4台时用于生产产品，。求这时该厂生产产品，的最优方案。第9页，此课件共51页哦 解 先计算B-1b,将结果反映到最终表1-5中，得表2-10。第10页，此课件共51页哦由于表2-10中b列有负数，故用对偶单纯形法求新的最优解。计算结果见表2-11。表2-11第11页，此课件共51页哦即该厂最优生产方案应改为生产4件产品，生产3件产品，获利z*=42+33=17(元)从表2.11

4、 看出x3=2，即设备还有2小时未被利用。第12页，此课件共51页哦7.2 目标函数中价值系数cj的变化分析分别就cj对应的非基变量和基变量两种情况讨论。(1)若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是 j=cj-CBB-1Pj 或 当cj变化cj后，要保证最终表中这个检验数仍小于或等于零，即j=cj+cj-CBB-1Pj0那么cj+cjYPj，即cj的值必须小于或等于YPj-cj，才可以满足原最优解条件，确定cj的范围。第13页，此课件共51页哦(2)若cr是基变量xr的系数。因crCB，当cr变化cr时，就引起CB的变化，这时(CB+CB)B-1A=CBB-1A+(0,c

5、r,0)B-1A=CBB-1A+cr(ar1,ar2,arn)第14页，此课件共51页哦cr 可变化的范围 第15页，此课件共51页哦例8 试以第1章例1的最终表表1-5为例。设基变量x2的系数c2变化c2，在原最优解不变条件下，确定c2的变化范围。解解 这时表1-5最终计算表便成为表2-12所示。第16页，此课件共51页哦若保持原最优解，从表2-12的检验数行可见应有由此可得c2-3 和c21。c2的变化范围为-3c21即x2的价值系数c2可以在0，4之间变化，而不影响原最优解。第17页，此课件共51页哦7.3 技术系数ij的变化 分两种情况来讨论技术系数ij的变化，下面以具体例子来说明。例

6、9 分析在原计划中是否应该安排一种新产品。以第1章例1为例。设该厂除了生产产品，外，现有一种新产品。已知生产产品，每件需消耗原材料A，B各为6kg，3kg，使用设备2台时；每件可获利5元。问该厂是否应生产该产品和生产多少?第18页，此课件共51页哦解解 分析该问题的步骤是：(1)设生产产品为x3台，其技术系数向量P3=(2,6,3)T，然后计算最终表中对应x3的检验数3=c3-CB-13 =5-(1.5,0.125,0)(2,6,3)T =1.250说明安排生产产品是有利的。第19页，此课件共51页哦 分析该问题的步骤(2)是：第20页，此课件共51页哦表 2-13(a)由于b列的数字没有变化

7、，原问题的解是可行解。但检验数行中还有正检验数，说明目标函数值还可以改善。第21页，此课件共51页哦分析该问题的步骤(3)是：(3)将x3作为换入变量，x5作为换出变量，进行迭代，求出最优解。表2-13(b)第22页，此课件共51页哦 计算结果见表2-13(b)，这时得最优解：x1=1，x2=1.5，x3=2 总的利润为16.5元，比原计划增加了2.5元。第23页，此课件共51页哦例10 分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术系数向量变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?第24页，此课件

8、共51页哦解 把改进工艺结构的产品看作产品，设x1为其产量。于是在原计算的最终表中以x1代替x1，计算对应x1的列向量。同时计算出x1的检验数为 c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1的列向量位置。得表2-14。第25页，此课件共51页哦表 2-14可见x1为换入变量，x1为换出变量，经过迭代。得到表2-15 第26页，此课件共51页哦表 2-15第27页，此课件共51页哦表2-15表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品，3.2单位；生产产品，0.8单位。可获利15.2元。注注意意：若若

9、碰碰到到原原问问题题和和对对偶偶问问题题均均为为非非可可行行解时，就需要引进人工变量后重新求解。解时，就需要引进人工变量后重新求解。第28页，此课件共51页哦例11 假设例10的产品的技术系数向量变为P1=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案?解解 方法与例10相同，以x1代替x1，并计算列向量x1的检验数为c1-CBB-1P1=4-（1.5,0.125,0)(4,5,2)T=-2.625。将这些数字填入最终表1-15的x1列位置，得到表2-16。第29页，此课件共51页哦表 2-16将表2-16的x1变换为基变量，替换x1，得表2-17。第30页，此课件共51

10、页哦表 2-17从表2-17可见原问题和对偶问题都是非可行解。于是引入人工变量引入人工变量x x6 6。第31页，此课件共51页哦因在表2-17中x2所在行，用方程表示时为0 x1+x2+0.5x3-0.4x4+0 x5=-2.4引入人工变量x6后，便为-x2-0.5x3+0.4x4+x6=2.4将x6作为基变量代替x2，填入表2-17，得到表2-18。第32页，此课件共51页哦表 2-18第33页，此课件共51页哦这时可按单纯形法求解。X4为换入变量，x6为换出变量。经基变换运算后，得到表2-19的上表。在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19

11、的下表。第34页，此课件共51页哦表 2-19第35页，此课件共51页哦除以上介绍的几项分析以外，还可以作增减约束条件等分析。留给读者自己考虑。此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品，0.667单位；产品，2.667单位，可得最大利润10.67元。第36页，此课件共51页哦第第8 8节节*参数线性规划参数线性规划灵敏度分析时，主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。而参数线性规划是研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这个参变量的线性函数，含这个参变量的约束条件是线性等式或

12、不等式。因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题。其步骤是：第37页，此课件共51页哦(1)对含有某参变量t的参数线性规划问题。先令t=0，用单纯形法求出最优解；(2)用灵敏度分析法，将参变量t直接反映到最终表中；(3)当参变量t连续变大或变小时，观察b列和检验数行各数字的变化。若若在在b b列列出出现现某某负负值值时时，则以它对应的变量为换出变量；用对偶单纯形法迭代用对偶单纯形法迭代。若若在在检检验验数数行行出出现现某某正正值值时时，则将它对应的变量为换入变量；用单纯形法迭代用单纯形法迭代。第38页，此课件共51页哦(4)在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复

13、步骤(3)，直到b列不能再出现负值，检验数行不能再出现正值为止。第39页，此课件共51页哦8.1 8.1 参数参数c c的变化的变化例12 试分析以下参数线性规划问题。当参数t0时的最优解变化。第40页，此课件共51页哦解 将此模型化为标准型第41页，此课件共51页哦令t=0，用单纯形法求解的结果，见表2-20。第42页，此课件共51页哦将c的变化直接反映到最终表2-20中，得表2-21。计算t的变化范围第43页，此课件共51页哦 当 t 增大，在40，即0t9/7时，为最优解(2,6,2,0,0)T；当 t 继续增大，t(3/2)/(7/6)=9/7时，在检验数行首先出现40；表示还可以继续

14、改进。t=9/7为第一临界点。当t9/7时，40，这时x4作为换入变量。用单纯形法迭代一步，得表2-22。第44页，此课件共51页哦 当t继续增大t(5/2)/(1/2)=5时，在检验数行首先出现50，在50，即9/7t5时，最优解(4,3,0,6,0)T。t=5为第二临界点。当t5时，50，这时x5作为换入变量，用单纯形法迭代一步，得表2-23。t 继续增大时，在检验数行恒有2，30，故当t5时，最优解为(4，0，0，12，6)T。第45页，此课件共51页哦8.2 8.2 参数参数b b的变化分析的变化分析例13 分析以下线性规划问题，当t0时，其最优解的变化范围。第46页，此课件共51页哦解解 将上述模型化为标准型第47页，此课件共51页哦令t=0，用单纯形法迭代两次，求解的结果，见表2-24。第48页，此课件共51页哦将此计算结果反映到最终表2-24，得表2-25。第49页，此课件共51页哦在表2-25中进行分析，当t增大至t2时，则b0；即0t2时，最优解为(2-t,4,0,0)T。当t2时，则b10；故将x1作为换出变量，用对偶单纯形法迭代一步，得表2-26 第50页，此课件共51页哦结论从表2-26可见，当t6时，问题无可行解；当2t6时，问题的最优解为 (0，6-t，0，-6+3t)T。第51页，此课件共51页哦