运筹学-第二章 线性规划的对偶理论

2、线性规划问题的对偶问题例2．1胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？2.1对偶问题数学模型maxg=50x1+30x2s.t.4x1+3x2120(2.1)2x1+x250x1,x20假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？假设y1,y2分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：mins=120y1+50y2目标函数中的系数120，50分别表示可供出租的木工和油漆工工时数。该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：4y1+2y2503y1+y230y1,y20得到另外一个数学模型：mins=120y1+50y2s.t.4y1+2y250(2.2)3y1+y230y1,y20模型(2.1)和模型(2.2)既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。如果模型(2.1)称为原问题，则模型(2.2)称为对偶问题。任何线性规划问题都有对偶问题，而且都有相应的意义。例2.2：常山机器厂生产Ⅰ、Ⅱ两种产品，按工艺资料获得如下资料：ⅠⅡ设备能力设备A2h2h12h设备B4h0h16h设备C0h5h15h单位利润（元）23问该企业因安排生产两种产品各多少件，使总的利润收入为最大？数学模型maxZ=2x1+3x2s.t.2x1+2x2124x1165x215x1,x20现某机械厂为扩大生产租借常山机器厂拥有的设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的设备？设常山厂将设备A、B、C每h的出租价格为y1,y2,y3;•它的对偶问题为minw=12y1+16y2+15y32y1+4y2≥22y1+5y3≥3y1,y2,y3≥0把例2.2用矩阵表示：对偶问题原问题:Maxz=(2,3)21xx0xx151612xx5004222121321yyy151612min0yyy32yyy502042321321线性规划的对偶关系：（I）Maxz=Cxs.t.Axb（2.3）x0(II)Minw=b’ys.t.A’yC’（2.4）y0（2.3)(2.4)称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。例2-3：写出下列线性规划问题的对偶问题minw=12x1+8x2+16x3+12x4s.t.2x1+x2+4x322x1+2x2+4x43x1，x2，x3，x40解：该问题的对偶问题：maxz=2y1+3y2s.t.2y1+2y212y1+2y284y1164y212y1，y20例2-4：写出下列线性规划问题的对偶问题maxS=10x1+x2+2x3s.t.X1+x2+2x310y14x1+2x2-x320y2x1，x2，x30解：该问题的对偶问题：ming=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y20例2-5：写出下列线性规划问题的对偶问题minS=x1+2x2+3x3s.t.2x1+3x2+5x323x1+x2+7x33x1，x2，x30解：用（-1）乘以第二个约束方程两边minS=x1+2x2+3x3s.t.2x1+3x2+5x32y1-3x1-x2-7x3-3y2x1，x2，x30该问题的对偶问题：maxz=2y1-3y2s.t.2y1-3y213y1-y225y1-7y23y1，y20例2-6：写出下列线性规划问题的对偶问题minS=2x1+3x2-5x3s.t.x1+x2-x352x1+x3=4x1，x2，x30解：将原问题的约束方程写成不等式约束形式：minS=2x1+3x2-5x3x1+x2-x35y12x1+x34y2’-2x1-x3-4y2”x1，x2，x30引入变量y1,y2’，y2”写出对偶问题maxg=5y1+4y2’-4y2”s.t.y1+2y2’-2y2”2y13-y1+y2’-y2”-5y1，y2’，y2”0令y2=y2’-y2”得到maxg=5y1+4y2s.t.y1+2y22y13-y1+y2-5y10，y2无非负约束此类问题称为非对称型对偶问题。前面的问题称为对称型对偶问题。综上所述其变换形式如下：原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项•例2-7：写出下列线性规划的对偶问题minz=7x1+4x2-3x3s.t.-4x1+2x2-6x3≤24-3x1-6x2-4x3≥155x2+3x3=30x1≤0,x2取值无约束,x3≥0Maxw=24y1+15y2+30y3s.t.-4y1-3y2≥72y1-6y2+5y3=4-6y1-4y2+3y3≤-3y1≤0,y2≥0,y3无约束例2-8：写出下列线性规划问题的对偶问题minw=3x1-2x2+x3s.t.x1+2x2=1y12x2-x3-2y22x1+x33y3x1-2x2+3x34y4x1，x20，x3无非负限制解:综合运用对偶原则得到maxg=y1-2y2+3y3+4y4s.t.y1+2y3+y432y1+2y2-2y4-2-y2+y3+3y4=1y2≤0,y3,y40，y1无非负约束定理2.1:(弱对偶定理)对于互为对偶问题(I)(II)中的任意的可行解x(0),y(0),都有cx(0)≤y(0)b2.2对偶问题的基本定理定理2.2(最优准则)若原问题的某一个可行解与对偶问题的某一可行解的目标函数值相等,则它们分别是原问题与对偶问题的最优解.定理2.3(对偶定理)若原问题有最优解,则对偶问题也有最优解,且最优值相等.•性质2.4如果原问题(对偶问题）具有无界解，则其对偶问题（原问题）无可行解。但原问题(对偶问题)无可行解时，其对偶问题（原问题）或无可行解或具有无界解。•定理2.5（互补松弛性）在线性规划问题的最优解中，如果该约束条件取严格等式，则对应某一约束条件的对偶变量值为非零；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。maxZ=2x1+3x2s.t.2x1+2x2≤124x1≤165x2≤15x1,x20它的最优解为（3，3）而对于第二个约束条件，为严格的不等式，所以y2=0y1y2y3•性质2.6对偶问题的最优解为原问题最优表中,相应的松驰变量检验数的相反数。（线性规划的原问题与对偶问题中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对于原问题的变量。）•例：maxZ=2x1+3x2•s.t.2x1+2x2+x312•4x1+x416•5x2+x515•x1,x20CB基bx1x2x3x4x52x130x443x2310½0-1/500-214/501001/5Cj-zj00-10-1/5原问题变量原问题松弛变量对偶问题变量对偶问题的剩余变量Y2Y5Y4Y3Y42.3影子价格在线性规划原问题和对偶问题中：m1iiin1jjjybxczbi代表第i种资源的拥有量，而yi代表对一个单位第i种资源的估价•影子价格不是市场价格，随企业的生产任务和产品结构而发生变化。•影子价格是一种边际价格。Z=bTy*=b1y1*+b2y2*++bmym*可知Z/bi=yi*2X+2y=12123456654321X=4X=3maxZ=2x1+3x2s.t.2x1+2x2124x1165x215x1,x20①点（3，3）是最优解，z*=15当A的资源变为13小时，z*=16,说明A的边际价格是1，即影子价格是1。•在对偶问题的互补松弛性质中有0yˆbxˆaiijn1jij，时表示某种资源bi没有充分利用，该种资源的影子价格为零。•如果ijn1jijibxˆa0yˆ时，表示该种资源已耗费完毕。是生产该种产品所消耗的各项资源的影子价格总和，即产品的隐含成本。•从影子价格的含义上再来考察单纯形法的计算：im1iijjjjyaczcim1iijya当检验数大于零，说明生产此种产品有利，可在生产中安排。2.4对偶单纯形法例：求解如下线性规划问题：minw=12y1+16y2+15y3s.t.2y1+4y2≥22y1+5y3≥3y1,y2,y3≥0划为标准形：maxw’=-12y1-16y2-15y3-2y1-4y2+y4=-2-2y1-5y3+y5=-3yi≥0（i=1,…,5)Cj-12-16-1500CB基bY1y2y3y4y50y4-20y5-3-2-4010-20[-5]01Cj-Zj-12-16-1500如何转换?•当bi≤0时，令min(bi)所对应的行中的Xr为换出基变量。•令0a|azcminrjrjjjj所对应的列变量为换入基变量•Y5为换出基变量515,2-12min故x3为换入基变量，-5为主元素Cj-12-16-1500CB基bY1y2y3y4y50y4-2-15y33/5[-2]-40102/5010-1/5Cj-Zj-6-1600-3•Y4为换出基变量416,2-6min故Y1为换入基变量，-2为主元素Cj-12-16-1500CB基bY1y2y3y4y5-12y11-15y31/5120-1/200-4/511/5-1/5Cj-Zj0-40-3-3故此问题的最优解为：Y1=1，Y2=0，Y3=1/5，W=15对偶单纯形法的基本思想对偶单纯形法的基本思想是：从原规划的一个基解出发，此基解不一定可行，但它对应着一个对偶可行解（检验数非正）；从对偶可行解出发，然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基解，此基解对应着另一个对偶可行解（检验数非正）。如果得到的基解的分量皆非负则该基解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基解由不可行逐步变为可行对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:①单纯形表的检验数行全部非正（对偶可行）；②变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。对偶单纯形法求解线性规划问题过程：1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b’≥0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转33.若所有akj’≥0(j=1,2,…,n)，则原问题无可行解,停止;否则,若有akj’0则选=min{j’/akj’┃akj’0}=r’/akr’那么xr为进基变量,转4；4.以akr’为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。•对偶单纯形法解的讨论ifbr0,而arj≥0,这时原问题解的情况如何？rnrn1m1m,rrbxaxax故不可能存在xj≥0（j