第3章 LP的对偶问题与灵敏度分析 §1 原问题与对偶问题 §2 对偶问题基本性质 §3 对偶单纯形法 §4 灵敏度分析
§2 对偶问题的基本性质 一、单纯形法的矩阵描述 设有LP问题： 化标准形： 不违背一般，设B是一个可行基，与B相应，做矩阵分块如下：
式（1），（2）可表示为： 即： 式（5）两端左乘B-1得： 由式（6）得：
带入式（4）得： 由式（8）得单纯形法的最优性条件为：
二、单纯形表的矩阵结构 由（7），（8）可构造单纯形表：
三、对偶规划与原规划最优解的关系 当原问题得到最优解时，必有： 令： ，上式等价为： 可知这是对偶规划的一个可行解 令： ，上式等价为： 可知这是对偶规划的一个可行解 且此时： ，可见对偶规划与原规划最优解的目标函数值相等，不是偶然的。
四、由原规划最终单纯形表确定对偶规划最优解 考察单纯形表结构，可在原规划得到最优解时，同时直接得到对偶规划最优解，这已经是明确的问题。 并且由： 还可发现对偶问题的最优解y= 实际是原问题松弛变量的检验数的相反数。
举例 MAX 50x1+100x2+0s1+0s2+0s3. S.T. x1 + x2+ s1+ 0s2+ 0s3=300,
迭代次数 基变量 CB x1 x2 s1 s2 s3 b 比值 bi/aij 50 100 0 0 0 2 x1 S2 x2 50 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 250 Zj 50 100 50 0 50 0 0 -50 0 -50 27500
Lindo求解对偶问题 min 300y1+400y2+250y3 st y1+y2>=50 y1+y2+y3>=100 end
五、对偶问题基本性质