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