《运筹学第2章对偶理论课件》由会员分享，可在线阅读，更多相关《运筹学第2章对偶理论课件（79页珍藏版）》请在金锄头文库上搜索。
1、Chapter2 对偶理论 ( Duality Theory ),单纯形法的矩阵描述 对偶问题的提出 线性规划的对偶理论 对偶问题的经济解释影子价格 对偶单纯形法 灵敏度分析(选讲) 掌握WinQSB软件求解对偶规划,本章主要内容：,化秽忆臣疗蔬走免偶杭秘洛胰门羽栏风辕绷升根莫缚入刚埂必提收猩羔蕾运筹学第2章对偶理论运筹学第2章对偶理论,学习要点： 1. 理解对偶理论，掌握描述一个线性规划问题 的对偶问题。 2. 能够运用对偶单纯形法来求解线性规划问题。 3. 会用互补松弛条件来考虑一对对偶问题的界。 4. 了解影子价格、灵敏度分析以及用WinQSB求 解对偶规划问题。,咳辰嫉册位眺研蟹遍冒圣
2、吭集笑约眠捌歹面费虚穆究码随掇饶究痹桩愧贤运筹学第2章对偶理论运筹学第2章对偶理论,2.1 单纯形法的矩阵描述,当耿扳操靶饲惜骚兜课遏严炒镑傀隘狮章躬獭迟仕烬眉洪宪涝确芥皂水福运筹学第2章对偶理论运筹学第2章对偶理论,每一列的含义？ 每个表中的B和B-1的查找？,单纯形法的矩阵描述,赛迄乞烦污肘训啃靶持首魂雄土透贵蛰空托铱攫钠废旅譬晦虏荆岁跌叼滦运筹学第2章对偶理论运筹学第2章对偶理论,单纯形法的矩阵描述,糜五祷学钠乐概丢体售改酮裸靶肤靳寇朱归洱珍怠单谤琼代秘蝎限喝豪于运筹学第2章对偶理论运筹学第2章对偶理论,单纯形法的矩阵描述,蔡纷缆御凄讼规制栓月夏蚂旭爸溺唾醒蔗沂亩瞻宽钥谣梭捅酪锈澳握浇领
3、运筹学第2章对偶理论运筹学第2章对偶理论,单纯形法的矩阵描述,炸叔泻欧漆累宗韵做榆罢芳朔讼他榆拓翼虱股叫蠕闯搪煤颇领吓幽闭扦瀑运筹学第2章对偶理论运筹学第2章对偶理论,单纯形法的矩阵描述,须优烯疡淌恍胀废趴扒佬各贤栈瘁丫铡钥祭婆菱数偶寥酚惫隘芳躯强墩危运筹学第2章对偶理论运筹学第2章对偶理论,2.3 对偶问题的提出,悉铀况尉曲觉牛洱刷景叼草标银停挫抓评痢筷嘴厕蓖稀竣履授晋追邻鳖钦运筹学第2章对偶理论运筹学第2章对偶理论,对偶理论是线性规划中最重要的理论之一，是深入了 解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的
4、重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？,对偶问题的提出,脑安哄淌司雷餐仇杀梁欠笔栽腮妒变觉果肚本撇巡是娩忻者团踊淖恒撮焊运筹学第2章对偶理论运筹学第2章对偶理论,俩家具制造商间的对话：,唉!我想租您的木工和油漆工一用。咋样？价格嘛好说，肯定不会让您兄弟吃亏。,王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。,Hi：王老板，听说近来家具生意好呀，也帮帮兄弟我哦!,家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。,价格嘛好商量， 好商量。只是.,王 老 板,李 老 板,引例1,
5、对偶问题的提出,汇副公实淡膛鲤涡馋挫穆铸苞沦道戈宰扎肪勉算炮氏亦需食赏网投都狮踌运筹学第2章对偶理论运筹学第2章对偶理论,王老板的家具生产模型： x1 、 x2是桌、椅生产量。 Z是家具销售总收入（总利润）。 max Z = 50 x1 + 30 x2 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）
6、,所得不得低于生产的获利（不吃亏原则） 要使对方能够接受 （竞争性原则）,两个原则,对偶问题的提出,狰嘛枕兼寥错新家酬夏恕凳腰耕恫壁慑绥埃威脉味诀磁攒阁烩戴希做橇欠运筹学第2章对偶理论运筹学第2章对偶理论,王老板按（D）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。,按时下最流行的一个词，叫什么来着,对偶问题的提出,肯藩收摩膘蚤滚缠绎币庄进辱铸遍揩揭羊汀搪疮盐狭梭枝抽沪捍陡闽妊昂运筹学第2章对偶理论运筹学第2章对偶理论,设三种资源的使用单价分别为 y1 , y
7、2 , y3,y1 y2 y3,生产单位产品A的资源消耗所得不少于单位产品A的获利,生产单位产品B的资源消耗所得不少于单位产品B的获利,y1 +3 y2 40,2y1 + 2 y2 + 2y3 50,引例2,通过使用所有资源对外加工所获得的收益,W = 30y1 + 60 y2 + 24y3,对偶问题的提出,漓零渤否瘁李金倒博饼售泻很涛撵钨嫡颤札需曳少噬涌炊蜒盲汝装辽娩骄运筹学第2章对偶理论运筹学第2章对偶理论,根据原则2 ，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：,Min W = 30y1 + 60 y2 + 24y3,y1 + 3y2 40 2y1 + 2 y2
8、+ 2y3 50 y1 , y2 , y3 0,s.t,目标函数,约束条件,原线性规划问题称为原问题，此问题为对偶问题， y1 , y2 , y3为对偶变量，也称为影子价格,对偶问题的提出,侦碎伪鲸缓瓷状阮文炯址椽旨租拍寒涌蜀同气予沟员虚炮尸渐锯素形汾捧运筹学第2章对偶理论运筹学第2章对偶理论,2.4 线性规划的对偶理论,言晕吗漆勺坊掀日醉其奇杜疼静顷童幌型凭庞麻围捆蹲审刹厚砖姥橡媚答运筹学第2章对偶理论运筹学第2章对偶理论,Max Z= 40 x1 +50 x2,x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0,s.t,原问题 （对偶问题）,对偶问题 （原问题）
9、,一、 原问题与对偶问题的对应关系,3个约束 2个变量,2个约束 3个变量,线性规划的对偶理论,包呸崎耻惺莱尊冯么辐汰橡蛀动姬凸沽根莎戈扭货莎屉愧坐邻夫丰俗萨界运筹学第2章对偶理论运筹学第2章对偶理论,对偶问题的形式,定义 设原线性规划问题为 则称下列线性规划问题,为其对偶问题，其中yi (i=1,2,m) 称为对偶变量,上述对偶问题称为对称型对偶问题,原问题简记为(P)，对偶问题简记为(D),称问题(P)和(D )为一对对偶问题,线性规划的对偶理论,坍州史犊着苦氧疙好图茶掩读晰密焚淘废乏窗亦注秆被抿级筏所悸美鲁崖运筹学第2章对偶理论运筹学第2章对偶理论,对称型问题的对偶规则,1、给每个原始约
10、束条件定义一个非负对偶变量yi(i=1,2,m)； 2、使原问题的目标函数系数 cj 变为其对偶问题约束条 件的右端常数； 3、使原问题约束条件的右端常数 bi 变为其对偶问题目 标函数的系数； 4、将原问题约束条件的系数矩阵转置，得到其对偶问 题约束条件的系数矩阵； 5、改变约束问题不等号的方向，即将“”改为“”； 6、原问题为“max”型，对偶问题为“min”型。,线性规划的对偶理论,颧橇嗓讽奎机愧畔量慌戏示贼渣淳炕牌屑聚撵粪标嘻巳幽栈妇耗篮伶档帅运筹学第2章对偶理论运筹学第2章对偶理论,原始问题 Max Z=CX s.t. AXb X 0,b,A,C,Max,n,m,对偶问题 Min W
11、=Yb s.t.YAC Y 0,Min,C,AT,b,n,m,线性规划的对偶理论,闺旨虽纱棺榔晤垒嘉纶贱类腋凤齐诉熊仙奇氰公鬃然废逐褒头被炯潦烹伤运筹学第2章对偶理论运筹学第2章对偶理论,当原问题为求极小值时，对偶问题为求极大值。 原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。 原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。 原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。 原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程
12、的匹配形式。,线性规划的对偶理论,开未佯窝砷疙掺染睹无肿犁郝寅盔沸傀皑透配奸扳滓针俄伍察祈恕瘴猪典运筹学第2章对偶理论运筹学第2章对偶理论,求线性规划问题的对偶规划,解：由原问题的结构可知为对称型对偶问题,例1,线性规划的对偶理论,蛮蜕潮樱辊拙肾烷废八闻脑以层镍谗毒器臭搂至龋樟砌鸿饺蓄皑莱怯窗慕运筹学第2章对偶理论运筹学第2章对偶理论,求线性规划问题的对偶规划,解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,例2,线性规划的对偶理论,薛毒卷私苞萌舷刃桩羚擒戳纪聂鉴侦薪肤贩扑播礼阶槛千披惕统枕绑茧专运筹学第2章对偶理论运筹学第2章对偶理论,求线性规划问题的对偶规划,解
13、：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,例3,线性规划的对偶理论,班任间艰渠擞构颁蹲挤奎肠讫漳高岛簿燕组闰坞句吵轴屑啼苗踏窃钥嚣砒运筹学第2章对偶理论运筹学第2章对偶理论,上式已为对称型对偶问题，故可写出它的对偶规划,令,则上式化为,线性规划的对偶理论,讶明览土质觅让茁案器稚辖褥呈约踌菏疫胎和泼韦邯恋埔家口秩杀稼辜拎运筹学第2章对偶理论运筹学第2章对偶理论,对偶问题的非对称形式,min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2
14、+8y3+15y4 s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0,=,unr,=,x10,x20,x3: unr,线性规划的对偶理论,眩凹黔总迹红拽州麻陪墩尤匿偿赔报述蛊搀淄欲腋浅纯骗夸星嘶底向铲帝运筹学第2章对偶理论运筹学第2章对偶理论,1 原问题为“max”，对偶问题为“min”； 2 原问题中目标函数系数 ci 变为其对偶问题约束条件的右端常数； 3 原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数； 4 原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵；
15、5 原问题的变量个数n等于其对偶问题的约束条件个数n，原问题 约束条件的个数m等于其对偶问题变量的个数m； 6 在求极大值的原问题中，“”，“”和“=”的约束条件分别对应其对偶变量“0”，“0”和“无符号限制”； 7 在求极大值的原问题中，变量“0”，“0”和“无符号限制”分别对应其对偶约束条件的“”，“”和“=”约束.,混合型问题的对偶规则：,线性规划的对偶理论,恰愧腹淀衔帆敷批肺虫粳驳词萤逢它作歌裴港巩缅窗芬屯跑贷烫粘娱兢娶运筹学第2章对偶理论运筹学第2章对偶理论,线性规划的对偶理论,隅黔秉匙糟看猪弊册渝毋肇刃补辑故乱舔胎慢褪常翌颊柜攫憎吮玄乓灶洪运筹学第2章对偶理论运筹学第2章对偶理论,
16、Max Z=40 x1+ 50 x2,x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0,s.t,y1 y2 y3,Min W = 30y1+ 60y2 + 24y3,y1+3y2 + 0y3 40 2y1+2y2 + 2y3 50 y1 , y2 , y3 0,s.t,Max W= -30y1- 60y2 - 24y3,y1+3y2 + 0y3 y4 = 40 2y1+2y2 + 2y3 y5 = 50 y1 , y2 , y3 , y4 , y5 0,s.t,例4,二、 对偶问题的解,线性规划的对偶理论,倾括右趋靴奖其毋括现度霖敛垮讥涡苫春凋暂桂眨履裹苟臭弊瓢猴赦叼汝运筹学第2章对偶理论运筹学第2章对偶理论,Max W= -30y1
