《单纯形法的灵敏度分析与对偶》由会员分享，可在线阅读，更多相关《单纯形法的灵敏度分析与对偶（55页珍藏版）》请在金锄头文库上搜索。
1、第六章 单纯形法的灵敏度分析与对偶本章内容：一、单纯形表的灵敏度分析二、线性规划的对偶问题三、对偶单纯形法一、单纯形表的灵敏度分析灵敏度分析步骤： 1.将参数的改变计算反映到最终单纯形表上；2.检查原问题是否仍为可行解； 3.检查对偶问题是否仍为可行解； 4.按表上所列情况得出结论和决定继续计算的步骤原问题对偶问题结论或继续计 算的步骤可行解 可行解 非可行解 非可行解可行解 非可行解 可行解 非可行解问题的最优解或最优基不变 用单纯形法继续迭代求最优解 用对偶单纯形法继续迭代求最优解 引进人工变量，编制新的单纯形表 重新计算一、单纯形表的灵敏度分析1. 灵敏度分析的方法当参数 C、b、A 中
2、的某些数据发生变化时，通过 改变目前最优基对应的单纯形表中的局部数据，考察是 否影响以下两组数据的成立：（1） B-1b 0（2） C CBB-1A 02. 目标函数中变量系数 C 的灵敏度分析不影响 B-1b 0可能改变 C CBB-1A 0C改变求出使该表达式仍然成立的 C 的变化范围若 C 的变化超出该范围，则原最优解将改变例1：某工厂用甲、乙两种原料生产A、B、C、 D四种产品，要求确定总利润最大的最优生产计划。该问题的线性规划模型如下：Max Z = 9 x1 +8x2 + 50x3 + 19x43x1+ 2 x2 + 10 x3 + 4 x4 18（甲材料） 2x3+ 1/2x4
3、3 （乙材料） x1，x2 ，x3 ，x4 0 其中： x1，x2 ，x3 ，x4 分别表示 A、B、C、D 四种产品的产量。 这个线性规划问题的最终单纯形表如下：X1 X2 X3 X4 X5 X6 9 8 50 19 0 0 X4 X319 502 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/32 1j= cj - zj-4 -2/3 0 0 -13/3 -10/3 Z = 88cjXBcBXb 最优生产计划是：生产1个单位产品C，生产2个单位产品D，不生产A、B产品。可得最大总利润 88 个单位。要求: 计算使得原最优解不变的产品 A 的单位利润的变动范围
4、。解：设 C1 = 9 + 则有：X1 X2 X3 X4 X5 X6 9+ 8 50 19 0 0 X4 X319 502 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/32 1j= cj - zj4 -2/3 0 0 -13/3 -10/3 Z = 88cjXBcBXb如果要使最优解不变，根据最优判别准则，应有： 4 0即： 4 当 4 或 C1= 9 + 9 + 4 = 13 时，原最优解不变，最大总利润仍为 88 个单位。可能改变 B-1b 0不影响 C CBB-1A 0 b改变求出使该表达式仍然成立的 b 的变化范围若 b 的变化未超出该范围，则原最优基
5、不变，对偶价格不变3. 约束方程右边常数 b 的灵敏度分析最优解 XB= B-1b 将改变要求: 甲原料的数量在什么范围内变动时，原来的基仍为最优基？例2：沿用前例 解：设 b1 = 18 + ，要使原来的最优解不变，因为检验数不受影响，应有B-1b 0，即：18+3=B-1b = 2/3 -10/3 -1/6 4/32 +（2/3） 1 /6 0X1 X2 X3 X4 X5 X6 9 8 50 19 0 0 X4 X319 502 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/32 1j= cj - zj-4 -2/3 0 0 -13/3 -10/3 Z =
6、88原最终单纯形表为cjXBcBXb求解2 +（2/3） 01 /6 0得：3 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-1 Pj 若 j= Cj CBB-1 Pj 0，则原最优解不变；若 j= Cj CBB-1 Pj 0，则继续迭代以求出新的最优解。如果该工厂考虑引进新产品E ，已知生产 E 产
8、品1 个单位要消耗甲材料3个单位和乙材料1个单位。 要求：产品E 的利润达到多少时才值得投产？例3：沿用例1 解：设生产 E 产品X7个单位，单位产品的利润为C7，则模型变为：Max Z = 9 x1 +8x2 + 50x3 + 19x4 + 0x5 + 0x6+ C7x73x1+ 2 x2 + 10 x3 + 4 x4 + x5 + 3 x7 = 18（甲材料） 2x3+ 1/2x4 + x6 + x7 = 3 （乙材料） x1，x2 ，x3 ，x4 ，x5 ，x6 ，x7 0 其中： x1，x2 ，x3 ，x4 分别表示 A、B、C、D 四种产品的产量。 由原最终单纯形表知：X* =（0，
9、0，1，2，0，0）T是原问 题的一个最优解，则（ X* ，0） T是这个问题的一个可行解。当 7 = C7 CBB-1 P7 0 时，新产品才值得投产（思考：为什么？）即： 7 = C7 （19，50）2/3 -10/3 -1/6 4/33 1= C7 （13/3，10/3）3 1= C7 49/3 0 C7 49/3 结论：当产品E 的利润超过 49/3 时才值得投产。X1 X2 X3 X4 X5 X6 X7 9 8 50 19 0 0 17 X4 X319 502 4/3 0 1 2/3 -10/3 -4/3 -1/2 -1/3 1 0 -1/6 4/3 5/62 1j= cj - zj
10、-4 -2/3 0 0 -13/3 -10/3 2/3 ZcjXBcBXb 例4：设 C7 = 17，问：新的最优方案的利润比原最优方案 的利润是否增加？若是，增加多少？ 解：P7 = B-1P7 = 2/3 -10/3 -1/6 4/33 1=-4/3 5/67 = C7 CBB-1 P7= 17 （19，50）-4/3 5/6= 2/3将它们反映到原最终单纯形表中，得到下表：X1 X2 X3 X4 X5 X6 X7 9 8 50 19 0 0 17 X4 X719 176/5 4/5 8/5 1 2/5 -6/5 0 -3/5 -2/5 6/5 0 -1/5 8/5 118/5 6/5j=
11、 cj - zj-18/5 -2/5 -4/5 0 -21/5 -22/5 0 Z = 88.8cjXBcBXb继续迭代，得下表： 最优解为：X4= 3.6，X7 =1.2，其余Xj= 0；最优值为88.8。即：当新产品E 的单位利润为17时，应改生产产品D 3.6个单位、产品E 1.2个单位。这时可得最大利润为 88.8，比原最优方案的利润增加0.8。5. 约束方程左边系数 aij 的灵敏度分析v 这类问题的分析方法与增加一个新变量的同，即把Pj = B-1Pj， j= Cj CBB-1 Pj 都反映到原最终单纯形表中，再判断是否需要继续迭代，以求出最终的结果。例5：沿用例1 如果生产A 产
12、品1个单位要消耗甲材料 4个单位和 乙材料2个单位，其利润为26个单位。 问：新的最优生产方案如何？X1 X2 X3 X4 X5 X6 X19 8 50 19 0 0 26 X4 X319 502 4/3 0 1 2/3 -10/3 -4 -1/2 -1/3 1 0 -1/6 4/3 22 11/2j= cj - zj-4 -2/3 0 0 -13/3 -10/3 2 ZcjXBcBXb 解：P1 = B-1P1 = 2/3 -10/3 -1/6 4/34 2=-4 21= C1 CBB-1 P1= 26 （19，50）-4 2= 2将它们反映到原最终单纯形表中，得到下表：X4 X119 261 2/3 2 1 1/3 -2/3 0 -1/4 -1/6 1/2 0 -1/12
