《对偶理论和灵敏度分析（新）ppt培训课件》由会员分享，可在线阅读，更多相关《对偶理论和灵敏度分析（新）ppt培训课件（128页珍藏版）》请在金锄头文库上搜索。
1、1,对偶理论和灵敏度分析,对偶的定义 原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关 系 对偶问题的性质 对偶的经济解释 对偶单纯形法 灵敏度分析,DUAL,2,第3节 线性规划对偶问题的提出,现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润为最大？,3,解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：,maxZ=4.5x1+5x2 s.t. 3x1+2x224 4x1+5x240 x1,x20,假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则 问题变成对于甲乙两种
2、原材料企业以多少最低价愿意出让？,解：设甲资源的出让价格为y1,乙资源的出让价格为y2,minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5y25 y1,y20,4,第4节 线性规划的对偶理论对偶问题的一般形式 一般认为变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“号。则称这些线性规划问题具有对称性。,max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,min w=b1y1+
3、b2y2+bmym s.t. a11y1+a21y2+am1ym c1 a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1, y2, , ym 0,Max Z=CX s.t. AXb X0,Minw=Yb s.t. AYC Y0,5,原始问题 max z=CX s.t. AXb X 0,对偶问题 min w=Yb s.t. AYC Y 0,max,b,A,C,C,AT,b,min,m,n,m,n,4.1原问题与对偶问题的关系,6,举例：,maxZ=3x1+2x2 s.t. -x1+2x24 3x1+2x214 x1-x2 3 x1,x20,minw=4y1
4、+14y2+y3 s.t. -y1+3y2+y33 2y1+2x2-y32 y1,y2,y30,y1,y2,y3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x1,x2,7,原始问题为 min z=2x1+3x2-x3 s.t. x1+2x2+x36 2x1-3x2+2x39 x1, x2, x30,根据定义，对偶问题为 max y=6y1+9y2 s.t. y1+2y22 2y1- 3y23 y1+2y2-1 y1, y20,原始问题是极小化问题 原始问题的约束全为 原始问题有3个变量，2个约束 原始问题的变量全部为非负,对偶问题是极大化问题 对偶问题的约束全为 对偶问题有2
5、个变量，3个约束 原始问题的变量全部为非负,原始问题变量的个数(3)等于对偶问题约束条件的个数(3) 原始问题约束条件的个数(2)等于对偶问题变量的个数(2),8,非对称形式的原对偶问题,minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x4=6 x10,x2,x30,x2+x3+x46 x2+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”)5 2x1 -2x3+(x4-x4”)-4 x2+x3 +
6、(x4-x4”) 6 -x2-x3-(x4-x4”) -6 x1,x2,x3 ,x4,x4” 0,y1,y2,y3,y3”,maxw=5y1-4y2+6(y3-y3”) s.t.-y1+2y2 -2 y1 +(y3-y3”) 3 -3y1-2y2 +(y3-y3”) -5 y1+y2+(y3-y3”) 1 -y1-y2-(y3-y3”) -1 y1,y2 ,y3,y3”0,9,maxw=5y1-4y2+6(y3-y3”) s.t.-y1+2y2 -2 y1 +(y3-y3”) 3 -3y1-2y2 +(y3-y3”) -5 y1+y2+(y3-y3”) 1 -y1-y2-(y3-y3”) -1
7、 y1,y2 ,y3,y3”0,设y2=-y2,y3=y3-y3”,则y20,y3无约束 此时对偶问题变为,maxw=5y1+4y2+6y3 s.t. y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 = 1 y10 ,y20,y3无约束,minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x45 2x1 +2x3-x4 4 x2+x3+x4 = 6 x10,x2,x30,10,原 始 对 偶 表,11,对偶关系,1、极大与极小的对偶 2、价值系数与资源系数的对偶 3、约束条件系数矩阵的对偶是矩阵的转置 4、反向不等式与非正的决策变量的对
8、偶 5、等式与非负限制的决策变量的对偶 6、最优解与检验数的对偶,12,min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max y=6w1+12w2+8w3+15w4 s.t. 3w1- w2+2w3+ w4 2 -w1+2w2+ w3+3w4 4 2w1- 3w2+2w3- w4 -1 w1 0,w2 ,w3 0,w4 0,=,Free,=,x10,x20,x3: Free,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(
9、4)。 原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。,写对偶问题的练习（1）,13,写对偶问题的练习（2）,原始问题,max z=2x1-x2+3x3-2x4 s.t. x1 +3x2 - 2x3 + x412 -2x1 + x2 -3x48 3x1 - 4x2 +5x3 - x4 = 15 x10, x2:Free, x30, x40,min y=12w1+8w2+15w3 s.t. w1 - 2w2 + 3w32 3w1 + w2 - 4w3=-1 -2w1 +5w33 w1 - 3w2 - w3-2 w10,w20, w3:Free,对偶
10、问题,14,maxZ=x1-2x2+3x3 s.t. 2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1, x30,练习,minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y31 4y1-2y2+3y3= -2 3y1+6y2+4y33 y10,y20,minZ=2x1+2x2+4x3 s.t. x1+3x2+4x32 2x1+ x2+3x33 x1+4x2+3x3=5 x1 0, x20,maxw=2y1+3y2+5y3 s.t. y1+2y2+ y32 3y1+ y2+4y3 2 4y1+3y2+3y34 y10,y20
11、,15,原始和对偶问题可行解目标函数值比较,min z=2x1+3x2 s.t. x1+3x23 2x1+x2 4 x1, x2 0,max w=3y1+4y2 s.t. y1+2y22 3y1+y2 3 y1, y2 0,16,单纯形法计算的矩阵描述,Max Z=CX AXb X0 其中X(x1,x2xn)T,Max Z=CX+0Xs AX+IXs=b X,Xs0 其中Xs(xn+1,xn+2xn+m)T I 为mm的单位矩阵,17,对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1； 初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b； 约束矩阵（A，I）（B，N，I），迭
12、代后为 （B-1B，B-1N，B-1I）（I，B-1N，B-1)； 初始单纯形表中xj的系数向量为Pj，迭代后为Pj，且Pj=B-1Pj。,18,当B为最优基时，XB为最优解时，则有：,CN-CBB-1N0,-CBB-10,CB-CBI=0,代入得： CNCBB-1N+CB-CBI0 CCBB-1(B+N)0,整理得： CCBB-1 A0 -CBB-10,令CBB-1为单纯形乘子，YCBB-1,则： CY A0 -Y0,Y AC Y 0,WYb=CBB-1b=Z,所以当原问题为最优解时，对偶问题为可行解且具有相 同的目标函数值。,19,maxZ=4.5x1+5x2 s.t. 3x1+2x224
13、 4x1+5x240 x1,x20,minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5y25 y1,y20,y1,y2,x1,x2,maxZ=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0,minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5Y2-y4=5 y1,y2,y3,y40,20,解原问题：,21,22,23,Z=4.540/7524/7=300/7,24,解对偶问题：,w=245/14406/7=300/7,25,(x3,x4)=(0,0),(y3,y4)=(0,0),
14、-y1,-y2,-y4,-y3,x1,x2,x4,x3,26,（1）对称性：对偶问题的对偶,max z=6x1+9x2 s.t. x1+2x22 2x1- 3x23 x1+2x2-1 x1, x20,minw=2y1+3y2-y3 s.t. y1+2y2+y36 2y1-3y2+2y39 y1, y2, y30,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。,max u=6w1+9w2 s.t. w1+2w22 2w1- 3w23 w1+2w2-1 w1, w20,4.2对偶问题的基本性质,27,maxZ=x1+4x2+2x3 s.t. 5x1-x2
15、+2x38 x1+3x2-3x35 x1,x2,x30,minw=8y1+5y2 s.t. 5y1+y21 -y1+3y24 2y1-3y2 2 y1,y20,28,4.2 对偶问题的基本性质,原始问题 max z=CX s.t. AXb X 0,对偶问题 min w=Yb s.t. AYC Y 0,（2）弱对偶性 若X为原问题的可行解，Y为对偶问题的可行解，则恒有 CXYb,29,推论： 原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。 （3）无界性 如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。 推论： 若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界 若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。,
