对偶问题(运筹学)

《对偶问题(运筹学)》由会员分享，可在线阅读，更多相关《对偶问题(运筹学)（34页珍藏版）》请在文档大全上搜索。

1、大连海事大学交通运输管理学院2.4.1 对偶问题的提出2.4.2 原问题与对偶问题2.4.3 对偶问题的性质2.4.4 对偶变量的经济含义2.4.5 对偶单纯形法 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多? -第2章 对偶问题-4-设 企业生产甲产品为X1件， 乙产品为X2件，则 (原问题) ( 对偶问题)设第i种资源价格为yi,( i=1, 2, 3) 则有y1y2y30,12416482122232max2121212121xxxxxx

2、xxxxzy4一般表示式：原问题： max z = c1 X1 + c2 X2 + + cn Xn s.t a11 X1 + a12 X2 + + a1n Xn b1 a21 X1 + a22 X2 + + a2n Xn b2 am1 X1 + am2 X2 + + amn Xn bm xj 0，j=1,2,n 对偶问题： min w = b1 y1 + b2 y2 + + bm ym s.t a11 y1 + a21 y2 + + am1 ym c1 a12 y1 + a22 y2 + + am2 ym c2 a1n y1 + a2n y2 + + amn ym cn yi 0，(i=1,2

3、,m )典式模型对应对偶结构矩阵表示（1）max z = C X s.t AX b X 0min w = Y b s.t YA C Y 0 对偶问题原问题（2）若模型为 max z = C X s.t AX b X 0max z = C X s.t - AX -b X 0变形min w = Y b s.t YA C Y 0 Min w=Y (-b) st. Y (-A) CY 0令 Y=- Y 对偶问题对偶变量Y（3）max z = C X s.t AX b X 0变形设X= -Xmax = -CX st. -AX b X 0min w = Y b s.t YA C Y 0则有min w =

4、Y b s.t -YA - C Y 0用矩阵形式表示： （1） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （2） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （3）max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 原问题(对偶问题) 对偶问题(原问题) 目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A约束条件系数行向量 AT 变量个数约束条件个数max min 变量 x j : 约束方程 i : x j 0

5、 x j 无约束 = x j 0 约束方程: 变量 y i : y i 0 = y i 无约束 y i 0 例2-10 写出下述线性规划问题的对偶问题。 无约束43213432243114321432100362422153532x,x ,x,xyxxxyxxxyxxxxxxxxzmin则由表中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题无约束3213213213121321001523322645y,y,yyyyyyyyyyyyyyzmax练习练习max z = 2y1+5y2+1y3y1+y2 + y3 y1 y2 + y3 3 y1 +1y3 - -1y1 0, y2 0,

6、s.t.解解 min = x1+x2 - -1 x3x1+x2+3x3 2 x1 x2 5 x1+x2+1 x3 1 x10, , x3 0 s.t. 性质性质1 规范原始、对偶问题规范原始、对偶问题(P1)与与(D1) 互相对偶互相对偶。即对偶。即对偶问题的对偶是原问题。问题的对偶是原问题。 性质性质2 设设X, , 分别为分别为(P1)与与(D1)的任意可行解，则的任意可行解，则 CX b 性质性质3 设设 , ,Y分别为分别为(P1)与与(D1)的任意可行解，则当的任意可行解，则当 C= Yb 时，时， , , Y分别是分别是(P1)与与(D1)的最优解。的最优解。 性质性质4 互为对偶

7、的两个线性规划问题，若互为对偶的两个线性规划问题，若其中一个问题的其中一个问题的，则，则另一个问题另一个问题。 互互为对偶的两个线性规划问题，为对偶的两个线性规划问题，若若其中一个问题有最优解，则其中一个问题有最优解，则另一个问题也有另一个问题也有最优解最优解，且且二者最优值相等。二者最优值相等。 ： 无界性无界性之逆命题不成立。之逆命题不成立。 因为一个问题因为一个问题时，时， 另一个问题可能另一个问题可能，也可能，也可能。 原始问题的原始问题的给出对偶问题的一个给出对偶问题的一个。 X*= (4, 6, 4, 0, 0)T, z* = 42y1y2y3y4y5Y*= (0, 1/2, 1,

8、 0, 0)T, w* = 42互补基本解互补基本解x3x2x1 x1 x2 x3 x4 x5 3 5 0 0 005 36 0 1 0 1/2 04 0 0 1 1/3 - -1/3 4 1 0 0 - -2/3 1/342 0 0 0 -1/2 -1cj 比值比值 基基 解解 : max z = 3x1 +5x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0s.t.( ( P1) ):min w=8y1+12y2+36y3 y1 +3y3 3 2y2+4y3 5 y1 , , y2, , y3 0s.t.( ( D1) ): max z = 3x1 +5x2 x1

9、+x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1, , x2 , , x3 , , x4 , , x5 0s.t.( ( Ps s) ):min w=8y1+12y2+36y3 y1 +3y3 -y4 = 3 2y2+4y3 -y5 = 5 y1 , , y2 , , y3 , , y4 , , y5 0s.t.( ( Ds s) )X*= (4 , ,6)TY*= (0 , , , ,1)TX*= (4, 6, 4, 0, 0)T Y*= (0, 1/2, 1, 0, 0)T, z*= 42 = w* (P)的基本解的基本解 与与(D)的基本解的基本解 相

10、互对应相互对应, , 且二者目标值相等。且二者目标值相等。我们把这样一对基本解我们把这样一对基本解 与与 ，称为，称为(P)与与(D)的的互补基本解互补基本解。 (P) 目目 标标 值值 (D) 序序号号 极极点点 基基 本本 解解 k Xk可可 行行 z = w Yk可可 行行 基基 本本 解解 k 1 O (0 ，0 ，8 ， 12 ， 36) 是是 0 否否 (0 ，0 ，0 ，- -3 ，- -5) 2 A (8 ，0 ，0 ， 12 ， 12) 是是 24 否否 (3 ，0 ，0 ， 0 ，- -5) 3 D (0 ，6 ，8 ，0 ， 12) 是是 30 否否 (0 ， 5/2 ，

11、 0 ，- -3 ， 0) 4 B (8 ，3 ，0 ，6 ， 0) 是是 39 否否 (- 3/4 ， 0 ， 5/4 ， 0 ， 0) 5 C (4 ，6 ，4 ，0 ， 0) 42 (0 ， 1/2 ， 1 ，0 ，0) 6 E (12 ， 0 ，- -4 ， 12 ， 0) 36 (0 , , 0 , , 1 , , 0 , , - -1) 7 G (0 ，9 ，8 ，- -6 ， 0) 否否 45 是是 (0 , , 0 , , 5/4 , , 3/4 , , 0) 8 F (8 ，6 ，0 ，0 , , - 12) 否否 54 是是 (3 , , 5/2 , , 0 , , 0 ,

12、 , 0) 为最优解。当且仅当，和那么题的可行解，分别为原问题和对偶问若YXXYXYY,XSS,; 00 7. 设设 = ( , , , , , , )T= ( , , , , , , )T是是(P1) (D1)的一对的一对，那么，那么 0， j = 1, 2 , , n 0， i = 1, 2 , , mmin =2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解 。max z=4y1+3y2y1+2y22 y1-y23

13、 2y1+3y25 y1+y22 3y1+y23 y1，y20得=1/53，=17/55，=7/52 它们为严格不等式； 由互补松弛性得 x2*=x3*=x4*=0。因y1，y2 0；原问题的两个约束条件应取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为 X*=(1，0，0，0，1)T；*=5对偶变量的意义代表对企业资源的估价，与该种资源的市场价格不同，因此我们称之为影子价格影子价格。（1）资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之

14、改变。（2）影子价格是一种边际价格，在（2-12）式中将Z对 求偏导数得 ，这说明 相当于在给定的生产条件下， 每增加一个单位目标函数Z的增量。（3）资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。例： min z=2x1+3x2 max z=-2x1-3x2+0 x3 +0 x4 s.t x

15、1+x23 标准化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10, x20 xj 0, (j=1,2,3,4) max z=-2x1-3x2+0 x3 +0 x4 s.t - x1-x2+x3=-3 - x1-2x2+x4=-4 xj 0, (j=1,2,3,4) Cj x1x2x3x4XBbCB-1 -1 1 0 -1 -2 0 1-2 -3 0 0-3 -4x3 x400cj - zj -2-300-1/2 0 1 -1/2 1/2 1 0 -1/2x3 x2-1 2cj - zj -1/2 0 0 -3/2 0 -31 0 -2 1 0 1 1 -1x1

16、 x221cj - zj 0 0 -1 -1-2 -3列单纯表计算：把把m阶阶LPLP问题化成问题化成标准形标准形（允许其右端常数为负允许其右端常数为负）, 在其系数阵中找出或构造一个在其系数阵中找出或构造一个作作, , 。若所有检验数。若所有检验数 j j00，则转，则转2 2; ：检查表中检查表中解列解列各数值各数值b bi i；若所有；若所有b bi i0,0, 则问题已得最优解，停止计算则问题已得最优解，停止计算; 否则转否则转3 3。：只要存在一个：只要存在一个b br r00，它所在行中，它所在行中所所有有 a arj rj00，则原始问题无可行解，对偶问题无下界，则原始问题无可行

17、解，对偶问题无下界，停止停止；否则转；否则转4 4。：先先确定确定离基离基变量，按变量，按 min min b bi ib bi i 0 0 = b bl 确定第确定第 l 行的基变量行的基变量 xB Bl 离基，第离基，第 l 行为行为主行主行； 确定确定变量，按变量，按： m in m in j j / / a alj ja alj j 0 0 = k k / / a alk k 确定进基变量确定进基变量 xk k 及及主元主元 a alk k。按按主元主元 a alk k 对当前表格进行一次对当前表格进行一次， 得到一个新单纯形表，返得到一个新单纯形表，返2 2 。第3章 对偶原理30m

18、in z = 3x1+2x2s.t.2x1+3x2 18 x1 - - x2 2 x1+3x2 10 x1, , x2 0max z= - -3x1 - -2x2s.t.2x1+3x2+x3 = 18 x1 -x2 x4 = 2 x1+3x2 x5 = 10 x1, , x2, , x3, , x4, , x5 0 x1+ x2 +x4 = 2x13x2 +x5 = 10第3章 对偶原理31max z= - -3x1 - -2x2 2x1+3x2+x3 = 18 - -x1 +x2 +x4 = - -2 - -x1 - -3x2 +x5 = - -10 x1, , x2, , x3, , x4

19、, , x5 0 s.t.cj 基基 解解 x1 x2 x3 x4 x5 -3 -2 0 0 0 2 3 1 0 0 x3x4 x5 18- -2 - -10 - -1 1 0 1 000 0 - -1 - -3 0 0 1 0 -3 -2 0 0 032/3min- -3比比 值值 第3章 对偶原理32cj 基基 解解 x1 x2 x3 x4 x5 - -3 - -2 0 0 0 2 3 1 0 0 x3x4x5 18- -2 - -10 - -1 1 0 1 0000 - -1 - -3 0 0 1 0 -3 - 2 0 0 0- -3x3x1 x2 0- -3- -2 4 1 0 0 -

20、 -3/4 - -1/4 4 0 0 1 3/4 5/4 2 0 1 0 1/4 -1/4- -16 0 0 0 -7/4 -5/4x3x4x2 0 0 - -2 8 1 0 1 0 1 10/3 1/3 1 0 0 - -1/3- -20/3 -7/3 0 0 0 -2/3- -16/3 - -4/3 0 0 1 1/3- - 4/3X*= (4, ,2)Tz* = 16单纯形法的矩阵描述Cj x1x2x3x4XBbCB1 1 1 0 1 2 0 12 3 0 034x3 x400cj - zj 23001/2 0 1 -1/2 1/2 1 0 1/2x3 x212cj - zj 1/2 0 0 -3/2031 0 2 -1 0 1 -1 1x1 x221cj - zj 0 0 -1 -12311B12B1.初等行变换 相当于 左乘一个相应的初等阵2. B-1 B = E3. b/ = B-1 b4. 目标函数AX= b B-1 AX= B-1 b CB B-1 AX= CB B-1 b与 Z= CX相加Z= CB B-1 b + (C- CB B-1 A ) X