第2章对偶理论和灵敏度分析-第7,8节

1、第7节 灵敏度分析 以前讨论线性规划问题时，假定aij, bi, cj都是常数。但实际上这些系数往往是估计值和预测值。 如市场条件一变，cj值就会变化；aij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。 因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。线性规划问题中某一个或几个系数发生变化 显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算

2、，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况 进行处理。表 2-9下面就各种情况分别按节进行讨论。 7.1 资源数量变化的分析 资源数量变化是指资源中某系数br发生变化，即br=br+br。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB= B-1(b+b) 这里b=(0,，br,0,，0)T。只要XB0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB为新的最优解。新的最优解的值

3、可允许变化范围用以下方法确定。B-1 是最终计算表中的最优基的逆mrirrrrmrrirrrrraaabbabababBbBbBbBbBbbB111111110000)(b列的元素变化0min0maxiririiriririiaabbaab例如求第1章例1中第二个约束条件b2的变化范围。 解：可以利用第1章例1的最终计算表中的数据：可计算b2：0008/12/14/12440008/12/112/1204/102440022211bbbBbB由上式，可得 b2-4/0.25=-16，b2-4/0.5=-8，b22/0.125=16。所以b2的变化范围是-8，16；显然原b2 =16，加它的变化

4、范围后，b2的变化范围是8，32。例7 从表1-5得知第1章例1中，每设备台时的影子价格为1.5元，若该厂又从其他处抽调4台时用于生产产品，。求这时该厂生产产品，的最优方案。 解 先计算B-1b,将结果反映到最终表1-5中，得表2-10。2800040125. 05 . 015 . 02025. 001bB由于表2-10中b列有负数，故用对偶单纯形法求新的最优解。计算结果见表2-11。 表2-11 即该厂最优生产方案应改为生产4件产品，生产3件产品，获利 z*=42+33=17(元) 从表2.11 看出x3=2，即设备还有2小时未被利用。7.2 目标函数中价值系数cj的变化分析分别就cj对应的

5、非基变量和基变量两种情况讨论。(1) 若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是 j=cj-CBB-1Pj 或 当cj变化cj后，要保证最终表中这个检验数仍小于或等于零，即j=cj+cj-CBB-1Pj0那么cj+cjYPj，即cj的值必须小于或等于YPj-cj，才可以满足原最优解条件，确定cj的范围。 miiijjjyac1(2) 若cr是基变量xr的系数。因crCB，当cr变化cr时，就引起CB的变化，这时(CB+ CB)B-1A= CBB-1A+(0, cr ,0) B-1A= CBB-1A+cr (ar1,ar2,arn) cr 可变化的范围 0min0maxrjrj

6、jjrrjrjjjaacaanjacaacarjjrrjrjjrrj, 2 , 1;, 0当;, 0当例8 试以第1章例1的最终表表1-5为例。设基变量x2的系数c2变化c2，在原最优解不变条件下，确定c2的变化范围。解解 这时表1-5最终计算表便成为表2-12所示。 若保持原最优解，从表2-12的检验数行可见应有 由此可得c2-3 和c21。 c2的变化范围为 -3c21 即x2的价值系数c2可以在0，4之间变化，而不影响原最优解。 0818025 . 122cc和7.3 技术系数ij的变化 分两种情况来讨论技术系数ij的变化，下面以具体例子来说明。 例9 分析在原计划中是否应该安排一种新产

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

8、 将x3作为换入变量，x5作为换出变量，进行迭代，求出最优解。表2-13(b) 计算结果见表2-13(b)，这时得最优解： x1=1，x2=1.5，x3=2 总的利润为16.5元，比原计划增加了2.5元。 例10 分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术系数向量变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响? 解 把改进工艺结构的产品看作产品，设x1为其产量。于是在原计算的最终表中以x1代替x1，计算对应x1的列向量。375. 05 . 025. 12520125. 05 . 015 . 02025

9、. 0011PB同时计算出x1的检验数为 c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1的列向量位置。得表2-14。表 2-14可见x1为换入变量，x1为换出变量，经过迭代。得到表2-15 表 2-15 表2-15表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品，3.2单位；生产产品，0.8单位。可获利15.2元。 注意：若碰到原问题和对偶问题均为非可行注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。解时，就需要引进人工变量后重新求解。例11 假设例10的产品的技术系数向量变为P

10、1=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案? 解解 方法与例10相同，以x1代替x1，并计算列向量375. 15 . 325. 12540125. 05 . 015 . 02025. 0011PBx1的检验数为c1-CBB-1P1=4-（1.5,0.125,0)(4,5,2)T = -2.625。将这些数字填入最终表1-15的x1列位置，得到表2-16。表 2-16将表2-16的x1变换为基变量，替换x1，得表2-17。 表 2-17从表2-17可见原问题和对偶问题都是非可行解。于是引入人工变量引入人工变量x x6 6。 因在表2-17中x2所在行，用方程表示时为

11、 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。表 2-18 这时可按单纯形法求解。 X4为换入变量，x6为换出变量。经基变换运算后，得到表2-19的上表。 在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19的下表。表 2-19 除以上介绍的几项分析以外，还可以作增减约束条件等分析。留给读者自己考虑。此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品，0.667单位；产品，2.667单位，可得最大利润10

12、.67元。 第第8 8节节* * 参数线性规划参数线性规划 灵敏度分析时，主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。 而参数线性规划是研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这个参变量的线性函数，含这个参变量的约束条件是线性等式或不等式。 因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题。其步骤是： (1) 对含有某参变量t的参数线性规划问题。先令t=0，用单纯形法求出最优解； (2) 用灵敏度分析法，将参变量t直接反映到最终表中； (3) 当参变量t连续变大或变小时，观察b列和检验数行各数字的

13、变化。若在若在b b列出现某负值时列出现某负值时，则以它对应的变量为换出变量；用对偶单纯形法迭代用对偶单纯形法迭代。若在检验数行出现某正值时若在检验数行出现某正值时，则将它对应的变量为换入变量；用单纯形法迭代用单纯形法迭代。 (4) 在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复步骤(3)，直到b列不能再出现负值，检验数行不能再出现正值为止。8.1 8.1 参数参数c c的变化的变化 例12 试分析以下参数线性规划问题。当参数t0时的最优解变化。0,18231224)5()23()(max21212121xxxxxxxtxttz解 将此模型化为标准型0,18231224)(0)5(

14、)23()(max54321521423154321xxxxxxxxxxxxxxxxtxttz令t=0，用单纯形法求解的结果，见表2-20。将c的变化直接反映到最终表2-20中，得表2-21。计算t的变化范围 当 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。 当t继续增大t(5/2)/(1/2)=5时，在检验数行首先出现50，在50，即9/7t5时，最优解(4,3,0,6

15、,0)T。 t=5为第二临界点。当t5时，50，这时x5作为换入变量，用单纯形法迭代一步，得表2-23。t 继续增大时，在检验数行恒有2，30，故当t5时，最优解为(4，0，0，12，6)T。8.2 8.2 参数参数b b的变化分析的变化分析例13 分析以下线性规划问题，当t0时，其最优解的变化范围。 0,6263max21212121xxtxxtxxxxz解解 将上述模型化为标准型0,626)(03max43214213214321xxxxtxxxtxxxxxxxz令t=0，用单纯形法迭代两次，求解的结果，见表2-24。 将此计算结果反映到最终表2-24，得表2-25。 在表2-25中进行分析，当t增大至t2时，则b0；即0t2时，最优解为 (2-t,4,0,0)T。当t2时，则b10；故将x1作为换出变量，用对偶单纯形法迭代一步，得表2-26 结论 从表2-26可见，当t6时，问题无可行解； 当2t6时，问