运筹学2.3对偶理论.ppt

2.3 对偶理论,纲锚粱叙稀哲揪献缄屈娘五猴纱字洋阜温允脐玄两桩碟水僻群拿谚屹邵页运筹学2.3 对偶理论运筹学2.3 对偶理论,Exp.:考虑第一章(引言)中所讲的奶制品加工的例子.,不考虑生产者自己生产,而是将各种资源(牛奶,工人,设备)承包给别人.试问:生产者应该如何给资源定价?,分析:,设,分别表示,每桶牛奶每小时加工时间设备甲每小时加工能力,三种资源的承包价格,Note:由于设备乙加工能力过剩,在承包时不考虑其收费.,伐拉派黍鸽堆刻桐酸娘辫葫糖陌躯挡锤碟汀篮冕翼础琢拌赠矗度衔拉韵焊运筹学2.3 对偶理论运筹学2.3 对偶理论,考虑承包后获得的利润不得小于直接生产获得的利润:,1桶牛奶&12h加工时间&设备甲3千克加工能力生产A1,可获得利润 72元,1桶牛奶&8h加工时间&生产A2,可获得利润 64元,当上述条件满足时,承包获得的收入不低于直接生产的收入,再考虑原来的生产者如何能将生产资源承包出去,即要考虑 对方容易接受的问题,对方的支出为:,数凯疥踞环玖运雁涟碉渤博炽陡呛君蕾冬瑞胺康鼠薯睦输替旧匪约臂全储运筹学2.3 对偶理论运筹学2.3 对偶理论,从原来的生产者考虑,越大越好.但从市场竞争的角度而言,定价越低越有利于竞争.于是得该问题的数学模型:,这也是一个 LP问题,我们称其为原Exp1中问题的对偶问题.相应的,原来的规划称为原始线性规划.,原问题与对偶问题是同一组数据参数,只是位置有所不同.两者实际上是从两种角度描述同一个问题.且:,价值系数 右端向量,形式上完全对称,夷站讳池钓琉挪阑革球栖升冷缚掀然摧凹映铲色鞘桌藻议离亩练旺灾蔫乡运筹学2.3 对偶理论运筹学2.3 对偶理论,其实,对几乎任一个实际问题,都可从不同角度给出类似上述的相互对称的LP描述.,考虑一般形式的LP问题:,需将(1)变为标准形式的LP问题,为约束矩阵 的第i个行向量,右端向量,(1),化汪番俊线顾辈抓型粒钻象烽气晃硫捡碉散喷厩梆住冈竹韦艰翁筐饲铺碳运筹学2.3 对偶理论运筹学2.3 对偶理论,对每个不等式约束:,减去一个非负的剩余变量,对每个自由变量:,A中相应的列 用列 和()替换,(2),鼓幢悲狸这收绪映啤浊唐普翅玛辑扶算融樱撵咙蹿创伤窒阎没骑兄陈梯码运筹学2.3 对偶理论运筹学2.3 对偶理论,令,单纯形乘子,则 满足线性约束,依照上述对 的列集合的划分,将该不等式约束划分为三组:,由单纯形法和最优性准则,若问题(2)有最优基本可行解,则问题(2)存在一个相应于 的可行基,使得检验数向量,逆耀己家帽足基麦炳蓄慧燎店暇寨畴慕趁接滇犊步活朋吹笺熊孽妓忠谩抢运筹学2.3 对偶理论运筹学2.3 对偶理论,对应于非负变量,对应于自由变量,对应于 的不等式约束(剩余变量):,LP问题的约束条件可用来定义一个新的,&若再加上一个目标函数,则得到如下新的LP:,当 时,它不仅是该问题的可行解,而且还是最优解,吵过穴畔噎墅怒淳滚枫雅罪谐蝉欺赴体釜钦保祟裔钟颈竭恢恤尼噶份败斩运筹学2.3 对偶理论运筹学2.3 对偶理论,Def.给定任一一般形式的LP问题,称它为原始LP问题,则它的对偶问题定义如下:,原始(P),对偶(D),障鬼寓锑野啊偶怨阳砌架撅赣痈酒唉盂臀挥壕舟溯倚调流袭并越登悄邓纪运筹学2.3 对偶理论运筹学2.3 对偶理论,两者之间的关系:,原始问题(P),对偶问题(D),min max,自由变量 等式约束,价值向量 右端向量,右端向量 价值向量,两个问题的约束系数矩阵互为转置,不等式约束 不等式约束,等式约束 自由变量,不等式约束 非负变量,非负变量 不等式约束,尔戴派纸雀帚浙咒窥惺球罪趟紧拄断嫉闽蓝俊窒捻泊旧硫妆神蛹值釜敞惧运筹学2.3 对偶理论运筹学2.3 对偶理论,规范形式:,对偶问题,标准形式:,又如:,(P),(D),程裤恭集旗锚奖行初篓育宜讲毡被泽店唾修该硼蕊娟针楞安裙血腮茎串醇运筹学2.3 对偶理论运筹学2.3 对偶理论,Th.:对偶定理 对偶LP问题的对偶即为原始的LP问题.,不失一般性,考虑上述互为对偶的两个LP(P)与(D),类似前一节,可定义对偶问题(D)的基本解、基本可行解,并分别称为对偶基本解、对偶基本可行解.,相对应地,称原始问题(P)的可行解、最优解为原始可行解、原始最优解.,对偶最优解:称使 达到最小值 的对偶可行解为对偶 最优解.,Def.对偶可行解:称满足条件 的 为(D)的对偶 可行解.,于终恋巳拴钮荆痴巩慰哄后哲最话骨炭砧雅讲柏糜碗拓翼悬眷隘晶软轨涤运筹学2.3 对偶理论运筹学2.3 对偶理论,Th.:弱对偶定理:,两个互为对偶的LP问题,任一个问题的可行解将产生另一问题最优目标函数值的一个界.,对任何原始可行解 与对偶可行解,必有,Proof:,由 的原始可行性,因 对偶可行,对于(P)的所有可行解x,必有,而对于(D)的所有可行解u,必有,熏渐尘宛县秽逛懂云巴竞摈魂黎斡值满速锣脑雏烽穆攒酝灶相分城渭渣彻运筹学2.3 对偶理论运筹学2.3 对偶理论,推论:若原始问题(P)有无界最优值,则问题(D)不可行.,Proof:,由B是最优基知,必有,是一个对偶可行解,设 为对应于B的基本最优解,则有关系:,由前一定理知 为一个对偶最优解.,Th.:若B为问题(P)的最优基,则 为问题(D)的最优解.,扫讣痹硕犹颗澈砾诣鸭涩狸维磨盏色姻等弟饶相绽浑庙办蜡惦裳噬啮败监运筹学2.3 对偶理论运筹学2.3 对偶理论,Th.:强对偶定理:,如果问题(P)和(D)同时存在可行解,则必同时有基本 最优解,进而,Proof:,两个问题均可行,(P)和(D)必都有最优解.,应用单纯形法,必可求得(P)的一个最优基.由前一个定理即得证.,有上界,有下界,其实,还可进一步证明:,(P)和(D)同时有最优解,它们同时有可行解,押谋谍蟹短您珐谬摄爆贤吱悔毋粹景抗芒航盛妆班会阶沼壕潜用皇右公邓运筹学2.3 对偶理论运筹学2.3 对偶理论,若设 分别为 的可行解,则它们分别为 的最优解,对于互为对偶的问题(P)和(D),只能有下列四种可能性:,b)(P)和(D)均 不可行.,a)和 有限且相等.,b),而(D)不可行.,c),而(P)不可行.,蠢气俏汤堡蒂录腺徊巫沥谴经填喇萧苍弃辞咨轩辉被印始亥皆哀蚊铺昔蒸运筹学2.3 对偶理论运筹学2.3 对偶理论,由前述三个定理易知:,是原始最优解和对偶最优解的充要条件为,Th.:原始可行解 和对偶可行解 是原始最优解和对偶 最优解,Proof:,由于,故该定理中的充要条件等价于,这里 为 的第j列.,焊坯田抿妇蜗韦订广东渔判判告蜒所捌混望活心眩弦笺竿甫添孜踏康社贬运筹学2.3 对偶理论运筹学2.3 对偶理论,以上条件 称为互补松弛性条件.,含义:,此时称第j 个约束对问题(D)是松的,此时称第j 个非负约束对问题(P)是紧的,a)若有某对偶最优解,使得对某下标j 有,对一切原始最优解,必使,b)反之,若有某最优解,使得对某下标j,满足,对一切对偶最优解,必有,身寐吐净谅佳友獭废拿慧钩狸斥痞伐景魁丙竹殆陕奈刹脚杯罐俊羌贮恨堂运筹学2.3 对偶理论运筹学2.3 对偶理论,若实际中LP问题的形式与以上所述不同,则亦可类似地定义其对偶问题.并易证上述所有有关对偶结论均成立.,例如:,假如原LP问题呈如下形式:,则其对偶规划应写为,进而,可行解分别是他们的最优解的充要条件是:,原始互补性条件,对偶互补性条件,豆跺靛侄胚孤最索恩颈唉锈闻犁剥峭构父减操另戎溃般趣辛挥姜撂宙酱赣运筹学2.3 对偶理论运筹学2.3 对偶理论,应用:,Farkas 引理:要么,要么存在一个 使得 且,但这两者不可能同时成立.,Proof:,考虑LP,与其对偶问题:,因该对偶问题有一显然的可行解 v=0,由LP的对偶理论知只可能有下列两种情形之一:,1,2,因此,且对任意使得vA0 的,有vb 0.,那么,且同时存在某一,使得vA0和vb 0.,查垫噬裙议痛粮绘锯饵犯丰元旭站旱迁密院卑琳醚檄什洞拒哺绢鞘阎孺荚运筹学2.3 对偶理论运筹学2.3 对偶理论,Farkas 引理的变形:,要么 要么,要么 要么,若,则要么,要么,Th.:设 有可行解,且,则必存在 向量,使得.,Proof:,从而必存在向量,使得,且.,靡饶无血数袍芜雨鳞隋蛰独锑碧撂裴郭惫幕姥竞拽替缠钮逮沧锐净施饶什运筹学2.3 对偶理论运筹学2.3 对偶理论,对偶单纯形法,考虑标准形式LP:,(P),(D),由单纯形法及其最优性准则,若基本可行解x对应的检验数向量,时,x为最优解.,对偶变量的可行性表示,琉绢绍喊赴距施三全云皆蛇奖远衫札入沈径祸晰萧给泛蔬孟赂阳糕盟庭膨运筹学2.3 对偶理论运筹学2.3 对偶理论,单纯形法的解释:从一个基本可行解开始,在保持其原始问题 可行解的前提下,向对偶可行解的方向迭代.,原始(单纯形)算法,对偶单纯形法:从一个对偶可行解开始,保持其对偶问题 可行性,向原始可行解的方向迭代.,对偶(单纯形)算法,对称地,从基阵B的观点看:,一般地,一个基阵B:可能:,a)仅为原始可行基.b)仅为对偶可行基.c)两者都不是.d)两者都是.,则此对应的 为原始问题的最优解,而 为对偶问题的最优解.,若基B使得:,则称B为一对偶可行基.,耗豺妈扰小膳午缕棕汽胰拿真蔬惋峰励绅涌絮暴侍忍堤躬芦秘帮意浙贷数运筹学2.3 对偶理论运筹学2.3 对偶理论,原始单纯形算法:从原始可行基向另一个原始可行基,并最终达到亦为对偶可行基.,对偶单纯形算法:从对偶可行基向另一个对偶可行基,并最终达到亦为原始可行基.,假设有一个原始问题的基本解,但不可行,减少原始问题的不可行性,对偶问题的可行解(0),离基变量,希望通过基变换来增加当前的目标函数值z,且保持对偶解的可行性,选择对应于原始不可行解的某个分量 对应的指标r,氧诸蹿倪羞蚤挺屯瘸儡晶诡噪妆揩烯玲射镁捷庆柬史畴账歹泞辱石钥壤会运筹学2.3 对偶理论运筹学2.3 对偶理论,若选择进基变量的指标为k:,为使,应选择使 的指标k.,为保持对偶可行性,即要求:,对于 的元素必须有,k选取的准则:,新的检验数,翌溅粒缀议仓紊夺坛郭磅派丑怖馈狈袍逐裕诀马标芝状状热忱它货滓州玉运筹学2.3 对偶理论运筹学2.3 对偶理论,对偶单纯形法迭代步骤:,S 1:选取一对偶可行基B,从而一对偶可行解.,S 2:若B亦为原始可行基,即,则终止,为 原始问题的最优解,为对偶问题最优解.,否则,令.,S 3:若对,均有,则原始问题无可行解,停止.,S 4:求,S 5:交换离基向量 与入基向量,即令,用 代替B,转 S 1.,晚碑媒吾丫虏诣陇羽讲口挡正脾表猪詹碑梆歪馒顷蚁匆六诗坚颅蜀感丸散运筹学2.3 对偶理论运筹学2.3 对偶理论,原始、对偶单纯形法之间的对称关系:,原始单纯形法 对偶单纯形法,检验数符号 右端向量分量符号,决定进基变量 决定离基变量,由变形后 的第k列中正元素 由变形后 的第r行中负元素与 与其对应的右端向量分量的 其对应检验数分量的 比值中最小者 比值中最小者,决定进基变量 决定离基变量,十分对称!,睫惯屠堡崔吞奥妓遥仟雕母条炉煞这恢链故歇攒稗筑淳盆射酚椅叠诊音荔运筹学2.3 对偶理论运筹学2.3 对偶理论,对偶单纯形法的实质:,将原始单纯形算法应用到对偶问题上.,收敛性:,非退化:,从一个原始(不可行)基本解,移动到另一个原始(不可行)基本解,并使目标函数值增加(当得到第 一个原始基本可行解 最优 终止)所遇到过的基本解不会重复出现,算法一定在有限步后终止.,退化:,亦可能出现循环,而导致不收敛.,但可用Bland法则、字典序法等来避免循环发生,从而保证收敛.,踏端垣溉刮费因煎席润堑溺塌卜柠梗弓睁堰咳频冕铰珊说层阂晃娜嘻丙怨运筹学2.3 对偶理论运筹学2.3 对偶理论,对偶单纯形法的优点:,当找不到原始问题的一个初始基本可行解,但却已知或易于 找到其对偶问题的一个对偶基本可行解时,则可采用它.,典型例子:已知某一LP问题的解,但在对其加上一些新的约 束后该解不再可行.,当问题的约束条件数目很多,如约束条件数多于变量个数的 非标准LP,用对偶单纯形法求解其对偶问题要比直接求解原 问题容易得多.,当问题的约束条件数目很少,如仅有两个行约束的LP.,大规模问题求解,约束有特殊结构 对偶问题“可分”,分解方法,喊诲耘荧纬寂皖懒检苹砸毋宜科陨控欢敛馋窘践乍隔吾扒煞儡藉雷姨跋咐运筹学2.3 对偶理论运筹学2.3 对偶理论,对偶单纯形法的改进,原始 对偶单纯形法(primal dual simplex method),在使用原始单纯形法时,若没有明显的初始解,就必须引入人工变量,办法之一是两阶段法.,思想:同时对对偶问题和第一阶段的辅助问题求解,故称为 原始 对偶单纯形法.它可以从对偶规划的任一 可行解开始,同时在迭代过程中保持对偶可行性 和互补松弛性条件.,原始单纯形法:在保证Ax=b的条件下寻找解x0.,原始 对偶单纯形法:在x0得到满足的条件下通过剔除人 工变量使Ax=b成立.,绣承康磺粮贮氢柠蒜啃袭忿鱼衔濒活唾固瞎混捶习誓点出谓粹凄剖柔领菊运筹学2.3 对偶理论运筹学2.3 对偶理论,设原始问题,对偶问题,(P),(D),人工变量,(),为保持互补松弛性令(P)与(D)中非临界约束对应的 都等于0,假设已知其一个可行解,称为相应于 的限定问题,辅助问题,之裹沥妒雷坑劲淄僻拉逮胎敝月哨究佣敢当氦涂栽迹荚芦茨慷龙敛阵淀嘘运筹学2.3 对偶理论运筹学2.3 对偶理论,则它是原辅助问题的基本可行解.,若,则 还是原问题(P)的最优解.,若,则找(D)的另一个基本可行解,使(D)的目标函数 值增加,同时使对应于 的限定问题的最优值将比对 应于 的限定问题的最优值有所减少.,甫尸纤九忻侩嘲廷姑砸谬蛰瞎雏古曾墨礁境威捂脾堰一流辱曰坏储接九肚运筹学2.3 对偶理论运筹学2.3 对偶理论,令 为 的最优解,这时有,若对,均有,则 还是辅助问题对偶 规划的最优解.于是 为辅助问题的最优解.,由于,故知原问题(P)不可行!,否则,这样构造(D)的新解,必须满足(D)的约束条件,即对,有:,绿狐盐圣撒午丽鞋快目萎胺蝎盗掖擅前泼眶满褐叠脑写付抵绎删粒朵揪非运筹学2.3 对偶理论运筹学2.3 对偶理论,且,当 时,用 代替 后就使得(D)的目标函数值有所增加了.,令,则得到对应于 的限定问题:,为其一个基本可行解,从而可以它为初始解进行求解,和 分别为 和 的最优解,若 则 且,于是,故若,必有,黄陡旧托局渤祝秃槛弟拨溺母彰玩蛆炬酞菊谊密讣嗡记霍浪分降匀酮穆馅运筹学2.3 对偶理论运筹学2.3 对偶理论,易知,且,而 恰好为该新的限定问题对应于解 的非基变量 的检验数.,一般地说,以 为初始解求解该限定问题,总能使目标函数值g有所减少.,撰泄架枣擦瞪汛拽昭仇籍戊肯跟谚画屹嫁搔尺纵筐流锯赁洱圾硷劲翌龙越运筹学2.3 对偶理论运筹学2.3 对偶理论,原始 对偶单纯形法的迭代步骤:,猖聘永馏燎臆西就葱谋墙吟晃悔泛梗惟鲜浆歇讣企策成势眺铃惕递智憋睡运筹学2.3 对偶理论运筹学2.3 对偶理论,讹疫调础巳纸妄臆莉蛛凭去荆尖镀才瞧朔星绘衡浮稳鞍峡氨姻邱诡猾热鸭运筹学2.3 对偶理论运筹学2.3 对偶理论,灵敏度分析与参数规划,实际中所搜集数据不精确,有可能进行修改?,环境变化 数据发生变化,增加新的变量,增加新的约束,改变价值向量c,改变右端向量b,改变系数矩阵A,增加新的变量,增加新的等式约束,增加新的不等式约束,对已求解的LP,遇到这些改变时,需要从头开始重新进行求解?,对解的影响?,如何有效修正现有的最优解?,灵敏度分析(sensitivity analysis),优化后分析(post optimality analysis),咀塘悔瑶频尿池畸爱责眶尼叙褒幢答银什剔硬谩绒垮屋爬惩宁油并攀锐优运筹学2.3 对偶理论运筹学2.3 对偶理论,