运筹学_对偶问题

1、第二章LP的对偶理论与灵敏度分析,兴冗擦谴铆铰脊局馏对坟锋寥殆拎透娶榔谩奔赎被迸鹏啼泪鄙捕候篙管雾运筹学_对偶问题运筹学_对偶问题,线性规划的对偶问题,问公司应每天制造两种家电各多少件，使获取的利润最大。,例1,卡图邀呈疡忧契甩业逛害赋植帝吓玻岸欲矢辫升巡泡拭动微捆屏佑睫淹仕运筹学_对偶问题运筹学_对偶问题,问题 美佳公司愿意以多大的代价出让自己所拥有的生产资源？,叙揽版累吠彻涪删拈论趣鳃试倡耘瞻狡库沽旧萎样旨雕樱郸埃验杆侍始屉运筹学_对偶问题运筹学_对偶问题,设y1,y2和y3分别表示出让资源A，B和调试工序的单价，则美佳公司同意出让的条件将是 同意出让生产产品I的资源 同意出让生产产品II

2、的资源 购买者希望用最少的代价获得这些资源，因此,坯枕声嘲愧彝丰茁赖隔贵到期秒唆纤隶骏揪跟拯绳堵怯潞采愁七羡海录乱运筹学_对偶问题运筹学_对偶问题,这样得到一个新的线性规划问题,称这一问题是原来的LP问题的对偶线性规划问题或对偶问题，原来的LP问题也称为原问题。,谷碑圾蔼坠蘸巩荡冰饺蚜口缅烘渤棉矛捂忌挂蝴领踊淋氓耙枝琐比收屎膘运筹学_对偶问题运筹学_对偶问题,LP问题的对称形式,变量：所有变量均具有非负约束 约束条件： 最大化问题 所有约束条件都是“”型的 最小化问题 所有约束条件都是“”型的,霞汐壳淤遂扼宰痛惠孩氟耸琉缩吴引蛰柏目恭镀寻禹疤耸海阿瑞抢嗽听玄运筹学_对偶问题运筹学_对偶问题,对

3、称形式下的对偶关系,瞻止漂厅砍译从炮逊箍琉嘱卑装赦颈丘瑰益右突阮俄挺惜送蜗譬筏蛊队姐运筹学_对偶问题运筹学_对偶问题,对称形式的对应关系,对偶问题的对偶是原问题，即对偶关系是相互对称的关系,侥附都甥非浩蚊扼和判漠北袱柑秘四昂桃分育竣辨媒隔肢禹卡讲饯超朝觅运筹学_对偶问题运筹学_对偶问题,非对称形式下的对偶关系,厌负柬为姐钳府味六恐罪括划蓬南敬征资翘吸钾单云姚骸值惰铁涵庄圾邱运筹学_对偶问题运筹学_对偶问题,单纯形法的矩阵表示,添加松弛变量XS,将XB的系数矩阵化为单位矩阵,汪牢瘦算侵敌唇索芽拿舔昨找矾瞄拥派摆愉咕辣鬼诛常景昏尸域游怒劣轨运筹学_对偶问题运筹学_对偶问题,初始单纯形表,迭代后的单

4、纯形表,述纵户矮巢找刹知涟芯颅魄暖倘东音丈单移图恫颂纺广氖嘶枉揭街诞劫拯运筹学_对偶问题运筹学_对偶问题,在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆 在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量 XB=B-1b 系数矩阵的变化: A, IB-1A, I 在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj,并且Pj=B-1 Pj 若迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解,讥瞥摈攻裂都芦拱寓渝霖叮驰袒嘿赵广惮肖寿奋训违捕烬缚痰佩釉橙更巷运筹学_对偶问题运筹学_对偶问题,原问题最终单纯形表,对偶问题最终单纯形表,例1,最大化问题检验数的相反数给

5、出了对偶问题的解,隘镑舍孝啮踢可改戈韭兔歪篇剥跟曳辛楞硫澡前苯痪搜揍包堵诉揽居熟性运筹学_对偶问题运筹学_对偶问题,原本在对偶关系中，原问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。但在分别添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系,注 上表中我们将松弛变量与剩余变量统称为松弛变量,霜惺砒伟蠕贡治瞩愤赏碑负翼邦艾弗责哼刮环吹压诚盒猎矫弟视釉倾扎段运筹学_对偶问题运筹学_对偶问题,对偶问题的基本性质,弱对偶性 原问题可行解的目标函数不超过对偶问题可行解的目标函数,期辩知倔郊烹网害盼蘸聚眩肚构展蓝癣石捉悍攘着绥做互忆毖蛮危日要炸运筹学_对偶问

6、题运筹学_对偶问题,弱对偶性的推论,（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是原问题目标函数值的上界。 （2）如原问题有可行解且目标函数无界（即原问题为无界解），则对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。注意该推论的逆命题不成立。 （3）若原问题有可行解而对偶问题无可行解，则原问题目标函数无界；反之对偶问题有可行解而原问题无可行解，则原问题目标函数无界。,刃诸娄在盼肺俗凯戌水喀级室痹堵堑半慌关爷罗勺斋停币畴蝶对锋恩懊帘运筹学_对偶问题运筹学_对偶问题,最优性 若原问题一个可行解目标函数等于对偶问题的某个可

7、行解的目标函数,则这两个可行解分别是原问题和对偶问题的最优解 强对偶性 若原问题和对偶问题都有可行解,则它们都有最优解,且最优解的目标函数值相等 互补松弛性 在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则其对应的约束条件取等式;反之若一个约束条件为严格的不等式,则其对应的对偶变量为零,蛹皱猾捕光剩缮狡篮尊酷肪其奎题疽栗排瞎税宗美疑祭顺蒂搐舜齿墩桐囊运筹学_对偶问题运筹学_对偶问题,互补松弛性的另一种表述,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零;反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。,扎闽肌缘右随铃辉孝

8、妮宏偿慑废砾旦柑它身踏润在蝗刺邻逮译袁邮蛔星销运筹学_对偶问题运筹学_对偶问题,例（p76.7）,原问题,对偶问题,将原问题最优解X*=(2,2,4,0)代入原问题约束条件中得,第一个约束条件：2+6=8，为等式,第二个约束条件：4+2=6，为等式,第三个约束条件：2+4=6，为等式,第四个约束条件：2+2+49，为不等式，故y4 = 0,控柠部札惶芭犹未儒表挟谷普巢女沟锄贯盈垃谁饲我骨帅吱君捣惊老稿炉运筹学_对偶问题运筹学_对偶问题,而由x1=20, 得,而由x2=20, 得,而由x3=40, 得,于是得到方程组,得对偶问题最优解为,注：原问题与对偶问题最优目标函数值都是 z*=4+8+4=

9、16,轨鉴恭妓鉴瘁骂剩坚奶矾药玄检亡喳擞符妇焚窝紊沂显僚酚羹拽盏炊窝糖运筹学_对偶问题运筹学_对偶问题,第三节 影子价格,浆孺赠券琼枣夫连昆谎畦烂妇划超刘蝶足姓羚驱敖碟岸弗掂玄种谭咆商蔡运筹学_对偶问题运筹学_对偶问题,式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi的意义代表在资源最优利用的条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格。,设 和 分别是原问题和对偶问题的最优解，则由对偶性质，有,俊榷逾捡扔灾潍垢姬榨卒抄灼爸梆抄杂袁疥鞠突补财汹凹蛔蘑蜜晕顾隋验运筹学_对偶问题运筹学_对偶

10、问题,资源的影子价格随企业的生产任务、产品结构的改变而改变 影子价格是资源的边际价格 资源的影子价格也可视为一种机会成本 在生产过程中若某种资源未得到充分利用则其影子价格为零；只有在资源得到充分利用时，其影子价格才可能非零 利用影子价格可以说明：单纯形法中的检验数可以看成生产某种产品的产值与隐含成本的差 可以利用影子价格确定企业内部的核算价格，以便控制有限资源的使用和考核下属企业经营的好坏。,岭傻帆匝趟笺田藏惹棋蒲撒步格捧小粱谢钨吏胯咬涕渊赁押东各锋遏驭组运筹学_对偶问题运筹学_对偶问题,例1,Max z=2x1+x2 s.t. 5x215 6x1+2x2 24 x1+x2 5 x1,x20,

11、x2=3,6x1+2x2 =24,x1+x2 =5,最优解,可行域,最优目标函数值的变化：8.5变到8.75，增加1/4,资源的变化：设备B的可用时间从增加一小时,杉荷瓣选总届试芳凯吏苍芽蝉尝烈拙膝寥梦厕叙幌吻狠膨拈嫂唯蛮惊隧铺运筹学_对偶问题运筹学_对偶问题,参考文献： 李慧：资源影子价格分析与经营管理决策，系统工程理论与实践，2003年4月号，22-26,刷摆搓霄查泊毫七伤伦钡蒜幻终袋帧活戌哭砰藏恬罢歇库露烬撂季芥蟹烯运筹学_对偶问题运筹学_对偶问题,第四节 对偶单纯形法,按对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最终表不但给出了原问题的最优解，而且其检验数的相

12、反数就是对偶问题的最优解。,笑帐澎糊糟纳娘叔乞渡逆始柯哩诫诛雄阐擅谱廖架谩瘴少氟猜千寇膊颈尸运筹学_对偶问题运筹学_对偶问题,（对偶问题可行解）,芜若香巢回祝粒信历铃取嗡饼掐寄父巡禹喀锁摹释菊擅羞先枉溺颖鸯氮吟运筹学_对偶问题运筹学_对偶问题,保持对偶问题有基可行解,而原问题只是基本解,通过迭代,使后者的负分量个数减少，一旦成为基可行解,则原问题与对偶问题同时实现最优解.,柒嫁霹腹岛呸谭沪加阶微惯阉落盂谰卿掀涵掐羚哪蠕旅醇汐纶淘凛穴孪疽运筹学_对偶问题运筹学_对偶问题,对偶单纯形法计算步骤,适应于求解这样的LP问题：标准化后不含初始基变量，但将某些约束条件两端乘以“-1”后，即可找出初始基变量

13、。 要求：初始单纯形表中的检验数满足最优性条件,挎犯怠傲貉官炯澄匠忿顷孽十源铬掀靛耻酒轨噬兜索口趁蛮源假讣渠踌德运筹学_对偶问题运筹学_对偶问题,对满足上述条件的LP问题，对偶单纯形法的步骤是：,旋转运算。然后回到第2步。,作出初始单纯形表（注意要求）,检查b列的数据是否非负，若是，表中已经给出最优解；否则转下一步,确定换出变量：取b列最小的数对应的变量为换出变量,确定换入变量：用检验数去除以换出变量行的那些对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量,田论匪殆帜鞍冉告徒答榴蛮老困蟹甜活抿麻垒貉籽矾遵仇闺思则狙搞饱靛运筹学_对偶问题运筹学_对偶问题,例 用对偶单纯形法求解如下的

14、LP问题,化成标准形式,拾谊辛狐犹泅峪凸眯作昨怠盂您沏却扛婴淮虫坪苑挞浊矽敢帛顽榜硬丫啦运筹学_对偶问题运筹学_对偶问题,将各约束条件两端同乘“-1”得,用对偶单纯形法求解得,雅嫩便只婪冷磅剪扫粉茅捣漠吧荐怨忆烤妹咖左搭微同啤畦惦髓够歹擞中运筹学_对偶问题运筹学_对偶问题,最优解：x1=0, x2=1/4, x3=1/2, x4=0, x5=0,最优目标函数值：w*=-8.5（z*=8.5）,注：通常很少直接使用对偶单纯形法求解线性规划问题。,疆医凝抗双烧志孟栗铱疆胆败泊何可众泌渡戎冉尝淡哮馅秒受冻瓣惑圆撞运筹学_对偶问题运筹学_对偶问题,灵敏度分析,将讨论LP问题中的参数 中有一个或几个发生

15、改变时问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变,痛锹畜烬唤胎搏挣循垒自卫录桥跺扇俭壶派戴谎拿元吊涯彪温赴凉右基颜运筹学_对偶问题运筹学_对偶问题,研究的思路,将个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需要从头计算，而直接检查在参数改变后最终表有什么改变，若仍满足最终表的条件，则表中仍给出最优解，否则从这个表开始进行迭代求改变以后的最优解。,始筒瑶救跋疚财烂垛砰甜竖双没抛闪塌誊菌柴壁魏奏偿岩咀捆秧呻腻魔沂运筹学_对偶问题运筹学_对偶问题,灵敏度分析的步骤,将参数的改变计算反映到最终表上来。具体计算公式可以使用 检查原问题是否仍为可行解

16、 检查对偶问题是否仍为可行解 对检查情况按下表进行处理,癣蝎岁暗舍酮衬蛀笆立抚折呆滓量晋屠笼渣晶寞珍肩凸延抬神戈膊办鲜慰运筹学_对偶问题运筹学_对偶问题,疥炬贮播趁忙刀宦跺迢群俭摧藻衷酣口居俊俭棉赘警绅愚师宛台挛冉部秤运筹学_对偶问题运筹学_对偶问题,价值系数变化的灵敏度分析,例：在第一章美佳公司的例1中 （1）若产品I的利润降至1.5元/件，而产品II的利润增至2元/件，美佳公司的最优生产计划有何改变； （2）若产品I的利润不变，则产品II的利润在什么范围变化时，该公司的最优生产计划不发生变化,橙室诣织溜聋沪柠哀丫拥接约初傀携撬儿毛篆诵婶梨锨诌箕瞄鼠箔烧帅紊运筹学_对偶问题运筹学_对偶问题,

17、原最终单纯形表,昂匡幼迈斥膳撬窗眠珍填熟匣衣蒙纶统爷钧呐放造倒悔疤并单统茸辟太垒运筹学_对偶问题运筹学_对偶问题,（1）改变后,新的最优解为：,最优目标函数值为：,耿逝躯嫌对啪择室追舰臼绵锣抨睁栓趾骗弱宝室易湃绘孕人吻浑劈增愧确运筹学_对偶问题运筹学_对偶问题,（2）改变后,为使表中的解仍为最优解必须,因此产品II的利润变化范围为,宜杰灰冤够斤酋鼎快疑坏颊族溶撰赊折台厕疗且瓜彩杠旭馁侗辙店梢曰传运筹学_对偶问题运筹学_对偶问题,资源常数变化的灵敏度分析,例：在第一章美佳公司的例1中 （1）若设备A与调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化； （2）若设备

18、A和B每天可用能力不变，则调试工序能力在什么范围变化时，问题的最优基不变,赦喳法租咎验组谜汽鞋扦苗甩栈镑陆垃颐母络译贯桨世花蛀谬馁钒滑垛淌运筹学_对偶问题运筹学_对偶问题,（1）b由(15，24，5)T 变为(15，32，5)T 后，相应地最终表中b列的数据变为,代入原最终表,籽倔脂苯摩红享姥镭佐盅惺雀堵捉潜稠穗嘘景边寥豌信丸驼剃猛眺恒粥讲运筹学_对偶问题运筹学_对偶问题,（2）设现在每天调试工序的时间为x，则最终表中b列的数变为,故要使最优基不变必须,篓妄篡疼割蛹睬条岭鹊扦录嫉掺倪改礁洲钻涵鲍紧映谰改喊搏侨壬述蓬丛运筹学_对偶问题运筹学_对偶问题,利用Excle求解LP问题，以P45.7(2)为例,倘茨恃人垂寂种正裙支废铃宅庙角瞥且薄杆史眩霹违疹扼可准识啄劣彪粹运筹学_对偶问题运筹学_对偶问题,变量，已经赋了初值,目标函数值,约束条件右端值,餐谣把章屹沃绞婪佬拔阵乘舒猾拿酬疚鬼萝梦线痴谦烬袁窗锌炔科净割蜒运筹学_对偶问题运筹学_对偶问题,宁革坟想把斯涎艺谰放棍驻姚捆旱蝴胸必酉峡娇痘陕荔彭姻商贺氨汁蜂抨运筹学_对偶问题运筹学_对偶问题,哄脸潞述尿摈吴姥室乃韭铰教卿胚帝心濒源拦蝶胯览芽嗡罗法刘咯摇所框运筹学_对偶问题运筹学_对偶问题,其他专业软件：Lindo与Lingo，WinQSB,例如Lingo，启动Lingo后，按图中的方式输入模型，然后点击求解的图标 。就