运筹学二章对偶线性规

第二章对偶理论与灵敏度分析2.1线性规划的对偶问题2.2对偶问题的基本性质2.3影子价格2.4对偶单纯形法2.5灵敏度分析DUAL4/14/20241可编辑ppt本章学习要求掌握对偶理论及其性质掌握影子价格的应用掌握对偶单纯形法熟悉灵敏度分析的概念和内容掌握右侧常数，价值系数，工艺系数的变换对原最优解的影响掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围4/14/20242可编辑ppt2.1线性规划的对偶问题问题的提出对称形式下对偶问题的一般形式非对称形式下的原问题与对偶问题的关系4/14/20243可编辑ppt一、对偶问题的提出每一个LP问题，都伴随着另一个LP，而且二者有密切关系，互为对偶，另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问题就可以了。例1：（美佳公司）美佳公司应如何生产安排，使已有资源利润最大化。某公司至少该出多大代价，使美佳公司愿意放弃自己的资源，产品资源ⅠⅡ资源约束A0515B6224调试工序115单位产品利润21产品资源AB调试工序单位资源利润Ⅰ0612Ⅱ5211资源量152454/14/20244可编辑ppt数学模型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.54/14/20245可编辑ppt二、对偶问题的一般形式一般认为变量均为非负约束的情况下，约束条件在目标函数取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≥04/14/20246可编辑ppt原问题maxz=CXs.t.AX≤b X≥0对偶问题minw=Y’bs.t.A’Y≥C’ Y≥0≥maxbCCATb≤minmnmnA4/14/20247可编辑ppt举例：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第一种资源第二种资源第三种资源第一种产品第二种产品x1x24/14/20248可编辑ppt原始问题为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个约束原始问题的变量全部为非负4/14/20249可编辑ppt对偶问题的对偶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≥04/14/202410可编辑ppt对偶问题的性质总结对偶的对偶就是原始问题maxz=CXs.t.AX≤bX≥0minw=Y’bs.t.ATY≥

C’ Y≥0对偶的定义maxu=CWs.t.AW≤C W≥04/14/202411可编辑pptmaxZ=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≥04/14/202412可编辑ppt三、非对称形式的原—对偶问题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无约束4/14/202413可编辑ppt结论LP(LD)MaxX≥0X≤0X无约束St≤st≥St=LD(LP)Minst≥St≤St=Y≥0Y≤0Y无约束4/14/202414可编辑pptminz=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）4/14/202415可编辑ppt写对偶问题的练习（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对偶问题4/14/202416可编辑pptmaxZ=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≤04/14/202417可编辑ppt课后作业P742.1(4)4/14/202418可编辑ppt2.2对偶问题的基本性质单纯形法的矩阵描述对偶问题的基本性质4/14/202419可编辑ppt一、单纯形法计算的矩阵描述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-1XS4/14/202420可编辑ppt某一决策变量xk系数列向量迭代前为Pk，迭代后为B-1Pk。当B为最优基时MaxZ=CBB-1b＋（CN-CBB-1N)XN-CBB-1XS令Y’=CBB-1由此可以看出，当X为最优解时，Y为对偶问题的可行解。且该可行解对应的目标函数值W=Y’b=CX*4/14/202421可编辑ppt非基变量基变量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’。4/14/202422可编辑ppt二、对偶问题的基本性质原始问题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≥CX04/14/202423可编辑ppt推论:(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目标函数无界。4/14/202424可编辑ppt2.最优性若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.强对偶性若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。4/14/202425可编辑ppt4.互补松弛定理如果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个约束为严格等式。4/14/202426可编辑ppt课堂作业P742.3课后作业(P75-P76)2.42.52.62.74/14/202427可编辑ppt2.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/24/14/202428可编辑ppt1.定理：根据对偶问题的基本性质对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*的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。4/14/202429可编辑ppt例：美佳公司……①……②……③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没有被充分利用。4/14/202430可编辑ppt2.影子价格的应用（对偶问题的应用）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元，问是否值得生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。4/14/202431可编辑ppt4）合理调配资源因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有些使用中价值低，有些使用中价值高。例：美佳公司有两个子公司（1）A→0B→1/4C→1/2(2)A→2B→0C→1因此：（1）（2）A→AB←BC→C4/14/202432可编辑ppt课后作业P762.84/14/202433可编辑ppt2.4对偶单纯形法一、基本思路从LP的一个基解出发，转换到另一个基解；在转换过程中，保持对应的LD的解Y的可行性（相当于LP的δj≤0），逐步消除该基解的不可行性，直到基解变成可行解，就获得了最优解。注：该方法不是求解LD的单纯形法，而是利用对偶关系求解LP的另一种方法。4/14/202434可编辑ppt二、计算步骤：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步。4/14/202435可编辑ppt比较单纯形法和对偶单纯形法单纯形法：先从基解、可行解出发，通过若干次迭代使满足δj≤0对偶单纯形法:先从基解，对偶可行解（等价于δj≤0）出发，再通过若干次迭代使之可行。对偶单纯形法的优缺点：优点:初始基解可为负，减少人工变量数量，使计算简单；灵敏度分析时使用方便。缺点：不能保证所有的Lp问题的初始单纯形表中的δj≤0。4/14/202436可编辑ppt例: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/54/14/202437可编辑ppt课后作业2.9（1）4/14/202438可编辑ppt2.5灵敏度分析Cj变化时bi变化时增加一个变量xj时增加一个约束条件时技术系数Pj发生变化时4/14/202439可编辑pptLP变化导致的变化可分为：X*不变，Z*改变X*中基变量不变，取值改变，Z*改变。X*中基变量改变，Z*改变XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-14/14/202440可编辑ppt一、分析cj变化当CNj发生变化时，对应的δNj变化δNj≤0X*,Z*不变δNj＞0用单纯形法进行基变换XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-1当CBi发生变化时，所有δNj变化δNj≤0X*不变,Z*变化δNj＞0用单纯形法进行基变换4/14/202441可编辑ppt例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≤24/14/202442可编辑ppt二、分析bi变化该变化只会引起右侧常数的变化：B-1b≥0则基变量不变，X*的取值变化，Z*变化B-1b＜0用对偶单纯形法进行基变换XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-14/14/202443可编辑ppt例6：美佳公司1.当其他能力不变，B设备由24变为32时，最优解有什么变化？2.当A,B不变，调试工序能力在什么范围内变换时，基变量不变？Cj21000CBXBbx1x2x3x4x5