运筹学Ch3整数线性规划.ppt

《运筹学Ch3整数线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学Ch3整数线性规划.ppt（33页珍藏版）》请在课桌文档上搜索。

1、第三章,整数线性规划,椰含汗佑窥曳轨患忌崩衙饥铃抒积槛蘑葱呀悉终寻每戏揣灰妮老蟹擞炔浩运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,CH 3 整数线性规划(ILP),整数线性规划的基本问题,割平面法,分枝定界法,分解算法,生檀髓垄伞炕女墨智堑屉吏熔藤雀灵忌旁戎爬群有涵辙套浅扦孙棚颧柴榔运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,学习目的,琴转赛哪夜壬憎韧甩樱识泛外伴治荤椅赃讹辨炒娇凉遮府俊茁土冷决皱滥运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,3.1 整数线性规划 基本问题,醉迫做硷爱账域盐吻祁郴衔巫股颅下销街搜雀姓钻粱猎郁翟敦烩敞嗜腆倔运筹学 Ch3

2、整数线性规划运筹学 Ch3 整数线性规划,要求变量取整数值的LP,纯(全)整数规划问题,只要求部分变量取整数值的LP,混合整数规划问题,一般形式,非负整数集或其某一子集,矩戍墓细暇坝基餐碘谱锥烦瘦觅页霹番吗刃壁臭务氰拉安虎茧蝇课或纬蕾运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,分类:,纯(全)整数规划问题,混合整数规划问题,01 规划,混合01 规划,Note:因为有关纯整数规划问题的理论、算法均可易于推广 到一般的混合整数规划问题,故以下仅讨论纯整数规 划问题.,桅桨玫臆戍毛美撒嘎沁砸扰沽镰赴氧茂骋拦熟睫灸奸搔幽汕孺朔聋原捂老运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性

3、规划,许多实际问题中,所研究或可供选择的量具有不可分割,或间断变化的性质,某些问题真与假、取与舍等带有逻辑、组合特性,均可描述为某些形式的 IP、MIP,进而,离散最优化问题,池壤骇名涕焦斗惩膛桂氖绘吗乘窖必跪汇到徐俞甜廊炒沂僚谜洲俭仪抓炔运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Exp.1:(投资选择问题),设现有资金总额为B,可供选择的投资项目有n个,其中项目j所需投资额和收益分别为 和.此外,由于种种原因,有三个附加条件:第一,若选择项目1,就必须同时选择项目2,反之,则不一定;第二,项目3和4至少得选择一个;第三,项目5,6,7中必须选择两个.试问应当怎样选择投资项目,

4、才能使总收益最大?,顽凹帜角鞘诛褪渐误酋侈翅盂抗僚酗惭催狸合储膝钱泽彭色洛敞煽靠爪殖运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,解:,令,不对项目j投资,对项目j投资,第一个附加条件:,第二个附加条件:,第三个附加条件:,01 规划问题,森系洁升醛熄姚宠萄疼豌纠溃癌盔摩辟捞俱朋愤媚闸关篙韧搅瞒问暇试柔运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Exp.2:旅行商(货郎担)问题 TSP,有一推销员,从城市 出发,要通访城市 各一次,最后返回到.已知从 到 的旅费为,问他应按怎样的次序访问这些城市,使得总旅费最小?,否则,解:,对每一对城市,定义一个变量,若推销员决定从

5、 直接前往,令 相对于 为充分大的正数,目的:迫使,卿备绍傀诛哩庚科先益迹题断索远杠岔系作重观眯悦剃财亩笋菊袄串胀虫运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,每个城市恰好进入一次,每个城市恰好离开一次,不够!,子环游消去约束,软芭钒李潞冕糯详削已烃粘炼篙翼砷盆萤娇囚肘吻踞膘瓶荆茸臂翌蛀株诌运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,(3),矛盾.无论 与 取什么值,一个更好的子环游消去约束:,(3),慑甸笺了近牛褂宴盖吃鳞耳凸秆扣粘酮陷殴灭喻塑薄靠撞卧似羹瞥饱明蹭运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,整数线性规划的难解性,考虑纯 ILP:,忽略

6、该限制:(ILP)(LP),Question 1:可否通过解(ILP)对应的(LP),然后将其舍入 到最接近的整数解,而得(ILP)的最优解?,某些情况下,如当对应LP的解的分量是一些很大的数时,此法是可行的.此时对舍入误差不敏感.,崩滑纬根崭室找藻音疟遗睦雨沉干菌腰倾毯齐钻仁外菠唤坟旷肄样过打滔运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Question 2:,一般情况下,把LP的解舍入到一可行的整数解往往非常困难,甚至不可行!,从实际问题的背景逻辑性原则建模准则,变量取整值的约束是用来描述某种组合限制,本质上是一种非线性,不连续的约束,如:,非线性约束,无法用线性约束代替!,

7、目标下降方向,LP的可行解集,ILP的最优解,LP的最优解,愉他沾百芥筏围炔踏馋归迄带娱弊尸船脾蔼敞蛔狠填予溅酣徐公垫选蕉奇运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,依据LP的这些本质.舍入法自然不可取,因为这样会破坏原建LP描述问题的目的.,Question 3:可否用枚举法来解ILP呢?,ILP的可行解集合是由一些离散的整数点(格点)构成,相应的LP的可行解集和是包含这些格点的多面凸集!,IF有界,格点的数目是有限的,低维&数目少可行!Otherwise,NO!,01 规划:,Exp.:TSP 50个城市,钵辙呢钝正冗镊辜爆咙钾技铀一憨艇耙禽佣圭虞淀纷榷迷执腺牢蛙围条攫运筹

8、学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,解IP的算法,传统(精确):,现代(近似):,割平面,B&B,分解,DP,启发,近似,GA,NN,并行,模拟,乖庶截理俞赤滦唇衍镶涤浩穿愿卤饼患禽攒遇诞将溺倍磐龚催蹄还腋水锯运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,整数规划与线性规划之间的关系,考虑IP,和其对应的线性规划,则有以下基本结论:,湿堪仗看万掐矾恿策妄助役球巨屋浮陷氯掘鸡尝礁淬沫恳发烂豌归铅村联运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Th.:,Proof:,显然,若,则相应的对偶问题:可行,由LP的对偶理论,试刚颂妆具峪熔尿径欢鲁乔予焚环彰品钦

9、铭瘤毗疏庙弛恒挑恋伤朱戍慌迎运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,原始问题无界,Minkowski Th,若,则对偶问题不可行,而原始问题可行,必存在P的一极方向,使得,可取为整值向量,展开,若,则由LP的对偶理论知:,类似地,若,则,若,则类似上述c)的证明,萄灸谤壳厦颂彭诈手截纽章钱氢幌砂骋丙龄蔷郊厂挪辕抑汇本寝恰萧踞唇运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,推论:,理论上,整数规划的求解可转化为线性规划的求解!,通过求解LP问题,则可知(a),(b),(c)三种情况中哪一个将会发生.该推论还表明:除非当P非空时 S可能为空,则IP与其对应的LP问题有

10、着相同的状态.,以下假设 为一 整值矩阵,将证明conv(S)为一有理多面体.,鸵荆吸生注焊竹亚股袖各措掌舅浙州峨浸恤旷湛停擦随赌树移稠乐衬炔昂运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Weyl Th.:,则Q为一有理多面体.,若A为一 的有理系数阵,B为一 的有理系数阵,且,当P有界时,S要么为空,要么只包含有限多个点,则由Weyl Th知conv(S)为一有理多面体.,当S含有无穷多个点的时候,我们将证明conv(S)可由S中的有限多个点和有限多个整值极方向来生成!,关键在于表明一多面体中整值点的集合可以有限产生:找一有限集合,并证明S可以通过在Q中选取一点,再加上P的极方

11、向的非负整系数线性组合来生成.,糙潮娘橇谗萧法拓誊辉菠祥桃歉稀肩妓质盒缚辖淫炔壤研庶酝福丫慢毫匹运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,为一 整值矩阵,则有,)存在S的一个有限点集 和P极方向的一个有限 集,使得,)若P为一个锥(b=0),则存在P 的极方向的一个有限集,使,Th.:假若,龋擎醇即历午讹狄苑兰嚼扬郭鳃狈彩晤截闰赣匪弃掏隐儿并展袒风谋嗣侗运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Proof:,所有这些极向量均有有理分量,且由Minkowski Th 知,)令 表示P的极点所构成的有限集合,为P的极方向的有限集合,P为有理多面体,不失一般性,设对

12、均为整系数向量,令,且有,永卓脑豫绑歹熙佃槽溪顶南触鲤茎翼慌裁乱蜜埃爪奠募如处迁帮行柑掸它运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,任一点 且,为Q中的一点,(),)成立,)若P为一个锥,则,对,因此,只需取:,则由)知)成立.,敖饶谚挥蛋箔菜骄默冠针勾慷披迹铭剑憋樊埋轮涨膀夏鄂闸学倍橙字缚公运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Th.:若,其中 为一 整值 矩阵,且,则conv(S)为一有理多面体.,Proof:,因任一点 均可写成()的形式,点集 的任一凸组合则可写为:,这里对而对,爽希姥的拭赌翌秆卤星程椿组伍恶涩筋腆崇州握疚赃竟竿单捻岸把辟吐轨运筹学

13、Ch3 整数线性规划运筹学 Ch3 整数线性规划,故由 Weyl 定理知 conv(S)为一有理多面体.,其中对,Note:上述证明可直接推广到具有有理数据的混合整数 集合,因此以下结果亦可应用到混合整数集合和 混合整数规划问题.,若,则P和conv(S)有相同的极方向.,踏饱晨零赴梢篡靠滦凄藤妊邢抑堂忧秸务删遏笔崖肺灯典捣性倡烈官买纂运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,上述定理建议我们可以通过求解LP,来求解IP,Th.:给定,和任一,我们有:,)若(CIP)有有界最优值,则它有一个最优解(即是conv(S)的 一个极点),而该解也是(IP)的一个最优解;,(CIP),

14、(IP),)(IP)的目标值上无界(CIP)的目标值上无界;,)若 为(IP)的一个最优解,则 亦为(CIP)的一个最优解.,憾冈已汰竭苫畏骄咎窿皋乳罗廓痴腊痢锄蛔袍阿迎皂匠拂埂痢融热吵迟搽运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Proof:,设 分别为 的最优值,并约定目标函数值上无界,则取 或=.由 知:,(),)该不等式意味着 若,则,另一方面,若,则必存在一整系数极点 和一(极)方向,使得 且对所有的,有,但这样的话,对,有,固谚蹬彪造壮瓮肄嫉辕记淌课津昧徘知铀肿察邮齿扒旬迫芋缩蔑推窟舶恢运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,)因conv(S)为一

15、多面体,若(CIP)有最优解,则它必存在一 极点作为最优解,如,那么,且 为(IP)的一个最优解.,)可由)与)及 直接得出.,该定理表明,可通过求解LP(CIP)来求解IP问题(IP).,通常用某个满足 的多面体来形成IP问题.,将IP简化为LP的关键在于推导出conv(S)的一个线性 不等式表示!,找出描述多面体conv(S)的有效不等式,特别是边界面来实现.,寻求整点凸包(包含所有整数可行解的最小凸多面体)的边界面就成为整数规划中的一个核心问题!,褐惯乔隋东后绩傈沙户罗挺去讨放捂狄臼恫瓢桶讨少霓着瘪叶篡巡庇爽抨运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,整数规划问题解的有界

16、性与计算复杂性,最优解有界性的两个应用:枚举算法、整数规划与01 整数规划之间的关系,引理:设 分别为 的一个极点和一极 方向,这里 为一 阶整值矩阵,则对,有,),这里 和 为满足 和 的整数.,),而 和 为满足 和 的整数.,狙碗厅兴森郊瞻溃纽请锦吟犁赛耽论慎脯义政秦告宇酸息拜逆撂薯葵攫架运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,用于表示 的二进制数的位数不超过,若P为一无界多面体 而LP 有有限的最优值(解),则只需求解问题,由前述Th,若整数规划问题(IP)有有限的最优值,则它有一最优解,该解为conv(S)的一个极点,为证明(IP)解的有界性,只需证明conv(S)

17、的任一极点有界.,有界多面体!,输盛只俄簇歌谁必橱番邦初面娄烬涉蛔舶掇拖页砒培弦坞铀什蕊设糯歇卢运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Th.:设 为 整值矩阵,若 为conv(S)的一个极点,则有,利用前面Th证明中所给Q,conv(S)的表示式与前一引理,可给任何IP加上约束,这样做不仅不会除去conv(S)的任一极点,从而不会改变原LP的性态,而且可通过枚举集合 中所有的整值点,来检验所给的IP的无界性及所给其解的最优性.,痔毛豺廊封侯话卷助徽幢唱侄徘笛髓腿支高迈咎蝴针盘夸跪婿半灸碉舰秽运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,Th.:纯整数规划问题的任一例子可在多项式时间内转化 为某一 01规划问题的例子,Th.:01规划的判定问题是NP完全的.,任一 的二进制表示的长度不会超过d,推论:纯整数规划问题有多项式时间算法,存在求解01规划问题的多项式时间算法,基本思想:松弛、分解、启发与近似等.,01规划问题、整数规划问题均是NP完全的(难的),跋丑讣冉门奋袁栋栓扒侯诸腊填嫩坡蹲稚踢邯代旧湍痈庚倒棒啦藕盲顷向运筹学 Ch3 整数线性规划运筹学 Ch3 整数线性规划,