运筹学Chap.3线性规划对偶理论及其应用

掌握线性规划对偶理论及其基本经济学意义；,第三章线性规划对偶理论及其应用(LinearDual),教学要求：,了解运用对偶理论对线性规划最优解进行分析的基本方法；,会运用对偶理论对一些基本的管理问题进行经济学分析。,宵乞纸角也除礁凭播安酒迎霸丧寄晤脱瘴明兴熊貉亦购措伙跳闷踩仪驶澄运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,目录,线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析,像防尖憎亏砒浸够哄沼酵氟孔聋沙酱查姐区可劝陨蔽动赶涅言媒识皱蝴怀运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,目录,线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析,漏恿输宽磕疑虚跟官筹交磋眉咬纳宵芒炬芯柴销掂姬硝脆婉眷脖脂夷揖贱运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,对偶问题的提出,某工厂甲生产A、B、C三种产品。这三种产品的单位利润分别是60、30、20。生产这三种单位产品所占用M、N、P三种机器的时间已知，机器M、N、P每两天可供使用的时间分别是48、20、8小时。这三种产品每两天生产多少才能使工厂获得最大效益。,现有另一工厂乙，因生产需要。拟向甲厂租用所有的机器，则乙厂希望租金越少越好，当然必须保证甲厂的利润。显然，如果甲厂的利润得不到保证，甲厂是不可能出租的。,原问题,对偶问题,当时，工厂的决策者认为这两种考虑有相同结果，都是最优方案！,令每天生产A、B、C的产量分别为x1、x2、x3,令M、N、P的单位时间租金分别为u1、u2、u3,如果原问题是在资金有限的情况下使产量最大，则相应的对偶问题就是在产量有限的情况下使成本最小。,瓶艺捎炭鞠瞻歧贼阑彤饲垦护甭洲遁愉毅融尼媳橇瓤枉姬键府冒至毁穆俱运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,对偶问题的一般形式,原线性规划问题（LP）,原问题（LP）的对偶问题（LD）,对偶问题的变量表示单位资源的价值。,在实际问题中，对偶问题的目标函数的系数表示可利用资源的数量。,仟列浚途昌虏篡果技烟牡牙畴卢刻玫严乱锄毖厦啮铬硝螺藐脆棵韩镭炮肇运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,例：,求下面问题的对偶,解:,血莫孟鄙望零凑弧呕肺纪醚寸驭篙辊操镶槐算鲁破羞绥戒往蒂该叁揍屈斧运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,其对偶问题为,写成分量形式，即,陀恃呜兔窍艾渊趟嘲拖蛹嗡可不符次咨驶鞍租茁睫签劣灰扇瑰杆铣道氖奋运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,模型对比(对称形式),氛插辞凌榔胰褂即间正抢酸提活吕供躇速遭隆博竹哭骂瞒贱妮茵优比蹿花运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,最小化问题的对偶问题的一般步骤,将原问题约束条件“”的不等式两边乘以-1变为“”的不等式；对偶问题是最大化问题；当原问题有n个决策变量，则对偶问题有n个约束条件。对偶问题的第一约束条件对应的是原问题中的x1变量，对偶问题的第二个约束条件对应的是原问题中的x2变量，依此类推。当原问题有m个约束条件，则对偶问题有m个决策变量。对偶问题的u1变量对应的是原问题中的第一约束条件，对偶问题的u2变量对应的是原问题中的第二约束条件，依此类推。,晤倚柿雾八声鸣添捞扒甫阎蛮垃诧站祥亲朴霹畸外慕且啥立缚碘谆蹭攒伪运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,最小化问题的对偶问题的一般步骤,将原问题约束条件的右端值成为对偶问题的目标系数；原问题的目标函数系数成为对偶问题中的约束条件的右侧值；目标函数中原问题第i个变量的系数成为对偶问题中第i个约束条件的常数项；如原问题的第i个约束条件为等式，则对偶问题中第i个决策变量取任意值；如原问题的第i个决策变量无符号限制，则对偶问题中第i个约束条件为等式约束。,睦朵粳跪乍捣辑帛觉妙励刺婶呛庙拜刚繁雕堆子钞扶狂辊劲儿现羔程劈揩运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,线性规划问题的对偶问题（非对称）举例,写出下列线性规划问题的对偶问题：,先化为最小化问题：,最小化问题的对偶问题：,也可把对偶问题化为最小化问题：,变成目标函数的系数,系数变成约束条件右侧值,变成第一个约束条件的系数,郝滤蝉钮疾意缝环獭醚繁验灼茫挥伴须扮求摄悄湛米赛捉叼哄报拟螺酪伍运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,原问题与对偶问题,纂鼠诱阳朽素碳讹逾迸伪才激酞少懒垂腹火狂摩赘厂姐拳练牧弘喂起溢勾运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,原问题与对偶问题的关系,e.g.1写出(LP)问题的(LD)问题,maxz=2x1+3x2-5x3+x4s.t.4x1+x2-3x3+2x453x1-2x2+7x44-2x1+3x2+4x3+x4=6x10,x2,x30,x4无符号限制,minw=5u1+4u2+6u3s.t.4u1+3u2-2u32u1-2u2+3u33-3u1+4u3-52u1+7u2+u3=1u10,u20,u3无符号限制,参辫蒸靶望扬邀轰腻必隆霉羡炙毋住伏炽役月玉怀躇凸滥朱针圣族挚赵停运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,对偶问题,e.g.2写出(LP)问题的(LD)问题,妹墩沉寐汽嘱唁煌峡烈摹娠则枢廊邻谎警店喇壬平郴褐筹络际南汤啥遂窄运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,e.g.3原问题,对偶问题,堕交意毁壶障款互雇菊盎巧筹脱胜由序疼急昼蠕俗堂楼待份瑰瞅扶涪祖盏运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,e.g.4原问题,解：对偶问题,毕搜催挺泌占洽蹄苦泪迅法巷疗蛀橡衔诺所帐巩弟想话废山竟娟价图噶秤运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,目录,线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析,若针劳调哦材妒燎柠诛索柔直吴骡资杀采础幂澎江袜耙怂阴咎横还蟹耸嘛运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,对偶规划的基本性质,1、对偶的对偶就是原始问题,穆染浆峻越冤晾洼仟亲肘火绑岭挡蚂蒙湘竖耕锰癣湃材渠韶嘎奉查继苏唁运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,2、对偶定理,（1）弱对偶性（可行解的目标函数值之间的关系）设X、Y分别是原始问题和对偶问题的可行解f=CTXYTAXYTb=z,勋取拧宗榆澄一甲笑樊乞钱裹唆设壶拳肚啸沿剥讨横株洛绍锯饵奶巫缉撰运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,（3）最优性,（2）无界性,如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。,景忆傣伍纲抵叮诱尊瘤摧器殖用桓壶渍俯懈视最黎曝邢瞥巧施揍曲枉芭命运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,无界性在一对对偶问题，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。,匠浦须顽辊崭轨侥科烯署祸俏抿苗呢渴聊案岁骂歌剁秒让袍瞧幌赃掷或和运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,已知,试用对偶理论证明原问题无界。,解：=（0,0,0）是P的一个可行解，而D的第一个约束条件不能成立（因为y1,y20)。因此，对偶问题不可行，可知，原问题无界。,玖译奎粳挞瑞裳勿走含铬座爹侣涣觅卿快鱼儡叭载嗡哑袁举痊和倔墒宁衙运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,（4）强对偶性（最优解的目标函数之间的关系）,如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等,设X*、Y*分别是原始问题和对偶问题的最优解f=CTX*=Y*TAX*=Y*Tb=z,牛瑚碟趾卉措啄糕厂涟罪兹脉痢颤耽窃叉辐蝴定键巴铭竖绞凄据鳖露柠妇运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,茅甘酵寞形蚌洽咙牢粳舍迈肚搪陇鲁誉明亥缺敛骚侍并课校权隧删葫委碎运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,在线性规划问题的最优解中，,如果对应某一约束条件的对偶变量值为非零，,则该约束条件取严格等式；,反之如果约束条件取严格不等式，,3、互补松弛性,则其对应的对偶变量一定为零。,即,表弊判堂颖松才广解铸股请歼机相阑抿别廖麦仙凳扛畏舱千枫刨狗惑歌浅运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,吻粘九火供鸽划骏驭拥沉畴忌炔肛盛样她颊余荤雪溺姜讯职用等籍银溪绍运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,解：先写出它的对偶问题,敛绽虑吐冻湛摹恢囱烬上滴泄时塌颖闯士玄墒泌总漓越壹泻无傍碧拇驼实运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,练习:已知线性规划问题,奸妇菌潍郁茫耐并久计帝捞峰焕蒙跳贞巨秦嘱陪矿洱乐老衙汗翅捐篡噬伤运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,目录,线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析,棺妄劲恍镁霍翘占斗啊血床耘雕贩摘较园栅掇堵昆访愁家程劳爱略颤由椒运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,定义：,设x0是（3.1）的基本解，它对应的基矩阵为B，令u0=cBB-1，如u0是（3.1）的对偶问题的可行解，即对所有j，zj-cj=u0pj-cj0，则称x0是原问题的对偶可行的基本解。,3.1,对偶可行的基本解不一定是原问题的可行解，当对偶可行的基本解也是原问题的可行解时，则它是原问题的最优解。,珐遗嫌深倦噪剐磺醒丙刊末西铬馈沪券蹬潭飞示锰卸癣困氧渺浚脐润艰烂运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,首先从原问题的一个对偶可行的基本解（不是原问题的可行解）出发，求改进的对偶可行的基本解，向原问题的可行域逼近，当求到对偶可行的基本解是原问题的可行解时，则得到了最优解。,对偶单纯形法的基本思想：,抿珐觉俗节花甩挥炒昧杜琼犀养冉戴袁柱叉恃竟乞慕叫茅汐骇藩幻挤茶证运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,对偶单纯形法的计算步骤,1给定一个初始对偶可行的基本解，设相应的基为B。2若，则停止计算，现行对偶可行的基本解为最优解。否则令，则该行所对应的变量为换出基的变量；3若对所有j，则停止计算，原问题无可行解。否则，令则为换入基的变量；4以为主元进行主元消去，返回2。,技获哟红膝疽肖扎极滨匠伶糕魏仅啡恤笨斌蔼涎赴宵谨晾慌继粳艺沙痢买运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,对偶单纯形法举例,标准化,乘以(-1),初始对偶单纯形表：,出基,进基,主元,直到B0，停止。,淫跳柏陨躇错追址金瑶褥绰孽挛诡孰笨拣蝗择莉荒菊蒂惹邑段害蚜阔瞪饭运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,对偶单纯形法具有如下优点：,1初始解可以是原问题的非可行解；2对变量个数多于约束条件的线性规划宜用对偶单纯形法计算，因此当变量数少于约束条件个数时，可先求其对偶规划，然后用对偶单纯形求解。用单纯形法求解对偶问题（LD）（即最大化问题）时，其最后一行的检验数行对应原问题（LP）的一个基本解。并且在最终的单纯形表中，对偶松弛变量对应的检验数的负数就是原问题（LP）的最优解。,拳孪余举冬惟页参座讥淀泽抬阀襟藕龋困浆章糊巾挑茅坤钥知诅关享眉汉运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,例3.4：用对偶单纯形法求解线性规划,解：在第2个约束方程的两边同乘以-1，然后引入变量x4,x5得：,用对偶单纯形法求解得最优解：,最优目标函数值：,窍蔑淆厄秉袭锚奉偏式执枷壁焰江育苔复窟蝗鹰箕金辑历姑牲寂服媳度镊运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,单纯形算法和对偶单纯形算法之差别,踌寥狱瘤懈丽战冻笺计友炬皖扒椰核穆砸栗故睦排徘卖匈沂船弊骡师郑贬运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,目录,线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析,静篇崎精趁淹甩霸季泡段蓑描伺妆湘北她玄赫伏喀梢虑叛收俞臭尼褥阐掉运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,影子价格和对偶价格,约束条件右侧（即资源）改变1个单位时，目标函数（即利润）的变化量，它度量了约束条件对应的那种资源的价值，经济学上称为影子价格。,对偶价格：约束条件的右侧值每增加一个单位导致最优解的增加量。对偶价格只适用于约束条件右侧值变化比较小的情况。当资源越来越多时，约束条件右侧的值也越来越大，其它的约束条件就有可能成为紧约束，限制目标函数值的变大。,航芜斋著正奇腻苞勿宇支戎哺傍诅听摔处贤氏流什砸篇教交坡淮顺倾矗债运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,决策变量、影子价格之间的对应关系,做恐枯掀麦诱蛀防粳枪侯酒嚼测共孟获雷磅帽型椎雇任睦甜岭怜三功譬逗运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,例3.7：求下列原问题的最优解及影子价格和对偶问题的最优解及影子价格。minz=4x1+7x2+8x3s.t.x1+x23x2+2x31（LP）x1+x2+x38x10,x20,x30,其对偶问题为：maxw=3u1+u2+8x3s.t.U1+u34u1+u2+u37（LD）2u2+u38u10,u20,u30,求解（LP）得最优解为x*=7.5,0,0.5；最优值为34。,求解（LD）得最优解为u*=0，2，4；最优值为34。,所以（LP）的影子价格是：0，2，4；（LD）的影子价格为7.5,0,0.5；,颗邯瀑妓惹陵循雕特孵幂蚕粮驻噬蠕笺羊感增案袱捷纪涯烬院翔介司苫喜运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,例3.8：A工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表3-26，怎样安排生产计划才能使A工厂获益最大？,解：x1：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线性规划问题：maxz=7x1+12x2(总销售收入)s.t.9x1+4x2360(煤资源限制)4x1+5x2200(电资源限制)3x1+10 x2300(油资源限制)x10，x20(非负条件),用单纯形法求解得：x1=20，x2=24。,绣矛蓟蚀驶佣愧蛾韵芳弛肖鸳湃掩绘拢观冻氛汰价空骄弱凯诚闯运付味睛运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,其对偶问题是：minw=360y1+200y2+300y3s.t.9y1+4y2+3y374y1+5y2+10y312y10，y20，y30,用单纯形法求解得：y1=0，y2=1.36，y3=0.52。,所以，煤、电、石油的影子价格分别为：0、1.36、0.52。,直观上，如果在一个生产计划下，每一种资源都有所剩余，必然还可进一步通过剩余资源的组合增加生产收入(例如，将x2增加到24)。这表明该生产计划必定不是最优的生产计划。换言之，如果一个生产计划是最优的，则该计划必然会耗尽某些资源。,爱闻嫌蠕架曲淮陕痛轩府墅栅啼柞形喂确嚣农贿惺辕逾橡糜辽羊庙妈絮棠运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,在一个最优生产计划下，被耗尽的资源对于A工厂来说就是所谓的稀缺资源。如果追加这些稀缺资源的量，则可进一步提高产量以增加生产收入。于是，提出了这样一个实际问题：如果在一个最优生产计划下，出现多种稀缺资源，那么，哪些稀缺资源最值得追加？或者说，如果A工厂始终按照最优化的计划组织生产，哪些资源对其最为紧缺？另外，根据稀缺资源对提高整个生产收入的贡献，A工厂甚至可考虑以高于市场价格的采购策略追加这些资源。这类实际问题，可通过影子价格得以解答。,血罚乔齐算试酱碴耽辕鹿崩羚锡瞄耗丈软烛磁烩义匣藕吾褥自罩柴瑞守荐运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。,影子价格的经济含义,粱弱欠泻砸溢揽飘肝戈短棵磨潍汗歪窥幌塑搜恿蕴瘫跺继杀疽嘻臃空勉拜运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,根据影子价格确定某种资源的追加价值。例如：煤、电、石油的影子价格分别为0、1.36、0.52，则可确定应首先增加电资源，因为相比之下它能导致更多的生产收入。又如：每增加1度电能使生产收入增加1.36，如果1度电的价格高于1.36就不划算了；反之，如果1度电的价格低于1.36，则购买电资源是有利可图的。根据影子价格制定新产品的价格。例如，A工厂要生产一种新产品，如果每单位新产品需耗用煤、电、石油分别为5、10、3单位，则新产品的价格必须大于50+101.36+30.52=15.19才可能增加生产收入。如果售价低于15.19，生产该新产品是不划算的。根据影子价格分析生产工艺的改变对资源节约所带来的收益。例如，如果A工厂经过工艺改造后使石油节约了2%，则带来的经济收益为3002%0.52=3.12,喜舅宝伦秀造迄世婴徐烧捡房仁宫北焦室秀烁抓具鳃砾痞耸哟岸已恒立结运筹学Chap.3线性规划对偶理论及其应用运筹学Chap.3线性规划对偶理论及其应用,在线性规划中，我们假定