运筹学2.4线性规划的对偶理论16主页China University of Mining and Technology
-16- China University of Mining and Technology 运筹学 2.4 线性规划的对偶理论
运筹学线性规划的对偶理论原问题与对偶问题的对应关系MaxZ=40x,+50x2MinW= 30y, + 60 y2 + 24y3X+2x≤30≥40yi + 3y23x+2x2≤602yi+2 y2 +2y3≥50s.ts.t2x,≤24(yi,2,y3202个约束3个约束X1,X2≥02个变量3个变量原问题对偶问题（对偶问题）（原问题）(yr)(y2)(y3)13040(x)22250(X2)min o243060-17-maxz主页上页下一页后退退出China University of Mining and Technology
-17- China University of Mining and Technology 运筹学 Max Z= 40x1 +50x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1， x2 0 s.t 原问题 （对偶问题） 对偶问题 （原问题） 一、 原问题与对偶问题的对应关系 Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 40 2y1 + 2 y2 + 2y3 50 y1 , y2 , y3 0 s.t （y1） （y2） （y3） （x1） 1 3 0 40 （x2） 2 2 2 50 30 60 24 minω max z 3个约束 2个变量 2个约束 3个变量 线性规划的对偶理论
线性规划的对偶理论运筹学对偶问题的形式定义设原线性规划问题为则称下列线性规划问题MaxMinW=biyi+b,y,+.+b.ymZ=cx, +cx,+...+c.x.aux,+a2x, +...+ainx,≤b,ainy'i+a2iy+...+amiymZcai2yi +a22y2 +.*.+am2m ≥c,a2x,+a22x2+..+a2n,≤b2s.ts.t..ainyi+a2nyz+...+amymZc.amix,+am2x,+..+amx.≤bm(y,≥0(i = 1,2,..,m)x, ≥0(j = 1,2,..,n)为其对偶问题，其中y(i-1,2....,m）称为对偶变量上述对偶问题称为对称型对偶问题原问题简记为(P)，对偶问题简记为(D称问题（P）和D）为一对对偶问题-18-主页退出China University of Mining and TechnologyT
-18- China University of Mining and Technology 运筹学 对偶问题的形式 ( ) = + + + + + + + + + = + + + x 0 j 1,2, ,n a x a x a x b a x a x a x b a x a x a x b s.t Max Z c x c x c x j m1 1 m2 2 mn n m 2 1 1 2 2 2 2n n 2 1 1 1 1 2 2 1n n 1 1 1 2 2 n n 定义 设原线性规划问题为 则称下列线性规划问题 ( ) = + + + + + + + + + = + + + y 0 i 1,2, ,m a y a y a y c a y a y a y c a y a y a y c s.t Min W b y b y b y i 1n 1 2n 2 mn m n 1 2 1 2 2 2 m2 m 2 1 1 1 2 1 2 m1 m 1 1 1 2 2 m m ⚫为其对偶问题，其中yi (i=1,2,.,m) 称为对偶变量 ⚫上述对偶问题称为对称型对偶问题 ⚫原问题简记为(P)，对偶问题简记为(D) •称问题(P)和(D )为一对对偶问题 线性规划的对偶理论
运筹学线性规划的对偶理论对称型问题的对偶规则1、给每个原始约束条件定义一个非负对偶变量y.(i-1,2,..m) ;2、使原问题的目标函数系数c,变为其对偶问题约束条件的右端常数；3、使原问题约束条件的右端常数b,变为其对偶问题目标函数的系数；4、将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵：5、改变约束问题不等号的方向，即将“<”改为“≥”；6、原问题为“max"型，对偶问题为“min"型-19-主页上页下页后银出China University of Mining and Technology
-19- China University of Mining and Technology 运筹学 对称型问题的对偶规则 1、给每个原始约束条件定义一个非负对偶变量 yi (i=1,2,.,m)； 2、使原问题的目标函数系数cj 变为其对偶问题约束条 件的右端常数； 3、使原问题约束条件的右端常数bi 变为其对偶问题目 标函数的系数； 4、将原问题约束条件的系数矩阵转置，得到其对偶问 题约束条件的系数矩阵； 5、改变约束问题不等号的方向，即将“≤”改为“≥” ； 6、原问题为“max”型，对偶问题为“min”型。 线性规划的对偶理论
线性规划的对偶理论运筹学Y为行向量原始问题对偶问题Min W-YbMax Z=CXs.t. [AX<bYA≥Cs.t.X≥0Y≥0Max福Minm20丰China University of Mining and Technology
-20- China University of Mining and Technology 运筹学 原始问题 Max Z=CX s.t. AX≤b X ≥0 A b C ≤ Max n m 对偶问题 Min W=Yb s.t. YA≥C Y ≥0 ≥ Min AT C b n m Y为行向量 线性规划的对偶理论