第4章灵敏度分析(2013使用版)

1、1第第4章章灵敏度分析灵敏度分析杨晓艺 数学建模（公修）2/31主要内容主要内容资源数量变化的分析资源数量变化的分析4.1价值系数变化的分析价值系数变化的分析4.2技术系数变化的分析技术系数变化的分析4.3杨晓艺 数学建模（公修）3/31v 以前讨论线性规划问题时，假定以前讨论线性规划问题时，假定aij ，bi，cj都是常数。但都是常数。但实际上这些系数往往是估计值和预测值。实际上这些系数往往是估计值和预测值。v 如市场条件一变，如市场条件一变，cj值就会变化；值就会变化； aij 往往是因工艺条件往往是因工艺条件的改变而改变；的改变而改变；bi是根据资源投入后的经济效果决定的一是根据资源投入

2、后的经济效果决定的一种决策选择。种决策选择。v 提出两个问题：提出两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。优解或最优基不变。杨晓艺 数学建模（公修）4/31v 系数发生变化是否影响问题的最优解？系数发生变化是否影响问题的最优解？v 如何求解新问题的最优解？是不是必须从头开始如何求解新问题的最优解？是不是必须从头开始计算？计算？v 如何把变化反映到原问

3、题最终的单纯形表上？如何把变化反映到原问题最终的单纯形表上？v 如何继续计算？如何继续计算？杨晓艺 数学建模（公修）5/314.1 4.1 资源数量变化的分析资源数量变化的分析v 资源数量变化是指资源中某系数资源数量变化是指资源中某系数br发生变化，即发生变化，即br=br+br。并假设规划问题的其他系数都不变。这样。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为使最终表中原问题的解相应地变化为XB=B-1(b+b)v 反映到单纯形表中，只有基变量列数字的变化，检验反映到单纯形表中，只有基变量列数字的变化，检验数不改变，若不是最优解则继续用对偶单纯形法求解。数不改变，若不

4、是最优解则继续用对偶单纯形法求解。杨晓艺 数学建模（公修）6/31例例4.1 4.1 求例求例1 1中第二个约束条件中第二个约束条件b2的变化范围。的变化范围。解：例解：例1 1的最终计算表中的数据：的最终计算表中的数据：cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 4 1 0 1 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 -z -14 0 0 -3/2 -1/8 0 杨晓艺 数学建模（公修）7/310008/12/14/12440008/12/112/1204/102440022211bbbBbBb2的

5、变化范围是的变化范围是-8，16, b2的变化范围是的变化范围是8，32。杨晓艺 数学建模（公修）8/31例例4.2 从例从例1中，每设备台时的影子价格为中，每设备台时的影子价格为1.5元，若该厂又从其元，若该厂又从其他处抽调他处抽调4台时用于生产产品台时用于生产产品，。求这时该厂生产产品。求这时该厂生产产品，的最优方案。的最优方案。杨晓艺 数学建模（公修）9/31 解解 先计算先计算B-1b,将结果反映到最终表中，得下表。将结果反映到最终表中，得下表。2800040125. 05 . 015 . 02025. 001bBcj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5

6、2 0 3 x1 x5 x2 4+0 4-8 2+2 1 0 0 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 cj-zj 0 0 -1.5 -0.125 0 杨晓艺 数学建模（公修）10/31由于表中由于表中b列有负数，故用对偶单纯形法求新的最优解。列有负数，故用对偶单纯形法求新的最优解。cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x3 x2 4 2 3 1 0 0 0 0 1 0 1 0 0.25 -0.25 0 0 -0.5 0.25 cj-zj 0 0 0 -0.5 -0.75 杨晓艺 数学建模（公修）11/31v

7、该厂最优生产方案应改为生产该厂最优生产方案应改为生产4件产品件产品，生，生产产3件产品件产品，获利，获利 z*=42+33=17(元元)v从最终表看出从最终表看出x3=2，即设备，即设备还还有有2小时未被利小时未被利用用 杨晓艺 数学建模（公修）12/314.2 目标函数中价值系数目标函数中价值系数cj的变化分析的变化分析1jjBjcC B P 分两种情况：分两种情况： 基变量基变量的价值系数变化的价值系数变化 所有非基变量的检验数重新计算；所有非基变量的检验数重新计算； 非基变量非基变量的价值系数的变化的价值系数的变化 只计算发生变化的非基变量的检验数即可只计算发生变化的非基变量的检验数即可

8、杨晓艺 数学建模（公修）13/31例例4.3 试以例试以例1的最终表为例。设基变量的最终表为例。设基变量x2的系数的系数c2变化变化c2，在原最优解不变条件下，确定在原最优解不变条件下，确定c2的变化范围。的变化范围。0818025 . 122cc和vx2的价值系数的价值系数c2可以在可以在0，4之间变化，而不影响原之间变化，而不影响原最优解。最优解。 杨晓艺 数学建模（公修）14/314.3 技术系数技术系数aij的变化分析的变化分析 例例4.4 分析在原计划中是否应该安排一种新产品。以分析在原计划中是否应该安排一种新产品。以例例1为例。设该厂除了生产产品为例。设该厂除了生产产品，外，现有一

9、种新外，现有一种新产品产品III。已知生产产品。已知生产产品III，每件需消耗原材料，每件需消耗原材料A，B各为各为6kg，3kg，使用设备，使用设备2台时；每件可获利台时；每件可获利5元。问元。问该厂是否应生产该产品和生产多少该厂是否应生产该产品和生产多少?杨晓艺 数学建模（公修）15/31v (1) 设生产产品设生产产品III为为x3台，其技术系数向量台，其技术系数向量P3=(2,6,3)T，然后计算最终表中对应然后计算最终表中对应x3的检验数的检验数3=c3-CB-13=5-(1.5,0.125,0)(2,6,3)T=1.250v 说明安排生产产品说明安排生产产品III是有利的。是有利的

10、。解解杨晓艺 数学建模（公修）16/31杨晓艺 数学建模（公修）17/31cj 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x5 2 0 3 x1 x5 x2 4 4 2 1 0 0 0 0 1 0 2 0.5 0.25 0.5 0.125 0 1 0 1.5 2 0.25 cj-zj 0 0 -1.5 -0.125 0 1.25 由于由于b b列的数字没有变化，原问题的解是可行解。列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，但检验数行中还有正检验数，说明目标函数值还可以改善。说明目标函数值还可以改善。杨晓艺 数学建模（公修）18/31(3) 将将

11、x3作为换入变量，作为换入变量，x5作为换出变量，进行迭代，求作为换出变量，进行迭代，求出最优解。计算结果见下表，这时得最优解：出最优解。计算结果见下表，这时得最优解：x1=1,x2=1.5，x3=2。总的利润为。总的利润为16.5元。比原计划增元。比原计划增加了加了2.5元。元。杨晓艺 数学建模（公修）19/31杨晓艺 数学建模（公修）20/31 例例4.5 分析原计划生产产品的工艺结构发生变化。仍分析原计划生产产品的工艺结构发生变化。仍以例以例1为例，若原计划生产产品为例，若原计划生产产品的工艺结构有了改进，的工艺结构有了改进，这时有关它的技术系数向量变为这时有关它的技术系数向量变为P1=

12、(2,5,2)T，每件利，每件利润为润为4元，试分析对原最优计划有什么影响元，试分析对原最优计划有什么影响? 杨晓艺 数学建模（公修）21/31解解 把改进工艺结构的产品把改进工艺结构的产品看作产品看作产品，设，设x1为其为其产量。于是在原计算的最终表中以产量。于是在原计算的最终表中以x1代替代替x1，计算对，计算对应应x1的列向量。的列向量。375. 05 . 025. 12520125. 05 . 015 . 02025. 0011PB同时计算出同时计算出x1的检验数为的检验数为c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表将以上计

13、算结果填入最终表x1的列向量位置的列向量位置.杨晓艺 数学建模（公修）22/31cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4 4 2 1.25 0.5 0.375 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 cj-zj 0.375 0 -1.5 -0.125 0 可见可见x1为换入变量，为换入变量，x1为换出变量为换出变量，经过迭代。得到表，经过迭代。得到表杨晓艺 数学建模（公修）23/31cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 3 x1 x5 x2 3.2 2.4

14、0.8 1 0 0 0 0 1 0 -2 0.5 0.2 0.4 0.2 0 1 0 cj-zj 0 0 -1.5 -0.2 0 杨晓艺 数学建模（公修）24/31v 表明原问题和对偶问题的解都是可行解。所以表中的表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品结果已是最优解。即应当生产产品，3.2单位；生产单位；生产产品产品，0.8单位。可获利单位。可获利15.2元。元。v 注意：若碰到原问题和对偶问题均为非可行解时，就注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。需要引进人工变量后重新求解。杨晓艺 数学建模（公修）25/31例例4.6

15、 4.6 假设例假设例4.54.5的产品的产品的技术系数向量变为的技术系数向量变为P P1 1=(4,5,2)=(4,5,2)T T，而每件获利仍为，而每件获利仍为4 4元。试问该厂应如何安排最元。试问该厂应如何安排最优生产方案优生产方案? ?v 解解 方法与例方法与例4.5相同，相同，以以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。将这些数字填入最终表的将这些数字填入最终表的x1列的位

16、置，得到表列的位置，得到表杨晓艺 数学建模（公修）26/31cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4 4 2 1.25 -3.5 1.375 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 cj-zj -2.625 0 -1.5 -0.125 0 将将x1变换为基变量，替换变换为基变量，替换x1，得表，得表杨晓艺 数学建模（公修）27/31cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 3 x1 x5 x2 3.2 15.2 -2.4 1 0 0 0 0 1 0 -2 0.5

17、 0.2 1.2 0.4 0 1 0 cj-zj 0 0 -1.5 0.4 0 可见原问题和对偶问题都是非可行解。可见原问题和对偶问题都是非可行解。于是引入人工变量于是引入人工变量x x6 6。因在表中因在表中x x2 2所在行，用方程表示时为所在行，用方程表示时为0 x0 x1 1+x+x2 2+0.5x+0.5x3 3-0.4x-0.4x4 4+0 x+0 x5 5= -2.4= -2.4杨晓艺 数学建模（公修）28/31v 引入人工变量引入人工变量x6后，便为后，便为-x2-0.5x3+0.4x4+x6=2.4v 将将x6作为基变量代替作为基变量代替x2，填入表，得到，填入表，得到杨晓艺 数学建模（公修）29/31cj 4 3 0 0 0 -M CB XB b x1 x2 x3 x4 x5 X6 4 0 0 x1 x5 x4 2 8 6 1 0 0 0.5 3 1 0.25 -0.5 -1.25 0 0 1 0 1 0 0.5 -3 2.5 cj-zj 0 1 -1 0 -M+2 4 3 0 x1 x2 x4 0.667 12.667 12.667 1 0 0 0 0 1 0 -2 0.5 0 0 1 -0.33 0.33 0.83 0 -1 0 cj-zj 0 3-M -0.5M 0