《第2章对偶理论和灵敏度分析第78节.ppt》由会员分享，可在线阅读，更多相关《第2章对偶理论和灵敏度分析第78节.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章对偶理论和灵敏度分析第78节现在学习的是第1页，共51页线性规划问题中某一个或几个系数发生变化显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况 进行处理。现在学习的是第2页，共51页表 2-9下面就各种情况分别按节进行讨论。现在学习的是第3页，共51页7.1 资源数量变化的分析资源数量变化是指资源中某系数br发生变化，即
2、br=br+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，
3、b2-4/0.5=-8，b22/0.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件
4、产品，获利z*=42+33=17(元)从表2.11 看出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
5、的变化，这时(CB+CB)B-1A=CBB-1A+(0,cr,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 技术系
6、数ij的变化 分两种情况来讨论技术系数ij的变化，下面以具体例子来说明。例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页 分析该问题
7、的步骤(2)是：现在学习的是第20页，共51页表 2-13(a)由于b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，说明目标函数值还可以改善。现在学习的是第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为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术
8、系数向量变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?现在学习的是第24页，共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表明原问题和对偶问题的解都是可
9、行解。所以表中的结果已是最优解。即应当生产产品，3.2单位；生产产品，0.8单位。可获利15.2元。注注意意：若若碰碰到到原原问问题题和和对对偶偶问问题题均均为为非非可可行行解时，就需要引进人工变量后重新求解。解时，就需要引进人工变量后重新求解。现在学习的是第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
10、。现在学习的是第29页，共51页表 2-16将表2-16的x1变换为基变量，替换x1，得表2-17。现在学习的是第30页，共51页表 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
11、为换出变量。经基变换运算后，得到表2-19的上表。在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19的下表。现在学习的是第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列列出出现现某某负负值值时时，则以它对应的变量为换出变量；用对偶单纯形法迭代用对偶单纯形法迭代。若若在在检检验验数数行行出出现现某某正正值值
13、时时，则将它对应的变量为换入变量；用单纯形法迭代用单纯形法迭代。现在学习的是第38页，共51页(4)在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复步骤(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
14、页，共51页 当 t 增大，在40，即0t9/7时，为最优解(2,6,2,0,0)T；当 t 继续增大，t(3/2)/(7/6)=9/7时，在检验数行首先出现40；表示还可以继续改进。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
15、，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页