第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析.

Presentation on theme: "第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析."— Presentation transcript:

1 第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析

2 §4 灵敏度分析 一、目标函数中系数Cj的灵敏度分析 例1 已知线性规划问题 试分析λ1和λ2分别在什么范围内变化时，问题的最优解不变。

3 分析：此例中目标函数的系数cj的变化仅仅影响到检验数σj的变化，所以将Cj的变化直接反映到最终单纯形表中。

4 （i）对基变量x1的目标函数系数进行灵敏度分析：将λ1的变化反映到最终单纯形表中：
解：当λ1=λ2=0时，上述LP问题的最终单纯形表如上表所示。 （i）对基变量x1的目标函数系数进行灵敏度分析：将λ1的变化反映到最终单纯形表中： 表中的解仍为最优解的条件是：-1-1/2λ1≤0 -1/5+1/5λ1≤0 故有-2≤λ1≤1时，该LP问题的最优解不变。

5 （ii）类似的可以得到，其他条件不变的情况下，λ2≥-1时，该LP问题的最优解不变。
-2/5+1/5（3+ λ2 ）

6 Lindo实验： Max 2x1+3x2 St 2x1+2x2<=12 4x2<=16 5x2<=15 end

7 二、约束条件右端常数项bi的灵敏度分析 例2 LP问题 分别分析右端常数项在什么范围内变化时，最优基不变。

8 分析：原问题的最终单纯形表如下为，

9 右端常数项的灵敏度分析： （i） 使问题最优基不变的条件是

10 （ii）类似的，使问题最优基不变的第二个约束条件右端常数项的变化范围是：
λ2≥-50 (iii）同样，-50≤λ3≤ 即200≤250+λ3≤300时，对偶价格不变，原问题的最优基不会发生变化。

11 Lindo实验： Max 50x1+100x2 St x1+x2<=300 2x1+x2<=400 x2<=250 end

12 三、增加一个变量的灵敏度分析 实际中，增加一个变量的计算步骤如下： （1）计算 ; （2）计算 ；
（1）计算 ; （2）计算 ； （3）若 ，只需将 和 的值直接反映到最终单纯形表中，原最优解不变； 若 ，则按单纯形法继续迭代计算。

13 例3 在例1中，若增加一个变量x6，有c6=4，P6=(2,4,5)T，试分析问题的最优解的变化。
解：

14 代入最后一张单纯形表中，有 16

15 例4 在例1中，增加一个约束条件3x1+2x2≤14，分析最优解的变化。
四、增加一个约束条件的分析 增加一个约束条件以后，必须验证该约束条件是否对最优解起作用，方法是将原问题的最优解变量的取值代入新增的约束条件中，如满足，说明新增加的约束条件未起作用；否则，须将新增约束条件直接反映到最终单纯形表中进行迭代运算。 例4 在例1中，增加一个约束条件3x1+2x2≤14，分析最优解的变化。 解：因有3×3+2×3=15>14，说明增加的约束条件有限制作用，将其添加到松弛变量后的方程3x1+2x2+x6=14反映到单纯形表中，并继续进行行初等变换，将P1，P4，P2，P6化成单位向量，并用对偶单纯形法迭代，结果如下：

16

17

18 五、约束方程系数矩阵A灵敏度分析 1、在初始单纯形表上的变量xk的系数列pk改变为pk’，经过迭代后，在最终单纯形表上xk是非基变量。

19 例5：某工厂计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原料的消耗，以及资源的限制，如下表所示：
资源限制 设备 1 300台时 原料A 2 400千克 原料B 250千克 该工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少个Ⅰ产品和 Ⅱ产品才能使工厂获利最多？

20 该问题的数学模型为： OBF: MAX 50x1+100x2. S.T. x1+x , 2x1+x , x xj 0

21 其最终单纯形表如下： 迭代次数 基变量 CB x1 x2 s1 s2 s3 b 比值 bi/aij 50 100 0 0 0 2 x1 S2
2 x1 S2 x2 50 100 250 Zj 27500

22 现假设该厂除了生产Ⅰ、Ⅱ产品外，现试制成一种新产品Ⅲ，已知生产产品Ⅲ，每件需要设备2台时，并消耗A原料0. 5公斤，B原料1
解：显然x3是非基变量。主要来计算x3的检验数。经过初等行变换，x3所在列的系数变成：

23 新单纯形表如下： 迭代次数 基变量 CB x1 x2 s1 s2 s3 x3 b 比值 50 100 0 0 0 150 x1 S2 x2
x1 S2 x2 50 100 250 Zj 27500

24 假设上例题中产品Ⅲ的工艺结构有了改进，这时生产1件产品Ⅲ需要设备1
假设上例题中产品Ⅲ的工艺结构有了改进，这时生产1件产品Ⅲ需要设备1.5台时，并消耗A原料2公斤，B原料1公斤，获利160元，问该厂的原生产计划是否需要修改？ 解：x3所在列的系数变成：

25 新单纯形表如下： 迭代次数 基变量 CB x1 x2 s1 s2 s3 x3 b 比值 50 100 0 0 0 160 2 x1 S2
2 x1 S2 x2 50 100 250 Zj 27500

26 迭代次数 基变量 CB x x s s s3 x3 b 比值 3 x3 S2 x2 160 100 50 150 —— Zj 31000

27 迭代次数 基变量 CB x x s s s3 x3 b 比值 4 x3 S3 x2 160 100 200 50 Zj 32000

28 2、在初始单纯形表上的变量xk的系数列pk改变为pk’，经过迭代后，在最终单纯形表上xk是基变量。这时一般需要重新进行计算。