单纯形法的灵敏度分析与对偶课件.ppt

《单纯形法的灵敏度分析与对偶课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章单纯形法的灵敏度分析与对偶本章内容：一、单纯形表的灵敏度分析二、线性规划的对偶问题三、对偶单纯形法一、单纯形表的灵敏度分析灵敏度分析步骤：1.将参数的改变计算反映到最终单纯形表上；2.检查原问题是否仍为可行解；3.检查对偶问题是否仍为可行解；4.按表上所列情况得出结论和决定继续计算的步骤原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算一、单纯形表的灵敏度分析1.灵敏度分析

2、的方法当参数C、b、A中的某些数据发生变化时，通过改变目前最优基对应的单纯形表中的局部数据，考察是否影响以下两组数据的成立：（1）B-1b≥0（2）C–CBB-1A≤02.目标函数中变量系数C的灵敏度分析不影响B-1b≥0可能改变C–CBB-1A≤0C改变求出使该表达式仍然成立的C的变化范围若C的变化超出该范围，则原最优解将改变例1：某工厂用甲、乙两种原料生产A、B、C、D四种产品，要求确定总利润最大的最优生产计划。该问题的线性规划模型如下：MaxZ=9x1+8x2+50x3+19x43x1+2x2+10x3+4x4≤18（甲材料）2

3、x3+1/2x4≤3（乙材料）x1，x2，x3，x4≥0►◄其中：x1，x2，x3，x4分别表示A、B、C、D四种产品的产量。◄►这个线性规划问题的最终单纯形表如下：X1X2X3X4X5X698501900X4X3195024/3012/3-10/3-1/2-1/310-1/64/321σj=cj-zj-4-2/300-13/3-10/3Z=88cjXBcBXbθ∴最优生产计划是：生产1个单位产品C，生产2个单位产品D，不生产A、B产品。可得最大总利润88个单位。要求:⑴计算使得原最优解不变的产品A的单位利润的变动范围。解：设C1=9

4、+λ则有：X1X2X3X4X5X69+λ8501900X4X3195024/3012/3-10/3-1/2-1/310-1/64/321σj=cj-zjλ–4-2/300-13/3-10/3Z=88cjXBcBXbθ如果要使最优解不变，根据最优判别准则，应有：λ–4≤0即：λ≤4∴当λ≤4或C1=9+λ≤9+4=13时，原最优解不变，最大总利润仍为88个单位。可能改变B-1b≥0不影响C–CBB-1A≤0b改变求出使该表达式仍然成立的b的变化范围若b的变化未超出该范围，则原最优基不变，对偶价格不变3.约束方程右边常数b的灵敏度分析最优

5、解XB=B-1b将改变要求:⑵甲原料的数量在什么范围内变动时，原来的基仍为最优基？例2：沿用前例►解：设b1=18+λ，要使原来的最优解不变，因为检验数不受影响，应有B-1b≥0，即：18+λ3=B-1b=2/3-10/3-1/64/32+（2/3）λ1–λ/6≥0X1X2X3X4X5X698501900X4X3195024/3012/3-10/3-1/2-1/310-1/64/321σj=cj-zj-4-2/300-13/3-10/3Z=88原最终单纯形表为cjXBcBXbθ求解2+（2/3）λ≥01–λ/6≥0得：–3≤λ≤6结论

6、：当15≤b1（甲原料的数量）≤24时，原来的基仍为最优基。但最优解和目标函数最优值都是λ的函数。在本例中，工厂生产（2+（2/3）λ）个单位D产品，（1–λ/6）个单位C产品，可得最大利润为：CBB-1b=（19，50）2+（2/3）λ1–λ/6=（88+（13/3）λ）个单位（其中：–3≤λ≤6）可见：当λ=1，即b1增加1个单位时，最大利润增加（13/3）个单位。由对偶价格的定义知，第一个约束条件的对偶价格是13/3。注意：“13/3”与原最终单纯形表中某松弛变量的检验数的关系。！约束条件的对偶价格与约束类型的关系约束类型对偶价

7、格的取值≤等于与这个约束条件对应的松弛变量的Zj值≥等于与这个约束条件对应的剩余变量的Zj值的相反数=等于与这个约束条件对应的人工变量的Zj值4.增加一个新变量的灵敏度分析设：新变量对应的目标函数系数为Cj，对应的约束条件的系数列向量为Pj则：在原最终单纯形表上，新变量对应的系数列为Pj'=B-1Pj，检验数为σj=Cj–CBB-1Pj若σj=Cj–CBB-1Pj≤0，则原最优解不变；若σj=Cj–CBB-1Pj≥0，则继续迭代以求出新的最优解。如果该工厂考虑引进新产品E，已知生产E产品1个单位要消耗甲材料3个单位和乙材料1个单位。要

8、求：⑶产品E的利润达到多少时才值得投产？例3：沿用例1►解：设生产E产品X7个单位，单位产品的利润为C7，则模型变为：MaxZ=9x1+8x2+50x3+19x4+0x5+0x6+C7x73x1+2x2+10x3+4x4