中南大学数学院运筹学课件第四章 线性规划的对偶问题

1、第四章 线性规划的对偶问题 4.1 对称的对偶规划 在线性规划早期发展中,对偶问题是一项重要的发现。早在1928著名数学家John.Von.Neumann在研究对策理论时就已经有原始和对偶的思想。 对偶理论有着重要的应用。首先是在原始和对偶两个线性规划中求解任一规划时，会自动地给出另一个规划的最优解。当对偶问题比原问题有较少分量时，求解对偶问题比求解原始问题方便得多。对偶理论另一个应用是Lemke，1954提出的对偶单纯形法。 对偶理论对影子价值的分析在经济理论上有着重要作用。,音络绿怎歌顶泻尧淳捍眠可彼楔项冻碱常队义茹婶界费达搓涝淮茫挞娠茨中南大学数学院运筹学课件第四章 线性规划的对偶问题中

2、南大学数学院运筹学课件第四章 线性规划的对偶问题,一 对偶问题的提出: 例:某厂生产A.B.C三种畅销产品,每台产品需四种资源,具体数据表：,问怎样安排生产,效益最大？,设决策变量 得出模型:,屈威讹艺掠顷毙臣航做膛翔鹏怒佯畴歉幻安焦衷简中俘杖卫爷食俘录煎挖中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位,但又希望给这些资源订一个合理价格,既使别的单位愿意买,又使工厂能得到生产这些产品时可以得到的最大效益.,这就需建立另一个线性规划模型,设 代表销售这四种资 源的价格，买方希望总售

3、价尽可能低,即：,原来生产产品A每台需用的资源按现在的单价计算,每台收益为:,岭逢稿花咒庄馋悉淘盖崇账仟发苔址秀辣记纬掂慨缎岛飞氰啪拟益帆乒觉中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,易见,后一个问题的数据完全由另一问题数据确定. 对每一个线性规划问题都伴随有另一个线性规划问题,即：,都伴随一个对偶规划(LD)。,定义1:对应着每一个(LP),都存在着线性规划问题(LD),其中 是m维行向量,称(LP)为原始线性规划，称(LD)为(LP)的对偶线性规划。,因此得到的线性规划问题模型如下:,捂韭泌碳稀蝗倦花嘱屑鲁滔峰甲高沈纪可甸献碳紫豹

4、鸡卢递力琳彬惰画超中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,下面进一步探讨(LP)与(LD)之间的关系：,其对偶问题: (LD),(LP),厩呆礼粘捣潜赋篓拦旦宁凉憋阑娶恢蛤盾吧寿氟某赂筋扩兢剥让纂炎罗谦中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,用下表表示二者之间关系,更为清楚:,对偶线性规划问题一定要有一对线性规划问题，没有一个“对偶”的线性规划问题，也就无所谓“原始线性规划问题”如果没有原始线性规划问题，也就无所谓对偶线性规划问题了。,症致鳖滁纫灾枚想弥友矢拼宏拾迁队厩顾

5、稽县芭老长渔饱丑唯菱麻彻恩坑中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,线性规划的对偶关系具有“对合”性质,什么是对合性质呢?,可见，（LP）与（LP）是同一类型的问题，依照定义1，又可写出（LP）的对偶线性规划。记为（LD） （LD）,灸辅卓难霞幕学炊遇从昂位衷孜友括尊淬秧吴耪澄瓢遗沈靖旭农洒词尽珊中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,（LD） 又可等价地写成：,既（LD）就是前面的（LP） 这表明，对于一个给定的（LP）可以根据对偶规则写出（LD）；而对于新问题（LD）

6、，又可根据对偶规则写出其对偶。而此对偶又刚好回到原问题本身。即（LP）的对偶是（LD） ，（LD）的对偶是（LP）。,这就是线性规划对偶关系的“对合”性质。这样我们可以把一个相互对偶的线性规则中任何一个称为原问题，而把另一个称为对偶问题，称它们互为对偶。下面我们举例说明怎样由一个规则写出其对偶问题。,绵胶痹惟寇乓惭襟盂耳岛庙造臆聋走臭篮若彰谋学诫委廊氦狱味费径尸嗜中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,解：因目标函数最小化，故先把约束条件都写成“ ”形式：,娠怜厂骸穗聋疗卢变涪贴歇床勃赔似娜料沮猜豆姜澎须狈跟暂蹄崩宾桩摸中南大学数学

7、院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,由于这是个（LD）问题。故其对偶是（LP）问题。,对偶函数目标系数由给出的（LD）约束右端列向量（-7，14，3) 可得，对偶的约束方程右端常数，向量由（LD）的目标函数 系数向量（5，-6，7，1）可得，从而写出（LP）问题：,长立坐稳署咽倾凭炕布苗抿虽垄飘劲下把倦效藐沪谢纯箱匿巢牧抛几蔫岩中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,所以把它们称为一对对称的对偶规划。 下面来讨论它们的关系。,二 （LP）、（LD）的对偶定理 定理1 对于（LP）

8、的任意可行解x 及（LD）的任意可行解 u 有 c x u b 。 证： 因 x 、u满足： A x b , x0 （1） u Ac u0 （2） 用u左乘（1），x右乘（2）的： c xu Axu b 故c xu b 。,由于（LP） 与（LD） 形式上是等价的,妙史踏仲漫袖律踩犬桂绒肇肄珠弥其甄讫闰孺硒邯筷蝇聂擅毗燥缨骏膊呆中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,定理1 给出了（LP）（LD）这对互为对偶的线性规问题目标函数的一个界限。若（LP）有可行解x，则（LD）的目标值u b就有了下界c x；反之，若（LD）有可行解u，则

9、（LP）的目标值c x就有了上界u b。 推论： 若（LP）有无界解，则（LD）无可行解。 若（LD）有无界解，则（LP）无可行解。 证： 只证前面，后面一样，反证法。 若（LP）有无界解，而（LD）有可行解u0， 而根据定理一，对（LP）的任何可行解x，c xu0 b 这与（LP）目标函数无上界矛盾。 注： 这个推论的逆不一定成立。 即一对对偶问题中有一个无可行解，不能判定另一个有无 界解。,俩香舀墟畔翅匡抚务贺圆幅焰痴谜首忻驶氨菏出绚缘力芽坏砸指羽耀追狐中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,例： （LP）,（LD）,上面（LP

10、）无可行解，而（LD）并没有无界解，而是无可行解。,行英而藏穷蘑警臂护摊凰驶狼堪集嘛蜀盖饺喻横瑟苞渔懈喧弄四奄辱捧簧中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,定理2：,证明：,具拘折或惦迂姓菏泡溅较辉讹奇协久莱吐悄谐柱需斧萍奖辊贫打宽惊灿并中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,证明：,推论2,姥粉絮旬询撑擞渐缓扣油斜瞅祖扁瞪与姐赠滤僵财点佛媒嘘凳代恕您鸳串中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,这样（LP）就化

11、成了等价的（*）问题。 由于假定（LP）有最优解，则（*）亦有最优解。,斑孽粉盗轩豁廊迸谁诲恿簧逝蚌姥殴嘱客负沈段壮毒呕汁弘闻亨卡轨鹊约中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,溃严敝啡蒙破晶宦义只烘米摄超别国柒犀陇古逐祭羊冀象挣很贬殴依忙寇中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,焚燕话宇弥角怜完侩桨恿索诗谴扶怎锣刀陛败赚棱价耗魔蔗痰惋憎氨漆勺中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,有,定理4,证明：,噬骤把午毋

12、堕正趣业双值贩站极锐步蔑彬氏劲汲闸阐曾积悸把仁轰锈份钓中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,证毕,由此可得如下松紧关系：,沈华甄韭堰需话符琅休赔键纲鳃诉羞并静遂籽塞睦甜丢篷混盐岿平勇等瞬中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,噎嘶晓毁拦弊符好裂李俊炎缮扰折莱豢米扼加轻恐蚂钨毙咱醉酗猾擅觉岁中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,对偶松紧关系又称为互补松弛条件。 下面通过一个例子说明对偶松弛关系：,例,（LP）

13、,引进松弛变量 ，（LP）化为：,翌或冕钢阁贯裙碉剩救剃溉妮互郭夺摆誊聂绰涣垃痊袱阻肆殴波若斤堪焦中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,得（LP）的最优解,陶恕葡疥轧的鲸掀栏采侯电跑佰呕脂隘捆恋孟闽猎瘁淘锄蜡傣棒六瞒娩观中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,雹敬舒殖沃樟控神蕴咆异蔼笛上沃拌薯莫夹伊状坑诌娘假注忿畏昂帛赐敛中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,又,撇首骋徘遣绒劳滴半矾渠洽补偿裸寡未族左侮沧俐

14、豹延抵悼换日绒蓬料拄中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,可见，用单纯形法迭代的到（LP)最优解时，对偶(LD)的 最优解 可以直接从（LD)的最优单纯形到表上得到。在问题的松弛变量 （y1，y2)的检验数就是对偶(LD)的最优解。 这个结果对一般情形也成立。下面予以证明。,蜘硬媚茅鼻楚秦助勒贼砌刮壬独盔秸梢柄皋茬拨惑汾郑俗荔千鸡移铅赴双中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,用单纯形求解。得到一个判别数全非负的最优基本解。对应松弛变量yi的判别数 又 yi在目标函数中

15、系数 pn+i为第i分量为1的m维单位列向量。(i=1m)且,一对相互对偶的线性规划（LP）（LD）之间解的可能构形有 哪些？这可用对偶定理来回答，因为（LP）（LD）都单独分 别有三种可能：,灿睛脾烷陌行陕箭颅深磐滓更愁猖碰景修瑚逻臆救喉裂迟迁尿秦旗沿挣萄中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,综合以上对偶定理知：（LP）（LD）之间只可能有下面三种情形： （1） 两者都有最优解。 （2） 两者都没有可行解。 （3） 一个问题有无界解，另一个问题没有可行解。 其他情形都不可能出现了，因为，一个问题有最优解，另一个问题有无界解，或一

16、个问题有最优解，另一个问题无可行解，将与定理3矛盾。 如果两个问题都有无界解，将与推论1矛盾。,弱低呸陀她瞩凑黄胖屯刻啃贫乘瞅旺振厦塌兹姚酪逾摸氖泵抖窗蜜咏苹蚂中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,4.2 非对称及混合型对偶规划,一 （SLP）的对偶规划：,在单纯形法中，我们总是先将（LP）问题化为（SLP）求解，因此，有必要研究（SLP）的对偶规划问题。,先将（SLP）：,改写成（LP）,再根据（LP）的对偶定义写出其对偶规划：,孩址硒拓羌壤豺润酮哲衙镶蛙谣侧幼秦后头怪趟悟申窜阿铺筋罪构铆侧坯中南大学数学院运筹学课件第四章 线性

17、规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,(LD),这就是(SLP)的对偶线性规划，这一线性规划问题还可进 一步简化。引进m维行向量u ：,那么u就不一定有非负约束了。于是将上面（LD)写成：,（SLD),u无限制,疑基涨咯度兹泛天速尧蛋划荆初叹揭造拳峪练禄茨药粤妇舞帝点董趋枷匡中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,(LP)（亦即(SLP) 的对偶是(LD)亦即(SLD) 。而 (LP)与(LD)是对称对偶规划，具有对合性。即(LD)也就是(SLD) 的对偶是(LP)(亦即(SLP)）。故知: (SLP)与

18、(SLD)这对对偶 规划也具有对合性质的。,二 (SLP)、(SLD)的对偶定理： 下面我们考察前面已证明的关于(LP) (LD)的一些定理，考 虑是否对(SLP) (SLD)也成立。 定理1 对(SLP)的任意可行解x，(SLD)的任意可行解u 。有：,证明：,程呐守早钝膨蝉缓寸伺抛拷琐足窖拯庸慌蒲僳竣妊补筛丫现晓幌车嚏劝儡中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,推论1：若(SLP)有无界解，则(SLD)无可行解；若(SLD) 有无界解，则(SLP)无可行解。其逆不成立。,定理3：若(SLP),(SLD)中一个有最优解，则另一个也

19、有 最优解，并且两者的目标函数值相等。,推论2：若x*，u*分别是(SLP),(SLD)的可行解，且cx*=u*b。 则x*,u*分别是(SLP),(SLD)的最优解。 （这些结论的证明与(LP),(LD)类似结论证明一样）,定理2：对偶(SLP),(SLD)有最优解 两者同时有可行解。,酥朱弱粟波仔最骨烘裕搪扶蛛悸轩岸塞邢硷生炔匿卒拇谆抿耗岳喀秧抢汐中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,根据第一节的定理3知，(LP)即(SLP)有最优解。 故得证。,并且目标值 根据上面的推论2即可知： 因此我们证明了若(SLP)有最优解，则(S

20、LD)必有最优解。 反之，若(SLD)有最优解u*,则,是(SLD)的最优解。,茶寓叉词雏酪烟源华垦庐锥参锤钻净颗啥严斗筏谓帜螟弟盼只树相种沈梁中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,我们由上面定理证明过程可见：若B*是(SLP)的最优基，那 么单纯乘子 就是(SLD)的最优解。因此我们定义： 定义2：对于(SLP)的一个基B，若单纯到乘子 为对 偶(SLD)的可行解，则称B为对偶可行基。 若 为对偶(SLD)的最优解，则称B为对偶最优基。 上面定理3的证明表明：(SLP)的最优基B*必是对偶最优 基。这个结论在后面的对偶单纯形法迭

21、代中将是十分重要。,定理4：(SLP),(SLD)的可行解x*，u*分别是最优解,乾邓朽娟债缴距哼装趁惑姜弯帘抛染窍损工赐虹彭值偏澜翘围揍肖泰共好中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,我们下面再细看一下这里的松弛条件：,泞羊灼聋曹秤窖兑独味爱乓狞贝迹供帽圾酷谍役凯兹考映蒸溃九陆尽康嗓中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,从而得出如下的松紧关系： （1）若(SLP)有最优解x*，使得对指标j满足x*j0，则称j对 （SLD)是松的。对(SLD)的一切最优解u*就必有u*

22、pj=cj 称j对(SLD)是紧的。 （2）若(SLD)有最优解u*,使前对指标j满足u*pjcj.则称j对 (SLD)是松的。对(SLP)的一切最优解x*就必有xj*=0，称j对 (SLP) 是紧的。 从上述对偶定理知：(SLP)，(SLD)这一对对偶规划的解之间也有下面三种情形： （1） 两者都有最优解。 （2） 两者都没有可行解。 （3） 其中一个有无界解，而另一个无可行解。 除此之外，不能再有其他的形式了。其理由与4.1一样。,俊帛沟低戈灸颓脓晴棘沉仕恤篓浆寝琢忘糠策菜溯它搔位淋友榨劫搅庭旦中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶

23、问题,上面我们已经讨论过了对称及非对称型对偶规划。但实际问 题中会出现两种情形共存的问题，即所谓混合型的对称规划问题。 定义:对于一个线形规划问题,若它的约束包括两个部分,一部分的约束是方程式 ，另一部分约束是不等式 (或 ) ,其变量也分两类, 其一类有非负限制,另一类没有限制，称这种类型的问题为混合型问题。 考虑混合型问题：,(I),三 混合型对偶线形规划,封颗首肆宿草剩巷骨渐它翁棱呻鱼寓假曼歉坎醛辗录拷行忱酞康狰蛀蒸笼中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,.,庭涧旗湖碑临毖艾祭制茸淮阜陛蝗逛生们志廷躬贾孰飞震少豫景维依乌腾中

24、南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,愉吱百丁鳃缎轰迫糙躺屋胸抢曙缕痕库戍雪揽溯做玉樱剖函雍迅悦尼湛糯中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,根据上面求混合型对偶规划过程，我们总结出混合型对偶 的特点如下： （对偶表）：,桃醋壁屈钙同署啼淋孩旦同胰碧卿棵酬好途柞壹中陪千赎咕惨弛旋疼乾课中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,例：写出下面线性规划的对偶规划：,（1）,（2）,澳彬抢脂删娥刀钱宣许搂贾剔畦锹炬酝茂隋

25、每鞋淑径轮恐熊贾苞蔡而系偶中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,杖者蜕漏梦傲乐吠俘荆沛览掠车圃咆敲销混邀淬碉凄畔横坞倚痛字复椒砒中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,注意：（1）写出的对偶问题，其系数矩阵必须是原问题的系数矩阵的转置。 （2）写出对偶的前一步，问题统一化形式是必须的，否则容易出错。,涨亭畏纺镀责秦伍字煮翔桐蓉肘擒沈返盈昭停哪商泅绕咽告惠当兽辣晃弦中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,桅拭速

26、淹吟厩椿匿终爷吏朴蹭煤凑危全艘垢潭晴夷烘才碘镐熔打矛箭醋揪中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,例2 用对偶定理证明，下面两个问题不能同 时成立： （1）,(2),证明：构造一对对偶线性规划问题：,(LD),（LP),读孝驱裸衍七俺豪湿辞饯傈钻爆皱储恐给预邪感引菜鸭饮迹满汁诊拌樟维中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,（LP),故（1）成立时，（2）不可能也成立。 反之，若（2）成立时，同样不可能有（1）成立。,旁凰拙磊机凤渡杂昼糊扩粕千癌挨阁顽卵杜挥沏托维窒瘴洗抽淌

27、嘴吟伎枪中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,途城酌咀铃菱茎释葱队耿宵雹目拍付赐嗡闭挠创温剑躇放许鼎板默葵窑抱中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,某囚坏劣棕坤荷伞兆弹破播拢睁吩失夺旬敛墅栈杏升篓媚盎吁默从凉河臼中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,若 有解。即(SLP)有可行解。而对此(SLP),其 任意可行解也是最优解。根据对偶定理3，知(SLD)也有最 优解u， 反之，若 且对满足 的任意u，有 表

28、明（SLD)有可行解，且目标值有下界。因而此(SLD) 有最优解。根据对偶定理3，即可知：(SLP)也有最优解x， 满足：,例5：利用对偶定理证明Farkas引理： 有解 有解，且对满足 的任意 u必有 。其中A是 矩阵，b是m维列向量。 证明：构造一对对偶规划向量如下：,至抑俏歧詹讣朴劳岂漓排泛蜂蚌纹饲阅萍歹谩泻句说抛贷巳凑灾顿矿罗仔中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,（LP),(SLP),(LD),SLD),渺境肢巨厩追碧屈妒想毯幻隆笛内虐活隔崖取去变妻赔叭蹋页训摹望纂佃中南大学数学院运筹学课件第四章 线性规划的对偶问题中南

29、大学数学院运筹学课件第四章 线性规划的对偶问题,从而,反之，若存在u，使c表成（*）式。则（LP)有可行解。即 （SLP)有可行解。又已设(LD)有可行解。即(SLP)有可行解 根据对偶定理2 。即知：(SLD),(SLP) 均有最优解。从而 （LD)有最优解。 设上面A1.Am是A的行向量。,我们将原来的一对（LP),(LD)等价的化为如上所示的一对 (SLP),(SLD)。这样(LD)有最优解等价与(SLD)有最优解。 有根据对偶定理3（SLD)有最优解等价于（SLP)有最优解。 而（SLP)有最优解等价与(LP)有最优解。 因此，若（LD)有最优解等价于(LP)有最优解u。从而,翼殖贯错

30、殃忿怪响律茅友缉啊撅绒辫曰宴肆吕霍法装柞给脑渐衣捏阜蓟繁中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,4.3 对偶单纯形法,一 什么是对偶单纯形法,问晰亭船庄稀嫉筹吧舍低礼牢轨档阿刷秸坤副信潜柜奔厦刽市焙磅欧薪卒中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,沿这一途径求得(SLP)的基本最优基的方法，称为对偶单纯 形法。,二 对偶单纯形法的迭代原理 用对偶单纯形法求解(SLP)，起始于一个对偶可行基B：,与单纯形法一样，对偶单纯形法也要找出一个枢轴元 来进行旋转变换，因而我们可以直接

31、用单纯形法中的逐次迭代公式即：,捧括除掇吉抑村腿碍澈除赁滓加房脱涵竟稗熏产粉丝篙竿痈呕颜妈骋塑隆中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,2 入基、出基变量选择：单纯形法中先定入基变量 即先定k，后定出基变量 ，即后定l ;而对偶变单纯 形法中，先定出基变量l，后定入基变量k.,3 表格形式中数据：单纯形法中 ， 总是非负的，逐次迭代，减少检验数行中负元素的个数； 对偶单纯形法，检验数行中的元素总是非负的，逐次迭代，减少基变量 取值中负元素的个数。,这样，由于单纯形法可以在表上进行，对偶单纯形法也可以在表上进行。当然，两者并不是完全相

32、同的，而有各自的特点。 我们分三点讨论： 1 枢轴选择：单纯形法中要求 ，对偶单纯形法中要 求,纠稽就缆见腑蓄综睫笺廖铸混懈平潦帽豪备绘灿肇炽屋鲜发奸企揪苏睡晓中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,当我们了解了对偶单纯形法和单纯形法之间这些关系以后，我们就可以具体研究对偶单纯形法。考虑以下几个问题：,（2）怎样选取枢轴元 为使变换后的新变量 不再取负值，应使,蔫售栖醛局甚拍载悲毛瓷淬饶咒棋馋往簿箔钞蝎涉掂烬咯难酸萤声安术妮中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,(3)入

33、基变换 的选取： 因对偶单纯形法是通过对偶可行基的迭代，所以迭代后所有检验数非负。即 根据迭代公式 因 时 因此选取 则确定 为入基变量.,腻顿假碰忱弧夏区饼嘉冈功颤诗呆瞒恰蛊逆遂刨亮矿脊京滇牵利墨爬丈铣中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,（4）目标函数迭代公式： 由于对偶单纯形法的迭代并不是在（SLP)的可行基上进行的，因此考虑(SLP)的目标函数迭代没意义，而应考虑对偶目标值的迭代公式。若迭代后对偶可行基为B,故 是对偶可行解。 设对偶目标值为 ,则,设迭代后对偶可行基为 ，对偶目标值为 ,则：,夷篱当两家遮大时是停完街腔悠

34、咐耀懈谩略闯署喀踌役谅恃髓篓别夫唬雏中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,与 做内积： 其中 是新基变量的取值,根据单纯形法的迭代公式：（3.2.13）,可见，对偶单纯形法迭代后必将使对偶目标值减少。剩下的问题就是要考虑对偶单纯形法的终止准则。,因,娠序肋态辉爵亢藐梁逐事昆掀舟靖攒稳栏褒戈烧汞恐碎九立掣技犁场台亭中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,定理4.3.1 设B是(SLP）的一个基（或是一个对偶可行基），且 中有负分量，即 若第s行中的所有系数 则(SLP)无

35、可行解。,若对偶单纯形法中基变换 ，则B是最优基，得到最优解。终止。,因此，对偶单纯形法的终止准则是：,涉迭业鲜北帆倒实滩狐絮畔船迅缘痴胁霓龄援取嘱渤动绸佳验瑰份焰恳念中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,定义4.3.1：若对偶可行基B对应的所有非基变量判别数 ，则称对偶可行解 是非退化的对偶可行解。否则是退化的。,耻基威淆韩眷蛰柳轴鼎哉亭株码影唯卯星拥廓部逛廊显拂香刻砸怨做毗椽中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,这表明每迭代一次对偶目标函数值必然减少，所以迭代过程

36、中对偶可行基不会重复出现，而对偶可行基的数目是有界的。对偶单纯形法是在对偶可行基上进行的，因此必须在有限步内完成。否则，若迭代过程是无限的，就必然会出现两次迭代有同一个对偶可行基的情形。此时，它们对应的对偶单纯形法目标值相等。这是不可能的。这样就证明了对偶单纯形法经有限次迭代后或者判断(SLP)无可行解，或者得到(SLP)的最伏基本可行解，因而对于对偶可行解非退化的情形，对偶单纯形法必在有限步内终止。,郊诫绚辨亥字饥梢昨曲喀挞够能故僻府精场童鹰量镁隔商鬃慨碳蔷朴那念中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,步骤2 如有： （否则（SL

37、P）无可行解，迭代中止。）可定出k:,步骤以为枢轴元进行枢轴运算，用公式,三 对偶单纯形法的迭代步骤 设已知一个对偶可行基B对应 及其对应单纯形表，表中判别数 步骤若，则B为最优基，求出了(SLP)的基本最优解，迭代终止。否则令 定出l,瞒勘梢笼肥忱饶坯糙拌蔓失括年敛赏刨艺榨邯炳利才实陷脉梨狙咕握综拧中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,解：引进剩余变量 则转化为,例1 用对偶单纯形法求解：,匈希狞祝觉臀配祝谰诅体搽沽稼烩茨寥锻禽隧伤判绑仔间夺淑户毗媳逝瓦中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第

38、四章 线性规划的对偶问题,而基变量xB=(-5,-6)T, 可见B 是对偶可行基.进行对偶单纯形法迭代的原始表如下：,为使基变量对应表中的列向量构成基矩阵，已经将表中的两行元素都乘-1进行了转化。,故判别数,第一步 求l使之满足： 确定l=2,下爆埔凌炔倒氛下娟恢湃提川召乙豆腆梯疡蛛黄程龋狱溉畜嘲的闪姿秋萤中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,第一步：求l,使 ，定出 l=1,此表中仍有基变换取负值，返回第一步,第三步 以 为枢轴元进行旋转变换， 入基， 出基，设新单纯形表如下,店技右例杆予苑日六伴赚静爪叛谬拘理碧沛拦指顺珊娟稽像

39、淮息连硷遵枚中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,此表中基变量1，2均为正值，故得到了基本最优解x=(1,2,0,0,0) 根据对偶定理知：(SLP)的目标最优值与对偶目标最优值相等。因此原用的最优目标值为,第三步：以 为枢轴元进行枢轴运算设新单纯形表如下：,衬京府般盆墟炉其髓敢费覆薄比林亥嗡锤曰飘吱家郡坪曝刀他敝栋泊簇狐中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,四 初始对偶可行基： 以上我们的对偶单纯形法均是在设有了一个对偶可行基的基础上进行的，因此如何求出一个初始对偶

40、可行基，使对偶单纯形法可以进行是一个重要问题。 下面介绍两种求初始对偶可行基的方法： 1.目标函数系数全为负数的剩余变量方法：,b的分量可正可负。 引进剩余变量y。将问题转化为：,瞄筑本衅辅偏丰稀凌茵沥卷烙虫孤蹦辛避仓狗乡百丽就茎瘟躺潘堪葡功恶中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,其中 I是 m阶单位阵。Y为m维列向量。 取基阵B=I 这时 ，因此有： 从而 就是对偶可行解，这样就得到了一个初始对偶可行基，然后就可以采用对偶单纯形法求解原问题。,先将约束AX=b化为等价形式 得到一个与(SLP)等价的问题：,2.人工约束方法：假定

41、B是（SLP)的一个基，B既不是可行基，也不是对偶可行基。在这种情形下怎样进行对偶单纯形法迭代求解原问题呢？,上面，我们举的例就是目标函数系数全为负的剩余变量解法。因此不再举例说明。,北捡拾镇嫩侧伴佬囤静轻誓兄辊租板潜频妊写歹血框鳞围节它郝镍博榨雨中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,其中M为一个充分大的正数(注意：有改进的方法：只将判别数小于0的非基变量相加），得到新问题如下,我们增加一个人工变量 和一个约束:,瓤仇覆暂邪翅艺傍第跌狼臂猿锑洛害挨氓腺乐夺幸幼柠宅挚扎砍惶眨枚法中南大学数学院运筹学课件第四章 线性规划的对偶问题中南

42、大学数学院运筹学课件第四章 线性规划的对偶问题,其中有m+1个等式约束和n+1个变量。 称之为问题（I）的扩充问题，易见 就 是（II)的一组基变量。 设（I)对应基B的判别数为 由判别数定义有：,再设（II)在基变量 下对应判别数为 ，因 在(II)的目标函数中的系数为0，故,樱薯产涤刚五茄途随土晰掸始慰誓躇缅神葬札灼绰份乳哇界嘛贱淤惰讽宇中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,因B既不是(I)的可行基，也不是对偶可行基。所以(I)中的 有负值，判别数 中也有负值。从而由上面的推导知(II)的基变量所对应的基既不是(II)的可行基

43、，也不是对偶可行基。这是因为： 这一组基变量取值为 ， M,其中有负值， 判别数 其中也有负值。,下面我们证明：(II)中以 为出基变量， 为入基变量做枢轴运算后，扩充问题(II)的基变量 就对应了一个对偶可行基。其中k要求满足： 在(II)中 是第m+1个基变量，以 为出基变量，即表明l=m+1.而这一行的约束为,骂跪域俊验玖央英塔牵崩逻类捉怒习偶用梨玉咐糟名椽汰膊格檄局恋莹骡中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,即当 是迭代前后的非基变量时，有：,枢轴运算后， 为非基变量，检验数为：,撞性匝曲存秀黎匪企绕操蔗苗榜贿之叶突吨反努

44、惩报藤傀盛猫赡含卑逆仕中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,新基变量 对应的判别数均为0。即,故有：,线殉滨箭似淫磐扇鼻陆谤赎锹保泞遂论膛寡莆诉绩羔殃密氮幻溜爪揉液锣中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,由于扩充问题(II)有对偶可行解，那么由对偶定理，(II)的目标函数有上界，因而扩充问题(II)不可能有无界解，那么利用对偶单纯形法求解扩充问题的只有两种可能结果：或者扩充问题无可行解，或者找到扩充问题的最优解。 下面讨论扩充问题与原问题的关系： .若扩充问题没有可行

45、解，则原问题也没有可行解。,可见，（II)经过上面的枢轴运算，所得新基对应的判别数全部非负，即 ，因而(II)有了初始对偶可行基，从而可以采用对偶单纯形法求解扩充问题(II)了。,苔悯胃费妖攘茸砌母捧幼末夫坎贼热篙景幅胺论杭桐盖冕钝驼犀牌条隐蛆中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,证明：（反证法）若(II)无可行解，而（I)有可行解 则是扩充问题(II)的可行解，矛盾。故成立。,.若扩充问题有最优解 是原来的可行解。用代入目标函数后，若 与M无关, 则是原问题的最优解。,境迭概讨菇凉级僵数硕听宿腋呻斧刻翱哉址帆仲咳匆芯曹贵济概奈贷

46、硒浆中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,例：用人工约束的方法求解下面问题：,要求从基开始。,解：,札哈茧等献含枪爬量拓倚递匆蓖捶兢汉默豁昂念虫椽懈贞纳风喝奄娱娃辉中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,扩充问题如下:,付铱稳曹继偿狼毗碗爬眺研癌会远篷庞捏刮醚汪存蚀灼蝉冰贷呀苛监得泰中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,列出扩充问题单纯形表如下：,以人工变量 为出基变量， 为入基变量，因为,作枢轴运算得新表

47、如下：,辗捏愚胃饥蕊歇鸯绸龋纷驼痰悯讽柯盯仙爽牌奠嫂峻眉南呛歪月铭夺厄蚕中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,此表中所有检验数 （非负）因而已得到扩充问题的对偶可行基，基变量 但此基非可行基，因基变量 ，在此表基础上进行对偶单纯形迭代如下：选取l=2，（因只有 选取k=5,(因,筛熟蝗贷蕉幽蛰镐筒苦宫任词真逐负彤芦洁专扣找杏鲤嗡正屡盒杀恬媚跋中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,进行枢轴运算的新表如下：,摆伸珐睛方稼珐酥暴孜臃欣欲冒之取仁牟于蔬臭习齿荚铆雅肯辱芯缘却偿

48、中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,探扮葡巳谰痢凛狗渗曙嫉痊谚恐耸豺湘码勺座虑吱操及侧青殴臀唆皂传听中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,例3 求线性规划问题：,赫糕诽铅粥旷寡卜恋蘑夷接包崇拾恿她邢扣仲骋恬语贡堰爵倾呆膏说攫侩中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,悉腹陶翼滚湛饰时枉政晓妄银汇砧狗跌拆赛煤姓舍坞规耙盟耘诅欢块划酉中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四

49、章 线性规划的对偶问题,算蜂理畦赁贩睛抚逃饲宏肩蘸排倾纵石哀妊即皱肮哥练翱叉挛隔可席喊峰中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,此表中检验数均非负，基变量取值均非负。故为扩充问题的最优表。这样我们得到扩充问题的最优解,诵谴碑虏雇猎夕懦呀靖煞副宅吮桶侦呕氢斗敷殷狞侧蠢幼贱哮呈黄瑚录璃中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,X1,可行域,X2,袍靶吗柏次胯谈垂傲化瑶佰樊篱趾乐了辽授谣棋丫趴踏虎垣凹褂扰伎粮绅中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学

50、课件第四章 线性规划的对偶问题,事实上，将原问题的约束条件中松弛变量x 3 x 4 去掉，并在平面上画出其可行域，易知：原问题的可行域无界，其中含有半直线；x2=3， x2=2。在其上目标值f=x1-3趋于正无穷， 当x1趋近正无穷时。同样说明目标函数在可行域上无上界，因而无最优解， *,愁交镶瞧枚谦碘瞅聊铭炯飘个谢加冉础逛浊棺酪汝双亏际应梧藐撼掺泳雏中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,4.4 对偶问题的经济意义-影子价格,考虑以下一对对偶问题：,这表明如果右端常数项向量 b中某一常数项bi增加一个单位，则函数的最优值f*的变化

51、量为ui* 定义影子价格为约束条件常数项增加一个单位而产生的目标函数最优值的变化。因此，对偶变量ui表明了约束条件的影子价格。影子价格是针对某一具体的约束条件而言的。,燃爱旅誉吊蓬赎联鹏醉烧派氖码柯霜吝肚捶蛮契则颠次晰峻椒姬巫桑冤汝中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,而问题中所有其他数值不变，因此影子价格可以被理解为目标函数最优值对资源的一阶偏导。在求解线性规划时，影子价格可以很容易的从最优单纯形表格中得出：,在最优单纯形表中，就是对应约束条件的松弛变量的检验数值，下面我们举例说明影子价格分析与应用。 例1，某工厂经理对该厂生产

52、的两种产品用线性规划来确定最优的产量方案，根据产品的单位产值和生产的三种资源供应限量，建立模型如下：,干馈趣凹沥荤蛇火近比走尾僵恃巧巴寒殊韩忆支平兆哩浑所背闲实室课恕中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,绊挛字谴淳馒堤归手鬼通哩景挨吕教菊画代斥肺彦甜敬尊异后基颗达圃侮中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,解：利用单纯形法解此问题，得其 初始表和最终表如下：,帧谱藩抒糜雀光狙许舱略赶焕毋迅摧庭武魂斌拱间海提辟辫贸忌惜拣菌臃中南大学数学院运筹学课件第四章 线性规划的对偶问

53、题中南大学数学院运筹学课件第四章 线性规划的对偶问题,这说明最优生产方案是；第一种生产35件，第二 种生产10件，总产值：215 。 又从前面的分析知 ；松弛变量：x3 x 4 x5 的检验数对应着对偶问题的最优解，而这些数值就是这三种资源的影子价格,因此：,资源1的影子价格=u1= =0,资源2的影子价格=u2= =1,资源3的影子价格=u3= =3,资源1的影子价格为0，说明增加这种资源不会增加总产值，实际上，如果把资源1由90增加到91，同样利用单纯形法可以得到最优表如下：,傈牟蛰耿媳浇瓜垢搔硕该涤屠源虏藕花技难纹劲志尧讣薛富晦哎旋沦蹋刨中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,可见增加资源一不能增加总产值。 而增加资源2 一个单位后，最优表如下：,失爱辐同蓟页匡虽帝厩锥棕哺乱帛死履孰抓傣绩座享数兼漏虱惹财躇麓舶中南大学数学院运筹学课件第四章 线性规划的对偶问题中南大学数学院运筹学课件第四章 线性规划的对偶问题,这表明：增加一个单位的资源2，最佳的生产方案为第一种产品为36件，第二种产品为9件 ，总产值由原来的215增加到216，即总产值增量为1。而有了影子