《运筹学二章对偶线性规.ppt》由会员分享，可在线阅读，更多相关《运筹学二章对偶线性规.ppt（49页珍藏版）》请在三一办公上搜索。
1、第二章 对偶理论与灵敏度分析,2.1 线性规划的对偶问题2.2 对偶问题的基本性质2.3 影子价格2.4 对偶单纯形法2.5 灵敏度分析,DUAL,本章学习要求,掌握对偶理论及其性质掌握影子价格的应用掌握对偶单纯形法熟悉灵敏度分析的概念和内容掌握右侧常数，价值系数，工艺系数的变换对原最优解的影响掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围,2.1线性规划的对偶问题,问题的提出对称形式下对偶问题的一般形式非对称形式下的原问题与对偶问题的关系,一、对偶问题的提出,每一个LP问题，都伴随着另一个LP，而且二者有密切关系，互为对偶，另其中一个问题为原问题，另一个问题为对偶
2、问题，只要得到了其中一个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问题就可以了。,例1：（美佳公司）美佳公司应如何生产安排，使已有资源利润最大化。,某公司至少该出多大代价，使美佳公司愿意放弃自己的资源，,数学模型,Z*=8.5,W*=8.5,二、对偶问题的一般形式 一般认为变量均为非负约束的情况下，约束条件在目标函数取Max时均取“”号；当目标函数求Min值时均取“号。则称这些线性规划问题具有对称性。,max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1
3、,x2,xn 0,min w=b1y1+b2y2+bmyms.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,原问题max z=CXs.t.AXb X 0,对偶问题min w=Ybs.t.AYCY 0,max,b,C,C,AT,b,min,m,n,m,n,A,举例：,maxZ=3x1+2x2 s.t.-x1+2x24 3x1+2x214 x1-x2 3 x1,x20,minw=4y1+14y2+y3 s.t.-y1
4、+3y2+y33 2y1+2x2-y32 y1,y2,y30,y1,y2,y3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x1,x2,原始问题为min z=2x1+3x2-x3s.t.x1+2x2+x36 2x1-3x2+2x39 x1,x2,x30,根据定义，对偶问题为max y=6y1+9y2s.t.y1+2y22 2y1-3y23 y1+2y2-1 y1,y20,原始问题是极小化问题原始问题的约束全为原始问题有3个变量，2个约束原始问题的变量全部为非负,对偶问题是极大化问题对偶问题的约束全为对偶问题有2个变量，3个约束原始问题的变量全部为非负,对偶问题的对偶,max z
5、=6x1+9x2s.t.x1+2x22 2x1-3x23 x1+2x2-1 x1,x20,minw=2y1+3y2-y3s.t.y1+2y2+y36 2y1-3y2+2y39 y1,y2,y30,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。,max u=6w1+9w2s.t.w1+2w22 2w1-3w23 w1+2w2-1 w1,w20,对偶问题的性质总结,对偶的对偶就是原始问题,max z=CXs.t.AXb X 0,min w=Ybs.t.ATY CY0,max u=CWs.t.AWCW 0,maxZ=x1+4x2+2x3 s.t.5x1-x
6、2+2x38 x1+3x2-3x35 x1,x2,x30,minw=8y1+5y2 s.t.5y1+y21-y1+3y24 2y1-3y2 2 y1,y20,三、非对称形式的原对偶问题,minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1+2x3-x44 x2+x3+x4=6 x10,x2,x30,minz=-2x1+3x2-5x3+(x4-x4”)1+x2-3x3+(x4-x4”)5 2x1-2x3+(x4-x4”)-4 x2+x3+(x4-x4”)6-x2-x3-(x4-x4”)-6 x1,x2,x3,x4,x4”0,y1,y2,y3,y3”,maxw=5y1
7、-4y2+6(y3-y3”)1+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,maxw=5y1+4y2+6y3 s.t.y1+2y2 2 y1+y3 3-3y1+2y2+y3-5 y1-y2+y3=1 y10,y20,y3无约束,结论,LP(LD)MaxX0X0X无约束St st St=,LD(LP)Minst St St=Y0Y0Y无约束,min z=2x1+4x2-x3s.t.3x1-x2+2x3 6-x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2
8、-x3 15,max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2-y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4-1 y1 0,y2,y3 0,y4 0,=,Free,=,x10,x20,x3:Free,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。原始问题约束条件的性质影响对偶问题变量的性质。,写对偶问题的练习（1）,写对偶问题的练习（2）,原始问题,max z=2x1-x2+3x3-2x4s.t.x1+3x2-2x3+x412-
9、2x1+x2-3x48 3x1-4x2+5x3-x4=15 x10,x2:Free,x30,x40,min w=12y1+8y2+15y3s.t.y1 2y2+3y32 3y1+y2 4y3=-1-2y1+5y33 y1 3y2-y3-2 y10,y20,y3:Free,对偶问题,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=2x
10、1+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,课后作业P74 2.1(4),2.2 对偶问题的基本性质,单纯形法的矩阵描述对偶问题的基本性质,一、单纯形法计算的矩阵描述,Max Z=CX AXb X0,Max Z=CX AX+Xs=b X 0,Xs0,令X=(XB,XN)T C=(CB,CN)A=(B,N),BXB+NXN+XS=bB-1BXB+B-1NXN+B-1XS=B-1bXB=B-1
11、b-B-1NXN-B-1XS,MaxZ=CB(B-1b-B-1NXN-B-1XS)+CNXN=CBB-1b（CN-CBB-1N)XN-CBB-1XS,某一决策变量xk系数列向量迭代前为Pk，迭代后为B-1Pk。,当B为最优基时MaxZ=CBB-1b（CN-CBB-1N)XN-CBB-1XS,令Y=CBB-1,由此可以看出，当X为最优解时，Y为对偶问题的可行解。且该可行解对应的目标函数值W=Yb=CX*,对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；约束矩阵（A，I）（B，N，I），迭代后为（B-1B，B-1N，B-1I）
12、（I，B-1N，B-1)；初始单纯形表中xj的系数向量为Pj，迭代后为Pj，且Pj=B-1Pj。,二、对偶问题的基本性质,原始问题max z=CXs.t.AXb X 0,对偶问题min w=Ybs.t.AY CY 0,1.弱对偶性若X0为原问题的可行解，Y0为对偶问题的可行解，则恒有CX0Y0b证明：X0 0为LP的可行解，Y0 0为LD的可行解，则有：AX0 b AY0 C Y0AX0 Y0b(AY0)X0(C)X0 Y0b Y0AX0 CX0,推论:(LP-Max LD-Min)1.LP任一可行解的目标函数是其LD目标函数值的下界，反之LD任一可行解的目标函数是其LP目标函数的上界。Z=C
13、XMaxZ=MinW Yb2.如LP有可行解且目标函数值无界，则其LD无可行解；反之LD有可行解且目标函数无界，则LP无可行解。(对偶问题无可行解时，其原问题无界解或无可行解。)Z=CX+Yb W=Yb-CX3.若LP有可行解而其LD无可行解时，LP目标函数无界反之，若LD有可行解而其LP无可行解时，LD目标函数无界。,2.最优性若X0为LP的可行解，Y0为LD的可行解，且CX0Y0b,则X0，Y0分别为LP和LD的最优解。证明：设LP的最优解为X*,LD的最优解为Y*又因为：CX*CX0=Y0b Y*b又由弱对偶性定理：CX Yb则X0必为X*,Y0必为Y*,3.强对偶性若原问题和对偶问题均
14、具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。,4.互补松弛定理如果X*,Y*分别为LP,LD问题的可行解，则X*,Y*为最优解的充要条件为：Y*XS*=0YS*X*=0,当LP中第i个约束是严格不等式，则Y中的Yi必为0，如果Yi不为0,则LP中第i个约束为严格等式。,当LD中第j个约束是严格不等式，则X中的xj必为0，如果xj不为0,则LD中第j个约束为严格等式。,课堂作业P74 2.3课后作业(P75-P76)2.4 2.5 2.6 2.7,2.3 影子价格,阐述对偶变量的经济意义，即对偶变量的经济解释引例：美佳公司,如果已知LP的X*=(7/2,3/2,15/2,0,0)
15、Z*=8.5求解Y*,W*？由对偶问题的基本性质知：W*=Z*=8.5,15Y1+24y2+5y3=8.5,又因为Y*XS*=0 X*代入LP的约束条件中，知为严格不等式，则xS10，则y1=0,由互补松弛定理：因为YS*X*=0 X10,X20则yS1*=0,yS2*=0，即LD的，为严格等式6y2+y3=25y1+2y2+y3=1,Y1=0 Y2=1/4 y3=1/2,1.定理：根据对偶问题的基本性质,对LP为生产问题而言：bi表示LP中第i种资源的拥有量；Cj表示第j种产品的利润或产值其中Yi*可用下面数学式求得：,1）yi*可解释为第i种资源的边际价格，即在其他条件不变的情况下，只增加
16、单位第i种资源所引起的目标函数最优值的变化，bibi+1,bi=1，Z*的值为yi*。2）yi*也可解释为出让单位第i种资源的收益；3）yi*的取值随cj,xj,Aij的变化而变化，因此企业不同，产业不同，资源拥有量不同，yi*的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。,例：美佳公司,X*=(7/2,3/2,15/2,0,0)Z*=8.5,由1）可知：y1*为变为5x216时Z*的增量，y1*Z*0Y2*为变为6x12x225时Z*的增量所以当A的资源增加时，Z*无变化，Y1*0LP中约束为严格的不等式，表明A没有被充分利用。,2.影子价格的应用（对偶问题的应用）,1）yi*实
17、际上是一种机会成本，当A的单位市场价格无论多低时，还应卖出A资源，直到15/2；当B的单位市场价格0表明该资源已充分利用，因此该资源的增加或减少均会引起Z*的变动，Yi*越大，变动越大。由美佳可得：Y1=0表明A没有充分利用，y2=1/4,y3=1/2表明y3的变动对美佳公司利益的影响要大。3）新产品是否投产以及合理定价的问题,例：美佳考虑生产电器，要耗A 3，B 2，调试1个单位，市场价格2元，问是否值得生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。,4）合理调配资源因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有些使用中价值低，有些使用中价值高。例：
18、美佳公司有两个子公司（1）A0 B 1/4 C 1/2,(2)A2 B 0 C 1,因此：（1）（2）A A B B C C,课后作业P76 2.8,2.4 对偶单纯形法,一、基本思路从LP的一个基解出发，转换到另一个基解；在转换过程中，保持对应的LD的解Y的可行性（相当于LP的j0），逐步消除该基解的不可行性，直到基解变成可行解，就获得了最优解。注：该方法不是求解LD的单纯形法，而是利用对偶关系求解LP的另一种方法。,二、计算步骤：1.假定已给一对偶可行基单位阵B（对应LD问题的解可行），相应的基解XBb。2.若b的各个分量均非负，则这个解就是最优解，停止迭代。3.如果XB有分量xl0，且x
19、l所在行的所有系数alj0，则LP无可行解，停止迭代。如果XB有分量xl0，且该分量所在行的系数alj有负分量，则该解不是LP的最优解，继续。4.如果min bi/bi0bl，则xl为换出变量minj/alj|alj0=k/alk,则xk为换入变量5.以alk为主元，进行系数行变换，得一新的对偶可行基解(也称正则解），转第2步。,比较单纯形法和对偶单纯形法单纯形法：先从基解、可行解出发，通过若干次迭代使满足j0对偶单纯形法:先从基解，对偶可行解（等价于j0）出发，再通过若干次迭代使之可行。对偶单纯形法的优缺点：优点:初始基解可为负，减少人工变量数量，使计算简单；灵敏度分析时使用方便。缺点：不能
20、保证所有的Lp问题的初始单纯形表中的j0。,例:,1,4/3,1,2,j,4/5,2,1,j,所以：X*=(x1,x2)T=(11/5,2/5)T Z*=28/5,课后作业2.9（1）,2.5 灵敏度分析,Cj变化时bi变化时增加一个变量xj时增加一个约束条件时技术系数Pj发生变化时,LP变化导致的变化可分为：X*不变，Z*改变X*中基变量不变，取值改变，Z*改变。X*中基变量改变，Z*改变,一、分析cj变化,当CNj发生变化时，对应的Nj变化Nj0 X*,Z*不变Nj0 用单纯形法进行基变换,当CBi发生变化时，所有Nj变化Nj0 X*不变,Z*变化Nj0 用单纯形法进行基变换,例5：美佳公
21、司,1.当C1由2变为1.5时，当C2由1变为2时，最优解有什么变化？,2.当C1不变，C2在什么范围内变换时，最优解不变？,解：1,1.5,1.5,1/8,-9/4,2,2,解：2,c2,c2,4,5,4=（c2-2）/405=（23c2）/2 0,2/3c22,二、分析bi变化,该变化只会引起右侧常数的变化：B-1b0 则基变量不变，X*的取值变化，Z*变化B-1b 0 用对偶单纯形法进行基变换,例6：美佳公司,1.当其他能力不变，B设备由24变为32时，最优解有什么变化？,2.当A,B不变，调试工序能力在什么范围内变换时，基变量不变？,解：1：,解：2,4b36,三、增加一个变量xj的分
22、析,相当于在单纯形表中增加了一列xk：k0 则X*,Z*不变k0 在最终单纯形表上进行基变换（添加一个变量，增加一列），系数列向量应相应变化Pk=B-1Pk,例7：新产品，耗A3小时，B4小时，调试时间2小时，预期盈利3元/件，问是否值得投产？如投产，该生产计划如何变化？解：设x6代表生产产品的件数。,表示值得投产,四、增加一个约束条件的分析,相当于添加一道工序。通常把X*代入新的约束条件。若满足，X*,Z*不变。若不满足，把新约束放入最终单纯形表中，用初等行变换使变成基解，再用对偶单纯形法变换。,例9：美佳公司增加一道环境检测工序，：3h，：2h，能力是12h，分析该生产计划如何变化？解：把X*=(x1,x2,x3)=(7/2,3/2,15/2)代入新约束：37/223/227/212不满足新约束。,0,0,0,1,j,五、技术系数Pj发生变化分析,通常是按列即Pj发生变化，该变化可转变为增加xj的情况：k0 则X*,Z*不变k0 在最终单纯形表上进行基变换（添加一个变量，增加一列），系数列向量应相应变化Pk=B-1Pk,课后作业 2.142.16,
