第三章对偶理论.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第三章对偶理论.ppt》由会员分享,可在线阅读,更多相关《第三章对偶理论.ppt(117页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三章 对偶理论3.1.1 线性规划对偶问题3.1.2 对偶问题的基本性质3.1.3 影子价格3.1.4 对偶单纯形法3.2.1 灵敏度问题及其图解法3.2.2 灵敏度分析3.2.3 参数线性规划3.1.1 3.1.1 线性规划的对偶问题线性规划的对偶问题n一、对偶问题的提出一、对偶问题的提出n二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型n三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系实例:某家电厂家利用现有资源生产两种实例:某家电厂家利用现有资源生产两种 产品,产品, 有关数据如下表:有关数据如下表: 设备设备A 设备设备B调试工序调试工序利润(元)利润(元)0
2、612521115时时24时时 5时时产品产品产品产品D一、对偶问题的提出一、对偶问题的提出如何安排生产,如何安排生产,使获利最多使获利最多?厂厂家家设设 产量产量 产量产量1x2x 0, 5 2426 155 2max 212121221xxxxxxxs.t.xxz 设:设备设:设备A A 元时元时 设备设备B B 元时元时 调试工序调试工序 元时元时1y2y3y收收购购 付出的代价最小,付出的代价最小, 且对方能接受。且对方能接受。出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。 设备设备A 设备设备B调试工序调试工序利润(元)利润(元)06
3、12521115时时24时时 5时时Dn厂家能接受的条件:厂家能接受的条件:n收购方的意愿:收购方的意愿:32152415minyyyw单位产品单位产品出租出租收入不低于收入不低于2 2元元单位产品单位产品出租出租收入不低于收入不低于1 1元元出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。1252632132yyyyy厂厂家家0, 5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw对对偶偶问问题题原原问问题题收收购购厂厂家家一对对偶问
4、题一对对偶问题0 min bAX 0X . .CXz max YC s.t. YAYb wts),(21ccC 21xxX)(ijaA ),y,y(yY321321bbbb3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题一般规律 特点:特点: 1 2限定向量限定向量b 价值向量价值向量C (资源向量)资源向量) 3一个约束一个约束 一个变量。一个变量。 4 的的LP约束约束“ ” 的的 LP是是“ ”的约束。的约束。 5变量都是非负限制。变量都是非负限制。 min max z maxzmin 其它形式其它形式的对偶的对偶? ?二、原问题与对
5、偶问题的数学模型二、原问题与对偶问题的数学模型n1对称形式的对偶对称形式的对偶 当原问题对偶问题只含有不等式约束时,当原问题对偶问题只含有不等式约束时,称为对称形式的对偶。称为对称形式的对偶。0 min bAX 0X . .CXz max YC s.t. YAYb wts原问题原问题对偶问题对偶问题情形一:情形一:0Y CA . min0X bAX .maxYtsYbwtsCXz原问题原问题对偶问题对偶问题)(YY化为标准对称型化为标准对称型情形二:情形二:证明证明0Y CA .min0X bAX .maxYtsbYwtsCXz对偶对偶n2、 非对称形式的对偶非对称形式的对偶 若原问题的约束条
6、件是等式,则若原问题的约束条件是等式,则无约束min0maxYCYAYbwXbAXCXz原问题原问题对偶问题对偶问题推导推导: : 0 maxXbAXbAXCX z 0 max XbbXAACX z原问题原问题 根据对称形式的对偶模型根据对称形式的对偶模型, ,可直接可直接写出上述问题的对偶问题写出上述问题的对偶问题: :-bb),Y(Yw21min0,0(2121Y YCAA),YY , YYC A)Y(Yb )Y(Yw00min 212121无约束YCYAYb w max令令 ,得对偶问题为:,得对偶问题为:21YYY证毕。证毕。三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系
7、 约束条件的限定向量目标函数的价值向量自由变量变量变量个变量约束约束约束个约束目标函数 00 maxmn z原问题(或对偶问题)原问题(或对偶问题)对偶问题(或原问题)对偶问题(或原问题)目标函数的价值向量约束条件的限定向量约束约束约束个约束自由变量变量变量个变量目标函数 00minmn w zmax zminn例例:无约束,x x,xxxxxxxxxxs.txxxx z432143214321432101023428854235max对偶问题为对偶问题为无约束21,0428233402521212121yyyyyyyyyys.t.21108minyyw线性规划的对偶问题线性规划的对偶问题n引
8、例引例n对称性对称性n弱对偶性弱对偶性n最优性最优性n对偶性(强对偶性)对偶性(强对偶性)n互补松弛性互补松弛性0, 5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw对对偶偶问问题题原原问问题题收收购购厂厂家家n引例引例( )32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxxjjzc 原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问
9、题的变量化为极小问题原问题化为极小问题,最终单纯形表:原问题化为极小问题,最终单纯形表:2154332543212/32/7002/152/32/1102/152/14/14/1014/54/1xxxxxyyyyyyyjjzc 原问题的变量原问题的变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量对偶问题的变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表( )32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxxjjzc 原问题原问题的变量的变
10、量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题化为极小问题原问题原问题最优解最优解对偶问题对偶问题最优解最优解原问题化为极小问题,最终单纯形表:原问题化为极小问题,最终单纯形表:n两个问题作一比较两个问题作一比较: :1.两者的最优值相同两者的最优值相同2.变量的解在两个单纯形表中互相包含变量的解在两个单纯形表中互相包含原问题最优解原问题最优解(决策变量)(决策变量)对偶问题最优解对偶问题最优解(决策变量)(决策变量)14 wz2/3, 2/721xx 对偶问题的松弛变量对偶问题的松弛变量2/ 1, 4/ 1, 0321yyy原问题的松弛
11、变量原问题的松弛变量 原问题与对偶问题在某种意义上来说,原问题与对偶问题在某种意义上来说,实质上是一样的,因为第二个问题仅仅在第实质上是一样的,因为第二个问题仅仅在第一个问题的另一种表达而已。一个问题的另一种表达而已。理论证明:理论证明:原问题与对偶问题解的关系原问题与对偶问题解的关系一、对称定理:一、对称定理: 定理:定理: 对偶问题的对偶是原问题对偶问题的对偶是原问题。设原问题(设原问题(1 1) 对偶问题(对偶问题(2 2)0. .maxXbAXtsCXz0. .minYCYAtsYbw二、弱对偶性定理:二、弱对偶性定理: 若若 和和 分别是原问题(分别是原问题(1 1)及对偶问题(及对
12、偶问题(2 2)的可行解,则有)的可行解,则有 bYXAYXCXCXAYCAYbYXAYbXA证明:证明:YXbYXCn(1 1)极大化问题(原问题)的任一可行解所)极大化问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值对应的目标函数值是对偶问题最优目标函数值的下界。的下界。n(2 2)极小化问题(对偶问题)的任一可行解)极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值所对应的目标函数值是原问题最优目标函数值的上界。的上界。n(3 3)若原问题可行,但其目标函数值无界,)若原问题可行,但其目标函数值无界,则对偶问题无可行解。则对偶问题无可行解。n(
13、4 4)若对偶问题可行,但其目标函数值无界,)若对偶问题可行,但其目标函数值无界,则原问题无可行解。则原问题无可行解。n(5 5)若原问题有可行解而其对偶问题无可行)若原问题有可行解而其对偶问题无可行解,则原问题目标函数值无界。解,则原问题目标函数值无界。n(6 6)对偶问题有可行解而其原问题无可行解,)对偶问题有可行解而其原问题无可行解,则对偶问题的目标函数值无界。则对偶问题的目标函数值无界。原问题原问题对偶问题对偶问题bYXCbYCX三、最优性定理:三、最优性定理: 若若 和和 分别是(分别是(1 1)和()和(2 2)的)的 可行解,且有可行解,且有 则则 分别是分别是(1 1)和()和
14、(2 2)的最优解)的最优解 。 YXYXbYCX,则则 为(为(1 1)的最优解,)的最优解,反过来可知:反过来可知: 也是(也是(2 2)的最优解。)的最优解。XYbYCXbYXC,证明:因为(证明:因为(1)的任一可行解)的任一可行解 均满足均满足X证明:证明:原问题与对偶问题的解一般有三种情况原问题与对偶问题的解一般有三种情况:n一个有有限最优解一个有有限最优解 另一个有有限最优解。另一个有有限最优解。n一个有无界解一个有无界解 另一个无可行解。另一个无可行解。n两个均无可行解。两个均无可行解。四、对偶定理(强对偶性):四、对偶定理(强对偶性): 若原问题及其对偶问题均具有可行解,若原
15、问题及其对偶问题均具有可行解,则两者均具有最优解,且它们最优解的目标函则两者均具有最优解,且它们最优解的目标函数值相等数值相等。 若若 分别是原问题(分别是原问题(1 1)与对偶)与对偶问题(问题(2 2)的可行解,)的可行解, 分别为(分别为(1 1)、)、(2 2)的松弛变量,则:)的松弛变量,则: 即:即:YX,SSYX ,YXXYXYSS,0, 0为最优解为最优解00,0000)(01iiisiinjjijisiisiiSybXAxbxaXAxyxyXAbYXY原问题第原问题第i条约束条约束 A的第的第i行行 说明:说明:在线性规划问题的最优解中,如果对在线性规划问题的最优解中,如果对
16、应某一约束条件的对偶变量值为非零,则该应某一约束条件的对偶变量值为非零,则该约束条件去严格等式;反之如果约束条件取约束条件去严格等式;反之如果约束条件取严格不等式,则其对应的对偶变量一定为零。严格不等式,则其对应的对偶变量一定为零。000 )(0)(0jjjjjjjjjSxcPYcPYxxcPYXCAYXY另一方面:另一方面:对偶问题的第对偶问题的第j条约束条约束n(1)从已知的最优对偶解,求原问题最)从已知的最优对偶解,求原问题最优解,反之亦然。优解,反之亦然。n(2)证实原问题可行解是否为最优解。)证实原问题可行解是否为最优解。n(3)从不同假设来进行试算,从而研究)从不同假设来进行试算,
17、从而研究原始、对偶问题最优解的一般性质。原始、对偶问题最优解的一般性质。n(4)非线性的方面的应用。)非线性的方面的应用。在单纯形法的每步迭代中,目标函数取值 ,和检验数 中都有乘子 ,那么Y的经济意义是什么? bBCzB1NBCCBN11BCYBn 当线性规划原问题求得最优解时,其对偶问题也得到最优解 ,且代入各自的目标函数后有:), 1(*njxj), 1(*miyi是线性规划原问题约束条件的右端项,它代表第 种资源的拥有量;ibinjmiijwybxczij11*(3) 对偶变量 的意义代表在资源最优利用条件下对单位第 种资源的估价,这种估价不是资源的市场价格,而是根据资源在生产中作出的
18、贡献而作的估价,为区别起见,称为影子价格(shadow price)。*iyin1资源的市场价格是已知数,相对比较稳定,而它的影子价格则有赖于资源的利用情况,是未知数。由于企业生产任务、产品结构等情况发生变化,资源的影子价格也随之改变。市场价格影子价格市场企业n2影子价格是一种边际价格。 在(3)式中, 。 说明 的值相当于在资源得到最优利用的生产条件下, 每增加一个单位时目标函数 的增量。z*iybzi*iyib(3,3)(15/4,5/4),z=8.75242621 xx(7/2,3/2),z=8.5252621xx3资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当第2种资源
19、的市场价格低于1/4时,可以买进这种资源;相反当市场价格高于影子价格时,就会卖出这种资源。随着资源的买进卖出,它的影子价格也将随之发生变化,一直到影子价格与市场价格保持同等水平时,才处于平衡状态。n4在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源 未得到充分利用时,该种资源的影子价格为零;又当资源的影子价格不为零时,表明该种资源在生产中已耗费完毕。 ijijijijbxa;ybxanjiinj110y 0时,时,当当ibn5从影子价格的含义上考察单纯形表的 检验数的经济意义。miijjjijjBaycPBCc11(4)jc第j种产品的产值miijiay1生产第j中产品所消耗各项资源
20、的影子价格的总和。(即隐含成本)可见,产品产值可见,产品产值隐含成本隐含成本 可生产该产品;可生产该产品;否则,不安排生产。否则,不安排生产。检验数的经济意义检验数的经济意义n6一般说对线性规划问题的求解是确定资源的最优分配方案,而对于对偶问题的求解则是确定对资源的恰当估价,这种估价直接涉及到资源的最有效利用。经济学研究如何管理自己的稀缺资源n 对偶单纯形法的基本思路对偶单纯形法的基本思路n 对偶单纯形法的计算步骤对偶单纯形法的计算步骤原问题基可行解原问题基可行解 最优解判断最优解判断0jjjzc01bBb对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判断最优解判断n线性规划问题0ma
21、xXbAXCXz 不妨设 为对偶问题的初始可行基,则 。),(21mPPPB0zcjj 若 ,即表中原问题和对偶问题均为最优解,否则换基。mibi, 2 , 1, 0确定换出基变量 对应变量 为换出基的变量0miniiirbbbrx确定换入基变量 为主元素, 为换入基变量rsssrjrjjjjazcaazc0minrsasx初始可行基0,y 125 26.32132132yyyyyyyts32152415minyyyw0,y 125 26.5215321432yyyyyyyyyts32152415maxyyyw0,y 125- 26.5215321432yyyyyyyyyts32152415m
22、axyyyw对偶问题的初始可行基2/32/7002/152/32/ 1102/152/ 154/ 14/ 1014/54/ 12404101513/ 13/2053/ 1006/ 16/ 1103/ 124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjcjjzc使对偶问题基变量可行,0,0, 1414a505406242y换出 换出42) 1, 2min(y换出换出2/32/7002/152/32/ 1102/152/ 154/ 14/ 1014/54/ 12404101513/ 13/2053/ 1006/ 16/ 1103/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 对偶 理论
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内