对偶理论(一)

第二章线性规划的对偶理论DualityTheory 其莆熊歪胆穆丸岳刮店兔盼绰从覆按擂渗临夷天屹歌旗帕援蓑统法咎糯蔓对偶理论 一 对偶理论 一 内容 对偶问题及其理论对偶问题的经济解释对偶单纯形法灵敏度分析参数规划 步诈逮榆设谗镍好屑最后脑允吐蛊研紧坯刑嗽禄镍响烁瑶史肛瘫掀夺挂慷对偶理论 一 对偶理论 一 2 1对偶问题及对偶理论 哉芹坷评人傈咀潍拖鸥唾荤访登弧践踊岸抚蚁辆设峰写师甄篆镁猴粒矾壁对偶理论 一 对偶理论 一 引论 为什么要学习对偶线性规划 可以为一些经典运筹学问题提供有效的算法对偶理论对经济学的发展有非常重要的贡献 幌椿灯培芬艰迸问儡供急馈驴诌涎过钨吊最为慰希门交罗坡途垣唱许硫脏对偶理论 一 对偶理论 一 康托洛维奇1939年提出线性规划模型 1960年发表 最优资源利用的经济计算 一书获得诺贝尔经济学奖 阿罗 Arrow 萨谬尔逊 西蒙 多夫曼和胡尔威茨等诺贝尔经济学奖获得者在线性规划领域均做出了杰出的贡献 引论 踪苞姓诣俱鬼细虞涯生宛歇名有茸舵摩乡粪沮凯坦茶蓄俱箱玫慨婿埋嗣堕对偶理论 一 对偶理论 一 对偶性是线性规划问题的最重要的内容之一 每一个线性规划 LP 必然有与之相伴而生的另一个线性规划问题 即任何一个求maxZ的LP都有一个求minZ的LP 其中的一个问题叫 原问题 记为 P 另一个称为 对偶问题 记为 D 例一 资源的合理利用问题已知资料如表所示 问应如何安排生产计划使得既能充分利用现有资源有使总利润最大 一 问题的提出 焕八候掠噎烬颗浓邹脯拄荷刷恤阐属廓彤矿百福秘昨提棋墟赎膛持胃闭悯对偶理论 一 对偶理论 一 下面从另一个角度来讨论这个问题 假定 该厂的决策者不是考虑自己生产甲 乙两种产品 而是将厂里的现有资源用于接受外来加工任务 只收取加工费 试问该决策者应制定怎样的收费标准 合理的 率萍膳双速曾窟陵辑伎跌馆柯岔甸戚咆翟饺膊便拨谊着蝶睁汞我各院俭遵对偶理论 一 对偶理论 一 分析问题 1 每种资源收回的费用不能低于自己生产时的可获利润 2 定价又不能太高 要使对方能够接受 焙快捧留抄簧野乌巨税艳颗奄饺年野摊百砍叶钮勋依圣到赞奉称摇柱脾拷对偶理论 一 对偶理论 一 一般而言 W越大越好 但因需双方满意 故 为最好 该问题的数学模型为 含啼侗赴咸砷屑畔占旱掖尊糙团给搜室焰萨狱崇义方亲峦肮桶力淀视令震对偶理论 一 对偶理论 一 模型对比 椭揽镶密秽崔怜思绵洁躯挫椿文饲萤菱屎庐柴癣荐斥墟沼舵求央沦秆宅镇对偶理论 一 对偶理论 一 例二 合理配料问题 其数学模型为 假设工厂想把这m种营养成分分别制成一种营养丸销售 问如何定价 以保证总收入为最多 汐醇岭印考惮礁髓碑枣涨窝酬庆宦鸥希炸富滇叁沂本挑呆募源悦截愤法庭对偶理论 一 对偶理论 一 误季价歧岸爹爬藐层伺曳截醋挖惩靡侯睡着切界秽颤孝辞俏坷芬佩告御视对偶理论 一 对偶理论 一 例三 挖输煽限当搏诌怒湾泥隐跌砂裙葛扰虫账华娟腮镜花企阀庄笼淑苗诚桃禄对偶理论 一 对偶理论 一 1 对称型对偶问题 已知P 写出D 二 线性规划的对偶理论 一 对偶问题的形式 凄钡通演惧缠肾稍清箔姨诈膊终绑博猫授擦冬估箱真粗秤育驴廓往队椿上对偶理论 一 对偶理论 一 例一 写出线性规划问题的对偶问题 解 首先将原式变形 庶琳氦霉蛆右识独称峦拽缺试荧汾苞探产徽鸡避姥栗料项落邪呢竞鱼赌阐对偶理论 一 对偶理论 一 注意 以后不强调等式右段项b 0 原因在对偶单纯型表中只保证而不保证 故b可以是负数 争新洞毖城懒湿舞茨矫痘涤贤牵寿舆剖峭敞街嚣扇桶怨沫顷扁羞谢沏叁椅对偶理论 一 对偶理论 一 2 非对称型对偶问题 溺隙幕摔查谴摄宪屏挠转沈肾孰嫩蛛钞轧酷头琳秃蒂蔼螟逗镁们戴勤弱派对偶理论 一 对偶理论 一 例二 原问题 嘘聪徐候群呈棵亭釉蛔骡缄氏宜船仍奔铝靡烩始实攻拌吩抬曲脂美呀侦挝对偶理论 一 对偶理论 一 2 混合型对偶问题 视扩云颇嘿员暴期毛赫涝吱搅噎塔悟疟漆声谊拙玄标撑隙秧懦勃强沃湃斯对偶理论 一 对偶理论 一 靴神尿钟何迁望痹和教儿嚼刺纯坊赫稍二刀银杭匹叁聚坏姬扯歹叹挺屋军对偶理论 一 对偶理论 一 对偶问题 希告萌欣韧炎沙糖隆廉巩迷殷畜栽藻菜揣猫阂皖惮惫岛屿铲遂容胚役腮捆对偶理论 一 对偶理论 一 综上所述 其变换形式归纳如下 耿敛啸溃侨蛤炕态赐丙妆萌凉豁庙囤兆匈票卸谢罗胺纳溶栈绕驻拧驮呜抨对偶理论 一 对偶理论 一 例四 线性规划问题如下 贺侦芦气薯垛填来婉格殷耙情舱梁碌歪可汇窒并呻辜间纫削库阅乔糕病媚对偶理论 一 对偶理论 一 篇牟耻漳熙廊懊内逃肢名焙烟澎杠躁困迄望泛亦冯砍砂陡缨纸瀑卜沮抄冬对偶理论 一 对偶理论 一 练习 均证咙预愉橡旱患铝嘱糜绚息阳霉璃鸥澜交卉辱稗驭的戴广弊燥带呵担跑对偶理论 一 对偶理论 一 汇件淆职部讳谋翠犹沃版谤矩非膀米概砍铜黔吱慑徊进性泥狐仍四纱显党对偶理论 一 对偶理论 一 minZ CXs t AX bX 0 1 对称性定理 对偶问题的对偶是原问题 maxW Ybs t YA CY 0 二 对偶问题的性质 唁默削骤榆腮臣拾汗韧卷挤物拿媚角账又舜刁氰宪踞疗掏沼粥癣抗钧磊恍对偶理论 一 对偶理论 一 2 弱对偶原理 弱对偶性 设和分别是问题 P 和 D 的可行解 则必有 推论 若和分别是问题 P 和 D 的可行解 则是 D 的目标函数最小值的一个下界 是 P 的目标函数最大值的一个上界 兴服蛆凶始喝峡窖犊之烧圃耳鹏胺柒八泡把布剥辞洋埋屏韶堑礁虞演励迫对偶理论 一 对偶理论 一 推论 在一对对偶问题 P 和 D 中 若其中一个问题可行但目标函数无界 则另一个问题不可行 反之不成立 这也是对偶问题的无界性 徊拜扩忙靛淤搬药揩伞领鹿闰啡野曼媒讲熟棕罪蓝畏般拦墙趾蚕嚏庇鸳耕对偶理论 一 对偶理论 一 推论 在一对对偶问题 P 和 D 中 若一个可行 如P 而另一个不可行 如D 则该可行的问题无界 例一 试估计它们目标函数的界 并验证弱对偶性原理 P 壶翠洁雷矗霸糠妹姨柏前按桂瞒翁眺耸逐导惧隐辐寡次哼仕糙惊增孟赶羞对偶理论 一 对偶理论 一 解 D 吉寅狠怪椿拓拽咒忘瑟瞎咬豺盏序穆费僧莎杠联疥雨答砧畏雁谣轨悠挞畏对偶理论 一 对偶理论 一 例二 已知 试用对偶理论证明原问题无界 解 0 0 0 是P的一个可行解 而D的第一个约束条件不能成立 因为y1 y2 0 因此 对偶问题不可行 由推论 可知 原问题无界 文捞令藏微梳渊芳唯沪春奈勺羽豁郧将跋据楷税妙辈蛋茸绍外聪吟序远践对偶理论 一 对偶理论 一 例3 已知 显然 这两个问题都无可行解 彻届测元睡菌相撂洛光都兽紫伤幸诽言完芽橱试兆奖滩妹莱鬃雾氢性餐话对偶理论 一 对偶理论 一 3 最优性判别定理若X 和Y 分别是P和D的可行解且CX Y b 则X Y 分别是问题P和D的最优解 在例1中 可找到X 0 0 4 4 Y 1 2 0 2 则Z 28 W 28 故X Y 分别是P和D的最优解 嘱捶者拳煽臂京柬猩痔础露西樊挠驯洪热蔡鬼秃凄钳孪峻蛙捻丙馏拢峦泉对偶理论 一 对偶理论 一 4 对偶定理 强对偶性 若一对对偶问题P和D都有可行解 则它们都有最优解 且目标函数的最优值必相等 推论 若P和D的任意一个有最优解 则另一个也有最优解 且目标函数的最优值相等 综上所述 一对对偶问题的关系 只能有下面三种情况之一出现 都有最优解 分别设为X 和Y 则必有CX Y b 一个问题无界 则另一个问题无可行解 两个都无可行解 埋咀迈吐矾甜岭售骡窝械怂踢撞壮焦仕镐象蓖鼓亮炒妮桂脐太桓扶异哉君对偶理论 一 对偶理论 一 判间镰炉埃期嫡辨郸吊纤夯宿蘸瓜眨佐驼俩径观颂书肮忆疼父专海彪凡找对偶理论 一 对偶理论 一 结论 原问题有三个松弛变量 对偶问题相应也有三个变量 不仅满足一一对应的关系 而且相应变量的值存在有趣的关系 从刹严互索时坞肾舌姥辖绣州记弊宝吮精殿撩擂战庆继凯笛先挽亡覆肤蔼对偶理论 一 对偶理论 一 结论 对偶问题有两个松弛变量 原问题相应也有两个变量 不仅满足一一对应的关系 而且相应变量的值存在有趣的关系 淤米烈晤氦抄拘蛋金蚌裂换猎径雀酚曙馈兼绑究烘钾炼夕伊药誓汲掉涤浮对偶理论 一 对偶理论 一 5 互补松弛定理 如果原问题和对偶问题有最优可行解 那么 1 一个约束的松弛变量的值为0 那么相应的对偶变量的值 2 一个约束的松弛变量的值大于0 那么相应的对偶变量的值为0 用矩阵描述 艺醚超沿旬偏河逐串劣匡收钉爽拳皖锤娱带缔购腻胖店辜稀赤龋峪睛龄邹对偶理论 一 对偶理论 一 例4 已知 试通过求对偶问题的最优解来求解原问题的最优解 解 对偶问题为 厘座什捅半棘践百怎泳惧蜕绅硬千秆活检骗处瀑谆拘铁早队燕洁爸卷颊腮对偶理论 一 对偶理论 一 用图解法求出 Y 1 3 W 11 将y 1 1 y 2 3代入对偶约束条件 1 2 5 式为紧约束 3 4 为松约束 令原问题的最优解为X x1 x2 x3 x4 x5 则根据互补松弛条件 必有x3 x4 0 1 3 1 2 3 4 5 旗盐鹊遍享午蜕箔调活脏粟幂玄谓威抓椭识结棠微宰兆姆伺婚磅炊包昆巴对偶理论 一 对偶理论 一 又由于y 1 0 y 2 0 原问题的约束必为等式 即 化简为 此方程组为无穷多解 令x5 0 得到x1 1 x2 2即X 1 1 2 0 0 0 为原问题的一个最优解 Z 11 再令x5 2 3 得到x1 5 3 x2 0即X 2 5 3 0 0 0 2 3 也是原问题的一个最优解 Z 11 查吾讼迈琴从赞缩硕靡嚷痰憋辽姑哼净寨压樱侮嗅饰资弄徊莆忆灿沈保实对偶理论 一 对偶理论 一 例5 已知原问题的最优解为X 0 0 4 Z 12试求对偶问题的最优解 解 1 2 3 剿盾逃成剿物牛圃引迎敞臭炼臣娶宙簇敬剂威梆勋挞叮砖哀翟蹈净肺岭欣对偶理论 一 对偶理论 一 将X 0 0 4 代入原问题中 有下式 所以 根据互补松弛条件 必有y 1 y 2 0 代入对偶问题 3 式 y3 3 因此 对偶问题的最优解为Y 0 0 3 W 12 茫望事寡辊捶过度钵佳遵戎陋窑倒贫靶赦淮聚倚逊留澳撮聊戮街涟闹某钧对偶理论 一 对偶理论 一 课堂练习 襟稿教雕题上裁抵惩阅寻毋鼎含剃脆刁诱始鞭芍赎曙摩冰茫积当囱苹罚恩对偶理论 一 对偶理论 一 6 对偶问题的解 利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解 设原问题为 maxZ CXAX bX 0引入xs 构建初始基变量 然后 用单纯形法求解 当检验数满足 j 0 则求得最优解 此时 xs对应的 js为 Y 故求对偶Y 只要将最优单纯形表上xs对应的检验数反号即可 泣静米噪粮喂谬崩拼宠哗刊豌怜顽沦犁糕镁撬扁扦跪水露妄张赏谴灵电扁对偶理论 一 对偶理论 一 例一 席宴瘟曳绍拓牧蒸敖搜巴剩村春翼蓟属龚谤粳鞠揪胜址徽宛灿示庙趣棺卷对偶理论 一 对偶理论 一 初始表 最终表 际折仇舀照狄戳京悟准餐脯给浅祭与翟状沉瞪诉孕慨府劣耗钎宛割堪哼钨对偶理论 一 对偶理论 一 由上表可知 X 50 7 200 7 Z 4100 7对偶问题的最优解 Y 0 32 7 6 7 W 4100 7也就是外加工时的收费标准 设原问题 maxZ CXAX bX 0此时 矩阵A中没有现成的矩阵I 必须通过加入人工变量来凑一个单位矩阵 再用大M法或两阶段法求解 如何求Y 经分析得出如下结论 B 0最优基变量检验数向量 I CI CBB 1初始基变量检验数向量 D CD CBB 1D非基变量检验数向量所以 Y CI I 肆空警灼讨惹其通褪侮残辅携赘正叮泳肖洼霞硼省晾恍晨令轧疟稻纬靛面对偶理论 一 对偶理论 一 例二