运筹学课件2-对偶理论

Copyright2013Czhang.Allrightsreserved.,2020/5/25,张冲南京邮电大学经济管理学院Email：zcbling,对偶理论,Copyright2013Czhang.Allrightsreserved.,2020/5/25,Chapter2对偶理论(DualityTheory),线性规划的对偶模型对偶性质对偶单纯形表（经管）灵敏度分析（经管）对偶问题的经济解释影子价格,本章主要内容：,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？且看下面详解,对偶基本理论,对偶问题？.,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划问题的数学模型,例生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价50元，椅子售价30元，生产1个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120，油漆工工时为50。该厂如何生产才能使每月销售收入最大？,王老板的家具生产模型：x1、x2是桌子和椅子的生产量。Z是家具销售总收入（总利润）。maxZ=50 x1+30 x2s.t.4x1+3x21202x1+x250 x1，x20,Copyright2013Czhang.Allrightsreserved.,2020/5/25,唉!我想租您的木工和油漆工一用。咋样？价格嘛好说，肯定不会让您兄弟吃亏讪。,引例俩家具制造商间的对话：,王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。,Hi：王老板，听说近来家具生意好惨了，也帮帮兄弟我哦!,家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。,价格嘛好商量，好商量。只是.,王老板,李老板,案例,价格,Copyright2013Czhang.Allrightsreserved.,2020/5/25,王老板的家具生产模型：x1、x2是桌子和椅子的生产量。Z是家具销售总收入（总利润）。maxZ=50 x1+30 x2s.t.4x1+3x21202x1+x250 x1，x20原始线性规划问题，记为（P）,王老板的资源出租模型：y1、y2单位木工、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2503y1+y230y1，y20对偶线性规划问题，记为（D）,案例模型,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶基本理论,王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。,按时下最流行的一个词，叫什么来着,双赢,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,例2.1设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：,产品数据表,问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？,1.对偶问题的现实来源,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,解：设甲、乙型产品各生产x1及x2件，则数学模型为：,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。,反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。,表2：原问题与对偶问题对比表,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,2.原问题与对偶问题的对应关系,原问题,对偶问题,（对偶问题）,（原问题）,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,Copyright2013Czhang.Allrightsreserved.,2020/5/25,由maxmin时对偶问题的约束与原问题变量一致，变量与约束相反；,非常重要的法则,线性规划的对偶模型,由minmax时对偶问题的约束与原问题变量相反，变量与约束一致；,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,验证例2.1的原问题和对偶问题,原问题,对偶问题,（对偶问题）,（原问题）,Copyright2013Czhang.Allrightsreserved.,2020/5/25,minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315,maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40,=,unr,=,x10,x20,x3:unr,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。原始问题约束条件的性质影响对偶问题变量的性质。,线性规划的对偶模型,例2.2,Copyright2013Czhang.Allrightsreserved.,2020/5/25,线性规划的对偶模型,例2.3写出下列线性规划问题的对偶问题.,解：原问题的对偶问题为,Copyright2013Czhang.Allrightsreserved.,2020/5/25,练习1,写出下列线性规划问题的对偶问题.,解：原问题的对偶问题为,Copyright2013Czhang.Allrightsreserved.,2020/5/25,写出下列线性规划问题的对偶问题.,练习2,Copyright2013Czhang.Allrightsreserved.,2020/5/25,练习3,写出下列线性规划问题的对偶问题.,解：,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,性质1对称性定理：对偶问题的对偶是原问题,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,性质2弱对偶原理(弱对偶性)：设和分别是问题(P)和(D)的可行解，则必有,Copyright2013Czhang.Allrightsreserved.,2020/5/25,补：弱对偶原理(弱对偶性)的证明,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,性质3无界性:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。,注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,例：,无可行解,必有无界解,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,性质4最优性定理：如果是原问题的可行解，是其对偶问题的可行解，并且:,则是原问题的最优解，是其对偶问题的最优解。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,性质5强对偶性：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。,性质6互补松弛性：设X0和Y0分别是P问题和D问题的可行解，则它们分别是最优解的充要条件是：,其中：Xs、Ys为松弛变量,Copyright2013Czhang.Allrightsreserved.,2020/5/25,互补松弛性,maxz=CTXs.t.AX+XS=bX,XS0,minw=bTYs.t.ATY-YS=CY,YS0,maxz=CXs.t.AXbX0,minw=bTYs.t.ATYCY0,XYS=0,YXS=0,互补松弛关系,X,Xs,Y,Ys,Copyright2013Czhang.Allrightsreserved.,2020/5/25,maxz=CXs.t.AX+XS=bX,XS0,minw=bTYs.t.ATY+YS=CY,YS0,XTYS=0YTXS=0,m,n,=,Y,YS,AT,I,C,n,=,A,XS,I,b,n,m,m,X,原问题和对偶问题变量、松弛变量的维数,Copyright2013Czhang.Allrightsreserved.,2020/5/25,y1yiymym+1ym+jyn+m,x1xjxnxn+1xn+Ixn+m,对偶问题的变量对偶问题的松弛变量,原始问题的变量原始问题的松弛变量,XjYm+j=0,YiXn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0.,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,例2.4已知线性规划,的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,写出原问题的对偶问题，即,标准化,标准化,解：写出原问题的标准型，即,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，X和Y满足：,即：,即：,可知，y30，y40，,因原问题的最优解为X=(6,2,0)T，代入上两式，得,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶性质,将y30，y40，带入对偶问题的方程中：,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y=(1,1)，最优值w=26。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,习题1：已知下面的LP1和LP2为一组对偶规划，且已知LP1的最优解为X=（1.5，1）T。试运用互补松弛定理求出对偶问题的最优解Y。,生产计划问题（LP1）,资源定价问题（LP2）,由互补松弛性可得：,Copyright2013Czhang.Allrightsreserved.,2020/5/25,习题2：已知线性规划问题minw=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x54s.t.2x1x2+3x3+x4+x53xj0（j=1,2,3,4,5）对偶问题的最优解为y1*=4/5，y2*=3/5，z=5，求原问题的最优解。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,解：写出对偶问题maxz=4y1+3y2s.t.y1+2y22y1y232y1+3y25y1+y223y1+y23y1，y20,y1*=4/5，y2*=3/5y1+2y2=2y1y232y1+3y25y1+y223y1+y2=3,根据互补松弛性：XYS=0，XSY=0可知x2*=x3*=x4*=0y1，y20，x6=0,x7=0.3x1*+x5*=42x1*+x5*=3,x1*=1x5*=1,x2*=x3*=x4*=0,Copyright2013Czhang.Allrightsreserved.,2020/5/25,用单纯形法求解线性规划问题时，迭代的每一步在得到原问题的一个基可行解的同时，其检验数行中的系数是其对偶问题的一个基解；在单纯形法中，原问题的松弛变量对应对偶问题的变量，对偶问题的松弛变量对应原问题的变量；这些互相对应的变量若在一个问题的解中是基变量，则在另一问题中是非基变量；将这两个解代入各自的目标函数中有z=w(1)原问题非最优解检验数为对偶问题的一个基解。(2)原问题最优解检验数为对偶问题的最优解。,变量对应关系,Copyright2013Czhang.Allrightsreserved.,2020/5/25,原问题最终单纯形表,对偶问题最终单纯形表,最大化问题检验数的相反数给出了对偶问题的解,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶单纯形法的基本思想:对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,3.对偶单纯形法,Copyright2013Czhang.Allrightsreserved.,2020/5/25,应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,对偶单纯形法是应用对偶原理求解原问题线性规划的一种方法,采用的技术是在原问题的单纯形表格上进行对偶处理。,！注意:对偶单纯形法不是求解对偶问题的单纯形法。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶单纯形法的基本思路,单纯形法的基本思路：原问题基可行解最优解判断,对偶问题的可行解,对偶问题最优解判断,对偶单纯形法基本思路,Copyright2013Czhang.Allrightsreserved.,2020/5/25,单纯形法的求解过程是：在保持原始可行(b列保持）的前提下，通过逐步迭代实现对偶可行（检验数行）。换个角度考虑线性规划的求解过程：能否保持对偶可行（检验数行保持）的前提下，通过逐步迭代实现原始可行(b列，从非可行解变成可行解）呢？答案是肯定的，这就是对偶单纯形法的基本思想。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,如何用？,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶单纯形法的计算步骤,线性规划问题,不妨设为对偶问题的初始可行基，则。,若，即表中原问题和对偶问题均为最优解，否则换基。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,换基方法：,确定换出基变量对应变量为换出基的变量,确定换入基变量为主元素，为换入基变量,Copyright2013Czhang.Allrightsreserved.,2020/5/25,初始可行基,例、用对偶单纯形法求解线性规划问题：,对偶问题的初始可行基,Copyright2013Czhang.Allrightsreserved.,2020/5/25,例、用对偶单纯形法求解线性规划问题：,换入,Copyright2013Czhang.Allrightsreserved.,2020/5/25,Copyright2013Czhang.Allrightsreserved.,2020/5/25,最优解,最优解为：y1=0,y2=1/4,y3=1/2,Copyright2013Czhang.Allrightsreserved.,2020/5/25,对偶单纯形法的优点：不需要人工变量；当变量多于约束时，用对偶单纯形法可减少迭代次数；在灵敏度分析中，有时需要用对偶单纯形法处理简化。对偶单纯形法缺点：在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,利用对偶单纯形法求解以下线性规划问题：,练习1,Copyright2013Czhang.Allrightsreserved.,2020/5/25,解：首先将不等式变为等式,进一步转换,Copyright2013Czhang.Allrightsreserved.,2020/5/25,cj,CB,XB,b,x1,x2,x3,x4,x5,-1,-3,0,0,0,-2-3-1,-1-2-2,100,010,001,-3-4-1,x3x4x5,000,-1,-3,0,0,0,cj-zj,1/3,3/2,x3x1x5,010,1/32/3-4/3,100,-2/3-1/3-1/3,001,cj-zj,-1/34/31/3,0,-7/3,0,-1/3,0,1/2,0-10,x4x1x5,3/21/2,010,-1/2-3/2,-3/2-1/2-1/2,100,001,0-10,cj-zj,0,-5/2,-1/2,0,0,-3/2,此时所有的B-1b均0，且所有的cj-zj均0，此时已得到最优解为：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2,练习,Copyright2013Czhang.Allrightsreserved.,2020/5/25,练习2,Copyright2013Czhang.Allrightsreserved.,2020/5/25,最优解Y*=（0,1/4,1/2）T,Z*=(略),Copyright2013Czhang.Allrightsreserved.,2020/5/25,练习3,用对偶单纯性表求解线性规划问题,Copyright2013Czhang.Allrightsreserved.,2020/5/25,Copyright2013Czhang.Allrightsreserved.,2020/5/25,灵敏度分析的意义线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。,4.灵敏度分析,Copyright2013Czhang.Allrightsreserved.,2020/5/25,灵敏度分析，是指对系统或事物因周围条件变化显示出来的敏感性程度的分析。资源向量的灵敏度分析Rangeoffeasibilityforright-hand-sidecoefficients(bi)价值向量的灵敏度分析Rangeofoptimalityforobjectivefunctioncoefficients(cj)技术系数的灵敏度分析Rangeofoptimalityformatrixcoefficients(aij),灵敏度分析简介,Copyright2013Czhang.Allrightsreserved.,2020/5/25,灵敏度分析简介,灵敏度分析所要解决的问题：1）当这些参数(bi,cj,aij)中的一个或几个发生变化时，问题的最优解会有什么变化；2）这些参数在一个多大的范围内变化时，问题的最优解不变。,灵敏度分析不需要用单纯形法从头再算。只需把发生变化的个别系数，经过一定计算后直接填入最终单纯形表中，并进行检查和分析。如最优解改变，可用单纯形法或对偶单纯形法继续迭代计算，直到找到新的最优解。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,初始单纯形表,迭代后的单纯形表,Copyright2013Czhang.Allrightsreserved.,2020/5/25,Copyright2013Czhang.Allrightsreserved.,2020/5/25,Copyright2013Czhang.Allrightsreserved.,2020/5/25,4.1右端项bi变化的灵敏度分析,bi变化到什么程度可以保持最优基不变？用xB=B-1b0。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,例4.1：求以下模型中第二个约束条件右端项b2的变化范围。,maxZ=70X1+120X29X1+4X23604X1+5X22003X1+10X2300X10X20,Copyright2013Czhang.Allrightsreserved.,2020/5/25,Copyright2013Czhang.Allrightsreserved.,2020/5/25,解：从最优单纯形表得出：XB=(20,24,84)T最优基为：,注意：应为初始数据。还可以从单纯形表中找出B-1.,Copyright2013Czhang.Allrightsreserved.,2020/5/25,设b2由200变为200b2，则b由由此得到迭代后的单纯形表：,Copyright2013Czhang.Allrightsreserved.,2020/5/25,上述解是最优解，必须是可行解：即：解得：50b226.9。可知右端项系数b2的变化范围是:（20050）（20026.9),Copyright2013Czhang.Allrightsreserved.,2020/5/25,在此范围内j0，B-1b0，最优解仍有效，即最优解的基变量不变，最优解为：最优值为：Z*=4280+13.6b2,Copyright2013Czhang.Allrightsreserved.,2020/5/25,4.2目标函数中价值系数cj的灵敏度分析,分cj是非基变量的系数还是基变量的系数两种情况来讨论：,若cj是基变量xj的系数，则引起的变化较大。,若cj是非基变量xj的系数，此时，当cj变化cj后，要保证最终表中这个检验数仍小于或等于零即可。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,参数cj的变化仅仅影响到检验数(cjzj)的变化，所以反映到最终单纯形表上，只可能出现两种情况：,检验数仍然全部0，则最优解不变；出现检验数0，需用单纯形法继续迭代求解。,1.5,2,1/8,-9/4,Copyright2013Czhang.Allrightsreserved.,2020/5/25,1+,-1/4+/4,-1/2-3/2,为使表中的解仍为最优解，应有,C2在什么范围变化的时候，最优解不变？,Copyright2013Czhang.Allrightsreserved.,2020/5/25,例：在模型例4.1中，求基变量x2的系数变化范围。解：本例的最优单纯形表如下：,Copyright2013Czhang.Allrightsreserved.,2020/5/25,基变量系数c2由120变为120c2后，可以得到迭代后的单纯形表。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,要保持最优解，必须使j0，即：13.6+0.12c20-5.2-0.16c20解得32.5c2113.3由此可知，c2的变化范围为：（12032.5)(120+113.3)，即87.5c2233.3。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,6.3技术系数aij的灵敏度分析,某非基变量技术系数的改变会影响该非基变量的检验数，如果检验数仍然可以满足，则最优解保持不变否则继续迭代某基变量技术系数的改变的灵敏度分析比较复杂，因为某基变量技术系数的改变对最终表解的可行性和检验数行的检验系数都可能产生影响,Copyright2013Czhang.Allrightsreserved.,2020/5/25,例：讨论线性规划,的系数列向量的情况。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,解：首先利用单纯形法得出初始单纯形表及最优单纯形表如下。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,由于.所以,27,-5,由此可知，当前解仍为最优解。,Copyright2013Czhang.Allrightsreserved.,2020/5/25,补充：增加一个约束条件,将原最优解x1=3/2,x2=1带入新的约束条件，29/46，不满足新