《运筹学课件对偶理论及灵敏度分析》由会员分享，可在线阅读，更多相关《运筹学课件对偶理论及灵敏度分析（137页珍藏版）》请在金锄头文库上搜索。
1、1,对偶线性规划,对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关系 对偶单纯形法 对偶的经济解释 灵敏度分析,DUAL,dual linear programming,2,2.1 线性规划的对偶问题,一、对偶问题的提出现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润最大？,3,解:设生产A1为x1单位，生产A2为x2单位,则线性规划问题为：,maxZ=4.5x1+5x2s.t. 3x1+2x2244x1+5x240x1,x20,解：设甲资源的出让单价为y
2、1,乙资源的出让单价为y2,minw=24y1+40y2s.t. 3y1+4y24.52y1+5y25y1,y20,另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？,4,解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：,maxZ=4.5x1+5x2s.t. 3x1+2x2244x1+5x240x1,x20,解：设甲资源的出让价格为y1,乙资源的出让价格为y2,minw=24y1+40y2s.t. 3y1+4y24.52y1+5y25y1,y20,另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？,
3、5,解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：,maxZ=4.5x1+5x2s.t. 3x1+2x2244x1+5x240x1,x20,解：设甲资源的出让价格为y1,乙资源的出让价格为y2,minw=24y1+40y2s.t. 3y1+4y24.52y1+5y25y1,y20,另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？,二、对称形式下对偶问题的一般形式,定义：变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“”号，称此线性规划问题具有对称形式,max z=c1x1+c2x2+cnxn
4、s.t. a11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2am1x1+am2x2+amnxn bmx1, x2, , xn 0,min w=b1y1+b2y2+bmym s.t. a11y1+a21y2+am1ym c1a12y1+a22y2+am2ym c2a1ny1+a2ny2+amnym cny1, y2, , ym 0,max Z=CXs.t. AXbX0,min w=bTYs.t. ATYCTY0,原始问题 max z=CX s.t. AXbX 0,对偶问题 min w=bTY s.t. ATYCTY 0,max,b,A,C,CT,AT,bT,min,
5、m,n,m,n,maxZ=3x1+2x2s.t. -x1+2x243x1+2x214x1-x2 3x1,x20,minw=4y1+14y2+3y3s.t. -y1+3y2+y332y1+2x2-y32y1,y2,y30,y1,y2,y3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x1,x2,举例,原问题： maxZ=x1+4x2+2x3s.t. 5x1-x2+2x38x1+3x2-3x35x1,x2,x30,对偶问题： minw=8y1+5y2s.t. 5y1+y21-y1+3y242y1-3y2 2y1,y20,练习,结论：对偶问题的对偶为原问题,原始问题 max Z=CX
6、 s.t. AXbX 0,对偶问题 min w=YTb s.t. ATYCTY 0,令w=-w,max w=-YTb s.t. -ATY-CTY 0,对偶,min Z=-CX s.t. -AX-bX 0,令Z=-Z,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题，另一个就是它的对偶问题。,11,对偶问题的对偶,max z=6x1+9x2 s.t. x1+2x222x1- 3x23x1+2x2-1x1, x20,minw=2y1+3y2-y3 s.t. y1+2y2+y362y1-3y2+2y39y1, y2, y30,根据定义写出对偶问题,根据定义写出对偶问题,max u=6
7、w1+9w2 s.t. w1+2w222w1- 3w23w1+2w2-1w1, w20,minz=2x1+3x2-5x3+x4s.t. x1+x2-3x3+x452x1 +2x3-x44x2+x3+x4=6x10,x2,x30,x2+x3+x46x2+x3+x46,-x1=x1,x10;x4-x4”=x4,x4 0,x4” 0,minz=-2x1+3x2-5x3+(x4-x4”)s.t.-x1+x2-3x3+(x4-x4”)52x1 -2x3+(x4-x4”)-4x2+x3 +(x4-x4”) 6-x2-x3-(x4-x4”) -6x1,x2,x3 ,x4,x4” 0,y1,y2,y3,y3”
8、,maxw=5y1-4y2+6(y3-y3”)s.t.-y1+2y2 -2y1 +(y3-y3”) 3-3y1-2y2 +(y3-y3”) -5y1+y2+(y3-y3”) 1-y1-y2-(y3-y3”) -1y1,y2 ,y3,y3”0,三、非对称形式的原对偶问题,引例,13,maxw=5y1-4y2+6(y3-y3”)s.t.-y1+2y2 -2y1 +(y3-y3”) 3-3y1-2y2 +(y3-y3”) -5y1+y2+(y3-y3”) 1-y1-y2-(y3-y3”) -1y1,y2 ,y3,y3”0,设y2=-y2,y3=y3-y3”,则y20,y3无约束 此时对偶问题变为,m
9、axw=5y1+4y2+6y3s.t. y1+2y2 2y1 +y3 3-3y1+2y2+y3 -5y1 -y2 +y3 = 1 y10 ,y20,y3无约束,14,maxw=5y1+4y2+6y3s.t. y1+2y2 2y1 +y3 3-3y1+2y2+y3 -5y1 -y2 +y3 = 1 y10 ,y20,y3无约束,minz=2x1+3x2-5x3+x4s.t. x1+x2-3x3+x452x1 +2x3-x4 4x2+x3+x4 = 6x10,x2,x30,原问题,对偶问题,比较后得出什么结论？,min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6-x1+2x2
10、-3x3 122x1+x2+2x3 8x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4 s.t. 3y1- y2+2y3+ y4 2-y1+2y2+ y3+3y4 42y1- 3y2+2y3- y4 -1y1 0,y2 ,y3 0,y4 0,=,Free,=,x10,x20,x3: Free,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。,写对偶问题的练习（1）,原始问题,max z=2x1-x2+3x3
11、-2x4 s.t. x1 +3x2 - 2x3 + x412-2x1 + x2 -3x483x1 - 4x2 +5x3 - x4 = 15x10, x2:Free, x30, x40,min w=12y1+8y2+15y3 s.t. y1 2y2 + 3y323y1 + y2 4y3=-1-2y1 +5y33y1 3y2 - y3-2y10,y20, y3:Free,对偶问题,写对偶问题的练习（2）,17,maxZ=x1-2x2+3x3s.t. 2x1+4x2+3x31003x1-2x2+6x32005x1+3x2+4x3=150x1, x30,练习,minw=100y1+200y2+150y
12、3s.t. 2y1+3y2+5y314y1-2y2+3y3= -23y1+6y2+4y33y10,y20,minZ=2x1+2x2+4x3s.t. x1+3x2+4x322x1+ x2+3x33x1+4x2+3x3=5x1 0, x20,maxw=2y1+3y2+5y3s.t. y1+2y2+ y323y1+ y2+4y3 24y1+3y2+3y3=4y10,y20,原问题Max Z=CXAXbX0 其中X(x1,x2xn)T,Max Z=CX+0XsAX+IXs=bX, Xs0 其中Xs(xn+1,xn+2xn+m)T I 为mm的单位矩阵,2.2 对偶问题的基本性质,一、单纯性法计算的矩阵
13、描述,其初始单纯性表及经过若干次迭代后的单纯性表如下：,20,(1)初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1； (2)初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b； (3)约束矩阵（A，I）（B，N，I），迭代后为（B-1B，B-1N，B-1I）（I，B-1N，B-1)； (4)初始单纯形表中xj的系数向量为Pj，迭代后为Pj，且Pj=B-1Pj。,21,(5),当B为最优基，XB为最优解时，则有：,CN-CBB-1N0,-CBB-10,CB-CBI=0,CCBB-1 A0-CBB-10,令YTCBB-1，称 CBB-1为单纯形乘子,则： CYT A0-YT0,AT
14、YCTY 0,Y为对偶问题的可行解且 WYTb=CBB-1b=Z,结论：当原问题为最优解时，Y为对偶问题为可行解且具有相 同的目标函数值。,maxZ=4.5x1+5x2s.t. 3x1+2x2244x1+5x240x1,x20,minw=24y1+40y2s.t. 3y1+4y24.52y1+5x25y1,y20,y1,y2,x1,x2,maxZ=4.5x1+5x2s.t. 3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,0,minw=24y1+40y2s.t. 3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y40,例题,24,(x3,x4)=(0,0),(y3,y4)=(0,0),-y1,-y2,-y4,-y3,x1,x2,x4,x3,25,maxZ=4.5x1+5x2s.t. 3x1+2x2244x1+5x240x1,x20,minw=24y1+40y2s.t. 3y1+4y24.52y1+5x25y1,y20,y1,y2,x1,x2,maxZ=4.5x1+5x2s.t. 3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,0,
