第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 §1 原问题与对偶问题 大自然中任何事物之间的关系均可以用阴阳八卦的思想来理解，有着生生相克的特性。一件事物有正面，还有反面；有积极作用，还有消极作用。对偶问题正是如此！

3 阴阳机器厂在计划期内生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需设备A、B、C台时如下：
产品Ⅰ 产品Ⅱ 资源限量 设备A 1 300台时 设备B 2 400台时 设备C 250台时 该工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应该怎样安排生产，才能获利最多？

4 设产品Ⅰ的计划产量为x1，产品Ⅱ的计划产量为x2， 则有线性规划问题LP1：
目标函数： 约束条件：

5 现假定有另一八卦机器厂，该厂的规模较小一些，想租用阴阳厂的设备进行生产。那么阴阳厂的领导应该给自己的设备制定一个怎样的出租价格呢？
设出租设备A、B、C的价格分别定为 y1、y2、 y3。该问题可从两个角度进行分析： 对于阴阳厂，总租金应当不低于原利润： 生产产品Ⅰ所需设备台时不应当低于原利润： 生产产品Ⅱ所需设备台时不应当低于原利润： 对于八卦厂，希望支付的总租金最少，即：

6 因此可以建立另一线性规划问题LP2： 目标函数： 约束条件：

7 在这种情况下，我们称LP1、LP2互为对偶问题，即一个为原问题，另一个则为对偶问题。
原问题 对偶问题

8 用矩阵形式，可表达为： 原问题 对偶问题

9 在上例中，原问题与对偶问题的矩阵形式可以写作：
原问题 对偶问题

10 二者之间的关系： 原问题中求目标函数极大化问题，对偶问题中求目标函数极小化问题。 原问题中约束条件的个数等于对偶问题中变量的个数。
原问题约束条件中符号为 号，对偶问题中约束条件符号为 号。 原问题目标函数的系数是其对偶问题约束条件的右端项。

11 可用如下表格来表示： 原问题（求极大） 右端项 对偶问题（求极小） b1 y1 b2 y2 bm ym c c … cn x x … xn a a … a1n a a … a2n … am am … amn ≤ b1 ≤b2 . ≤bm ≥ c ≥ c … ≥cn

12 例1：写出下述线性规划问题的对偶问题

13 解：第一步：将5x1-3x2+x3 =200转换成： 5x1-3x2+x3≥200 和 5x1-3x2+x3≤200, 然后将所有的约束条件写成≤（≥亦可），有

14 第二步：令与上式中四个约束条件对应的对偶变量分别为y1,y2,y3’,y3’’(因为它俩来自于同一个约束条件），则有对偶问题：

15 第三步：再令y3=y3’-y3’’，则有最终的对偶问题：

16 例2：写出下述LP的对偶问题：

17 按照上述三个步骤，求得其对偶问题为：

18 原问题与对偶问题互化关系表： 原问题（对偶问题） 目标函数（max） 对偶问题（原问题） 目标函数（min） ｎ个 变 ≥０ 量 ≤０
　　　　ｎ个 　变　　≥０ 　量　　≤０ 　　　　无约束 目标函数中变量的系数 　约　　ｍ个 　束　　 ≤ 　条　　 ≥ 　件　　 ＝ 约束条件右端项 　ｎ个 　 　约 　≥　　　 　束 　≤　　　 　条 　=　　　　 件 　ｍ个 　 ≥０　 　变 　 ≤０　 量 　无约束