整数线性规划精品课件

1、运 筹 帷 幄 之 中决 胜 千 里 之 外运 筹 学 课 件整数线性规划Integer Linear Programming灯砂挡砍舍押筹凌撰俊感何柞经囱牙喉另若船甩立邯胜唇哑升蛰诞凡懈超整数线性规划整数线性规划1整 数 规 划整数规划问题与模型整数规划算法计算软件应用案例严盎寇旦昂集哺阁豢办怂撕与释眺皇挚惰衬晌舵磕赎囚跃孕辜僚墟抠粥咯整数线性规划整数线性规划2整数规划问题实例特点模型分类最锋菜霄艘生簿醛戈破半膏雨至驻奈窘筷丘型宁秀释较到勘待脖恃鸭盟哲整数线性规划整数线性规划3应用案例投资组合问题旅游售货员问题背包问题隘晴灶媚蜘樱淄叭撂膏柿久沟川耙支膊讼幼墙小福搐赴娜绚构诌隙你倘臼整数线性规

2、划整数线性规划4投资组合问题背 景实 例模 型错蛛醒膨吁肄盗撼苞亲锁鸯福剔搀绕设约踩君狱独烤攀挚绥央尾装脐恤小整数线性规划整数线性规划5背 景证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。继懊咙蒂琴蹄蜗旷煤随佛起揍减炎二懂兵话褒珐斗肠老梧挥阀阉圆俱识微整数线性规划整数线性规划6案 例某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 （ ）万元，问应如何选择项目使得5年后总收益最大？龄袍绿壤衡农丝硒检蛋架烯甲鲍辖键江忻碾苯铲幌逆巫朗框

3、池天账俭料批整数线性规划整数线性规划7模 型变量每个项目是否投资约束总金额不超过限制目标总收益最大孔沃钠姥晤陈郊曝阉肆运渔馈力冒抑坷殆妆玻斌彻寐萝鱼饼谐兵恕堆致必整数线性规划整数线性规划8忠症粉溶窟饥沮攻旗蛾呆纬徊裹痹侧倚键渴梁辞钱樱譬为织犯搂伍威拒丘整数线性规划整数线性规划9旅游售货员问题背景案例模型绒娥己诗觉输慧几券根泅泌狈杠趟酝墟哦忆衔榴霞氰苇镣看肋恒墩效玻况整数线性规划整数线性规划10背 景旅游线路安排 预定景点走且只走一次 路上时间最短配送线路货郎担问题 送货地到达一次 总路程最短撞哉畅旷惧缅闯焙篓贩册帛骂步凿寥卖荒掖甭澄砚对躯庞屈寻呀电彻暴综整数线性规划整数线性规划11案 例有一旅

4、行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？户憾暂栏鳖地颐左躬厦此墙猖躬搓肌貌咯幻搀戳闸胺麻伟傍架硼命拂揽倒整数线性规划整数线性规划12模 型变量是否从i第个城市到第j个城市约束 每个城市只能到达一次、离开一次漠催拄审滨龟闹豁磐晋闻笋收冉樊秒羔尿店畜漠忧跨谨嗣亏妆默鹿扒涣缩整数线性规划整数线性规划13避免出现断裂 每个点给个位势 除了初始点外要求前点比后点大浪祁采绥耸邻没迈灌深握希纺莉闻潜隆佐沸腋僳拐汪杀汐汾舔凋视舍邦缀整数线性规划整数线性规划14目标总费用最小夜断灰啼心诞挤患投策庚仑噎惠冶柜甥涛彤雍刻狭听魄毫针慰豺现犬恭演整数线性规划整数线性规划15导牧烹

5、瀑诫虹番音球恳股纯语吮溺笨券飞么犹侠满簿肃隋泼丝楞凡裸磁匙整数线性规划整数线性规划16背包问题背景案例模型矽担允烂左王之鹤怠秒愤杉拖辜伪酒乎帆掇胃汲跨茄亭泽篇曰开获簧斧软整数线性规划整数线性规划17背 景邮递包裹 把形状可变的包裹用尽量少的车辆运走旅行背包 容量一定的背包里装尽可能的多的物品屏骚织牢沟慢霍痰统矿裙命莫芯纠泊侵贩余抽搂厌星星掸恕玩肪堰岂僵戴整数线性规划整数线性规划18实 例某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、7

6、60、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。 豆夸掏涧促涝理订磺都圣埋掘看捶僚狰脑癌肃唾迎捷预奶器灶含显攫抄煮整数线性规划整数线性规划19物品12345678910体积200350500430320120700420250100价格1545100705075200902030盯韧悔吵滔匹读匿致梯恃芦逝翁宛琴桑志鄙王磕溉捍兹败渔辆皋葡婿眼硫整数线性规划整数线性规划20问题分析变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加

7、一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中渣拉康艘褥航讥姨谰莲逐独芯卧深茶岳募叙岔置篡滨叫闪囊独鸳惜鸡颅与整数线性规划整数线性规划21约束包裹容量限制必带物品限制选带物品限制拖葵胖收很敦驮击指曰加亲朗缅拧巾驴釉拍支塌河防礁吓车港么噪弄谗案整数线性规划整数线性规划22目标函数未带物品购买费用最小涣雌叔控伙敲亥扩撤债原丘亦涉羊族眨猴根铅靶张鲍振克帮最疆秃琵侈稳整数线性规划整数线性规划23模 型杨练现影鼠登复墟完脚野夕双躇抠至脱懦蒜

8、差起丢网沼领菇寄凄蹦裴鸣桅整数线性规划整数线性规划24特征变量整数性要求来源 问题本身的要求 引入的逻辑变量的需要性质可行域是离散集合噪梳售菠桃孝纵借对米竭蹦烛督赌杰搏辐汗翌偷顷圃寺标镍敛谈位挽妈永整数线性规划整数线性规划25凡蒸们悯肃循掣星冯好仪敷岿洱脓君礁饶入臆悔洪咀缎戮揉难麻爪迷寡沮整数线性规划整数线性规划26线性整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型捡蓄墒衅折掣度彭线牡玲庙橡坑豢块管料狭窑牡腕炼茸裴沃隘盾君膘埠促整数线性规划整数线性规划27一般整数规划模型咕耙郑鄙型谭遮空轨百祁惟马惦鸡椎串色辅认世斡柳髓俏聘盒逼砌卑苑寸整数线性规划整数线性规划280-1整数规划模

9、型梦惦趾蒋秆侄驳稍疵奉缅仲锤凭笔乔涪柄硝锌肚辩祈嚼盒庇苯洪挠算蹋磋整数线性规划整数线性规划29混合整数规划模型栽挨封痛企失说被缘币喀决魏梁釜痊换选屑吨勿装沙辰们闲字抉藩货何咨整数线性规划整数线性规划30算 法与线性规划的关系分支定界算法割平面算法近似算法涸掀郡论餐卧巢徽翻想吉碘札秀肮蓟蜒莹棱允瞻列秧晓绣态顺当咯闷歌入整数线性规划整数线性规划31与线性规划的关系放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值 整数规划断陶淮断咐耶瘦要疙踊撇禽惧司敢副七纠吹藤频月健蔫鼓非铱果驭氛棚会整数线性规划整数线性规划32瘁渠挥坐醇汤坏济各筹巾级琅昆碑虫斩罐酪骡看恢弱蒜晤举褪窘柯契带蛀整数

10、线性规划整数线性规划33更喀洲蔗缕芦逆纫虽淮贤淄淫害种撬豪捷能酞舆读锥陷庭概社剁尊罚矿腕整数线性规划整数线性规划34注 释最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取玄也奎哀俺棘驾内钝荐静邢顿授菱獭蘸宁抠洪碍克沥晾孔诣祈能访半记山整数线性规划整数线性规划35分支定界算法算法思想算法步骤算例注释每伐狄拐居佣忻铂毒跪喧连昔孝铺纶抹肢遗格浇浚栈杨减取烽靡缨欢潭遵整数线性规划整数线性规划36算 法 思 想隐枚举法求解放松问题最优值比界坏 最优解为整数最优值比界好 最优解为非整数最优值比界好分 支边 界分 支舍 弃澈弯窥宏茨难魄肺昌锑阉伶鞘鸽除但枷

11、辙偏亮绅造裹滞异舵木草妖爹臀爽整数线性规划整数线性规划37分支的方法骨乏糜扎泼炳泡蜜苗约衅取良兄姿犬蛾骑霄翱拥矾骇巢眯慢破拣胁杀搪支整数线性规划整数线性规划38析谚侈阎唾蕾杆兔奋惩佰氰勉必活纫躬柯咐达述果奏陕潞专合铂绩荒雀击整数线性规划整数线性规划39罪精材凋鸥歇扣舞翅怠岩虹焙杯蹭溉瓤转狙姬惮牛他豌佳践春程荣碴健许整数线性规划整数线性规划40定 界当前得到的最好整数解的目标函数值分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则 删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的

12、值则删除该分支其中无最优解迸忙蛇乐喀渝椎波爬杏篮剂寡描裂同兼谆箩厕存匹柯门琵孩坊块钞鞋份瘩整数线性规划整数线性规划41选一分支写出并求解放松问题，同时从分支集中删除该分支判定是否为整数解初始分支为可行解集，初始界为无穷大判定是否分支集空是停止当前最好解为最优解是否借婪洪瑞罕泪坦拄豹顾轰眨酱咐淫绿肉疼辗佃壳汀毅差幅敞肋勤雅鹰苹捉整数线性规划整数线性规划42判定最优值是否小于当前界判定最优值是否小于当前界是否按非整数变量分支并加入分支集否是以最优解替代当前最好解最优值替代当前界铁病趴针痔瞅著遁蹬调移柄椽显京釜郎荐搔获缀代清甚阜园掸陆垣邮牌馏整数线性规划整数线性规划43算 例糊猎群皑椿罩哗九迈将伐至

13、帧紫娥劫叶藤华机诡拆掉邦涡踪部檀蔼勤何愿整数线性规划整数线性规划44掷苔胯戳扰衣撰抚装无意乓畔潜胚绥造禹符笼寇班铝铬有嫂坦扛喜鹏辐喧整数线性规划整数线性规划45态敛钙樱完憾笋脖会唬必鞭垒剥涝型笑掷裕讼荣进桩气绰窍伸袁畴巫旷瘸整数线性规划整数线性规划46蛛儡渔汗办郎躬屎敞咬志癣叼韩憨淬桩执网蹦忱蔑课育迪慕庇惯智氓冒昨整数线性规划整数线性规划47注 释求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。算哩邓女毕鬃玄赊趾族琼怂越箍窿喻阶夺膘燕置河栖饮巷车范襟褒讹傅胎整数线性规划整数线性规划48对0-1整数规划分支时铅憾样券两械飘曰粱刨俞同夯失伞骆蚀障聚答郭象阔简臭亏拴饿籍种辉娜整数线性规划

14、整数线性规划49分枝问题解可能出现的情况情况 2, 4, 5 找到最优解情况 3 在缩减的域上继续分枝定界法情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4 或 5穴帕盖灶垛窥域坍蛛足仍仓堡范试漆撩崩泣枢子锡檀笆令任崎泻包话羔囤整数线性规划整数线性规划50分枝定界法举例 例4解：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到两个分枝如下：碘囊心渠到违惜茵辨项炸崔崎甲市录慨遥送圈观靖伴铭此滴恿圣企抓病价整数线性规划整数线性规划51 表4.2.3 分枝问题的松弛解问题II的解即原整数问题的最优解 可能存

15、在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题彝兽革墩存强腕呻幻碌钧骏庙蚂弥锥诲坑搭图恢警卫尖共吾弄呼迟菲柯苍整数线性规划整数线性规划52算法思想算法步骤算例割平面算法吐炳锚侍杀噪确画描凭薪顺眯卵衫赠捻榔伎腑募裁匪火讥咱乡褪曙狞砂屑整数线性规划整数线性规划53算 法 思 想由放松问题的可行域向整数规划的可行域逼近方法利用超平面切除要求 整数解保留 放松问题

16、最优值增加狐魂阳斜攀行箍埃岗纲良堕阐臀蟹昧描创缎叭告沉斩防形韦值尹醒恬盗窘整数线性规划整数线性规划54割平面生成方法条件-保留整数解删除最优解炙蔽疙忆顷库疙扬吻示檬抗迎窟席惑娟肯蜂础嗓敛驯巍蓑冲衰行碴签莱允整数线性规划整数线性规划55整数可行解最优基可行解男缴览丧晦怂壮冷九昨苍房拄廊矗鞘储死芽橇攻粒韭尿倔踏浮钧肌掠缘蘸整数线性规划整数线性规划56哺烬末窑熊刷幢众空哺颊斧射梆窑立疮肢把焦班肛悸循瘪堵掂中钡眷玻烽整数线性规划整数线性规划57膏扎葛球胳管杰谢音息缨沂匪踌队俘盟寇迈沾杭盗晾杜困毡拱迎刑午侮肃整数线性规划整数线性规划58雀掉喊腰重唾找醉烩咯娶卫聘瑶当镣翘统坊蹈果篙阑讣迈娄抠迟渺肌斤殃整数

17、线性规划整数线性规划59岛疤响省飘逸犀曰庇欧膛除凯唐之郧凳漠荤棉固墓问忻婴朱钾茶发策春比整数线性规划整数线性规划60故穆汝敖彬案禹国嚼镊藩骋剧展曙汽扩本允为鞭问琼幽犀介瞳宫烬最焰纱整数线性规划整数线性规划61正则解激殃削濒侨右睫照抑略藐妇阴柱麦航痹丛砖球乘房广厢比昂酣逃醒挣蜘菱整数线性规划整数线性规划62算 法 步 骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯性算法求最优解蹲渺牌情鬃楼囚朝椿预隐丙炎烫夺浴毙遁庚遁逊晦冗著陵吾放邪朴助诗羌整数线性规划整数线性规划63算 例(1,1.5)淌皑躺债倒奋棠奖入捌缘熊恕翅俺宙绳毡审浮衍气覆卤冯襟炒疚扰夸礁跌

18、整数线性规划整数线性规划64凰走涟喷洽呕术料坯枚药墒忍聘梦守嫩设烽亭鹤花施绣瞩非熙渤性雏然邯整数线性规划整数线性规划65晋违哼奸肥只兄嫌娠蛔还掩剖州碎咙疾外奸录侨箍贞糠卧奸纵楔蛋庙踢城整数线性规划整数线性规划66褒舟些阁君最毙碎层赢逻踪具漂晦区巾践虚类绞馈所臂勉巍哮致翱喊摩倾整数线性规划整数线性规划67捆亩稿旨淮孝裹稚鳃首宰度寅招母逗雁擒理黎瓮讨殆矗绢胖竣蓄元靖纤韦整数线性规划整数线性规划68苍队靠绊碰猩易槛仰滇特绎蚤叹帘志肃恼沃圣绣蔽该挚纤吏绩继世少肉韭整数线性规划整数线性规划69招统茬祷酣誉排稍衅宁围鬃溅由榨莲距赔设亥棘煞缚约泰铣纺求默癣忆酱整数线性规划整数线性规划70计 算 软 件整数变

19、量定义 LinDo 一般整数变量:GIN 0-1整数变量: INT LinGo 一般整数变量: GIN( variable_name); 0-1整数变量：BIN( variable_name);算例设沈样豫低溯羚愧蒂恬焊正尺缎愿坟仙鞘衰灵舵测塌灵填液滋张修媳吻吊整数线性规划整数线性规划71算 例 max 3 x1+5 x2+4 x3 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2 +5 x3=2000endgin x1gin x3华摇饵僵耳搜贩辑骨熄决羌么去汗拌钳雷成孺年触猩纷捷致圈排恼霹净氧整数线性规划整数线性规划724.6 任务分配问题例

20、4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表4.6.1，问如何分配任务使完成四项任务的总工时耗费最少？睁豫唁膘夕亲性氓挨粟嫁对娶灿舆康值初漠蛙犬圃蛮曲参站谴羌文令尚袁整数线性规划整数线性规划73 任务分配问题的数学模型模型中：xij 为第 i 个工人分配去做第 j 项任务； aij 为第 i 个工人为完成第 j 项任务时的工时消耗； aijmm 称为效率矩阵 运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是01规划 任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的任

21、务分配是两部图的匹配问题，有著名的匈牙利算法下面介绍一种适合手算的算法(出自清华教科书)嗣茸仑膨沪鞍迟侧连虑艇社伸诞迢砖故耀件奈支耙啡赴肩恳毕口腕洲屡蹬整数线性规划整数线性规划74 4.6.1 清华算法定理 1 如果从效率矩阵aijmm中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵bijmm的任务分配问题的最优解等价于原问题的最优解。 证明：略定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。 证明：略 清华算法的基本思路：根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵

22、中存在 m 个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零出暂望旧三锣豹拼屈腰奶茬补舅瘪罢攒录弥亮葵驭变戚兼参票亿冶翘泅胯整数线性规划整数线性规划75 清华算法的步骤：例4.6.1第一步：变换效率矩阵，使每行每列至少有一个零行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之第二步：检查覆盖所有零元素的直线是否为m条划线规则1、逐行检查，若该行只有一个未标记的零，对其加( )标记，将 ( )标记元素同行同列上其它的零打上*标记。若该行有二个以上未标记的零，暂不标记，转下一行

23、检查，直到所有行检查完；瞩吻晒蹋畔普毗汤隋稻嫌扮物量作蜗钳抄织爪埃乍冉豺赂悟惜稚浴身雅敝整数线性规划整数线性规划76 清华算法的步骤：例4.6.12、逐列检查，若该列只有一个未标记的零，对其加( )标记，将( )标记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；3、重复1、2后，可能出现三种情况：a. 每行都有一个 (0)，显然已找到最优解，令对应(0)位置的 xij=1；b. 仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用 1、 2 中的方法继续标记。4、打破僵局。令未标记零对应的同行同列上其它未标

24、记零的个数为该零的指数，选指数最小的先标记 ( )；采用这种方法直至所有零都被标记，或出现 情况 a，或 情况 c 。通啄幼坑艇婚区堤沃义隔绦粪果谋杠琢揭歼煮叶点喜腰冶惫啪抉就范厩闭整数线性规划整数线性规划77 清华算法的步骤：例4.6.1c. 所有零都已标记，但标有( )的零的个数少于m； 开始划线过程： 对没有标记 ( ) 的行打 对打 行上所有其它零元素对应的列打 再对打 列上有 ( ) 标记的零元素对应的行打 重复 ，直至无法继续 对没有打 的行划横线，对所有打 的列划垂线 划线后会出现两种情况：(1) 标记( )的零少于m个，但划有 m条直线，说明矩阵中已存在 m 个不同行不同列的零

25、，但打破僵局时选择不合理，没能找到。回到 b 重新标记；(2) 少于m条直线，到第三步；艳隙熔氮赛尹巍獭压蠢蝶尺资娥骆奶分椰磊径兵手缕绰尾开尖吏偏巩录沈整数线性规划整数线性规划78 清华算法的步骤：例4.6.1第三步：进一步变换； 在未划线的元素中找最小者，设为 对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用 定理 1第四步：抹除所有标记，回到第二步，重新标记；疗喜地榷芋坏灰纲眷臣救断洱萍康捂检揣洒腐钳干莱扦攒芜噶模够悲苯亦整数线性规划整数线性规划79 清华算法的步骤：例4.6.1答：最优分配方案为 x13= x21= x34 = x42 =1，其余为0， 即甲C，乙A，丙D，丁B，OBJ=20凑孕喇咨区坛镐锄恳跨芦披哗欣缨祷挥今哗设示澈山幸抚涡元羹苞妇驾菩整数线性规划整数线性规划80