运筹学教程-胡运权版

第二章对偶线性规划对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的互补松弛关系对偶单纯形法对偶的经济解释灵敏度分析2020/5/181DUAL线性规划对偶问题的提出一、对偶理论的提出现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润为最大？A1A2可供量甲3224已4540利润4.552020/5/182解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：2020/5/183maxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则问题变成对于甲乙两种原材料企业以多少最低价愿意出让？解：设甲资源的出让价格为y1,乙资源的出让价格为y2minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5y2≥5y1,y2≥032453425二、对偶问题的一般形式一般认为变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“≤”号；当目标函数求极小值时均取“≥“号。则称这些线性规划问题具有对称性。2020/5/184maxz=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原始问题maxz=CXs.t.AX≤bX≥02020/5/185对偶问题minw=Y’bs.t.A’Y≥C’Y≥0≥maxbACCATb≤minmnmn举例：2020/5/186maxZ=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第一种资源第二种资源第三种资源第一种产品第二种产品x1x22020/5/187原始问题为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个约束原始问题的变量全部为非负原始问题变量的个数(3)等于对偶问题约束条件的个数(3)原始问题约束条件的个数(2)等于对偶问题变量的个数(2)2020/5/188对偶问题的对偶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≥02020/5/189maxZ=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三、非对称形式的原—对偶问题2020/5/1810minz=2x1+3x2-5x3+x4s.t.x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0x2+x3+x4≥6x2+x3+x4≤6-x1=x1’,x1≥0;x4’-x4”=x4,x4’≥0,x4”≥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写出对偶问题2020/5/1811maxw=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”,则y2≤0,y3无约束此时对偶问题变为maxw=5y1+4y2+6y3s.t.y1+2y2≥2y1+y3≤3-3y1+2y2+y3≤-5y1-y2+y3=1y1≥0,y2≤0,y3无约束minz=2x1+3x2-5x3+x4s.t.x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0比较原问题和对偶问题2020/5/1812minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxy=6w1+12w2+8w3+15w4s.t.3w1-w2+2w3+w42-w1+2w2+w3+3w442w1-3w2+2w3-w4-1w10,w2,w30,w40≤≥=≥Free≤≥≥=≤≥x1≥0x2≤0x3:Free原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（1）2020/5/1813写对偶问题的练习（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≥0miny=12w1+8w2+15w3s.t.w1-2w2+3w3≥23w1+w2-4w3=-1-2w1+5w3≤3w1-3w2-w3≥-2w1≥0,w2≤0,w3:Free对偶问题2020/5/1814maxZ=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≤02020/5/1815原始和对偶问题可行解目标函数值比较minz=2x1+3x2s.t.x1+3x2≥32x1+x2≥4x1,x2≥0maxw=3y1+4y2s.t.y1+2y2≤23y1+y2≤3y1,y2≥001234321A(3,0)B(1.8,0.4)C(0,4)D(2,2)可行解z最优解A6B4.8是C12D10321012A(1,0)B(1.9,0.4)C(0,1)O(0,0)可行解w最优解O0A3B4.8是C4对偶问题的基本性质一、单纯形法计算的矩阵描述2020/5/1816MaxZ=CXAX≤bX≥0其中X＝(x1,x2……xn)TMaxZ=CX+0XsAX+IXs=bX,Xs≥0其中Xs＝(xn+1,xn+2……xn+m)TI为m×m的单位矩阵非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0……基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-12020/5/1817•对应初始单纯形表中的单位矩阵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’。当B为最优基时，XB为最优解时，则有：2020/5/1818CN-CBB-1N≤0-CBB-1≤0∵CB-CBI=0代入得：CN－CBB-1N+CB-CBI≤0C－CBB-1(B+N)≤0整理得：C－CBB-1A≤0-CBB-1≤0令CBB-1为单纯形乘子，Y‘＝CBB-1则：C－Y’A≤0-Y’≤0Y’A≥C’Y’≥0W＝Y’b=CBB-1b=Z所以当原问题为最优解时，对偶问题为可行解且具有相同的目标函数值。2020/5/1819maxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5x2≥5y1,y2≥0y1y2x1x2maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0y1y2x1x2cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55002020/5/1820解原问题：cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55000x387/501-2/55x284/5101/5cj-zj1/200-12020/5/1821cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55000x387/501-2/540/75x284/5101/510cj-zj1/200-12020/5/1822cj4.5500θCBXBbx1x2x3x40x3243210120x44045018cj-zj4.55000x387/501-2/540/75x284/5101/510cj-zj1/200-14.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/72020/5/1823Z=4.5×40/7＋5×24/7=300/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/72020/5/1824解对偶问题：w=24×5/14＋40×6/7=300/7cj4.5500θCBXBbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000θCBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/72020/5/1825(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x3二、