运筹学对偶问题精品文稿.ppt

运筹学对偶问题第1页，本讲稿共47页4.1 对偶问题(1)(1)对偶问题的提出对偶问题的提出例例1 1、生产组织与计划问题、生产组织与计划问题A,BA,B各生产多少各生产多少,可获最大利润可获最大利润?可用资源可用资源煤煤劳动力劳动力仓库仓库AB123202单位利润单位利润4050306024第2页，本讲稿共47页MaxZ=40 x1+50 x2x1+2x2 303x1+2x2 602x2 24x1，x2 0s.t目标函数目标函数约束条件约束条件如果因为某种原因，不愿意自己生产，而希望通过将现有如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的资源承接对外加工来获得收益，那么应如何确定各资源的使用价格使用价格？第3页，本讲稿共47页MaxZ=40 x1+50 x2x1+2x2 303x1+2x2 602x2 24x1，x2 0s.t目标函数目标函数约束条件约束条件两个原则两个原则1.所得不得低于生产所得不得低于生产的获利的获利2.要使对方能够接受要使对方能够接受设三种资源的使用单价分别为设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品生产单位产品A A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A A的获利的获利生产单位产品生产单位产品B B的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品B B的获利的获利y1+3y2 402y1+2y2+2y3 50 50第4页，本讲稿共47页通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3根据原则根据原则2，对方能够接受的价格显然是越低越好，因此，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：此问题可归结为以下数学模型：MinW=30y1+60y2+24y3y1+3y2 402y1+2y2+2y3 50y1,y2,y3 0s.t目标函数目标函数约束条件约束条件原线性规划问题称为原线性规划问题称为原问题原问题，此问题为此问题为对偶问题对偶问题，y1,y2,y3称为称为影子价格影子价格第5页，本讲稿共47页(2)(2)对偶问题的形式对偶问题的形式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题为其对偶问题，其中为其对偶问题，其中yi(i=1,2,m)称为称为对偶变量对偶变量。上述对偶问题称为上述对偶问题称为对称型对偶问题对称型对偶问题。原问题简记为原问题简记为(P)，对偶问题简记为，对偶问题简记为(D)第6页，本讲稿共47页原始问题原始问题MaxZ=CXs.t.AXbX0bACMaxnm对偶问题对偶问题MinW=Ybs.t.YATCY0MinCTATbTnm第7页，本讲稿共47页例例2：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知为对称型对偶问题解：由原问题的结构可知为对称型对偶问题第8页，本讲稿共47页例例3：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知不是对称型对偶问题，解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。可先化为对称型，再求其对偶规划。第9页，本讲稿共47页例例4：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知不是对称型对偶问题，解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。可先化为对称型，再求其对偶规划。第10页，本讲稿共47页上式已为对称型对偶问题，故可写出它的对偶规划上式已为对称型对偶问题，故可写出它的对偶规划令令则上式化为则上式化为第11页，本讲稿共47页对偶关系对应表对偶关系对应表原问题原问题对偶问题对偶问题目标函数类型目标函数类型MaxMin目标函数系数目标函数系数目标函数系数目标函数系数右边项系数右边项系数与右边项的对应关系与右边项的对应关系右边项系数右边项系数目标函数系数目标函数系数变量数与约束数变量数与约束数变量数变量数n约束数约束数n的对应关系的对应关系约束数约束数m变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型变量变量 0约束约束 的对应关系的对应关系无限制无限制原问题约束类型与原问题约束类型与 0对偶问题变量类型对偶问题变量类型约束约束 变量变量 0的对应关系的对应关系无限制无限制第12页，本讲稿共47页4.2 对偶问题的基本性质定理定理1 1 对偶问题的对偶就是原问题对偶问题的对偶就是原问题MaxW=-Ybs.t.-YA-CY0MinZ=-CXs.t.-AX-bX0MaxZ=CXs.t.AXbX0MinW=Ybs.t.YACY0对偶的定义对偶的定义对偶的定义对偶的定义第13页，本讲稿共47页定理定理2 2(弱对偶定理弱对偶定理)分别为分别为(P),(D)的可行解，则有的可行解，则有C bX，yXy证明：由证明：由AX b,y 0有有 yAX by由由Ay C,X 0有有yA X CX所以所以CX yAX yb第14页，本讲稿共47页推论推论2、(P)有可行解有可行解,但无有限最优解，则但无有限最优解，则(D)无可行解。无可行解。定理定理3、yX,分别为分别为(P),(D)的可行解，且的可行解，且XyC=b,则它们是则它们是(P),(D)的最优解。的最优解。证明：对任证明：对任X，有，有CX by=CXX最优最优推论推论1、(P),(D)都有可行解，则必都有最优解。都有可行解，则必都有最优解。第15页，本讲稿共47页定理定理4 4(主对偶定理主对偶定理)若一对对偶问题若一对对偶问题(P)(P)和和(D)(D)都有可行解，则它们都有最优都有可行解，则它们都有最优解，且目标函数的最优值必相等。解，且目标函数的最优值必相等。证明：证明：(1)当当X*和和Y*为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。最优解；对偶问题有下界，也存在有限最优解。第16页，本讲稿共47页(2)当当X*为原问题的一个最优解，为原问题的一个最优解，B为相应的最优基为相应的最优基,通过引入松弛变量通过引入松弛变量Xs,将问题将问题(P)转化为标准型转化为标准型令令令令所以所以Y*是对偶问题的可行解，是对偶问题的可行解，对偶问题的目标函数值为对偶问题的目标函数值为X*是原问题的最优解，原是原问题的最优解，原问题的目标函数值为问题的目标函数值为第17页，本讲稿共47页推论：推论：若一对对偶问题中的任意一个有最优解，则另一个若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：1.1.都有最优解，且目标函数最优值相等；都有最优解，且目标函数最优值相等；2.2.两个都无可行解；两个都无可行解；3.3.一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。第18页，本讲稿共47页定理定理5若若X,Y分别为分别为(P),(D)的可行解，则的可行解，则X,Y为最优解的充要条件是为最优解的充要条件是同时同时成立成立证证:(:(必要性）必要性）原问题原问题 对偶问题对偶问题第19页，本讲稿共47页MaxZ=CXs.t.AX+XS=bX,XS0MinW=Ybs.t.ATY-YS=CW,WS0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数第20页，本讲稿共47页y1yiymym+1ym+jyn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0 0，另一个一定等于，另一个一定等于0 0第21页，本讲稿共47页4.3 对偶问题的解令令设原问题为设原问题为为原问为原问题的一题的一最优解最优解则则为对偶问题为对偶问题的一最优解的一最优解CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN-CBB-1N-CBB-1第22页，本讲稿共47页例例1MaxZ=40X1+50X2X1+2X2 303X1+2X2 602X2 24X1,X2 0 0s.ty1y2y3MinW=30y1+60y2+24y3y1+3y2+0y3 402y1+2y2+2y3 50y1,y2,y3 0 0s.tMaxW=-30y1-60y2-24y3y1+3y2+0y3y4=402y1+2y2+2y3y5=50y1,y2,y3,y4,y5 0 0s.t第23页，本讲稿共47页MaxW=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7)y1+3y2+0y3y4+y6=402y1+2y2+2y3y5+y7=50y1,y2,y3,y4,y5 0 0s.tC-30-60-2400-M-MCByBby1y2y3y4y5y6y7-My640130-101040/3-My7502220-10125Z-90M-30+3M-60+5M-24+2MMM00第24页，本讲稿共47页C-30-60-2400-M-MCByBby1y2y3y4y5y6y7-60y240/31/310-1/301/30-My770/34/3022/3-1-2/31Z-800-70M/3-10+4M/30-24+2M2M/3-M0-60y240/31/310-1/301/3040-24y335/32/3011/3-1/2-1/31/235/2Z-1080600-12-12-60y215/201-1/2-1/21/41/6-1/4-30y135/2103/21/2-3/4-1/23/4Z-97500-9-15-15/2第25页，本讲稿共47页例例1、MaxZ=40X1+50X2X1+2X2 303X1+2X2 602X2 24X1,X2 0 0s.tX1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1X5 0 0s.tCBXBBX1X2X3X4X540X115101/2-1/200X59003/2-1/2150X215/297501-3/41/40Z00-35/2-15/20第26页，本讲稿共47页第27页，本讲稿共47页y1yiymym+1ym+jyn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0 0，另一个一定等于，另一个一定等于0 0第28页，本讲稿共47页第29页，本讲稿共47页C23-5-M0-MCBXBbX1X2X3X4X5X6-MX471111007-MX6102-510-115Z-17M2+3M3-4M2M-50-M0-MX4207/21/211/2-1/24/72X151-5/21/20-1/21/2Z2M-1003M/2+8M/2-60M/2+1-3M/2-13X24/7011/72/71/7-1/72X145/7106/75/7-1/71/7Z102/700-50/7-M-16/7-1/7-M+1/7第30页，本讲稿共47页(P)第31页，本讲稿共47页第32页，本讲稿共47页4.4 影子价格(1)(1)原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题单位产品的利润（元单位产品的利润（元/件）件）产品产量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源（吨）剩余的资源（吨）消耗的资源（吨）消耗的资源（吨）第33页，本讲稿共47页(2)对偶问题对偶问题资源限量（吨）资源限量（吨）资源价格（元资源价格（元/吨）吨）总利润（元）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格（影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润原始和对偶问题都取得最优解时，最大利润MaxZ=MinW第34页，本讲稿共47页(3)(3)资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0 0第35页，本讲稿共47页y1y2ym(4)(4)产品的机会成本产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源第36页，本讲稿共47页机会成本机会成本利润利润差额成本差额成本(5)产品的差额成本（产品的差额成本（ReducedCost）差额成本差额成本=机会成本机会成本-利润利润第37页，本讲稿共47页(6)互补松弛关系的经济解释互补松弛关系的经济解释在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产第38页，本讲稿共47页4.5 对偶单纯形法n定义：设定义：设A=(B N)，其中，其中B是一个非奇异的是一个非奇异的m m阶方阵，对阶方阵，对应地应地C=(CB CN)，则，则YB=CB的解的解Y*=CBB-1称为对偶问题称为对偶问题(D)的一个基本解；若的一个基本解；若Y*还满足还满足Y*NCN，则称，则称Y*为为(D)的一个基的一个基可行解；若有可行解；若有Y*NCN，则称，则称Y*为非退化的基可行解，否则为非退化的基可行解，否则称为退化的基可行解。称为退化的基可行解。(1)(1)对偶单纯形法的基本原理对偶单纯形法的基本原理l定义：如果原问题定义：如果原问题(P)的一个基本解的一个基本解X与对偶问题与对偶问题(D)的的基可行解基可行解Y对应的检验数向量满足条件对应的检验数向量满足条件l则称则称X为原问题为原问题(P)的一个正则解。的一个正则解。原问题原问题(P)的正则解的正则解X与对偶问题与对偶问题(D)的基可行解的基可行解Y一一对应一一对应第39页，本讲稿共47页对偶单纯形法的基本思想对偶单纯形法的基本思想v从原规划的一个基本解出发，此基本解不一定可行从原规划的一个基本解出发，此基本解不一定可行(正则正则解解)，但它对应着一个对偶基可行解（检验数非正），所，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。应着另一个对偶基可行解（检验数非正）。v如果得到的正则解的分量皆非负则该正则解为最优解。如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。解时，便得到原规划的最优解。第40页，本讲稿共47页(2)(2)对偶单纯形法的迭代步骤对偶单纯形法的迭代步骤1.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个基本解对应一个基本解,所有检验数所有检验数均非正均非正,转转2；2.若若b0,则得到最优解则得到最优解,停止停止;否则否则,若有若有bk0则选则选k行的行的基变量为出基变量基变量为出基变量,转转33.若所有若所有akj0(j=1,2,n)，则原问题无可行解，则原问题无可行解,停停止止;否则否则,若有若有akj0则选则选=min j/akjakj0=r/akr那么那么xr为进基变量为进基变量,转转4；4.以以akr为转轴元为转轴元,作矩阵行变换使其变为作矩阵行变换使其变为1,该列其他元该列其他元变为变为0,转转2。第41页，本讲稿共47页例例解：将上式标准化解：将上式标准化第42页，本讲稿共47页C-2-3-400CBXBbX1X2X3X4X50X4-3-1-2-1100X5-4-21-301-f0-2-3-4000X4-10-5/21/21-1/2-2X121-1/23/20-1/2-f-40-4-10-1-3X22/501-1/5-2/51/5-2X111/5101/5-1/5-2/5-f-28/500-9/5-8/5-1/5第43页，本讲稿共47页第44页，本讲稿共47页C23-5-M0CBXBbX1X2X3X4X5-MX47111100X5-10-25-101Z-7M2+M3+M-5+M003X27111100X5-45-70-6-51Z21-10-8-M-303X24/7011/72/71/72X145/7106/75/7-1/7Z102/700-50/7-M-16/7-1/7第45页，本讲稿共47页是是是是是是是是否否否否否否否否所有所有所有所有得到得到最优解最优解计算计算计算计算典式对应原规划的典式对应原规划的基本解是可行的基本解是可行的典式对应原规划的基典式对应原规划的基本解的检验数本解的检验数所有所有所有所有计算计算计算计算以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代停停没没有有最最优优解解没没有有最最优优解解单纯形法单纯形法对偶单纯形法对偶单纯形法第46页，本讲稿共47页n第四章作业第四章作业n1（选（选2）、）、2、4、6、8、9（选（选2）第47页，本讲稿共47页