《运筹学04-对偶问题.ppt》由会员分享，可在线阅读，更多相关《运筹学04-对偶问题.ppt（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 线性规划的对偶理论线性规划的对偶理论4.1 对偶问题4.2 对偶问题的基本性质4.3 对偶问题的解4.4 影子价格4.5 对偶单纯形法1/28/202314.1 对偶问题(1)(1)对偶问题的提出对偶问题的提出n 对偶对偶理论是线性规划中最重要的理论之一，是深入了理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，统进行经济分析和敏感性分析的重要工具
2、。那么，对偶问对偶问题是怎样提出的，为什么会产生这样一种问题呢？题是怎样提出的，为什么会产生这样一种问题呢？1/28/20232引例引例俩家具制造商间的对话：俩家具制造商间的对话：唉唉!我想租您的木工和我想租您的木工和油漆工一用。咋样？价油漆工一用。咋样？价格嘛格嘛好说，肯定不好说，肯定不会让您兄弟吃亏。会让您兄弟吃亏。王老板做家王老板做家具赚了大钱，具赚了大钱，可惜我老李可惜我老李有高科技产有高科技产品，却苦于品，却苦于没有足够的没有足够的木工和油漆木工和油漆工咋办？只工咋办？只有租咯。有租咯。Hi：王老板，听王老板，听说近来家具生意说近来家具生意好惨了，也帮帮好惨了，也帮帮兄弟我哦兄弟我哦
3、!家具生意还真赚钱，家具生意还真赚钱，但是现在的手机生但是现在的手机生意这么好，不如干意这么好，不如干脆把我的木工和油脆把我的木工和油漆工租给他，又能漆工租给他，又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量，好好商量。只是商量。只是.王王 老老 板板李李 老老 板板1/28/20233王老板的王老板的家具生产模型家具生产模型：x1、x2是桌、椅生产量。是桌、椅生产量。Z是家具销售总收入（总利润）。是家具销售总收入（总利润）。max Z=50 x1+30 x2s.t.4x1+3x2 120（木工）木工）2x1+x2 50（油漆工）油漆工）x1，x2 0原始线性规划问题，记为
4、（原始线性规划问题，记为（P）王老板的王老板的资源出租模型资源出租模型：y1、y2单位木、漆工出租价格。单位木、漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W=120y1+50y2s.t.4y1+2y2 50 3y1+y2 30 y1，y2 0对偶线性规划问题，记为（对偶线性规划问题，记为（D）1.所得不得低于生产的获利所得不得低于生产的获利2.要使对方能够接受要使对方能够接受两个原则两个原则1/28/20234 王老板按（王老板按（D）的解的解 y1、y2出租其拥有的木、漆工资源，出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生既保证了自
5、己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金力（李老板所付出的总租金W最少）。最少）。按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着1/28/20235Max Z=40 x1+50 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件设设三种资源的使用单价分别为三种资源的使用单价分别为 y1,y2,y3y1 y2 y3生产单位产
6、品生产单位产品A A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A A的获利的获利生产单位产品生产单位产品B B的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品B B的获利的获利y1+3 y2 40 2y1+2 y2+2y3 50 50例例1 11/28/20236通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W=30y1+60 y2+24y3根据原则根据原则2，对方能够接受的价格显然是越低越好，因此，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：此问题可归结为以下数学模型：Min W=30y1+60 y2+24y3 y1+3y
7、2 402y1+2 y2+2y3 50y1,y2,y3 0s.t目标函数目标函数约束条件约束条件原线性规划问题称为原线性规划问题称为原问题原问题，此问题为此问题为对偶问题对偶问题，y1,y2,y3为为对偶变量对偶变量，也称为，也称为影子价格影子价格1/28/20237(2)(2)对偶问题的形式对偶问题的形式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题为其对偶问题，其中为其对偶问题，其中yi(i=1,2,m)称为称为对偶变量对偶变量。上述对偶问题称为上述对偶问题称为对称型对偶问题对称型对偶问题。原问题简记为原问题简记为(P)，对偶问题简记为对偶问题简记
8、为(D)1/28/20238原始原始问题问题Max Z=CXs.t.AXbX 0bACMaxnm对偶问题对偶问题Min W=Ybs.t.YATCY 0MinCTATbTnm1/28/20239例例2：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知为对称型对偶问题解：由原问题的结构可知为对称型对偶问题1/28/202310例例3：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知不是对称型对偶问题，解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。可先化为对称型，再求其对偶规划。1/28/202311例例4：求线性规划问：求
9、线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知不是对称型对偶问题，解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。可先化为对称型，再求其对偶规划。1/28/202312上式已为对称型对偶问题，故可写出它的对偶规划上式已为对称型对偶问题，故可写出它的对偶规划令令则上式化为则上式化为1/28/202313对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 Max Min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数
10、与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制1/28/2023144.2 对偶问题的基本性质对偶的定义对偶的定义对偶的定义对偶的定义1/28/2023151/28/202316定理定理4 4(主对偶定理主对偶定理)若一对对偶问题若一对对偶问题(P)(P)和和(D)(D)都有
11、可行解，则它们都都有可行解，则它们都有最优解，且目标函数的最优值必相等。有最优解，且目标函数的最优值必相等。证明：证明：(1)当当X*和和Y*为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。最优解；对偶问题有下界，也存在有限最优解。1/28/202317(2)当当X*为原问题的一个最优解，为原问题的一个最优解，B为为相应的最优基相应的最优基,通过引入松弛变量通过引入松弛变量Xs,将问题将
12、问题(P)转化为标准型转化为标准型令令令令所以所以Y*是对偶问题的可行解，是对偶问题的可行解，对偶问题的目标函数值为对偶问题的目标函数值为X*是是原问题的最优解，原原问题的最优解，原问题的目标函数值为问题的目标函数值为1/28/202318推论：推论：若一对对偶问题中的任意一个有最优解，则另一个若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：1.1.都有最优解，且目标函数最优值相等；都有最优解，且目标函数最优值相等；2.2.两个都无可行解；两个都无可行解；
13、3.3.一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。1/28/202319证证:(:(必要性）必要性）原问题原问题 对偶问题对偶问题1/28/202320Max Z=CXs.t.AX+XS=bX,XS 0Min W=Ybs.t.ATY-YS=CW,WS 0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数1/28/202321 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题
14、的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0 0，另一个一定等于，另一个一定等于0 01/28/2023224.3 对偶问题的解CCBCN0解解基系数基系数基变量基变量XBXNXsCBXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1b令令设原问题为设原问题为为原问为原问题的一题的一最优解最优解则则为对偶问题为对偶问题的一最优解的一最优解1/28/202323例例1 Max Z=40X1+50X2 X1+2X2 303X1
15、+2X2 60 2X2 24 X1,X2 0 0s.ty1y2y3Min W=30y1+60y2+24y3 y1+3y2+0y3 402y1+2y2+2y3 50 y1,y2,y3 0 0s.tMax W=-30y1-60y2-24y3 y1+3y2+0y3 y4=402y1+2y2+2y3 y5=50 y1,y2,y3,y4,y5 0 0s.t1/28/202324Max W=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7)y1+3y2+0y3 y4+y6=402y1+2y2+2y3 y5+y7=50 y1,y2,y3,y4,y5 0 0s.tcj-30-60-2400-M
16、-MB-1bcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2j3M-305M-602M-24-M-M00-90M1/28/202325cj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3j4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2j600-12-12-M+12-
17、M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2j00-9-15-15/2-M+30-M-15/2-9751/28/202326例例1、Max Z=40X1+50X2 X1+2X2 303X1+2X2 60 2X2 24 X1,X2 0 0s.t X1+2X2+X3=303X1+2X2+X4=60 2X2+X5=24 X1 X5 0 0s.tcj4050000 B-1bcBxBx1x2x3x4x540 x1101/2-1/20150 x5003/2-1/21950 x201-3/41/4015/2j00-35/
18、2-15/209751/28/2023271/28/2023281/28/2023291/28/2023301/28/202331例例3 3解：解：1/28/202332cj23-5-M0-M B-1bcBxBx1x2x3x4x5x6-Mx411110077-Mx62-510-11105j3M+2-4M+32M-50M0-17M-Mx407/21/211/2-1/224/72x11-5/21/20-1/21/25j07M/2+8M/2-60M/2+1-3M/2-110-2M3x2011/72/71/7-1/74/72x1106/75/7-1/71/745/7j00-50/7-M-16/7-1/
19、7-M+1/7102/71/28/202333(P)1/28/2023341/28/202335单位产品消耗的资源单位产品消耗的资源(吨吨/件件)4.4 影子价格(1)(1)原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题总利润总利润(元元)产品产量产品产量(件件)单位产品的利润单位产品的利润(元元/件件)消耗的资源消耗的资源(吨吨)剩余的资源剩余的资源(吨吨)资源限量资源限量(吨吨)1/28/202336(2)对偶问题对偶问题对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格影子价格（Sh
20、adow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 Max z=Min w总利润总利润(元元)资源限量资源限量(吨吨)资源价格资源价格(元元/吨吨)1/28/202337(3)(3)资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0 01/28/2023380X2X1X=(15,7.5)Z=97
21、5X=(15.5,7.25)Z=982.5X=(14.5,8.25)Z=992.51/28/202339y1y2ym(4)产品的机会成本产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源1/28/202340机会成本机会成本利润利润差额成本差额成本(5)产品的差额成本（产品的差额成本（Reduced Cost）差额成本差额成本=机会成本机会成本-利润利润1/28/202341(6)互补松弛关系的经济解释互补松弛关系的经济解释在利
22、润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产1/28/2023424.5 对偶单纯形法n定义：设定义：设A=(B N)，其中其中B是一个非奇异的是一个非奇异的m m阶方阵，对应地阶方阵，对应地C=(CB CN)，则，则YB=CB的解的解Y*=CBB-1称为对偶问题称为对偶问题(D)的一个基本解；若的一个基本解；若Y*还还满足满足Y*NCN
23、，则称则称Y*为为(D)的一个基可行解；若有的一个基可行解；若有Y*NCN，则称则称Y*为为非退化的基可行解，否则称为退化的基可行解。非退化的基可行解，否则称为退化的基可行解。(1)(1)对偶单纯形法的基本原理对偶单纯形法的基本原理 定义：如果原问题定义：如果原问题(P)的一个基本解的一个基本解X与对偶问题与对偶问题(D)的基可行解的基可行解Y对对应的检验数向量满足条件应的检验数向量满足条件 则称则称X为原问题为原问题(P)的的一个正则解。一个正则解。原问题原问题(P)的正则解的正则解X与与对偶问题对偶问题(D)的基可行解的基可行解Y一一对应一一对应原问题原问题(P)的基本解的基本解X与与对偶
24、问题对偶问题(D)的基本解的基本解Y一一对应一一对应原问题原问题(P)的最优解的最优解X*与对偶问题与对偶问题(D)的最优解的最优解Y*一一对应一一对应1/28/202343原问题解空间原问题解空间对偶问题解空间对偶问题解空间可行解可行解可行解可行解基本解基本解基本解基本解正则解正则解正则解正则解基可行解基可行解基可行解基可行解最优解最优解1/28/202344对偶单纯形法的基本思想对偶单纯形法的基本思想v从原规划的一个基本解出发，此基本解不一定可行从原规划的一个基本解出发，此基本解不一定可行(正则正则解解)，但它对应着一个对偶基可行解（检验数非正），所，但它对应着一个对偶基可行解（检验数非正
25、），所以也可以说是从一个对偶基可行解出发；然后检验原规以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。应着另一个对偶基可行解（检验数非正）。v如果得到的正则解的分量皆非负则该正则解为最优解。如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的
26、正则解由不可的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。解时，便得到原规划的最优解。1/28/202345(2)(2)对偶单纯形法的迭代步骤对偶单纯形法的迭代步骤1.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个基本解对应一个基本解,所有检验数所有检验数均非正均非正,转转2；2.若若b0,则得到最优解则得到最优解,停止停止;否则否则,若有若有bk0则选则选k行的行的基变量为出基变量基变量为出基变量,转转33.若所有若所有akj0(j=1,2,n)，则原问题无可行解
27、则原问题无可行解,停停止止;否则否则,若有若有akj0 则选则选 =min j/akjakj0=r/akr 那么那么xr为进基变量为进基变量,转转4；4.以以akr为主元为主元,作矩阵行变换使其变为作矩阵行变换使其变为1,该列其他元变该列其他元变为为0,转转2。1/28/202346例例1/28/202347cj-120-5000B-1bcByBy1y2y3y40y3-4-210-500y4-3-101-30j-120-50000-120/-4-50/-2-50y221-1/20250y4-10-1/21-5j-200-250-12502050-50y201-3/2215-120y1101/2
28、-15j00-15-20-13501/28/202348例例1/28/202349cj23-5-M0B-1bcBxBx1x2x3x4x5-Mx411110770 x5-25-101-10jM+2M+3M-500-7M3x21111070 x5-70-6-51-45j-10-7-M-30211/77/6(M+3)/53x2011/72/71/74/72x1106/75/7-1/745/7j00-50/7-(M+16)/7-1/7102/71/28/202350例例 1/28/202351cj3-1-100-MB-1bcBxBx1x2x3x4x5x60 x41-2110011110 x54-1-2
29、010-3-Mx6-20100111j-6M+3-1M-1000-Mcj3-1-100-MB-1bcBxBx1x2x3x4x5x60 x43-2010-1100 x50-10012-1-1x3-2010011j1-1000-M+1-11/28/202352cj3-1-100-MB-1bcBxBx1x2x3x4x5x63x11001/3-2/3-5/34-1x20100-1-21-1x30012/3-4/3-7/39j000-1/3-1/3-M+2/32cj3-1-100-MB-1bcBxBx1x2x3x4x5x60 x43001-2-512-1x20100-1-21-1x3-2010011j1
30、000-1-M-1-21/28/202353是是是是是是是是否否否否否否否否所有所有所有所有得到得到最优解最优解计算计算计算计算典式对应原规划的基典式对应原规划的基本解是可行的本解是可行的典式对应原规划的基本典式对应原规划的基本解的检验数解的检验数所有所有所有所有计算计算计算计算以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代停停没没有有最最优优解解没没有有最最优优解解单纯形法单纯形法对偶单纯形法对偶单纯形法1/28/202354n第四章作业第四章作业n1（选（选2）、）、2、4、6、8、9（选（选2）1/28/202355补充例题补充例题1/28/202356
31、1/28/2023571/28/202358C2-13-M-MCBXBBX1X2X3X4X52X1311/201/203X31/201/41-3/41/2-15/20-11/40-M+5/4-M-3/21/28/2023591/28/2023601/28/202361cj32000B-1bcBxBx1x2x3x4x50 x3-1210040 x4320101240 x51-100133j3200000 x301101770 x40501-333/53x11-10013j0500-390 x3001-1/58/532/52x20101/5-3/53/53x11001/52/518/5j000-10121/28/2023621/28/2023631/28/202364cj2-11000B-1bcBxBx1x2x3x4x5x60 x431110060200 x51-2201010100 x611-10012020j2-1100000 x407-51-303030/72x11-22010100 x603-30-111010/3j03-30-20200 x40021-2/3-7/320/32x110001/32/350/3-1x201-10-1/31/310/3j0000-1-1301/28/2023651/28/202366