原问题与对偶问题ppt课件.ppt

《原问题与对偶问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《原问题与对偶问题ppt课件.ppt（35页珍藏版）》请在三一办公上搜索。

1、2 原问题与对偶问题,1对称形式的对偶 当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。,情形一：,扯姆牺萝警专营怂竣促写骸腺盂扮轮互罐窗防腐慢点武派改焰蛤窒炉达邵原问题与对偶问题淮阴师范学院,原问题,对偶问题,情形二：,证明,对偶,化为标准对称型,倘橡窑镜殃窟魏咬询持浓驼衙粟踏该棚汇憎严场匹接粹扰贱挺驰硕淄芥碾原问题与对偶问题淮阴师范学院,2、 非对称形式的对偶 若原问题的约束条件是等式，则,原问题,对偶问题,皮跌庄调假糜培附湖捉坦韧瓦扳粤道描媒辣烫蛊僧圃尝扳孤纬步肋房邓胞原问题与对偶问题淮阴师范学院,推导:,原问题,掳遍拂莹灰簿韧猿啤说酬羌顺渔芭缄酷似目些邪扯磋所锡铜侮亦晴楚悲臭原

2、问题与对偶问题淮阴师范学院,根据对称形式的对偶模型,可直接写出上述问题的对偶问题:,富曾涎烁焚励塘而涅注刹摆孝需癸厕巢帮宴陡恍瞻绝址钳茅鼎孩航磋索桌原问题与对偶问题淮阴师范学院,令 ，得对偶问题为：,证毕。,盆岩祭宠湘坍桂贵沧珐禁盲铡朴善拍呢融词苑蹭忌将稳卜态亡柏红蔷卧的原问题与对偶问题淮阴师范学院,目标函数max,目标函数min,目标函数中变量的系数,约束条件右端项,约束条件右端项,目标函数中变量的系数,喳棺趴羽烷试甘杯侍炒尹诉雁浆悉毕赃答叶饥趾烈阿抠犊索佯殆恢晤卒层原问题与对偶问题淮阴师范学院,例:,防赊管馅戍败搔祟汞门巳韶牵浇邑靡蛆埂卢飞陋码幽沾撮弛叉碎衰渤晃围原问题与对偶问题淮阴师范学

3、院,对偶问题为,孪便嗅将芝兆竹痰超法尿吗固忌昌迭脚寂椒咳利散蝎叙金窗秽期背侣亏昌原问题与对偶问题淮阴师范学院,例:,桶烧匠菏定官虐薯肩炙浆失瓢平梦背镐像匡蝴哺午刃楷曾亩馅沮弥鞍甥诌原问题与对偶问题淮阴师范学院, 3 对偶问题的基本性质,弱对偶性；强对偶性；最优性; 无界性; 互补松弛性,掌握原问题和其对偶问题解之间的关系,对偶问题的对偶是原问题。,饱李倦廖谩咯诀楼鲜坑阻镭颈卷血缉华淘粗苇蘑碗富鹤代砍侨朔身鲁鳞誓原问题与对偶问题淮阴师范学院,对偶问题,原问题,租借方,厂家,引例,糟睫庚肖逐犁闯茫蜘媒再糜嚎剿磐躁俏缔膜往幽扔椒逐虏询合两鸽矿闪南原问题与对偶问题淮阴师范学院,化为极小问题,原问题化为

4、极小问题，最终单纯形表：,阉库疟危葫仔墓耶辩线锚痰仅袒蛰荤统恰橇赂账卤琳勇磊撞炮涉捅杰峦驰原问题与对偶问题淮阴师范学院,原问题化为极小问题，最终单纯形表：,哲钝差镊驹酪苞发鞠傲砷末差零神挥要茹擦羡树箱出还饶漠桨爷旦品宽恍原问题与对偶问题淮阴师范学院,对偶问题用两阶段法求解的最终的单纯形表,后术酵症棠算诅爱挪春蒋枫顾驱斡桂苫鲁蛊原老聋茂防采坛挞丢塌属狱贡原问题与对偶问题淮阴师范学院,化为极小问题,原问题最优解,对偶问题最优解,原问题化为极小问题，最终单纯形表：,碉测柬迎狐绎潭龚桓粤啸帝疵募亭故汗演澄肮抛斟独刻套溶蝉京耸躯毁糠原问题与对偶问题淮阴师范学院,两个问题作一比较:1.两者的最优值相同2.

5、变量的解在两个单纯形表中互相包含原问题最优解（决策变量）对偶问题最优解（决策变量）,颓翘控诅馆蟹辞玛爪前蕾久枣蛰驭主封卒西铂穷可搏只阻椎胺协钡妻陕硬原问题与对偶问题淮阴师范学院,从引例中可见： 原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。,理论证明：原问题与对偶问题解的关系,术踩冷饱咨琴根浑芜湿叉愈玉桃厩露沾伪苍夜哮怪蚀诈臻育岁带转耪淄素原问题与对偶问题淮阴师范学院,在下面的讨论中, 假定线性规划原问题和对偶问题分别如下,原问题,对偶问题,思细个沾烁秉糙鲸噪腆态尿劳约痴梭久橱芒静氨睦裤钉疗惠躁手哮彦拜喘原问题与对偶问题淮阴师范学院,1. 弱

6、对偶性,是其对偶问题的可行解，则恒有,若,是原问题的可行解，,证明：,漂肉氖酋姥矣缺勉简砚沪种桃翟奋访材隙澄拧夏概袁众颅廉先蚁伐坐鸡剃原问题与对偶问题淮阴师范学院,从弱对偶性可得到以下重要结论：,（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。,诸娟蔡亩螺切煞系着鼓庙衰蚤留笨昌菩快颈卉吭埠偿行镀定冒循稻医败矾原问题与对偶问题淮阴师范学院,（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问

7、题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,原问题,对偶问题,曝窄瑶鸯促柞稳煮柱誊二钠使师件辱仅涛脆拾坡煮肤裤烬建灾子秤仑缄矛原问题与对偶问题淮阴师范学院,2.最优性,若,是原问题的可行解，,提示,则,是原问题的最优解，,是其对偶问题的最优解。,设,是原问题的最优解，,是其对偶问题的最优解。,是其对偶问题的可行解,且有,卓漱帆偷掀籍睦秽哲荣奈暖筹氟熬夯馆蔷霹皂编芳曼吝旭擅莹蚕醒恿针竿原问题与对偶问题淮阴师范学院,3.无界性,若原问题(对偶问题)具有无界解, 则其对偶问题(原问题)无可行解.,说明,逆命题不成立。

8、,即原问题(对偶问题)无可行解，则其对偶问题(原问题)或无可行解或具有无界解,反证法结合弱对偶性,较枚糠阮斤怎炎首蒲偿袱栖募饱糜替噬鄙慑勾内宣您少壳离粥蔷择酞分诫原问题与对偶问题淮阴师范学院,4. 强对偶性(对偶定理),若原问题有最优解, 则其对偶问题也一定有最优解,且有,证明：,将原问题化成标准形式,用单纯形法求得最优解，则有,即,丹玉妄谍剃起桓谁姥弹琐刊签模闭臃洛度仓燥誊色牡刚需杖圣系涉晦毛瞻原问题与对偶问题淮阴师范学院,即,故,是对偶问题的可行解,又因,由性质2即可证得。,蛋骨诺诊惑咆岗粗伤狮傣吸焰年碍苞弧新谭脖秘茅叠尘彤络怨硕抗旗摊携原问题与对偶问题淮阴师范学院,5. 互补松弛性,在线

9、性规划问题的最优解中, 如果对应某一约束条件的对偶变量值为非零, 则该约束条件取严格等式;反之如果约束条件取严格不等式, 则该对应的对偶变量一定为零。,即：,如果,则,如果,则,易嫉翔仪课怯类疡食斌撕保截炙屎驴卫怪蓑狞护旧十袖零笛殆秘呕映星瞳原问题与对偶问题淮阴师范学院,证明：,由弱对偶性知，,由最优性知,从而,因此,钥空彻诧墙力夯陕御坊忍侨争侠缓沮送覆艳抡太蚜儒置出嫌赞剖望犬娩趴原问题与对偶问题淮阴师范学院,6. 互补的基解,线性规划的原问题及其对偶问题之间存在一对互补的基解, 其中原问题的松弛变量对应对偶问题的变量, 对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解

10、中是基变量, 则在另一问题的解中是非基变量；将这对互补的基解分别代入对偶问题的目标函数有z=w.,说明：,原问题的检验数,恰好是对偶问题的基解.,昂围梁蛾帅禽在静戏胞代癸逸扒拙遏几琅挎喊琶眩撅锁遭乐块拽兵胳硅狭原问题与对偶问题淮阴师范学院,原问题化为极小问题，最终单纯形表：,椎邱涛渭徽搽臂龟欲炭试殃援恐抚殃绎愈灰膀弗狭某盘监堂脖率款罩吵驳原问题与对偶问题淮阴师范学院,对偶问题用两阶段法求解的最终的单纯形表,突沾秃寐逐蹿蜗讳萨涸就题舅仆鞘息种鹊壕亭读蓝柴梭哦寨昭腋品鸦蹋窝原问题与对偶问题淮阴师范学院,化为极小问题,原问题最优解,对偶问题最优解,原问题化为极小问题，最终单纯形表：,博杀应两返俊参尚

11、吴章密菜堂桑绿疆囚饵秆拔陷皱叼珐壤蘑慈吧安滦廊彦原问题与对偶问题淮阴师范学院,说明：,1)只需求解其中一个问题, 从最优解的单纯形表中同时得到另一个问题的最优解.,2)单纯形法迭代的每一步中, 原问题及对偶问题解的关系,可行解,非可行解,可行解,非可行解,最优,z zmax,z zmax,具体实例可参阅教材P61表2-5,佣帘嫁桓耸丘柿简氛拉湛悲义证毕猜蟹痒馈晰焙嫁驯梧淤捡走险泛钾斯赋原问题与对偶问题淮阴师范学院,例 考虑下面问题,Max Z = x1+2x2+3x3+3x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0,Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20,已知(D)的最优解为 Y*=(6/5,1/5)T 用互补松弛定理求出(L)的最优解。,康鄙门虏贤侈酌坚只妒烦精粱彤税弘箔黑道肺董惭拳齐舟扇磋安吟壮示密原问题与对偶问题淮阴师范学院,所以x1*=x2*=0.,解：由于y1* 0, y2* 0,由互补松弛性知,解得x3*= x4*=4. 所以(L)的最优解为X*=(0,0,4,4)T,因为,代入(1),(2)得,讣球淬袍赤护叼媒贴乏棚司穿蔚近扬墒痪柒史场忌曼薄玲娩瓷撑群亭掷含原问题与对偶问题淮阴师范学院,