课件忻展红-运筹学-课件运筹二1

1、管理与人文学院1999，4忻展红第二章线性规划的对偶理论及其应用窗含西岭千秋雪，门泊东吴船对偶是一种普遍现象2.1 线性规划的对偶理论2.1.1 线性规划原问题与对偶问题的表达形式 任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？2max f ( x) = x1 + 2 x2 - 3x3 + 4 x4x1 + 2x2 + 2x3 - 3x4 25A资源s.t.2x+ x- 3x+ 2x 15B资源1234x1, x2 , x3, x4 0例2.1.1 目标函数min g(y)=25y1+15y23y1 + 2 y2

2、1产品1的所得2 y+ y 2产品2 的所得12s.t.2 y1 - 3 y2 -3产品3的所得- 3 y+ 2 y 4产品4 的所得12y1, y2 0 设A、mBa资x f源( x的) =出x售1 +价2格x2 分- 3别x3为+ 4yx4和 y12 显然商人希x望1 +总2的x2收+ 2购x价3 -越3x小4 越2好5A资源 工厂希s.t望.出2售x资+源x 后- 3所x得+不2x比应15用这B些资资源源生产产1234品所得少 x , x , x , x 012342.1.1 线性规划原问题与对偶问题的表达形式4原问题:max f ( x) = CXs.t. AX b X 0对偶问题:m

3、in g( y) = Ybs.t.YA C Y 0上两式中X= ( x1, x2 ,L, xn )TY= ( y1, y2 ,L, ym )C = (c1, c2 ,L, cn )b = (b1, b2 ,L, bm )T a11a12La1n A = a21a22La2n MMOM aaLam1m2mn 2.1.1 线性规划原问题与对偶问题的表达形式实际上，营养配餐问题的对偶问题同样有经济解释！5对偶问题习惯写为: min g(Y ) = bTYT ATYT CTs.t.Y 0把对偶问题展开min g( y) = b1 y1 + b2 y2 +L+ bm ym a11 y1 + a21 y2

4、 +L+ am1 ym c1 ay+ ay+L+ ay c121222m2m 2s.t.Ma1n y1 + a2n y2 +L+ amn ym cny1, y2 ,L, ym 02.1.2 标准(max,)型的对偶变换目标函数由 max 型变为 min 型对应原问题每个约束行有一个对偶变量 yi，i=1,2,m 对偶问题约束为 型，有 n 行；而原问题约束为 型， 有 m 行原问题的价值系数 C 变换为对偶问题的右端项原问题的右端项 b 变换为对偶问题的价值系数原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶 对偶问题可能比原问题容易求解 对偶问题还有很多理论

5、和实际应用的意义62.1.3 非标准型的对偶变换令 y1 = w1, y2 = -w2 , y3 = w3 - w4经整理得:min g( y) = 20 y1 + 10 y2 + 5y33y1 + 4 y2 + y3 4s.t.2 y- 3y+ y= 5123 y1 0, y2 0, y3 不限应用标准型对偶变换规则min h(w) = 20w1 - 10w2 + 5w3 - 5w43w1 - 4w2 + w3 - w4 42w+ 3w+ w- w 5s.t.1234- 2w- 3w- w+ w -51234w1, w2 , w3 , w4 0例2.1.2原线性规划问题max f ( x)

6、= 4 x1 + 5x23x1 + 2 x2 204 x- 3x 10s.t.12x+ x= 512x2 不限, x1 0化为(max, )型标准问题max f ( x) = 4 x1 + 5x2 - 5x23x1 + 2 x2 - 2 x2 20- 4 x+ 3x - 3x -10122s.t.x1 + x2 - x2 5- x- x + x -5122x1, x2 , x2 0表2.1.1 对偶变换的规则新增加的对偶规律： 约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的，对偶可分为三组8原问题(max)对偶问题(min)技术系数矩阵A技术系数矩

7、阵 AT价值系数C右端项b右端项b价值系数C 第 i 行约束条件为型对偶变量yi 0 第 i 行约束条件为型对偶变量yi 0第 i 行约束条件为=型对偶变量yi 不限决策变量xj 0第 j 行约束条件为型决策变量xj 0第 j 行约束条件为型决策变量xj 不限第 j 行约束条件为=型2.2 线性规划的对偶定理 为了便于讨论，下面不妨总是假设2.2.1 弱对偶定理定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值9证: 由于X 0,Y 0分别为原问题和对偶问题的可行解,故有 AX 0 bY 0 A CX 0 0 Y 0 0容易看出有Y 0b

8、 Y 0 AX 0 CX 0.#对偶问题:min g( y) = Ybs.t.YA C Y 0原问题:max f ( x) = CXs.t. AX b X 0弱对偶定理推论 max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限 如果原max(min)问题为问题无可行解解，则其对偶 min (max) 如果原max(min)问题有可行解，其对偶 min (max)问题无可行解，则原问题为解 注：有可能存在原问题和对偶问题同时无可行解的情况10原问题与对偶问题解的关系11对偶原问题有限最优解解无可行解有限最优解I解

9、II无可行解IIIII原问题与对偶问题都无可行解的例子min y1 + y2min x1x1 + x2 1 y1 - y2= 1s.t. -x- x 1s.t. y1 - y= 0122x , x 不限y , y 01212122.2.2 最优解判别定理定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是对应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0 = Y0b CX,Y0b = CX0 Yb 。证毕。2.2.3 主对偶定理定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理

10、推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。13主对偶定理的证明证：现证明定理的后一句话。设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B-1 b，则其检验数满足 C - CBB-1A 0令Y0= CBB-1，则有Y0 A C ；而对原问题松弛变量的检验数有0 - CBB-1I 0，即 Y0 0 。显然Y0为对偶问题的可行解。因此有对偶问题目标函数值，g(Y0)=Y0b= CBB-1 b而原问题最优解的目标函数值为f(X0)=CX0= CBB-1 b故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。 该定理的证明告诉我们一个非常重要的

11、概念：对偶变量的最优解等于原问题松弛变量的机会成本 即对偶变量的最优解是原问题资源的价格142.2.4 互补松弛定理定理 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0（库恩证：由定理所设，可知有条件）。X0, U0 0Y0, V0 0A X0 + U0 = b(1)(2)Y0 A -V0= C分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得Y0 U0 + V0 X0 = Y0 b -C X0若 Y0 U0 + V0 X0 = 0，根据最

12、优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。证毕。15v0x0 = 0j = 1,2,L, ny0u0 = 0i = 1,2,L, mjjii2.2.4 互补松弛定理Y0 U0 + V0 X0 = 0有什么应用若(Y0 )i 0，则 (U0 )i =0，意味着原问题第 i 约束行必须为 = 约束；对(X0 )i 0 亦如此可用来简化问题的求解线性规划的高级算法：利用互补松弛定理，原问题与对偶问题同时解 原问题为基础可行解，对偶问题为非可行解，但满足互补松弛条件；则当对偶问题为可行解时，取得最优解16v0x0 = 0j = 1,2,L, ny0u0 = 0i = 1,2,

13、L, mjjii2.2.5 原问题检验数与对偶问题的解在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的机会成本对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。17例2.2.3 原问题检验数与对

14、偶问题的解18Cj CBXBb536-600-Mx1x2x3x3x4x5x60x4180x516-Mx610121-110021(3)-3010111-1001OBJ=-10Mcj - zj-M-M-MM00-M 5+M3+M6+M-6-M0000x438/36x316/3-Mx614/31/35/3001-1/302/31/31-101/301/3(2/3)000-1/31OBJ=32-14M/3cj - zj4-M/32-2M/36-602+M/3-M1+M/31+2M/3000-2-M/300x416x333x27-1/200011/2-5/2(1/2)01-101/2-3/21/210

15、00-1/23/2OBJ=39cj - zj9/236-603/23/21/20000-3/2-M-3/20x445x163x24001-111-3102-201-101-1(1)0-12OBJ=42cj - zj537-702-100-110-2-M+10x485x114-6x34010010-112000-1301-110-12OBJ=46cj - zj546-60130-1000-1 -M-3对偶问题最优解：y4=0y5=1y6=0y1=0y2=1y3=319原问题最优解： x1=14, x2=0, x3=-4, x4=8, x5=0, x6=0, OBJ=46Cj CBYBb18161

16、000My1y2y3y4y5y60y4-50y5-3My66-1-2-1100-2-1-101013(1)001OBJ=6Mcj - zjM3MM00M18-M16-3M10-M0000y410y5310y360(1)0101-120011131001OBJ=60cj - zj10301000108-14000M-1016y210y5110y33010101-300-21-1101-30-2OBJ=46cj - zj101610-140-4800140M-4原问题最优解：x4=8x5=0x6=0x1=14x2=0x3=-4对偶问题最优解： y1=0, y2=1, y3=3, y4=0, y5=

17、1, y6=0,OBJ=46202.3 对偶单纯型算法2.3.1 基本思路原单纯型迭代要求每步都是基础可行解 b=B-1b0达到最优解时，检验数 cjzj 0 (max) 或 cjzj 0 (min) 但对于(min, )型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代， 但保证检验数满足最优条件， cjzj 0 (max) 或 cj zj 0 (min) 每步迭代保持检验数满足最优条件，但减少非可行度 如何判断达到最优解 如何保证初始基础解满足最优条件 为什么叫对偶单纯型法212.3.2 迭代步骤1 确定出变量

18、找非可行解中最小者，即min bi | bi0，设第 i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi*2 确定入变量 最大比例原则设 j* 列满足(2.3.1)式， j* 列称为主列，xj* 为出变量3 以主元 ai*j* 为中心迭代4 检查当前基础解是否为可行解 若是，则当前解即为最优解 否则，返回步骤 122 c- zmax jja 0(2.3.1)jai* ji* j最大比例原则令V=C -CBB-1A为检验数向量对min 问题，V 0 称为正则，即满足最优判定条件可以证明，V 的迭代也满足四角运算法则 令 xr 为出变量，在第i*行；若选非基变量 xj* 为入变量 必须满足什么条件才能保证迭代后的解仍为正则的？若xj仍为基变量，则可知 vj = vj = 0ai*j=0 ,因此只需考虑 非基变量xj 观察出变量 xr 对应的检验数变化，因为有 ai*r =1，故 vr= 0 - v j*ai*r/ ai* j*= -v j* / ai* j* 0 由于 vj* 0，故必有 ai*j* 0 时，显然有 0v j若 ai*j 0 时，则要求 vj - vj* ai*j / ai*j* 0,可解出结合上述的几个条件，则得到最大比例