线性规划的对偶理论与灵敏度分析运筹学.pptVIP

2002-03-01 2002ZLZK-PM-KICKOFF 运筹学方法及其应用 原始问题 max z=CX s.t. AX≥b X ≥0 原问题与对偶问题的关系 对偶问题的基本性质 (弱对偶定理) 3、最优性 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解 证：由弱对偶定理推论1，结论是显然的。 即CX0 = Y0b ? CX, Y0b = CX0 ? Yb 。 证毕。 6、互补松弛性 证：由定理所设，可知有 A X0 + U0 = b X0, U0 ?0 (1) Y0 A ? V0 = C Y0, V0 ?0 (2) 分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0 + V0 X0 = Y0 b ? C X0 若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。 我们前面介绍的一般单纯形法，是从“可行”(右端项非负）开始，逐步地迭代运算，直到得出最优解。而应用对偶规划的性质，可以找到一种求解线性规划的新方法——对偶单纯形法。对偶单纯形法则是从“不可行”(右端项含负）开始，在保持最优性之下逐步迭代，直到不可行变为可行，即得到可行最优解为止。当对偶问题的约束条件的数目较原问题为少时，应用对偶单纯形法求解较为方便。 ① 单纯形表检验数行全部非正（对偶可行） ② 变量取值可有负数（非可行解） 对偶单纯形法与原始单纯形法内在的对应关系 最优单纯形表 用图解法求出： Y*=（1 . 3）， W=11。 将y*1=1， y*2=3 代入对偶约束条件， （1）（2）（5）式为紧约束，（3）（4）为松约束。 令原问题的最优解为X* = （x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3 = x4 =0 (1 . 3) （1） （2） （3） （4） （5） 又由于y*1＞0， y*2 ＞0，原问题的约束必为等式，即 化简为 此方程组为无穷多解 令x5 =0,得到x1=1，x2=2 即X*1 =（1.2.0.0.0）为原问题的一个最优解，Z=11。 再令 x5 =2/3，得到x1=5/3，x2=0 即X*2 （5/3.0.0.0.2/3）也是原问题的一个最优解，Z=11。 例2.10 max z=2x1+3x2+0x3+0x4+0x5 2x1+2x2+x3 =12 y1 4x1 + x4 =16 y2 5x2+ x5=15 y3 xj≥0 min w=-12y1-16y2-15y3+0y4+0y5 -2y1-4y2 +y4 =-2 x1 -2y1 -5y3 +y5=-3 x2 yi ≥0 y1 y2 y3 y4 y5 对偶问题变量 对偶问题的剩余变量 变量 1 0 1/5 0 0 0 0 1/5 0 1 x2 3 -2 1 4/5 0 0 x4 4 1/2 0 -1/5 1 0 x1 3 x3 x4 x5 x1 x2 原问题松弛变量 原问题变量 基 b