运筹学课程03-线性规划对偶理论及其应用

1,线性规划对偶理论及其应用,窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象,2,对偶问题的提出,线性规划的对偶理论,对偶问题的经济解释-影子价格,对偶单纯形法,灵敏度分析,本章主要内容,3,一、问题的提出,示例1：资源的合理利用问题已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源又使总利润最大？,4,相应的线性规划模型：,一、问题的提出,5,下面从另一个角度来讨论这个问题：,假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（合理的）？,分析：1、每种资源收回的费用不能低于自己生产时的可获利润；2、定价又不能太高，要使对方能够接受。,一、问题的提出,6,一、问题的提出,7,一般而言，W越大越好，但因需双方满意，故,为最好。,该问题的数学模型为：,一、问题的提出,8,模型对比,一、问题的提出,9,一、问题的提出,示例2：合理配料问题某饲养场用n种饲料B1,B2,Bn配置成含有m种营养成分A1,A2,Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？,10,其数学模型为：,一、问题的提出,11,假设工厂想把这m种营养成分分别制成一种营养丸销售，问如何定价（以保证总收入为最多）？,12,二、线性规划的对偶模型,（一）、对偶问题的形式,1、对称型对偶问题：已知P，写出D。,13,二、线性规划的对偶模型,14,例一、写出线性规划问题的对偶问题,解：首先将原式变形,15,对偶模型不强调等式右端项b0,二、线性规划的对偶模型,16,2、非对称型对偶问题,二、线性规划的对偶模型,17,例二、原问题,18,3、混合型对偶问题,19,20,对偶问题,例三、,21,综上所述，其变换形式归纳如下：,22,例四、线性规划问题,23,24,25,三、对偶问题的基本性质,为了便于讨论，下面不妨总是假设,1、对称性定理：对偶问题的对偶是原问题。,26,2、弱对偶原理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有,推论1原问题的任何可行解目标函数值是其对偶问题目标函数值的下限对偶问题的任何可行解目标函数值是其原问题目标函数值的上限,27,推论2如果原问题(max)有可行解且目标函数值无界，则其对偶问题(min)无可行解，反之也成立反之：如果对偶问题(min)有可行解且目标函数值无界，则原问题(max)无可行解注：逆不成立因为当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解推论3如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解注：存在原问题和对偶问题同时无可行解的情况,28,例,29,例：已知,试用对偶理论证明原问题无界。,解：=（0.0.0）是P的一个可行解，而D的第一个约束条件不能成立（因为y1,y20)。因此，对偶问题不可行，由推论可知，原问题无界。,30,例：已知,显然，这两个问题都无可行解。,31,例已知,（P）,试估计它们目标函数的界，并验证弱对偶性原理。,32,解：,（D）,由观察可知：，分别是（P）和（D）的可行解。Z=10，W=40，故有，弱对偶定理成立。由推论可知，W的最小值不能小于10，Z的最大值不能超过40。,33,3、最优性判别定理若X*和Y*分别是P和D的可行解且CX*=Y*b，则X*，Y*分别是问题P和D的最优解。,证明：由上面推论，可得CX*Y*bCX，Y*bCX*Yb结论显然。,4、强对偶性（对偶定理）如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。,34,单纯形法计算的矩阵描述（回顾）,线性规划问题,化为标准型,35,单纯形法计算的矩阵描述（回顾）,XS为松弛变量,XS=(xn+1,xn+2,xn+m),I为mm矩阵,36,初始单纯形表,初始基变量,单纯形法计算的矩阵描述（回顾）,37,当前检验数,当前基解,设若干步迭代后，基变量为,在初始单纯形表中的系数矩阵为B，而A中去掉B的若干列组成矩阵N，则迭代后的单纯形表为：,单纯形法计算的矩阵描述（回顾）,38,单纯形法计算的矩阵描述（回顾）,检验数,因此,39,40,综述，一对对偶问题的关系，只能有下面三种情况之一出现：都有最优解，分别设为X*和Y*，则必有CX*=Y*b；一个问题无界，则另一个问题无可行解；两个都无可行解。,41,5、互补松弛性：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即,42,其余结论类似可证。,以上性质同样适用于非对称形式,43,例：已知原问题的最优解为X*=（0.0.4），Z=12试求对偶问题的最优解。,44,将X*=（0.0.4）代入原问题中，有下式：,所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为Y*=（0.0.3），W=12。,45,6、变量对应关系：设原始问题化为标准型为,则原始问题单纯形表中的检验数行，对应其对偶问题的一个基本解。对应关系如下：,46,若是已求得的原始问题的一个基本可行解的基变量取值，则与其对应的非基变量检验数为：,令并将其带入上式即得,47,对偶问题,原问题,48,49,50,两个问题作一比较:1.两者的最优值相同2.变量的解在两个单纯形表中互相包含原问题最优解（决策变量）对偶问题最优解（决策变量）,51,实际上，只要从最优单纯形表上找出最优基的逆矩阵，由前面已经得到的关系式即可求得最优对偶解。即：,用单纯形方法求解一个LP问题时，迭代的每一步，在得到原始问题的一个基本可行解的同时，其检验数行对应对偶问题的一个基本解。由此不难想到：从原始问题的最优单纯形表的检验数行也可以得到最优对偶解。,52,设：B是问题P的最优基，由前式可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+y*ibi+y*mbm当bi变为bi+1时（其余右端项不变，也不影响B）,四、对偶问题的经济解释影子价格,53,目标函数最优值变为：Z*=y*1b1+y*2b2+y*i（bi+1）+y*mbmZ*=Z*Z*=y*i,也可以写成：即y*i表示Z*对bi的变化率。,对偶变量y*i意义：其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化（边际利润）。也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。,54,定义：在一对P和D中，若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。,55,对偶变量的经济意义：代表在资源最优利用条件下对单位第种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadowprice)。,资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。,56,影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺,若第i种资源的单位市场价格为mi，当yimi时，企业愿意购进这种资源，单位纯利为yimi，则有利可图；如果yimi，则企业有偿转让这种资源，可获单位纯利miyi，否则，企业无利可图，甚至亏损。,如果最优生产计划下某种资源有剩余，该资源的影子价格一定等于0，影子价格大于0的资源没有剩余。,57,例,58,多了32/7,59,多了6/7,60,五、线性规划的对偶单纯形方法,由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。,61,对偶单纯形方法的思路：,max型原问题：,单纯形法：找基B，满足B-1b0，但C-CBB-1A不全0，（即检验数）。,迭代,保持B-1b0，使C-CBB-1A0，即CBB-1AC,62,对偶单纯形法：找基B，满足C-CBB-1A0，但B-1b不全0,保持C-CBB-1A0，使B-1b0,对偶单纯形法不是专门求解对偶问题的方法，而是求解线性规划的另一种方法。是根据对偶原理和单纯形法的原理而设计出来的，因而称为对偶单纯形法。,63,有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。,对偶单纯形方法应用前提：,对偶单纯形方法特别适合于求解如下的LP问题：,64,迭代步骤,1、确定换出变量找非可行解中最小者，即minbi|bi0，设第i*行的最小，则i*行称为主行，该行对应的基变量为出变量xi