![第二章对偶线性规_第1页](http://file4.renrendoc.com/view/48650c74f04f43cb8a6c9aca6d17a2ee/48650c74f04f43cb8a6c9aca6d17a2ee1.gif)
![第二章对偶线性规_第2页](http://file4.renrendoc.com/view/48650c74f04f43cb8a6c9aca6d17a2ee/48650c74f04f43cb8a6c9aca6d17a2ee2.gif)
![第二章对偶线性规_第3页](http://file4.renrendoc.com/view/48650c74f04f43cb8a6c9aca6d17a2ee/48650c74f04f43cb8a6c9aca6d17a2ee3.gif)
![第二章对偶线性规_第4页](http://file4.renrendoc.com/view/48650c74f04f43cb8a6c9aca6d17a2ee/48650c74f04f43cb8a6c9aca6d17a2ee4.gif)
![第二章对偶线性规_第5页](http://file4.renrendoc.com/view/48650c74f04f43cb8a6c9aca6d17a2ee/48650c74f04f43cb8a6c9aca6d17a2ee5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第二章对偶线性规2023/5/3浙江科技学院经济管理学院管工系1第1页,共49页,2023年,2月20日,星期三本章学习要求掌握对偶理论及其性质掌握影子价格的应用掌握对偶单纯形法熟悉灵敏度分析的概念和内容掌握右侧常数,价值系数,工艺系数的变换对原最优解的影响掌握增加新变量和增加新约束条件对原最优解的影响,并求出相应因素的灵敏度范围第2页,共49页,2023年,2月20日,星期三2.1线性规划的对偶问题问题的提出对称形式下对偶问题的一般形式非对称形式下的原问题与对偶问题的关系第3页,共49页,2023年,2月20日,星期三一、对偶问题的提出每一个LP问题,都伴随着另一个LP,而且二者有密切关系,互为对偶,另其中一个问题为原问题,另一个问题为对偶问题,只要得到了其中一个问题的解(目标值),也得到另一问题的解,因此通常只求解一个问题就可以了。例1:(美佳公司)美佳公司应如何生产安排,使已有资源利润最大化。某公司至少该出多大代价,使美佳公司愿意放弃自己的资源,产品资源ⅠⅡ资源约束A0515B6224调试工序115单位产品利润21产品资源AB调试工序单位资源利润Ⅰ0612Ⅱ5211资源量15245第4页,共49页,2023年,2月20日,星期三数学模型Cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2cj-15-24-500-MCBYBby1y2y3y4y5y6θ-My62061-1011/3-15y11/512/51/50-1/505/2σj06M-18M-2-M-30-24y21/3011/6-1/601/62-15y11/5102/151/15-1/5-1/151/2σj001-3-3-M+8-24y21/4-5/410-1/41/41/2-5y31/215/2011/2-3/2-3σj-15/200-7/2-3/2-M-3①②Z*=8.5W*=8.5第5页,共49页,2023年,2月20日,星期三二、对偶问题的一般形式一般认为变量均为非负约束的情况下,约束条件在目标函数取Max时均取“≤”号;当目标函数求Min值时均取“≥“号。则称这些线性规划问题具有对称性。maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2……am1x1+am2x2+……+amnxn≤bmx1,x2,……,xn≥0minw=b1y1+b2y2+……+bmyms.t.a11y1+a21y2+……+am1ym≥c1a12y1+a22y2+……+am2ym
≥c2……a1ny1+a2ny2+……+amnym
≥cny1,y2,……,ym≥0MaxZ=CXs.t.AX≤bX≥0Minw=Y’bs.t.A’Y≥C’Y≥0第6页,共49页,2023年,2月20日,星期三原问题maxz=CXs.t.AX≤b X≥0对偶问题minw=Y’bs.t.A’Y≥C’ Y≥0≥maxbCCATb≤minmnmnA第7页,共49页,2023年,2月20日,星期三举例:maxZ=3x1+2x2s.t.-x1+2x2≤43x1+2x2≤14x1-x2≤3x1,x2≥0minw=4y1+14y2+y3s.t.-y1+3y2+y3≥32y1+2x2-y3≥2y1,y2,y3≥0y1y2y3第一种资源第二种资源第三种资源第一种产品第二种产品x1x2第8页,共49页,2023年,2月20日,星期三原始问题为minz=2x1+3x2-x3s.t.x1+2x2+x3≥62x1-3x2+2x3≥9x1,x2,x3≥0根据定义,对偶问题为maxy=6y1+9y2s.t.y1+2y2≤22y1-3y2≤3y1+2y2≤-1y1,y2≥0原始问题是极小化问题原始问题的约束全为≥原始问题有3个变量,2个约束原始问题的变量全部为非负对偶问题是极大化问题对偶问题的约束全为≤对偶问题有2个变量,3个约束原始问题的变量全部为非负第9页,共49页,2023年,2月20日,星期三对偶问题的对偶maxz=6x1+9x2s.t.x1+2x2≤22x1-3x2≤3x1+2x2≤-1x1,x2≥0minw=2y1+3y2-y3s.t.y1+2y2+y3≥62y1-3y2+2y3≥9y1,y2,y3≥0对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。根据定义写出对偶问题根据定义写出对偶问题maxu=6w1+9w2s.t.w1+2w2≤22w1-3w2≤3w1+2w2≤-1w1,w2≥0第10页,共49页,2023年,2月20日,星期三对偶问题的性质总结对偶的对偶就是原始问题maxz=CXs.t.AX≤bX≥0minw=Y’bs.t.ATY≥
C’ Y≥0对偶的定义maxu=CWs.t.AW≤C W≥0第11页,共49页,2023年,2月20日,星期三maxZ=x1+4x2+2x3s.t.5x1-x2+2x3≤8x1+3x2-3x3≤5x1,x2,x3≥0minw=8y1+5y2s.t.5y1+y2≥1-y1+3y2≥42y1-3y2≥2y1,y2≥0第12页,共49页,2023年,2月20日,星期三三、非对称形式的原—对偶问题minz=2x1+3x2-5x3+x4s.t.x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0minz=-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变为对称形式y1y2’y3’y3”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写出对偶问题maxw=5y1+4y2+6y3s.t.y1+2y2≥2y1+y3≤3-3y1+2y2+y3≤-5y1-y2+y3=1y1≥0,y2≤0,y3无约束第13页,共49页,2023年,2月20日,星期三结论LP(LD)MaxX≥0X≤0X无约束St≤st≥St=LD(LP)Minst≥St≤St=Y≥0Y≤0Y无约束第14页,共49页,2023年,2月20日,星期三minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥Free≤≥≥=≤≥x1≥0x2≤0x3:Free原始问题变量的个数(3)等于对偶问题约束条件的个数(3);原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习(1)第15页,共49页,2023年,2月20日,星期三写对偶问题的练习(2)原始问题maxz=2x1-x2+3x3-2x4s.t.x1+3x2-2x3+x4≤12-2x1+x2-3x4≥83x1-4x2+5x3-x4=15x1≥0,x2:Free,x3≤0,x4≥0minw=12y1+8y2+15y3s.t.y1–2y2+3y3≥23y1+y2–4y3=-1-2y1+5y3≤3y1–3y2-y3≥-2y1≥0,y2≤0,y3:Free对偶问题第16页,共49页,2023年,2月20日,星期三maxZ=x1-2x2+3x3s.t.2x1+4x2+3x3≥1003x1-2x2+6x3≤2005x1+3x2+4x3=150x1,x3≥0练习minw=100y1+200y2+150y3s.t.2y1+3y2+5y3≥14y1-2y2+3y3=-23y1+6y2+4y3≥3y1≤0,y2≥0minZ=2x1+2x2+4x3s.t.x1+3x2+4x3≥22x1+x2+3x3≤3x1+4x2+3x3=5x1≥0,x2≤0maxw=2y1+3y2+5y3s.t.y1+2y2+y3≤23y1+y2+4y3≥24y1+3y2+3y3≥4y1≥0,y2≤0第17页,共49页,2023年,2月20日,星期三课后作业P742.1(4)第18页,共49页,2023年,2月20日,星期三2.2对偶问题的基本性质单纯形法的矩阵描述对偶问题的基本性质第19页,共49页,2023年,2月20日,星期三一、单纯形法计算的矩阵描述MaxZ=CXAX≤bX≥0MaxZ=CXAX+Xs=bX≥0,Xs≥0引入松弛变量令X=(XB,XN)TC=(CB,CN)A=(B,N)
BXB+NXN+XS=bB-1BXB+B-1NXN+B-1XS=B-1bXB=B-1b-B-1NXN-B-1XSMaxZ=CB(B-1b-B-1NXN-B-1XS)+CNXN
=CBB-1b+(CN-CBB-1N)XN-CBB-1XS第20页,共49页,2023年,2月20日,星期三某一决策变量xk系数列向量迭代前为Pk,迭代后为B-1Pk。当B为最优基时MaxZ=CBB-1b+(CN-CBB-1N)XN-CBB-1XS令Y’=CBB-1由此可以看出,当X为最优解时,Y为对偶问题的可行解。且该可行解对应的目标函数值W=Y’b=CX*第21页,共49页,2023年,2月20日,星期三非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0……基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1对应初始单纯形表中的单位矩阵I,迭代后的单纯形表中为B-1;初始单纯形表中基变量Xs=b,迭代后的表中为XB=B-1b;约束矩阵(A,I)=(B,N,I),迭代后为(B-1B,B-1N,B-1I)=(I,B-1N,B-1);初始单纯形表中xj的系数向量为Pj,迭代后为Pj’,且Pj’=B-1Pj’。第22页,共49页,2023年,2月20日,星期三二、对偶问题的基本性质原始问题maxz=CXs.t.AX≤b X≥0对偶问题minw=Y’bs.t.A’Y≥C’ Y≥01.弱对偶性若X0为原问题的可行解,Y0为对偶问题的可行解,则恒有CX0≤Y0’b证明:X0≥0为LP的可行解,Y0≥0为LD的可行解,则有:AX0≤bA’Y0≥C’→Y0’AX0≤Y0’b(A’Y0)’X0≥(C’)’X0→Y0’b≥Y0’AX0≥CX0第23页,共49页,2023年,2月20日,星期三推论:(LP-MaxLD-Min)1.LP任一可行解的目标函数是其LD目标函数值的下界,反之LD任一可行解的目标函数是其LP目标函数的上界。Z=CX≤MaxZ=MinW≤Y’b2.如LP有可行解且目标函数值无界,则其LD无可行解;反之LD有可行解且目标函数无界,则LP无可行解。(对偶问题无可行解时,其原问题无界解或无可行解。)Z=CX→+∞≤Y’bW=Y’b→-∞≥CX3.若LP有可行解而其LD无可行解时,LP目标函数无界反之,若LD有可行解而其LP无可行解时,LD目标函数无界。第24页,共49页,2023年,2月20日,星期三2.最优性若X0为LP的可行解,Y0为LD的可行解,且CX0=Y0’b,则X0,Y0分别为LP和LD的最优解。证明:设LP的最优解为X*,LD的最优解为Y*又因为:CX*≥CX0=Y0’b≥Y*’b又由弱对偶性定理:CX≤Y’b则X0必为X*,Y0必为Y*3.强对偶性若原问题和对偶问题均具有可行解,则两者均具有最优解,且他们的最优解的目标值相等。第25页,共49页,2023年,2月20日,星期三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个约束为严格等式。第26页,共49页,2023年,2月20日,星期三课堂作业P742.3课后作业(P75-P76)2.42.52.62.7第27页,共49页,2023年,2月20日,星期三2.3影子价格阐述对偶变量的经济意义,即对偶变量的经济解释引例:美佳公司……①……②……③……①……②如果已知LP的X*=(7/2,3/2,15/2,0,0)’Z*=8.5求解Y*,W*?由对偶问题的基本性质知:W*=Z*=8.5→15Y1+24y2+5y3=8.5又因为Y*’XS*=0X*代入LP的约束条件中,知①为严格不等式,则xS1>0,则y1=0由互补松弛定理:因为YS*‘X*=0X1>0,X2>0则yS1*=0,yS2*=0,即LD的①,②为严格等式6y2+y3=25y1+2y2+y3=1→Y1=0Y2=1/4y3=1/2第28页,共49页,2023年,2月20日,星期三1.定理:根据对偶问题的基本性质对LP为生产问题而言:bi表示LP中第i种资源的拥有量;Cj表示第j种产品的利润或产值其中Yi*可用下面数学式求得:1)yi*可解释为第i种资源的边际价格,即在其他条件不变的情况下,只增加单位第i种资源所引起的目标函数最优值的变化,bi→bi+1,△bi=1,△Z*的值为yi*。2)yi*也可解释为出让单位第i种资源的收益;3)yi*的取值随cj,xj,Aij的变化而变化,因此企业不同,产业不同,资源拥有量不同,yi*的值不同,是具体企业,具体产品和具体资源拥有量的特定价格。第29页,共49页,2023年,2月20日,星期三例:美佳公司……①……②……③X*=(7/2,3/2,15/2,0,0)’Z*=8.5由1)可知:y1*为①变为5x2≤16时Z*的增量,y1*=△Z*=0Y2*为②变为6x1+2x2≤25时Z*的增量所以当A的资源增加时,Z*无变化,Y1*=0LP中①约束为严格的不等式,表明A没有被充分利用。第30页,共49页,2023年,2月20日,星期三2.影子价格的应用(对偶问题的应用)1)yi*实际上是一种机会成本,当A的单位市场价格无论多低时,还应卖出A资源,直到15/2;当B的单位市场价格<1/4时,应该买进。2)对企业资源薄弱环节的分析由互补松弛定理:当Yi*=0表明bi没有被充分利用;当Yi*>0表明该资源已充分利用,因此该资源的增加或减少均会引起Z*的变动,Yi*越大,变动越大。由美佳可得:Y1=0表明A没有充分利用,y2=1/4,y3=1/2表明y3的变动对美佳公司利益的影响要大。
3)新产品是否投产以及合理定价的问题例:美佳考虑生产电器Ⅲ,要耗A3,B2,调试1个单位,市场价格2元,问是否值得生产。又如果美佳决定生产该种产品,则要定价多少该公司才不会亏本。第31页,共49页,2023年,2月20日,星期三4)合理调配资源因为影子价格是资源在特点环境下的价值,随环境的变化而变化,同一资源在有些使用中价值低,有些使用中价值高。例:美佳公司有两个子公司(1)A→0B→1/4C→1/2(2)A→2B→0C→1因此:(1)(2)A→AB←BC→C第32页,共49页,2023年,2月20日,星期三课后作业P762.8第33页,共49页,2023年,2月20日,星期三2.4对偶单纯形法一、基本思路从LP的一个基解出发,转换到另一个基解;在转换过程中,保持对应的LD的解Y的可行性(相当于LP的δj≤0),逐步消除该基解的不可行性,直到基解变成可行解,就获得了最优解。注:该方法不是求解LD的单纯形法,而是利用对偶关系求解LP的另一种方法。第34页,共49页,2023年,2月20日,星期三二、计算步骤:1.假定已给一对偶可行基单位阵B(对应LD问题的解可行),相应的基解XB=b。2.若b的各个分量均非负,则这个解就是最优解,停止迭代。3.如果XB有分量xl<0,且xl所在行的所有系数alj≥0,则LP无可行解,停止迭代。如果XB有分量xl<0,且该分量所在行的系数alj有负分量,则该解不是LP的最优解,继续。4.如果min{bi/bi<0}=bl,则xl为换出变量θ=min{δj/alj|alj<0}=δk/alk,则xk为换入变量5.以alk为主元,进行系数行变换,得一新的对偶可行基解(也称正则解),转第2步。第35页,共49页,2023年,2月20日,星期三比较单纯形法和对偶单纯形法单纯形法:先从基解、可行解出发,通过若干次迭代使满足δj≤0对偶单纯形法:先从基解,对偶可行解(等价于δj≤0)出发,再通过若干次迭代使之可行。对偶单纯形法的优缺点:优点:初始基解可为负,减少人工变量数量,使计算简单;灵敏度分析时使用方便。缺点:不能保证所有的Lp问题的初始单纯形表中的δj≤0。第36页,共49页,2023年,2月20日,星期三例:cj-2-3-400CBXBbx1x2x3x4x50X4-3-1-2-1100x5-4-21-301σj-2-3-400θ14/3[]0x4-2x112-1/23/20-1/2-10-5/21/21-1/2σj0-2-10-1θ4/52-3x2-2x1[]12/50-1/5-2/51/511/5107/5-1/5-2/5σj00-9/5-8/5-1/5所以:X*=(x1,x2)T=(11/5,2/5)TZ*=28/5第37页,共49页,2023年,2月20日,星期三课后作业2.9(1)第38页,共49页,2023年,2月20日,星期三2.5灵敏度分析Cj变化时bi变化时增加一个变量xj时增加一个约束条件时技术系数Pj发生变化时第39页,共49页,2023年,2月20日,星期三LP变化导致的变化可分为:X*不变,Z*改变X*中基变量不变,取值改变,Z*改变。X*中基变量改变,Z*改变XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-1第40页,共49页,2023年,2月20日,星期三一、分析cj变化当CNj发生变化时,对应的δNj变化δNj≤0X*,Z*不变δNj>0用单纯形法进行基变换XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-1当CBi发生变化时,所有δNj变化δNj≤0X*不变,Z*变化δNj>0用单纯形法进行基变换第41页,共49页,2023年,2月20日,星期三例5:美佳公司1.当C1由2变为1.5时,当C2由1变为2时,最优解有什么变化?2.当C1不变,C2在什么范围内变换时,最优解不变?Cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2解:1Cj1.52000CBXBbx1x2x3x4x50x46004/51-61.5x1210-1/5012x23011/500σj00-1/100-3/21.51.51/8-9/4[]22解:2Cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2c2c2δ4δ5δ4=(c2-2)/4≤0δ5=(2-3c2)/2≤02/3≤c2≤2第42页,共49页,2023年,2月20日,星期三二、分析bi变化该变化只会引起右侧常数的变化:B-1b≥0则基变量不变,X*的取值变化,Z*变化B-1b<0用对偶单纯形法进行基变换XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-1第43页,共49页,2023年,2月20日,星期三例6:美佳公司1.当其他能力不变,B设备由24变为32时,最优解有什么变化?2.当A,B不变,调试工序能力在什么范围内变换时,基变量不变?Cj21000CBXBbx1x2x3x4x50x335/2
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 空气动力学仿真技术:多物理场耦合:热流耦合分析方法
- 如何开展经济合同审计
- 8000Nm3h制氢及50万吨年加氢精制装置改造可行性实施报告
- 酒水物流运输服务计划方案
- 无人售货机运营项目商业计划书
- 全国职业院校技能大赛高职组(工业互联网集成应用赛项)备赛试题库(含答案)
- 2024年浙江省汽车维修工职业技能竞赛理论考试题库-下(判断题)
- 《舞蹈鉴赏》期末考试复习题库(含答案)
- 保健科血糖监测、生命体征监测、静脉输液考核试题及答案
- 办公室健康与安全试题及答案
- 数控铣床实训教案-自动编程
- 牛津大学英语介绍课件
- 大学生安全教育高职PPT完整全套教学课件
- 计量经济学期末考试重点
- 七年级劳动技能课全册教案
- 胎膜早破的诊断与处理指南
- 大型干船坞施工组织设计
- 全国公证岗位培训统一考试模拟试题
- 品质周报表模板
- 抗菌药物临床应用指导原则(2023年版)
- vc约起来史上最全180个知名投资人联系方式
评论
0/150
提交评论