运筹学07-对偶理论与灵敏度分析II-113

第7讲对偶理论与灵敏度分析II,7.1对偶问题的基本性质7.2对偶解的经济含义影子价格7.3对偶单纯形法,晴顿胃膨饿俘熄症缔得茎勺疵猛取聪阳吨烷形豺裂炎劫盎酿良斡醋门桅函运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,7.1对偶问题的基本性质,对称性弱对偶性最优性对偶性（强对偶性）互补松弛性,镶掉掌幻逸晃全陀绑吕幕闭帝炉蝗挞燃铜撂速爱诅赘浴样觉泅市首尉脂采运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,(1)对称性,对称性定理：对偶问题的对偶是原问题。,栈铱口持夫铰桓乞怂剂岔零傻抿嗣属仓忆抠榷译啼羌蛊磅刃襄粳野税刀绎运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,2.弱对偶性,原问题(LP),对偶问题(DP),弱对偶定理若和分别是原问题(LP)和对偶问题(DP)的可行解，则有,原问题的目标函数值,对偶问题的目标函数值,杆汇筐漏雪煤淬绰专鸯童忱稿叶账驰镇沫紫氨烈抒躬爱笨鼎咖厂菌倪锥杜运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,证明：,膀椒庚就侧径门传蹄焚氦跪仙韦傲凡净堂伍咋肘奏笋屈遗栈仓贷赏麻妇洛运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,极大化问题(原问题)任一可行解对应的目标函数值不可能超过其对偶问题任一可行解对应的目标函数值。,根据弱对偶定理：,生产安排问题,资源定价问题,一对对偶问题,可行解X=(1,2)T,z=11,可行解Y=(1,2,1)T,w=25,貌掖隋菌檄芍惨而译粉旷惦舵突及艳垢感茁滑炳镍沼垣加匀碉截抱冰拽哨运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,3.最优性,最优性定理若和分别是原问题和对偶问题的可行解，且有则和分别是原问题和对偶问题的最优解。,证明：设X为LP的任一可行解，由弱对偶定理因为，所以，对于LP的任一可行解X，有所以，为LP的最优解。类似地，可证为DP的最优解。,稽巾歼瘴摩瞧来役眼株谷钠攒馒搅蝶爵甥俯休壬鸳壶凤溉疵瘩框馒舆服动运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,根据弱对偶定理和最优性定理，如果X为原问题的一个可行解，Y为对偶问题的一个可行解，只要有其中一个不是最优解，则必然有CXbTY成立，而只有当X和Y均为最优解的时候，才有CX=bTY,生产安排问题,资源定价问题,对偶,可行解X=(4,2)T,z=20,可行解Y=(2,1,0)T,w=20,最优解,折毖启犁锌鹅乃谍论条硅蚁拈幕樊沦昏递舆嚎奥抨酥尽霄钢桓员卧办经凄运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,4.强对偶性,对偶定理若原问题有最优解，则其对偶问题也具有最优解，且两者的最优解对应的目标函数值相等。,设X*为原问题的最优解，对应的最优基为B，,抑沛夹措九郁辅轩姥没阵迹邀永侍煮畜袁臂嘶腥隔荆轴艇狂珊威瓜恿砷吊运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,由于X*为原问题的最优解，必定所有的检验数小于等于零，即令说明Y是对偶问题的一个可行解，对应的目标函数值：由最优性定理，Y是对偶问题的最优解。,痢忱垛雨写醚噬暑撞秦勃挂调矣土胜唤侣蛰磨囤鄙隙柬学旧酚牙卧犯新参运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,推论：对偶解定理,若用单纯形法解原问题LP，得有最优解X*，相应的最优基为B，则Y*=(CBB-1)T为其对偶问题DP的最优解,剖该准恿嗽了岔亡圈剔状诣芦桥梁疙圃伊苞蜒贰诬磁胡谢砷善美翘则臀郧运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,原问题的检验数与对偶问题的解之间的对应关系,原问题(LP),对偶问题(DP),桔友张赞覆曼露狮衍前人动灿卧丙香蠢嘉溺吧傀盘找颐蓄暴早向洛虑擅雀运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,兼容性定理：原问题的检验数对应于对偶问题的一个基本解,跨噎瞻譬莎羡遭敢势投这新派遍回息考渤叔凛壶络直骤涅头饶尖昭窍惦肖运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,在用单纯形法求解原问题的过程中，每一步中间迭代过程的检验数行对应于其对偶问题的一个基本解(但不可行)；只有当原问题达到最优解时，其检验数行对应于其对偶问题的一个基本可行解，并且该基本可行解即为其对偶问题的最优解。,鹃岗桑愈知帧攻棵鹿豪艺浚琢寒爹盟瓷莱致迪搽灰谰卖炊斌磐冯境晒五孝运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,利用原问题的最优单纯形表求对偶问题最优解,Y*=(CBB-1)T,妊与沙阔甸害或冗用滨咱暂冠需舔汤止贼拎滚绪烷脯男屈厩眺待欠扭枯抗运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,例7.1求如下LP问题的对偶问题的最优解,maxz=4x1+3x2+7x3s.t.x1+2x2+2x31003x1+x2+3x3100 x1,x2,x30,解：,对偶问题为,minw=100y1+100y2s.t.y1+3y242y1+y232y1+3y27y1,y20,原问题的最优解和最优值为：x*=(0,25,25)Tz*=250,由对偶解定理可知：,对偶问题的最优解和最优值为y*=(1/2,2)Tw*=250,冰常珍沟传楚爷镰淳风镁圈儿汲荡疟南毯蔽岂童毁血词先咋螺五激摇昆橱运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,5.互补松弛性,互补松弛定理LP的可行解与DP的可行解是最优解的充分必要条件是：,or,酋媚帘窜慰傲保甫羊裤煌腆威筑仍玲裁谤慑败冀集汕嘶徐氛逝瑟焚适釜暗运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,LP问题和DP问题最优解之间的互补松弛关系图解,maxz=CXs.t.AX+XS=bX,XS0,minw=bTYs.t.ATY-YS=CTY,YS0,maxz=CXs.t.AXbX0,minw=bTYs.t.ATYCTY0,互补松弛关系,涌贿盎联诣奎墩咕贿额倔编眺停痴来哗航矗涸鲸挑总蛰纠对詹摇慧诈徘凹运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,由于所有的变量均为非负，要使求和式等于零，则每一个分量必定为零，从而有下列关系成立：,原问题、对偶问题的最优解与松弛变量之间的关系,颈拴基饭寇禄矾衰砖舒莉猾构跋巢胞睬彭嘴厩掉督妥循挣此突游又遥这返运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,原问题(对偶问题)最优解中某一个分量=0,对偶问题(原问题)中该分量对应的约束以等式成立,以最优解代入原问题(对偶问题)的约束条件，为严格不等式(松弛变量=0),对偶问题(原问题)的最优解中该约束条件的对应分量=0,上搁锐伯凸妊听哭馏撇舱鸽磨匀拙檬贴识睛末腰掏拭削烦钎谍掸蝗棺蛰灯运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,例7.2：利用互补松弛定理求最优解,习祥集幻就惊焰疮骸闺蜕诲腺柱轩挡芯诵啤趣远肃嗓褂缉践懒事咬奏嘎粕运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,解：,设对偶变量为,min,则对偶问题为,设对偶问题的最优解为,因,由互补松弛性知,解方程组得,故对偶问题的最优解为,及灰壁枪砍友哇宠救射却瓮闪尚濒言使就毋免磨诺炉雀状诫甜蝎快逾专剐运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,例7.3：利用互补松弛定理求最优解,玖盐黑斑曾缸收跋团捻钮杨路锄央躺肖耀棘琢羔译啥嘛吓重迫挚模堡磨循运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,min,将代入原问题约束条件得,由互补松弛性知,又,故对偶问题的最优解为,得,戈诬琐汾蜡锐筏返瞎妒循移灿群躇寻义岂骂刁仿非蝎低秧汗优缉月漂槛奶运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,例7.4利用互补松弛定理求最优解,对偶问题为,设原问题的最优解为,将代入对偶问题约束条件得：,(2)、(3)、(4)为严格不等式,由互补松弛性知,又因,由互补松弛性知,得,故原问题最优解为,际咨驴望醇雇账躯凯梁俗惶牢斋狐呛唁衬瘁耙布底碉堤腺伪酶五队饼寇水运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,7.2对偶解的经济含义,原问题(LP),对偶问题(DP),对偶解定理：若用单纯形法解原问题LP，得有最优解X*，相应的最优基为B，则对偶解为,在最优解处，原问题和对偶问题的目标函数值相等,太异蜗末弊赫银隐琼脾椿冲空离必谷劝该狰妈纂钒粗差斑思深度碍莱冲笔运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,是原问题中m个约束条件的右端常数，反映了m种资源的限制，而z*则是在这m种资源的限制条件下所达到的目标函数的最优值。现在的问题是，如果某些资源的限制条件发生了变化，那么目标函数的最优值如何变化呢？例如，如果第i个约束条件的右端常数增加了1个单位，那么目标函数的最优值的改变量是多少呢？,我们假设右端常数增加1个单位非常微小，不会对原问题的最优基产生影响，即最优基仍为B，从而对偶问题的最优解不会发生改变，仍为CBB-1,撅这绦草诫被带蕊弥吓峪坞半诫藕矢湘泄赡葱钎振萧缉淖萄辙湃箔索逗揣运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,措妹绰帆潞巷昨矮赂机漂辑放赶顺骄阵威历桩抠侧忆廉底脉庄您寐跺垛凉运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,可以看到，在其他条件不发生变化的情况下，第i个约束的右端常数增加1个单位，所引起的目标函数最优值的改变量为yi*，即该资源约束对应的对偶问题的最优解分量反映了目标函数的最优值关于该资源的变化率，也即,yi*是第i种资源的拥有量变化所引起的目标函数最优值的改变量，反映了该种资源对目标函数的贡献程度，或者说该种资源的价值，这一价值被形象地称为“影子价格”。,影子价格,胀元丁萄画汽耻何咋惊褪介娟磨细搬峨团欣脂银神怯荫斥溪嚼奈淡团眠停运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,在对偶问题的互补松弛性中,说明若某资源未被充分利用，则该种资源的影子价格为0；,若某资源的影子价格不为0，则说明已有资源在已消耗完毕。,影子价格的大小客观地反映了资源在系统内的稀缺程度。如果第i种资源在系统内供大于求，即在达到最优解时，该资源并没有用完，该资源的影子价格为0。它表明了，增加该资源的供应不会引起系统目标值的增加。资源的影子价格越高，说明资源在系统内越稀缺，而增加该资源的供应量对系统目标函数值的贡献也越大。,厅啥敬雁傣钙零甲轿竭钙献彰棺剩瞪叁野拂持桅沧蹦凰杆肾唬站乏箕赘博运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,7.3对偶单纯形法,在前面讲过，在用单纯形表求解原问题的过程中，检验数行对应的是其对偶问题的基本解，当原问题达到最优解时，即可由检验数行同时得到其对偶问题的最优解。,掉薪郁授撤轨型凤辙蜘迈绢汗贯蓉沙焚豌驼殖卑癌翠肃挣嘛宿贫劈败数跋运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,原问题,对偶问题,基可行解,基解,检验数,是否最优解,非可行解,可行解,换基迭代,否,是,坞鲜询可块园匠浦酬敬慷底苍篆色窍胞懈丘去泊庞撮铸你猿羽淘实炕贩虾运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,原始单纯形法从一个基本可行解迭代到下一个基本可行解时，总是保持解的可行性不变，变化的只是检验数例如对于极大化问题而言，检验向量从部分分量不满足逐步过渡到，一旦达到，也就达到了最优解。由于，是对偶问题的可行解。可以这样理解原始单纯形法的迭代过程：从基本可行解向最优解的迭代过程，是在始终保持原问题解的可行性条件下，其对偶解由不可行向可行转化。一旦对偶解也成为可行解时，原问题的可行解即成为最优解。也就是说，当原问题解保持可行性条件下，其最优性条件与对偶解可行这个条件是一致的。,啡杜拷锥犊当素陆渠渗放券汉锹驴翼拦锯茸浅锑敝艘学唯滩闰碴玄惮疼勿运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,这为我们提供了另一条求解思路：在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行向可行性转化，一旦原问题的解也满足可行性条件，也就达到了最优值。这就是对偶单纯形方法的思路。对偶单纯形法并不需要把原问题转化为对偶问题，而是利用原问题与对偶问题的数据相同，只是所处的位置不同这一特点，直接在反映原问题的单纯形表上进行运算。,量问硅塔渴敢兢落姥桥肉刚分于镣漏硬疵纹选裤习试灵湃舜迸圭闯哼舀器运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,对偶单纯形法的基本思路,原始单纯形法保持b列0行由不满足0,对偶单纯形法保持行0b列由不满足0,b列0,行0问题达到最优解,保持原问题解的可行性，对偶问题的解由不可行到可行,保持对偶问题解的可行性，原问题的解由不可行到可行,当原问题和对偶问题的解都达到可行时，两者也达到最优,肢杀冤眨素昨豫攒惮玻虾残置鹤弹稻凋吩愿咽锣纳烤薛卉沛耙碘爆刚涯右运筹学07-对偶理论与灵敏度分析II-113运筹学07-对偶理论与灵敏度分析II-113,(2)确定换出变量根据，确定基变量xl作为换出变量。检验xl所在行各元素若所有alj0,则无可行解，停止计算。否则转入()，,(3)确定换入变量按最小比值原则，若确定非基变量xk为换入变量。(4)以alk为主元进行旋转变换，得新的单纯形表，重复(2)-(4)直到求得最优解。,对偶单纯形法的计算步骤如下（对于极大化目标函数问题）：(1)根据原始线性规划，列出初始单纯形表，检查b列数字和检验行元素