对偶问题及对偶单纯形法完整.ppt

《对偶问题及对偶单纯形法完整.ppt》由会员分享，可在线阅读，更多相关《对偶问题及对偶单纯形法完整.ppt（61页珍藏版）》请在三一办公上搜索。

1、Duality Theory,线性规划的对偶问题,对偶问题的经济解释影子价格,对偶单纯形法,第四章 线性规划的对偶理论,灵敏度分析,对偶问题的基本性质,线性规划的对偶问题,Duality Theory,对偶问题的经济解释影子价格,对偶单纯形法,灵敏度分析,对偶问题的基本性质,第四章 线性规划的对偶理论,例如：平面中矩形的面积与周长的关系周长一定面积最大的矩形是正方形:面积一定周长最短的矩形是正方形,一、对偶问题的提出,对同一问题从不同角度考虑，有两种对立的描述。,例1、应如何安排生产计划，使一天的总利润最大？,某企业生产甲、乙两种产品，要用A、B、C三种不同的原料。每生产1吨甲产品，需耗用三种

2、原料分别为1，1，0单位；生产1吨乙产品，需耗用三种原料分别为1，2，1单位。每天原料供应的能力分别为6，8，3单位。又知道每生产1吨甲产品企业利润为300元，每生产1吨乙产品企业利润为400元。,例1、应如何安排生产计划，使一天的总利润最大？,max,x1 0,x2 0,s.t.,x1+x2 6,z=3x1+4x2,x1+2x2 8,x2 3,设 xj 表示第 j 种产品每天的产量,假设该企业决策者决定不生产甲、乙产品，而是将厂里的现有资源外售。决策者应怎样制定每种资源的收费标准才合理？,例1、应怎样制定收费标准才合理？,设 yj 表示第 j 种原料的收费单价,分析问题：1、出让每种资源的收

3、入不能低于自己生产时的可获利润；2、定价不能太高，要使对方能够接受。,把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨甲产品的利润：,乙产品同理：,把企业所有原料出让的总收入：,只能在满足所有产品的利润的条件下,其总收入尽可能少,才能成交.,一、对偶问题的提出,任何一个求极大的线性规划问题都有一个求极小的线性规划问题与之对应，反之亦然.把其中一个叫原问题，则另一个就叫做它的对偶问题，这一对互相联系的两个问题就称为一对对偶问题。,原问题（P）,对偶问题（D）,二、原问题与对偶问题的对应关系,yj 表示对第 j 种资源的估价,矩阵形式：,s.t.,s.t.,(一)对称型对偶问题,其中 y

4、i 0（i=1,2,m）称为对偶变量。,变量均具有非负约束，且约束条件：当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。,(二)非对称型对偶问题,分析：化为对称形式。,令,(二)非对称型对偶问题,对偶变量,min,对偶问题：,(二)非对称型对偶问题,令,3个=,约束条件,变 量,(二)非对称型对偶问题,目标函数 max,目标函数 min,目标函数的系数,约束条件右端常数,约束条件右端常数,目标函数的系数,3个=,3个00无符号限制,约束条件,变 量,3个00无符号限制,原问题（对偶问题）,对偶问题（原问题）,3个=,约束条件,变 量,(一)对称型对偶问题,目标函数 max,目标函数

5、 min,目标函数的系数,约束条件右端常数,约束条件右端常数,目标函数的系数,3个=,3个00无符号限制,约束条件,变 量,3个00无符号限制,2个,2个,二、原问题与对偶问题的对应关系,例2、写出下述线性规划问题的对偶问题,解：,设对偶变量为,min,则对偶问题为,例3、写出下述线性规划问题的对偶问题,解：,设对偶变量为,max,则对偶问题为,练习、写出下述线性规划问题的对偶问题,对偶问题的基本性质,Duality Theory,线性规划的对偶问题,对偶问题的经济解释影子价格,对偶单纯形法,灵敏度分析,第二章 线性规划的对偶理论,对偶问题的基本性质,对称性,弱对偶性,无界性,最优性,原问题与

6、对偶问题单纯形表间的性质,互补松弛性,强对偶性,对偶问题的基本性质,1、对称性,定理：对偶问题的对偶是原问题。,2、弱对偶性,定理：设 和 分别是原问题（P）和其对偶问题（D）的可行解，则恒有,2、弱对偶性,定理：设 和 分别是原问题（P）和其对偶问题（D）的可行解，则恒有,推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,3、无界性,定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。,原问题有可行解但目标函数值无界,对偶问题无可行解,对偶问题有可行解但目标函数值无界,原问题无可行解,推论：

7、原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,3、无界性,定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。,原问题有无界解,对偶问题无可行解,推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,可能是无可行解,推论1：在互为对偶的两个问题中，若一个问题无可行解，则另一个问题或具有无界解或无可行解。,3、无界性,定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。,推论1：在互为对偶的两个问题中

8、，若一个问题无可行解，则另一个问题或具有无界解或无可行解。,推论2：在互为对偶的两个问题中，若一个问题有可行解，另一个问题无可行解，则可行的问题无界。,无界解,无可行解,无可行解,无界解,例1、利用对偶理论证明问题无界（无最优解）,解：,设对偶变量为,min,则对偶问题为,由 知，,第一个约束,可知对偶问题无,条件不成立，,可行解。,易知(0,0,0)T 是原问题的一,个可行解，故原问题可行。,由无界性定理可知，原问题,有无界解，即无最优解。,练习、证明下列线性规划问题无最优解,max,原问题的一个可行解：,对偶问题不可行：找矛盾,4、最优性,设 和 分别是P和D的最优解：,因此,5、互补松弛

9、性,定理：设 和 分别是原问题和其对偶问题的最优解，,若对偶变量，则原问题相应的约束条件,若约束条件，则相应的对偶变量,5、互补松弛性,定理：设 和 分别是原问题和其对偶问题的最优解，,若对偶变量，则原问题相应的约束条件,若约束条件，则相应的对偶变量,5、互补松弛性,定理：设 和 分别是原问题和其对偶问题的最优解，,若对偶变量，则原问题相应的约束条件,若约束条件，则相应的对偶变量,若，则,若，则,若，则,若，则,例2、利用互补松弛定理求最优解,解：,设对偶变量为,min,则对偶问题为,设对偶问题的最优解为,因,由互补松弛性知,解方程组得,故对偶问题的最优解为,例3、利用互补松弛定理求最优解,对

10、偶变量为,min,则对偶问题为,设对偶问题的最优解为,将 代入原问题约束条件得,解：,由互补松弛性知,又,故对偶问题的最优解为,得,例4、利用互补松弛定理求最优解,对偶问题为,设原问题的最优解为,解：,将 代入原问题约束条件得：,(2)、(3)、(4)为严格不等式,由互补松弛性知,又因,由互补松弛性知,得,故原问题最优解为,6、强对偶性（对偶定理）,定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。,s.t.,用单纯形法求原问题的最优解：,s.t.,非基变量,基变量,Xs,X,I,A,0,C,基变量 基变量 基可 系数 行解,0 Xs b,XB XN,B N,CB

11、CN,XB,I,0,CB CN,B N,XB XN,单纯形法计算的矩阵描述,非基变量,基变量,Xs,I,0,基变量 基变量 基可 系数 行解,0 Xs b,基变量,非基变量,XB,CNCBB-1N,B-1N B-1,XN Xs,B-1b,CB,进行初等行变换,CBB-1,若CNCBB-1N 0,CBB-1 0,最优解X*=B-1b,B-1存在,6、强对偶性（对偶定理）,若CNCBB-1N 0,CBB-1 0,最优解X*=B-1b,令YT=CBB-1，则有,CNYT N 0，,Y 0,因CBYTB=0，故,CYT A 0，,即AT Y CT，,说明Y是D的可行解,此时目标函数值,w=bTY=YT

12、b=CBB-1b,原问题的最优值,z=CB-1b=CBB-1b,由最优性定理知，Y是D的最优解。,定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。,6、强对偶性（对偶定理）,推论：若一对对偶问题都有可行解，则它们都有最优解，且目标函数的最优值必相等。,定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。,互为对偶的两个问题，只会出现以下三种关系：都有最优解，且最优值相等 一个有无界解，另一个无可行解；两个都无可行解。,判断下列说法是否正确，为什么？,1、如果线性规划问题存在可行解，则其对偶问题也一定存在可行解。,2、如果线性规划问题的对偶

13、问题无可行解，则原问题也一定无可行解。,3、如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划一定具有有限最优解。,对偶问题的基本性质,7、原问题与对偶问题单纯形表间的性质？,XB,I,0,CB CN,B N,XB XN,非基变量,基变量,Xs,I,0,基变量 基变量 基可 系数 行解,0 Xs b,基变量,非基变量,XB,CNCBB-1N,B-1N B-1,XN Xs,B-1b,CB,YT=CBB-1,CBB-1,Duality Theory,线性规划的对偶问题,对偶问题的经济解释影子价格,对偶单纯形法,灵敏度分析,对偶问题的基本性质,第二章 线性规划的对偶理论,第一步：找到一个满

14、足最优检验的初始基本解；第二步：检验当前解是否可行。若可行，已得到最优，否则转入下一步。第三步：选择b最小一行的变量作为换出变量第四步：换入变量mincj-zj/aij(负数和零不参与比较)第五步：迭代运算，到第二步。,对偶单纯形法,对偶单纯形法,Max z=-6x1-3x2-2x3,例：,对偶单纯形法,找到一个满足最优检验的初始基本解,检验当前解不可行，选择b最小一行的变量作为换出变量；换入变量mincj-zj/aij,对偶单纯形法,检验当前解不可行，选择b最小一行的变量作为换出变量；换入变量mincj-zj/aij,对偶单纯形法,对偶问题的经济解释影子价格,Duality Theory,线

15、性规划的对偶问题,对偶单纯形法,灵敏度分析,对偶问题的基本性质,第二章 线性规划的对偶理论,bi 代表第i种资源的拥有量；yi*代表在资源最优利用条件下对第i种资源的单位估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。,一、影子价格的概念,设 xj 表示第 j 种产品每天的产量,设 yj 表示第 j 种原料的收费单价,由对偶定理知当P问题求得最优解X*时，D问题也得到最优解Y*，且有,影子价格,一、影子价格的概念,由 得,说明 的值相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数z的增量,边际价格,说明若某资源 未被充分利用，则该种资源的影子价格为0；

16、,若某资源的影子价格不为0，则说明已有资源在已消耗完毕。,二、在经营管理中的应用,y1*=2y2*=1y3*=0,Y*T=CBB-1,CBB-1,二、在经营管理中的应用,y1*=2y2*=1y3*=0,若原料A增加1单位，该厂按最优计划安排生产可多获利200元；若原料B增加1单位，可多获利100元;原料C本已剩余，再增加不会带来收益。,1、指示企业内部挖潜的方向,影子价格能说明增加哪种资源对增加经济效益最有利,二、在经营管理中的应用,y1*=2y2*=1y3*=0,2、在企业经营决策中的作用,当某种资源的影子价格高于市场价格时：当某种资源的影子价格低于市场价格时：,企业经营决策者可通过把本企业

17、资源的影子价格与当时的市场价格进行比较，决定资源的买卖，以获取较大利润。,买进,卖出,特别是影子价格为零时,二、在经营管理中的应用,y1*=2y2*=1y3*=0,3、在新产品开发决策中的应用,利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产。,假设该企业计划生产一类新产品，单件消耗三种原料的数量为（2,3,2），则新产品的单位利润必须大于 22+13+02=7（百元）才能增加公司的收益，否则生产是不合算的。,二、在经营管理中的应用,y1*=2y2*=1y3*=0,4、分析现有产品价格变动对资源紧缺情况的影响,若甲产品提价，单位利润增至4，则影子价格改变，由,Y*T=C

18、BB-1,说明如果甲产品提价的话，资源A将变得更紧俏.,二、在经营管理中的应用,y1*=2y2*=1y3*=0,5、分析工艺改变后对资源节约的收益,若企业革新技术，改进工艺过程后使资源A能节约2%，则带来的经济收益每天将是 262%=0.24（百元）,二、在经营管理中的应用,y1*=2y2*=1y3*=0,注意:,1、以上分析都是在最优基不变的条件下进行的,2、应对影子价格有更为广义的理解,若增加产量约束 x1+x2 40：产量不超过市场需求量,若y4*较大，则说明扩大销路能比增加资源带来更大的经济效益,Y*T=CBB-1,Duality Theory,线性规划的对偶问题,对偶问题的经济解释影子价格,对偶单纯形法,灵敏度分析,对偶问题的基本性质,第二章 线性规划的对偶理论,