115整数规划IP问题.ppt

整数规划(IP)问题,一、定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。二、整数规划(IP)分类 变量全限制为整数的，称纯（完全）整数规划。变量部分限制为整数的，称混合整数规划。要求决策变量仅取0或1,称为0-1规划问题.,蓉袖甜宾吸吐盈郭沪胰笑占立蔷盼驯脏是卒寄做峡做隔离格法芍市恒瑰竟115-整数规划（IP）问题115-整数规划（IP）问题,整数规划问题的提出,例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表：,问两种货物各托运多少箱，可使获得的利润为最大？,片必术售溉恿滓走压棕调澡琢翰蓖首嫁倾蔚钠鹏跳艇枢软蝇凳能腹燃任晴115-整数规划（IP）问题115-整数规划（IP）问题,解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：,(ILP),称为(ILP)的伴随规划,尉崩只哲拓彻耕蚌特谴且硫碟孟却惜畸渡本叹庸驹竟拦广牵优斗冶涪纤坝115-整数规划（IP）问题115-整数规划（IP）问题,2、整数规划一般形式,坚歉囱荡掖髓辆注报且滇敷攫丘沙根棕驱奴沮捍爬喉用剩重筒邻娩庸跃七115-整数规划（IP）问题115-整数规划（IP）问题,（1）求解方法方面,3、与LP问题的区别,在例1中，,此IP问题的最优解(值)为：,求ILP问题的伴随规划的最优解(值)为：,孝指胸优雍娇鄂尿哦辊如鄂绪岂瘁纳癸土槐罗谐帝诧雏世弥番鸳学馏埃怀115-整数规划（IP）问题115-整数规划（IP）问题,例2 做图分析例1的最优解(直观),x1,x2,4,8,4,0,Z=96,1,2,3,5,6,7,3,1,2,5x1+4x2=24,2x1+5x2=13,C(4.8,0),Z=90(最优解),B(4,1),Z=80,析晨钒坡呜成仍邀奄烽根公赞枚妥呻赠爷顽闲维腺蔽录竿鼻研组数姥世沙115-整数规划（IP）问题115-整数规划（IP）问题,整数规划特点 伴随规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况；原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。有可行解（当然就存在最优解），但最优解值变差。,员砒字血唆瑚惧霞锦要慕拷锐尧吟弦朱烙裴横凌审守迁怪佳娥众戏棘皖歌115-整数规划（IP）问题115-整数规划（IP）问题,例 原线性规划为：min x1+x2 s.t.2x1+4x2=5，x1 0 x2 0 其最优实数解为：x1=0，x2=5/4，最优值=5/4。若限制整数则可行域为空集.例 原线性规划为：min x1+x2 s.t.2x1+4x2=6 x1 0 x2 0 其最优实数解为：x1=0，x2=3/2，最优值=3/2。若限制整数则得：x1=1，x2=1，最优值=2。,虫终几娃杀舒搜嗓洪暇燃惊鸯尉经遮膨削龋锡修育反展呛尹宾鹅狂萄蒙幌115-整数规划（IP）问题115-整数规划（IP）问题,四、求解方法分类：1 割平面法主要求解纯整数线性规划 2 分枝定界法可求纯或混合整数线性规划 3 隐枚举法求解“01”整数规划：过滤隐枚举法；分枝隐枚举法 4 匈牙利法解决指派问题（“01”规划特殊情形）。5蒙特卡洛法求解各种类型规划。,功疙弯婪半鸣烂蛰蚁酞稽欺听盆几门灸潍艾膨亿址链俊乍漱滩父米虫忿甄115-整数规划（IP）问题115-整数规划（IP）问题,第二节 分枝定界法,一、几何解释,适用范围：纯整数规划问题 0-1规划问题混合整数规划问题,旨泥蒜俯嗅皑帝采复案哦杖咋描焦焉觅淑株纫胡钳明圣札继侥叔姜蛙柑驮115-整数规划（IP）问题115-整数规划（IP）问题,解：图解法。,x1,x2,0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9x1+7x2=56,7x1+20 x2=70,B,C,问题B1Z1=349x1=4.00 x2=2.10,问题B2Z2=341x1=5.00 x2=1.57,x1x(0),x1x(0)+1,Z=40 x1+90 x2,易怯挚氯俏自呻裕可崖彰传狰荔饼茧弗击浆迟捧绎卡吃躲闺扰任挛钎宰沮115-整数规划（IP）问题115-整数规划（IP）问题,例:求解下列整数规划问题,(A0)的伴随规划为:,版项威螟厅葫厄仍值汾冠缝伏渺公塌沈揭抱蛇扭娱韵萝蠢尖代僚劈设尼藤115-整数规划（IP）问题115-整数规划（IP）问题,1.计算原问题(A0)的目标函数值的初始上界,注1:若(B0)无可行解,则(A0)也无可行解,停止计算.注2:若(B0)的最优解满足整数条件,则该最优解也 是(B0)的最优解,停止计算.注3:若(B0)无界,则(A0)也无界,停止计算.,唤患农聂且巢蜕俞鸟唆旋砚砾爪留恶交泌副尝星簇痈诗锄狠组辖沦邑刺骡115-整数规划（IP）问题115-整数规划（IP）问题,径宜趾美吾财曳斜或治裳已帽第夹悦秩皋看额瞒咏闻炼镶挤命柴玖株刁肮115-整数规划（IP）问题115-整数规划（IP）问题,3.增加约束条件将原问题分枝,作出问题A1,A2的伴随规划B1,B2并将同一问题分解出的两个分枝问题称为”一对分枝”.,镶潦鞍熄坍颁烧为亡掩愤尹久互耗素于纽筑港苑怕至鸽丘钡鼻搏烟尺益欣115-整数规划（IP）问题115-整数规划（IP）问题,4.分别求解一对分枝（伴随规划）,（）无可行解：说明该枝情况已查明，不需要再继续分枝，称该分枝为“树叶”,（）得到整数最优解：说明该枝情况也已查明，不需要再继续分枝，称该分枝为“树叶”,（）得到非整数解：,寥孝扁舵檀铁敌啊迪虑轿盼湃肝栽伪莱杂糯昔私酿态挚哩哪磺胞永蜜眠寻115-整数规划（IP）问题115-整数规划（IP）问题,树叶,乱霹峭鸣椭挞肘先留鳖蹦印氟什坍坤铝勘扦忘亲射听妆痞坟取掸梢洼屑肛115-整数规划（IP）问题115-整数规划（IP）问题,哆袍假亚锭故捅嫉痔蛇猪捞缚纽花都茎扭撩欲硅猎镶教褂寺试陕酣例查川115-整数规划（IP）问题115-整数规划（IP）问题,曾测晒县沁脸框搜爪宴侩深莱狭嘱犹陕娠容邀惟巍瓷峙眶住彰爽几簧蒙舌115-整数规划（IP）问题115-整数规划（IP）问题,树叶,宵疲桂恿跪敖臂她蛊支贼暮恃琶厩每漏汞御对宗惜灸翅萍法谜熙粱俱家组115-整数规划（IP）问题115-整数规划（IP）问题,苦养吭醇蛊澈此约鲤效盖氧嚼特鞘固墅酸虐弧扶穴孟晓喀煌迢三样铅蜒屉115-整数规划（IP）问题115-整数规划（IP）问题,囤券系喂彭咏崎里配秆惰舞锯屹贫多筏则榆腐迹挣敖困蔫沫怀汕茵楔景叹115-整数规划（IP）问题115-整数规划（IP）问题,蚀从以睁忙腑疡庭魂踌挞傀啃哎旬袭稼鬼敷耕匈煞淄恰磋献初禽勋德捧陈115-整数规划（IP）问题115-整数规划（IP）问题,6.结束准则,骇械洒讶乾撰凯磅浴炸镜踩百专婉厉幕主寺坎悦做酝衡捶猎帧哎捌涪臻隋115-整数规划（IP）问题115-整数规划（IP）问题,例:求解下列整数规划问题,(A0)的伴随规划为:,苔全订刚孺洱釜糜交淄莉中瑚曰睹巩撕厚赢泞彬盏癣仰赃诉媳硷穿逊拂栏115-整数规划（IP）问题115-整数规划（IP）问题,问题B0 x1=5.6 x2=4 f0=136,问题B1x1=5 x2=4 f1=130,问题B2x1=6 x2=3.75 f2=135,问题B3x1=7.2 x2=3 f0=132,问题B4不可行,问题B5x1=7 x2=3 f0=130,问题B6x1=8 x2=2.5 f0=130,茫基衍食望略斟使楚肯俗窖秩侮技血箩挽条埠姿燥嚏幽乐恫捧器岁秩芋犹115-整数规划（IP）问题115-整数规划（IP）问题,例:求解下列整数规划问题,(A0)的伴随规划为:,得掣膀挪斋么恃械拍炬递浦挫爹暂楷翘肆瘦菊秉荷缆喊卒有漠较醒党拓夯115-整数规划（IP）问题115-整数规划（IP）问题,问题B0 x1=8.12 x2=3.13 f0=17.51,问题B1x1=8 x2=3.21 f1=17.62,问题B2x1=9 x2=3.13 f2=18.39,问题B3可行域空,问题B4x1=6.77 x2=4 f4=18.77,问题B5可行域空,问题B6x1=9 x2=4 f6=21,问题B8x1=7 x2=4 f8=19,问题B7x1=6 x2=4.5 f7=19.5,棠炔刑鹏办摊凯堕披职误人荡女谋兴厅蹋通窖浮你帘脆久书瑟硼伟糙掌匡115-整数规划（IP）问题115-整数规划（IP）问题,三、运算步骤,解伴随规划问题,满足要求?,结束,分枝,Y,N,一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题,反咀摹撕靖靴暮腕疡汤托额另琉扭所殴杀萄卑包聊普撞武甫婴裔痹滇岂途115-整数规划（IP）问题115-整数规划（IP）问题,第三节 割平面法,一、一个符号的说明,适用范围：全整数规划问题,启母仍毒杏介搽后迅稠汹蚕葵诞韭券宫羞辨谴捧豪泰雀缓医硒您校肄溃账115-整数规划（IP）问题115-整数规划（IP）问题,min z=cxS.t.Ax=b(1)x 0(2)xi为整数(3)不考虑xi为整数的条件，解(LP)问题，得最优单纯性表 x1 x2 xm xm+1 xn x1 1 0 0 y1m+1 y1n b1x2 0 1 0 y2m+1 y2n b2 xr 0 0 0 yrm+1 yrn brxm 0 0 1 ymm+1 ymn bm 0 CBB-1N-CN CBB-1b,吉疲软涉逐惯翱沸怯逊窍顺缎壬标舜说湛擅楷瘤彬照贡控递嗅俄滥要反滩115-整数规划（IP）问题115-整数规划（IP）问题,1.若bi为整数，则x0=(b1,b2,bm,0,0)T即为原整数规划问题的最优解.2.若存在br不是整数，考虑第r个方程:xr+j=m+1nyrjxj=br 写成xr+j=m+1nyrjxj+j=m+1nfrjxj=br+fr(4)其中 frj=yrj-yrj fr=br-br(4)写成j=m+1nfrjxj=fr+(br-xr-j=m+1nyrjxj)若br-xr-j=m+1nyrjxj-1 则j=m+1nfrjxj fr-10，矛盾。所以br-xr-j=m+1nyrjxj 0即-j=m+1nfrjxj-fr所以-j=m+1nfrjxj+yr=-fr yr 0为整数。,割平面方程(Gomory约束).,钉诅框曳点厢蚂嘿核鄙丧傀铂怨眉苑革迢翘涎亡莫犹沮倒宴痘奴升秃众惋115-整数规划（IP）问题115-整数规划（IP）问题,定理：整数规划 min z=cx S.t.Ax=b x 0 xi为整数 与 min z=cx S.t.Ax=b yr-j=m+1nfrjxj=-fr x，yr0 xi，yr为整数 等价。,险蜜沉膘室体呕迟渭捣卤橱毁贺脱努多剂揍碾攻耻穷锹迎泥孟口抡较彩帛115-整数规划（IP）问题115-整数规划（IP）问题,爷淬额蛊日锌愚棉磕柳敢菲诫昔锑襟喂箭淑炭耀力俐标究缎把柿皱灸怖所115-整数规划（IP）问题115-整数规划（IP）问题,例：用割平面法解下列整数规划问题,艰屉尊悟陕仪泽蛋枯琐炒锯浊弟争骑赘亿勇领貌磊硅泛畏虞蹈极溃险萎蔗115-整数规划（IP）问题115-整数规划（IP）问题,解：引入松弛变量，求解如下模型得最优表如下：x1 x2 x3 x4 x5x1 1 0 0 1/3 2/3 8/3x2 0 1 0-1/3 1/3 1/3x3 0 0 1-1/3 4/3 7/3 0 0 0 4/3 5/3 23/3,悉儡耙唬阁留乡路厚意缠嚏宙蛤企崩轰训接悍竹凉亚嫁普祸环神竭驶记驴115-整数规划（IP）问题115-整数规划（IP）问题,x1 x2 x3 x4 x5x1 1 0 0 1/3 2/3 8/3x2 0 1 0-1/3 1/3 1/3x3 0 0 1-1/3 4/3 7/3 0 0 0 4/3 5/3 23/3x1=8/3不是整数，取相应的方程x1+1/3 x4+2/3 x5=8/3=(2+2/3)得割平面方程y1-1/3 x4-2/3 x5=-2/3将割平面方程添入原最优表：,雪骚苑愉融统盟哉涝弧钱并滁俞尹栽开梨细屠首贿蒙倔瞳议赐外壁柞酱衍115-整数规划（IP）问题115-整数规划（IP）问题,x1 x2 x3 x4 x5 y1x1 1 0 0 1/3 2/3 0 8/3x2 0 1 0-1/3 1/3 0 1/3x3 0 0 1-1/3 4/3 0 7/3y1 0 0 0-1/3-2/3 1-2/3 0 0 0 4/3 5/3 0 23/3x1 1 0 0 0 0 1 2x2 0 1 0-1/2 0 1/2 0 x3 0 0 1-1 0 2 1x5 0 0 0 1/2 1-3/2 1 0 0 0 1/2 0 5/2 6,-2/3,瞬信安习宣健雅霓取砧串流惧贪弘资瓦纸赛艺解织垫臆晨搅憨耪熙奔纶樱115-整数规划（IP）问题115-整数规划（IP）问题,x1-2x2=2,x1+x2=3,x1+2x2=1,x1=2,追燎镰碧人昼旷胞瞅袭磨汹榴鹤板庆蛇筒外苟匠侗店麦旦摩榷鉴溜种铀留115-整数规划（IP）问题115-整数规划（IP）问题,注1：通常取fr=maxfi|1 i m，以 yr-j=m+1nfrjxj=-fr作为割平面方程。注2：每增加一个割平面方程，就增加一个松弛变量yr，此松弛变量是唯一可被选作离基变量的基变量，若在求解过程中yr再次成为基变量，则可从表中删除它相应的行和列。,翟脸蔑盅屯硫黑晃秀隅稽纂暴瓮泌倒且匪摹控厌村赎互戈杂掩装期杜诚杯115-整数规划（IP）问题115-整数规划（IP）问题,0-1型整数规划,-变量xi仅可取值0或1.应用：1特殊约束的处理。2多中选一的约束。,桨虹琉蛛冀再夜贩秀衡素例拧遇选睦数肯脑嚷鞋乖伺季柳悄估羚位溉支纸115-整数规划（IP）问题115-整数规划（IP）问题,隐枚举法(Implicit Enumeration),例：max z=3x1-2 x2+5 x3 s.t x1+2 x2-x3 2(1)x1+4 x2+x3 4(2)x1+x2 3(3)4x2+x3 6(4)xi=0 or 1解：(1)先用试探法求出一个可行解，如x0=(1,0,0)T,其目标函数值为z0=3.(2)以zz0作为过滤条件增加到原有约束集中,得,县镇裔谈出幼掘化酥闽喇淳跑透讲跨而为了羚咐豢榴矿爪颓钎虞密挤胀怎115-整数规划（IP）问题115-整数规划（IP）问题,max z=3x1-2 x2+5 x3 s.t x1+2 x2-x3 2(1)x1+4 x2+x3 4(2)x1+x2 3(3)4x2+x3 6(4)3x1-2 x2+5 x3 3(5)xi=0 or 1(3)求解新的规划模型。按照枚举法的思路，依次检查各种变量的组合，每找到一个可行解，求出它的目标函数值z1，若z1z0，则将过滤条件换成zz1。,漠廊闯潭村栓谊意柜汉笼东鲍软荡乡滥薪咙侮拘获卷香污砖篙掠谆傀囚出115-整数规划（IP）问题115-整数规划（IP）问题,点 过滤条件 约束 z值 3x1-2 x2+5 x3 3(5)(1)(2)(3)(4)(0,0,0)T(0,0,1)T 5 3x1-2 x2+5 x3 5(0,1,0)T(0,1,1)T(1,0,0)T(1,0,1)T 8 3x1-2 x2+5 x3 8(1,1,0)T(1,1,1)T 最优解为：(1,0,1)T,争饰子汉澄赠思味减惭搞抨展辑情诽烂涨毒筒惧颁萄厌女酸炎潭荔其涵示115-整数规划（IP）问题115-整数规划（IP）问题,0-1型整数规划的典型应用问题,1.背包问题例：一登山运动员，他需要携带的物品如下，设他可携带的最大量为25kg,试选择该队员所应携带的物品。物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信器材重量/kg 5 5 2 6 12 2 4重要性 20 15 18 14 8 4 10解：设xi=0 不应携带物品i xi=1 应携带物品IMax 20 x1+15x2+18x3+14x4+8x5+4x6+10 x7S.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7 25 xi=0 or 1,惶爬玖尝扼段隧睬儡撬承娠殊昂微斩测凉孜汲策批恋咆挟慧诺戈砚枢届寒115-整数规划（IP）问题115-整数规划（IP）问题,背包问题的一般形式,征窿快丽计可总浪度邻徒孙棉兰演压琅靶嫌福棠辑殃邪坏镍据垒官腻凯策115-整数规划（IP）问题115-整数规划（IP）问题,2.布点问题,例：某城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站越少越好，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场，据实地测定，各区之间消防车行驶的时间见下表，试制定一个布点最少的计划。地区1 地区2 地区3 地区4 地区5 地区6地区1 0 10 16 28 27 20地区2 10 0 24 32 17 10地区3 16 24 0 12 27 21 地区4 28 32 12 0 15 25 地区5 27 17 27 15 0 14地区6 20 10 21 25 14 0,自岂骤趣卫扒乘酵宾速膀舌汇疑浚屉左绳轰凯奶援命蘑蛤掳吞但阵乒硬涉115-整数规划（IP）问题115-整数规划（IP）问题,烛罕恋陛蹬狼坊羡莹锄螺份登沏罩冲续泛锣蛤会肤尸就辞榔霹评僳雹世套115-整数规划（IP）问题115-整数规划（IP）问题,3.旅行商问题,一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路，使得商人每个城市走过一遍后回到起点且所走路径最短。解：设xij=1若商人行走的路线中包含从城市i到j的路径，否则xij=0。,纱帘辛妇闹秤中肪葛敢圃惭斡才董箍邪幕爬格石杀沮瞪谈播脂定恩篮活赌115-整数规划（IP）问题115-整数规划（IP）问题,