对偶问答(运筹学).ppt

《对偶问答(运筹学).ppt》由会员分享，可在线阅读，更多相关《对偶问答(运筹学).ppt（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-,1.最大生产利润模型,设 企业生产甲产品为X1件， 乙产品为X2件，则,2.资源最低售价模型,(原问题) ( 对偶问题),设第i种资源价格为y

2、i,( i=1, 2, 3) 则有,y1,y2,y3,y4,二、 原问题与对偶问题的关系,一般表示式： 原问题： 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 a1

3、n y1 + a2n y2 + + amn ym cn yi 0，(i=1,2,m ),典式模型对应对偶结构矩阵表示,（1）max z = C X s.t AX b X 0,min w = Y b s.t YA C Y 0,对偶问题,原问题,对偶模型其他结构关系,（2）若模型为 max z = C X s.t AX b X 0,max 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,变形

4、,设X= -X,max = -CX st. -AX b X 0,min w = Y b s.t YA C Y 0,则有,min w = 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,原问题与对偶问题关系表,原问题(对偶问题) 对偶问题(原问题) 目标

5、函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A约束条件系数行向量 AT 变量个数约束条件个数 max min 变量 x j : 约束方程 i : x j 0 x j 无约束 = x j 0 约束方程: 变量 y i : y i 0 = y i 无约束 y i 0,例2-10 写出下述线性规划问题的对偶问题。,例子,则由表中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题,对偶问题解法,练习,max z = 2y1+5y2+1y3 2 y1+3 y2 +1y3 3 1 y1 -5 y2 +1y3 2 3 y1 +1y3 -1,=,y1 0,y2 0,y3自由,s

6、.t.,解,三、对偶问题的性质,性质1 对称性 规范原始、对偶问题(P1)与(D1) 互相对偶。即对偶问题的对偶是原问题。 性质2 弱对偶性 设X, Y分别为(P1)与(D1)的任意可行解，则 CX Y b 性质3 最优性 设X,Y分别为(P1)与(D1)的任意可行解，则当 CX = Yb 时， X, Y分别是(P1)与(D1)的最优解。,三、对偶问题的性质,性质4无界性 互为对偶的两个线性规划问题，若其中一个问题的解无界，则另一个问题无可行解。 性质5 对偶定理 互为对偶的两个线性规划问题，若其中一个问题有最优解，则另一个问题也有最优解，且二者最优值相等。 注意： 无界性之逆命题不成立。 因

7、为一个问题无可行解时， 另一个问题可能解无界，也可能无可行解。,三、对偶问题的性质,兼容性 原始问题的检验行的相反数给出对偶问题的一个基本解。,X*= (4, 6, 4, 0, 0)T, z* = 42,y1,y2,y3,y4,y5,Y*= (0, 1/2, 1, 0, 0)T, w* = 42,3,4,5,1,2,互补基本解,X*= (4 ,6)T,Y*= (0 , ,1)T,X*= (4, 6, 4, 0, 0)T, Y*= (0, 1/2, 1, 0, 0)T,z*= 42 = w*,(P)的基本解 与(D)的基本解 相互对应, 且二者目标值相等。 我们把这样一对基本解 与 ，称为(P)

8、与(D)的互补基本解。,7. 互补松弛性 设 = ( x1 , x2 , , xn , xn+1, , xn+m )T = ( y1 , y2 , , ym , ym+1, , ym+n )T 是(P1) (D1)的一对互补基本解，那么, xj ym+j = 0， j = 1, 2 , , n xn+i yi = 0， i = 1, 2 , , m,例 已知线性规划问题,min =2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出

9、原问题的最优解 。,解：先写出它的对偶问题,max z=4y1+3y2 y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20,将y1* =4/5,y2* =3/5的值代入约束条件，,得=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,对偶变量的意义代表对企业资源的估价，与该种资源的市场价格不同，因此我们称之为影子价

10、格。,四、 对偶变量的经济含义,（1）资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 （2）影子价格是一种边际价格，在（2-12）式中将Z对 求偏导数得 ，这说明 相当于在给定的生产条件下， 每增加一个单位目标函数Z的增量。 （3）资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡

11、状态。,五、 对偶单纯形法,由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。,例：,min z=2x1+3x2 max z=-2x1-3x2+0 x3 +0 x4 s.t x1+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 ,x1,x2,x3,x4,XB,b,CB,-1 -1 1 0 -1 -2 0 1

12、,-2 -3 0 0,-3 -4,x3 x4,00,cj - zj,-2,-3,0,0,-1/2 0 1 -1/2 1/2 1 0 -1/2,x3 x2,-1 2,cj - zj,-1/2 0 0 -3/2,0 -3,1 0 -2 1 0 1 1 -1,x1 x2,21,cj - zj,0 0 -1 -1,-2 -3,列单纯表计算：,对偶单纯形法步骤：,1把m阶LP问题化成标准形（允许其右端常数为负）, 在其系数阵中找出或构造一个m阶排列阵作初始基, 建立初始单纯形表。若所有检验数 j0，则转2; 2最优性检验：检查表中解列各数值bi；若所有bi0, 则问题已得最优解，停止计算; 否则转3。

13、3无可行解判断：只要存在一个br0，它所在行中所有 arj0，则原始问题无可行解，对偶问题无下界，停止；否则转4。,4确定主元：先确定离基变量，按 min bibi 0 = bl 确定第 l 行的基变量 xBl 离基，第 l 行为主行； 后确定进基变量，按最小比值规则： m in j / aljalj 0 = k / alk 确定进基变量 xk 及主元 alk。 5按主元 alk 对当前表格进行一次换基运算， 得到一个新单纯形表，返2 。,第3章 对偶原理,30,练习,解,max z= -3x1 -2x2,s.t.,2x1+3x2+x3 = 18 x1 -x2 x4 = 2 x1+3x2 x5

14、 = 10 x1, x2, x3, x4, x5 0,x1+ x2 +x4 = 2,x13x2 +x5 = 10,第3章 对偶原理,31,3,2/3,min,-3,比 值,第3章 对偶原理,32,cj,基,解,x1 x2 x3 x4 x5,-3 -2 0 0 0,2 3 1 0 0,x3 x4 x5,18 -2 -10,-1 1 0 1 0,0 0 0,-1 -3 0 0 1,0 -3 - 2 0 0 0,-3,x3 x1 x2,0 -3 -2,4 1 0 0 -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/4,x3 x

15、4 x2,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/3,X*= (4,2)T z* = 16,单纯形法的矩阵描述,Cj ,x1,x2,x3,x4,XB,b,CB,1 1 1 0 1 2 0 1,2 3 0 0,34,x3 x4,00,cj - zj,2,3,0,0,1/2 0 1 -1/2 1/2 1 0 1/2,x3 x2,12,cj - zj,1/2 0 0 -3/2,03,1 0 2 -1 0 1 -1 1,x1 x2,21,cj - zj,0 0 -1 -1,23,1.初等行变换 相当于 左乘一个相应的初等阵 2. B-1 B = E 3. b/ = B-1 b 4. 目标函数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,