第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析
§1 原问题与对偶问题 大自然中任何事物之间的关系均可以用阴阳八卦的思想来理解，有着生生相克的特性。一件事物有正面，还有反面；有积极作用，还有消极作用。对偶问题正是如此！
阴阳机器厂在计划期内生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需设备A、B、C台时如下： 产品Ⅰ 产品Ⅱ 资源限量 设备A 1 300台时 设备B 2 400台时 设备C 250台时 该工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应该怎样安排生产，才能获利最多？
设产品Ⅰ的计划产量为x1，产品Ⅱ的计划产量为x2， 则有线性规划问题LP1： 目标函数： 约束条件：
现假定有另一八卦机器厂，该厂的规模较小一些，想租用阴阳厂的设备进行生产。那么阴阳厂的领导应该给自己的设备制定一个怎样的出租价格呢？ 设出租设备A、B、C的价格分别定为 y1、y2、 y3。该问题可从两个角度进行分析： 对于阴阳厂，总租金应当不低于原利润： 生产产品Ⅰ所需设备台时不应当低于原利润： 生产产品Ⅱ所需设备台时不应当低于原利润： 对于八卦厂，希望支付的总租金最少，即：
因此可以建立另一线性规划问题LP2： 目标函数： 约束条件：
在这种情况下，我们称LP1、LP2互为对偶问题，即一个为原问题，另一个则为对偶问题。 原问题 对偶问题
用矩阵形式，可表达为： 原问题 对偶问题
在上例中，原问题与对偶问题的矩阵形式可以写作： 原问题 对偶问题
二者之间的关系： 原问题中求目标函数极大化问题，对偶问题中求目标函数极小化问题。 原问题中约束条件的个数等于对偶问题中变量的个数。 原问题约束条件中符号为 号，对偶问题中约束条件符号为 号。 原问题目标函数的系数是其对偶问题约束条件的右端项。
可用如下表格来表示： 原问题（求极大） 右端项 对偶问题（求极小） b1 y1 b2 y2 . . . . bm ym c1 c2 … cn x1 x2 … xn a11 a12 … a1n a21 a22 … a2n . . . . . … . . . . am1 am2 … amn ≤ b1 ≤b2 . ≤bm ≥ c1 ≥ c2 … ≥cn
例1：写出下述线性规划问题的对偶问题
解：第一步：将5x1-3x2+x3 =200转换成： 5x1-3x2+x3≥200 和 5x1-3x2+x3≤200, 然后将所有的约束条件写成≤（≥亦可），有
第二步：令与上式中四个约束条件对应的对偶变量分别为y1,y2,y3’,y3’’(因为它俩来自于同一个约束条件），则有对偶问题：
第三步：再令y3=y3’-y3’’，则有最终的对偶问题：
例2：写出下述LP的对偶问题：
按照上述三个步骤，求得其对偶问题为：
原问题与对偶问题互化关系表： 原问题（对偶问题） 目标函数（max） 对偶问题（原问题） 目标函数（min） ｎ个 变 ≥０ 量 ≤０ ｎ个 变 ≥０ 量 ≤０ 无约束 目标函数中变量的系数 约 ｍ个 束 ≤ 条 ≥ 件 ＝ 约束条件右端项 ｎ个 约 ≥ 束 ≤ 条 = 件 ｍ个 ≥０ 变 ≤０ 量 无约束