运筹学课件04对偶问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章 线性规划的对偶理论,4.1 对偶问题,4.2 对偶问题的基本性质,4.3 对偶问题的解,4.4 影子价格,4.5 对偶单纯形法,9/29/2024,1,4.1 对偶问题,(1) 对偶问题的提出,对偶,理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？,9/29/2024,2,引例,俩家具制造商间的对话：,唉!我想租您的木工和油漆工一用。咋样？价格嘛好说，肯定不会让您兄弟吃亏。,王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。,Hi：王老板，听说近来家具生意好惨了，也帮帮兄弟我哦!,家具生意还真赚钱，但是现在的 生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。,价格嘛好商量， 好商量。只是.,王 老 板,李 老 板,9/29/2024,3,王老板的家具生产模型：,x1 、 x2是桌、椅生产量。,Z是家具销售总收入总利润。,max Z = 50x1 + 30x2,s.t. 4x1+3x2 120木工,2x1+ x2 50 油漆工,x1，x2 0,原始线性规划问题，记为P,王老板的资源出租模型：,y1、 y2单位木、漆工出租价格。,W是资源出租租金总收入。,min W =120y1 + 50y2,s.t. 4y1+2y2 50,3y1+ y2 30,y1，y2 0,对偶线性规划问题，记为D,所得不得低于生产的获利,要使对方能够接受,两个原那么,9/29/2024,4,王老板按D的解 y1 、y2出租其拥有的木、漆工资源，既保证了自己不吃亏出租资源的租金收入并不低于自己生产时的销售收入，又使得出租价格对李老板有极大的吸引力李老板所付出的总租金W最少。,按时下最流行的一个词，叫什么来着,9/29/2024,5,Max,Z=,40x,1,+,50x,2,x,1,+ 2x,2,30,3x,1,+ 2x,2,60,2x,2,24,x,1，,x,2,0,s.t,目标函数,约束条件,设三种资源的使用单价分别为,y,1, y,2, y,3,y,1,y,2,y,3,生产单位产品A的资源消耗所得不少于单位产品A的获利,生产单位产品B的资源消耗所得不少于单位产品B的获利,y,1,+3 y,2, 40,2y,1,+ 2 y,2,+ 2y,3, 50,例1,9/29/2024,6,通过使用所有资源对外加工所获得的收益,W = 30y,1,+ 60 y,2,+ 24y,3,根据原那么2 ，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：,Min,W = 30y,1,+ 60 y,2,+ 24y,3,y,1,+ 3y,2, 40,2y,1,+ 2 y,2,+ 2y,3, 50,y,1, y,2, y,3,0,目标函数,约束条件,原线性规划问题称为,原问题,，,此问题为,对偶问题,，,y,1, y,2, y,3,为,对偶变量,，也称为,影子价格,9/29/2024,7,(2) 对偶问题的形式,定义 设原线性规划问题为 那么称以下线性规划问题,为其对偶问题，其中,y,i,(i=1,2,m,),称为,对偶变量,。,上述对偶问题称为,对称型对偶问题,。,原问题简记为(P)，对偶问题简记为(D),9/29/2024,8,原始,问题,Max Z=CX,s.t. A,X,b,X,0,b,A,C,Max,n,m,对偶问题,Min W=Yb,s.t.YA,T,C,Y 0,Min,C,T,A,T,b,T,n,m,9/29/2024,9,例2：求线性规划问题的对偶规划,解：由原问题的结构可知为对称型对偶问题,9/29/2024,10,例3：求线性规划问题的对偶规划,解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,9/29/2024,11,例4：求线性规划问题的对偶规划,解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,9/29/2024,12,上式已为对称型对偶问题，故可写出它的对偶规划,令,那么上式化为,9/29/2024,13,对偶关系对应表,原问题 对偶问题,目标函数类型 Max Min,目标函数系数 目标函数系数 右边项系数,与右边项的对应关系 右边项系数 目标函数系数,变量数与约束数 变量数n 约束数 n,的对应关系 约束数m 变量数m,原问题变量类型与,0,对偶问题约束类型 变量,0,约束,的对应关系 无限制 ,原问题约束类型与,0,对偶问题变量类型 约束,变量,0,的对应关系 无限制,9/29/2024,14,4.2 对偶问题的基本性质,对偶的定义,对偶的定义,9/29/2024,15,9/29/2024,16,定理4(主对偶定理),假设一对对偶问题(P)和(D)都有可行解，那么它们都有最优解，且目标函数的最优值必相等。,证明：,(1) 当X*和Y*为原问题和对偶问题的一个可行解,有,原问题目标函数值,对偶问题目标函数值,所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。,9/29/2024,17,(2) 当,X*,为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型,令,令,所以,Y*,是对偶问题的可行解，对偶问题的目标函数值为,X*,是原问题的最优解，原问题的目标函数值为,9/29/2024,18,推论：,假设一对对偶问题中的任意一个有最优解，那么另一个也有最优解，且目标函数最优值相等。,一对对偶问题的关系，有且仅有以下三种：,都有最优解，且目标函数最优值相等；,两个都无可行解；,一个问题无界，那么另一问题无可行解。,9/29/2024,19,证: (必要性,原问题 对偶问题,9/29/2024,20,Max Z=CX,s.t.AX+X,S,=b,X, X,S,0,Min W=Yb,s.t. A,T,Y-Y,S,=C,W, W,S,0,X,T,Y,S,=0,Y,T,X,S,=0,m,n,=,Y,Y,S,A,T,-I,C,n,=,A,X,S,I,b,n,m,m,X,原始问题和对偶问题变量、松弛变量的维数,9/29/2024,21,y,1,y,i,y,m,y,m+1,y,m+j,y,n+m,x,1,x,j,x,n,x,n+1,x,n+i,x,n+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,x,j,y,m+j,=0y,i,x,n+i,=0(i=1,2,m; j=1,2,n),在一对变量中，其中一个大于0，另一个一定等于0,9/29/2024,22,4.3 对偶问题的解,C,C,B,C,N,0,解,基系数,基变量,X,B,X,N,X,s,C,B,X,B,I,B,-1,N,B,-1,B,-1,b,0,C,N,-C,B,B,-1,N,-C,B,B,-1,C,B,B,-1,b,令,设原问题为,为原问题的一最优解,那么,为对偶问题,的一最优解,9/29/2024,23,例1,Max Z=40X,1,+ 50X,2,X,1,+2X,2, 30,3X,1,+2X,2, 60,2X,2, 24,X,1,X,2,0,y,1,y,2,y,3,Min W = 30y,1,+ 60y,2,+ 24y,3,y,1,+3y,2,+ 0y,3,40,2y,1,+2y,2,+ 2y,3,50,y,1,y,2,y,3,0,Max W = -30y,1,- 60y,2,- 24y,3,y,1,+3y,2,+ 0y,3, y,4,=,40,2y,1,+2y,2,+ 2y,3, y,5,=,50,y,1,y,2,y,3,y,4,y,5,0,9/29/2024,24,Max W = -30y,1,- 60y,2,- 24y,3,+0(y,4,+,y,5,)-M (y,6,+,y,7,),y,1,+3y,2,+ 0y,3, y,4,+,y,6,=,40,2y,1,+2y,2,+ 2y,3, y,5,+,y,7,=,50,y,1,y,2,y,3,y,4,y,5,0,c,j,-30,-60,-24,0,0,-M,-M,B,-1,b,c,B,y,B,y,1,y,2,y,3,y,4,y,5,y,6,y,7,-M,y,6,1,3,0,-1,0,1,0,40,40/3,-M,y,7,2,2,2,0,-1,0,1,50,50/2,j,3M-30,5M-60,2M-24,-M,-M,0,0,-90M,9/29/2024,25,c,j,-30,-60,-24,0,0,-M,-M,B,-1,b,c,B,y,B,y,1,y,2,y,3,y,4,y,5,y,6,y,7,-60,y,2,1/3,1,0,-1/3,0,1/3,0,40/3,-M,y,7,4/3,0,2,2/3,-1,-2/3,1,70/3,35/3,j,4M/3-10,0,2M-24,2M/3+20,-M,-5M/3+20,0,800-70M/3,-60,y,2,1/3,1,0,-1/3,0,1/3,0,40/3,40,-24,y,3,2/3,0,1,1/3,-1/2,-1/3,1/2,35/3,35/2,j,6,0,0,-12,-12,-M+12,-M+12,-1080,-60,y,2,0,1,-1/2,-1/2,1/4,1/2,-1/4,15/2,-30,y,1,1,0,3/2,1/2,-3/4,-1/2,3/4,35/2,j,0,0,-9,-15,-15/2,-M+30,-M-15/2,-975,9/29/2024,26,例1、,Max Z=40X,1,+ 50X,2,X,1,+2X,2, 30,3X,1,+2X,2, 60,2X,2, 24,X,1,X,2,0,X,1,+2X,2,+X,3,= 30,3X,1,+2X,2,+X,4,=60,2X,2,+X,5,= 24,X,1,X,5,0,c,j,40,50,0,0,0,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,40,x,1,1,0,1/2,-1/2,0,15,0,x,5,0,0,3/2,-1/2,1,9,50,x,2,0,1,-3/4,1/4,0,15/2,j,0,0,-35/2,-15/2,0,975,9/29/2024,27,9/29/2024,28,9/29/2024,29,9/29/2024,30,9/29/2024,31,例3,解：,9/29/2024,32,c,j,2,3,-5,-M,0,-M,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,-M,x,4,1,1,1,1,0,0,7,7,-M,x,6,2,-5,1,0,-1,1,10,5,j,3M+2,-4M+3,2M-5,0,M,0,-17M,-M,x,4,0,7/2,1/2,1,1/2,-1/2,2,4/7,2,x,1,1,-5/2,1/2,0,-1/2,1/2,5,j,0,7M/2+8,M/2-6,0,M/2+1,-3M/2-1,10-2M,3,x,2,0,1,1/7,2/7,1/7,-1/7,4/7,2,x,1,1,0,6/7,5/7,-1/7,1/7,45/7,j,0,0,-50/7,-M-16/7,-1/7,-M+1/7,102/7,9/29/2024,33,(P),9/29/2024,34,9/29/2024,35,单位产品消耗的资源(吨/件),4.4 影子价格,(1),原始问题是利润最大化的生产计划问题,总利润(元),产品产量(件),单位产品的利润(元/件),消耗的资源(吨),剩余的资源(,吨),资源限量(吨),9/29/2024,36,(2),对偶问题,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格Shadow Price,原始和对偶问题都取得最优解时，,最大利润,Max z,=,Min w,总利润(元),资源限量(吨),资源价格(元/吨),9/29/2024,37,(3),资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺,影子价格越小，说明这种资源相对不紧缺,如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于,0,9/29/2024,38,0,X,2,X,1,X=,(15,7.5),Z=975,X=,(15.5,7.25),X=,(14.5,8.25),9/29/2024,39,y,1,y,2,y,m,(4) 产品的机会成本,机会成本,表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,9/29/2024,40,机会成本,利润,差额成本,(5) 产品的差额成本Reduced Cost,差额成本=机会成本 - 利润,9/29/2024,41,(6) 互补松弛关系的经济解释,在利润最大化的生产计划中,1边际利润大于0的资源没有剩余,2有剩余的资源边际利润等于0,3安排生产的产品机会成本等于利润,4机会成本大于利润的产品不安排生产,9/29/2024,42,4.5 对偶单纯形法,定义：设A=(B N)，其中B是一个非奇异的m m阶方阵，对应地C=(CB CN)，那么YB=CB的解Y*=CBB-1称为对偶问题(D)的一个基本解；假设Y*还满足Y*NCN，那么称Y*为(D)的一个基可行解；假设有Y*NCN，那么称Y*为非退化的基可行解，否那么称为退化的基可行解。,(1),对偶单纯形法的基本原理,定义：如果原问题(P)的一个基本解X与对偶问题(D)的基可行解Y对应的检验数向量满足条件,那么称X为原问题(P)的一个正那么解。,原问题(P)的正那么解X与对偶问题(D)的基可行解Y一一对应,原问题(P)的基本解,X,与对偶问题(D)的基本解,Y,一一对应,原问题(P)的最优解,X*,与对偶问题(D)的最优解,Y*,一一对应,9/29/2024,43,原问题解空间,对偶问题解空间,可行解,可行解,基本解,基本解,正那么解,正那么解,基可行解,基可行解,最优解,9/29/2024,44,对偶单纯形法的基本思想,从原规划的一个基本解出发，此基本解不一定可行(正那么解)，但它对应着一个对偶基可行解检验数非正，所以也可以说是从一个对偶基可行解出发；然后检验原规划的正那么解是否可行，即是否有负的分量，如果有小于零的分量，那么进行迭代，求另一个正那么解，此正那么解对应着另一个对偶基可行解检验数非正。,如果得到的正那么解的分量皆非负那么该正那么解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性即检验数非正，使原规划的正那么解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,9/29/2024,45,(2),对偶单纯形法的迭代步骤,建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；,假设b0,那么得到最优解,停止;否那么,假设有bk0那么选k行的基变量为出基变量,转3,假设所有akj0( j = 1,2,n )，那么原问题无可行解,停止;否那么,假设有akj0 那么选,=minj / akjakj0=r/akr,那么xr为进基变量,转4；,以akr为主元,作矩阵行变换使其变为1,该列其他元变为0,转2。,9/29/2024,46,例,9/29/2024,47,c,j,-120,-50,0,0,B,-1,b,c,B,y,B,y,1,y,2,y,3,y,4,0,y,3,-4,-2,1,0,-50,0,y,4,-3,-1,0,1,-30,j,-120,-50,0,0,0,-120/-4,-50/-2,-50,y,2,2,1,-1/2,0,25,0,y,4,-1,0,-1/2,1,-5,j,-20,0,-25,0,-1250,20,50,-50,y,2,0,1,-3/2,2,15,-120,y,1,1,0,1/2,-1,5,j,0,0,-15,-20,-1350,9/29/2024,48,例,9/29/2024,49,c,j,2,3,-5,-M,0,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,-M,x,4,1,1,1,1,0,7,7,0,x,5,-2,5,-1,0,1,-10,j,M+2,M+3,M-5,0,0,-7M,3,x,2,1,1,1,1,0,7,0,x,5,-7,0,-6,-5,1,-45,j,-1,0,-7,-M-3,0,21,1/7,7/6,(,M+3,)/5,3,x,2,0,1,1/7,2/7,1/7,4/7,2,x,1,1,0,6/7,5/7,-1/7,45/7,j,0,0,-50/7,-(M+16)/7,-1/7,102/7,9/29/2024,50,例,9/29/2024,51,c,j,3,-1,-1,0,0,-M,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,1,-2,1,1,0,0,11,11,0,x,5,4,-1,-2,0,1,0,-3,-M,x,6,-2,0,1,0,0,1,1,1,j,-6M+3,-1,M-1,0,0,0,-M,c,j,3,-1,-1,0,0,-M,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,3,-2,0,1,0,-1,10,0,x,5,0,-1,0,0,1,2,-1,-1,x,3,-2,0,1,0,0,1,1,j,1,-1,0,0,0,-M+1,-1,9/29/2024,52,c,j,3,-1,-1,0,0,-M,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,3,x,1,1,0,0,1/3,-2/3,-5/3,4,-1,x,2,0,1,0,0,-1,-2,1,-1,x,3,0,0,1,2/3,-4/3,-7/3,9,j,0,0,0,-1/3,-1/3,-M+2/3,2,c,j,3,-1,-1,0,0,-M,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,3,0,0,1,-2,-5,12,-1,x,2,0,1,0,0,-1,-2,1,-1,x,3,-2,0,1,0,0,1,1,j,1,0,0,0,-1,-M-1,-2,9/29/2024,53,是,是,是,是,否,否,否,否,所有,所有,得到,最优解,计算,计算,典式对应原规划的基本解是可行的,典式对应原规划的基本解的检验数,所有,所有,计算,计算,以为中心元素进行迭代,以为中心元素进行迭代,停,没有最优解,没有最优解,单纯形法,对偶单纯形法,9/29/2024,54,第四章作业,1选2、2、4、6、8、9选2,9/29/2024,55,补充例题,9/29/2024,56,9/29/2024,57,9/29/2024,58,C,2,-1,3,-M,-M,C,B,X,B,B,X,1,X,2,X,3,X,4,X,5,2,X,1,3,1,1/2,0,1/2,0,3,X,3,1/2,0,1/4,1,-3/4,1/2,-15/2,0,-11/4,0,-M+5/4,-M-3/2,9/29/2024,59,9/29/2024,60,9/29/2024,61,c,j,3,2,0,0,0,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,0,x,3,-1,2,1,0,0,4,0,x,4,3,2,0,1,0,12,4,0,x,5,1,-1,0,0,1,3,3,j,3,2,0,0,0,0,0,x,3,0,1,1,0,1,7,7,0,x,4,0,5,0,1,-3,3,3/5,3,x,1,1,-1,0,0,1,3,j,0,5,0,0,-3,9,0,x,3,0,0,1,-1/5,8/5,32/5,2,x,2,0,1,0,1/5,-3/5,3/5,3,x,1,1,0,0,1/5,2/5,18/5,j,0,0,0,-1,0,12,9/29/2024,62,9/29/2024,63,9/29/2024,64,c,j,2,-1,1,0,0,0,B,-1,b,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,3,1,1,1,0,0,60,20,0,x,5,1,-2,2,0,1,0,10,10,0,x,6,1,1,-1,0,0,1,20,20,j,2,-1,1,0,0,0,0,0,x,4,0,7,-5,1,-3,0,30,30/7,2,x,1,1,-2,2,0,1,0,10,0,x,6,0,3,-3,0,-1,1,10,10/3,j,0,3,-3,0,-2,0,20,0,x,4,0,0,2,1,-2/3,-7/3,20/3,2,x,1,1,0,0,0,1/3,2/3,50/3,-1,x,2,0,1,-1,0,-1/3,1/3,10/3,j,0,0,0,0,-1,-1,30,9/29/2024,65,9/29/2024,66,