整数规划带答案市公开课一等奖百校联赛获奖课件.pptx

1第八章第八章 整整 数数 规规 划划 运运运运 筹筹筹筹 学学学学第1页2第八章第八章 整数规划整数规划1整数规划图解法整数规划图解法2整数规划计算机求解整数规划计算机求解3整数规划应用整数规划应用4整数规划分枝定界法整数规划分枝定界法第2页3整整数数规规划划是是一一类类要要求求变变量量取取整整数数值值数数学学规规划划，可分成可分成线性线性和和非线性非线性两类。两类。求整数解线性规划问题，求整数解线性规划问题，应注意：应注意：不不是是用用四四舍舍五五入入法法和和去去尾尾法法对对线线性性规规划划非非整整数解加以处理就能处理。数解加以处理就能处理。整整数数线线性性规规划划一一些些基基本本算算法法设设计计是是以以对对应应线线性规划最优解为出发点性规划最优解为出发点而发展出来。而发展出来。依依据据变变量量取取值值情情况况，整整数数线线性性规规划划又又能能够够分分为为纯纯整整数数规规划划（全全部部变变量量取取非非负负整整数数），混混合合整整数数规规划划（部部分分变变量量取取非非负负整整数数），0-1整整数数规规划划（变量只取（变量只取0或或1）等。）等。第八章第八章 整数规划整数规划第3页4整整数数规规划划是是数数学学规规划划中中一一个个较较弱弱分分支支，当当前前有有成成熟熟方方法法解解线线性性整整数数规规划划问问题题，而而非非线线性性整整数数规规划问题，还没有好方法。划问题，还没有好方法。整整数数线线性性规规划划(Integer Linear Programming，简简记记为为ILP)问问题题研研究究是是要要求求变变量量取取整整数数值值时时，在在一一组组线线性性约约束束条条件件下下一一个个线线性性函函数数最最优优问问题题，是应用非常广泛运筹学一个主要分支。是应用非常广泛运筹学一个主要分支。第八章第八章 整数规划整数规划第4页51 1 整数规划图解法整数规划图解法例例1.某某企企业业拟拟用用集集装装箱箱托托运运甲甲、乙乙两两种种货货物物，这这两两种种货货物物每每件件体体积积、重重量量、可可赢赢利利润润以以及及托托运所受限制如表所表示。运所受限制如表所表示。甲甲种种货货物物至至多多托托运运4件件，问问两两种种货货物物各各托托运运多多少件，可使取得利润最大。少件，可使取得利润最大。货物货物每件体积每件体积(立方米立方米)每件重量每件重量(百千克百千克)每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140第5页6货物货物每件体积每件体积(立方米立方米)每件重量每件重量(百千克百千克)每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140解解：设设x1、x2分分别别为为甲甲、乙乙两两种种货货物物托托运运件件数数，建建立立模型。模型。目标函数：目标函数：Max z=2x1+3x2 约束条件：约束条件：s.t.195 x1+273 x2 1365 4 x1+40 x2 140 x1 4 x1，x2 0,为整数为整数。假如去掉最终一个约束，就是一个线性规划问题假如去掉最终一个约束，就是一个线性规划问题.1 1 整数规划图解法整数规划图解法第6页7利利用用图图解解法法，得得到到线线性性规规划划最最优优解解为为x1=2.44,x2=3.26,目标函数值为目标函数值为14.66。由由图图表表可可看看出出,整整数数规规划划最最优优解解（黄黄色色叉叉号号）为为x1=4,x2=2,目标函数值为目标函数值为14。Max z=2x1+3x2195x1+273x2=13654 x1+40 x2=1404231123x2x11 1 整数规划图解法整数规划图解法Max z=2x1+3x2 约束条件：约束条件：s.t.195 x1+273 x2 1365 4 x1+40 x2 140 x1 4第7页8因因为为对对应应线线性性规规划划可可行行域域包包含含了了其其整整数数规规划划可可行行点点，则则对对于于整整数数规规划划，易易知知有有以以下下性质：性质：性性质质1：任任何何求求最最大大目目标标函函数数值值纯纯整整数数规规划划或或混混合合整整数数规规划划最最大大目目标标函函数数值值小小于于或或等等于于对对应应线线性性规规划划最最大大目目标标函函数数值值；任任何何求求最最小小目目标标函函数数值值纯纯整整数数规规划划或或混混合合整整数数规规划划最最小小目目标标函函数数值值大大于于或或等等于于对对应应线线性性规规划最小目标函数值。划最小目标函数值。1 1 整数规划图解法整数规划图解法第8页9例例2：Max z=3x1+x2+3x3 s.t.-x1+2x2+x3 4 4x2-3x3 2 x1-3x2+2x3 3 x1,x2,x3 0,均为整数均为整数用用管管理理运运筹筹学学软软件件求解得：求解得：x1=5 x2=2 x3=2 2 2 整数规划计算机求解整数规划计算机求解纯整数规划问题纯整数规划问题第9页10第10页11例例3：Max z=3x1+x2+3x3 s.t.-x1+2x2+x3 4 4x2-3x3 2 x1 -3x2+2x3 3 x3 1 x1,x2,x3 0 x1，x3 为整数，为整数，x3 为为0-1变量变量用用管理运筹学管理运筹学软件求软件求解得解得:z=16.25x1=4 x2=1.25 x3=1 第11页12第12页3 3 整数规划应用整数规划应用应用实例：应用实例：投资投资场所选择问题场所选择问题 背包问题背包问题 固定成本固定成本问题问题 指派指派问题问题 分布系统设计分布系统设计 投资投资问题问题13第13页143 3 整数规划应用整数规划应用 一、投资场所选择 例4、京成畜产品企业计划在市区东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj(j=1,2,3,10)可供选择，考虑到各地区居民消费水平及居民居住密集度，规定:在东区由A1，A2，A3 三个点至多项选择择两个；在西区由A4，A5 两个点中最少选一个；在南区由A6，A7 两个点中最少选一个；在北区由A8，A9，A10 三个点中最少选两个。Aj 各点设备投资及每年可获利润因为地点不一样都是不一样，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?第14页解解：设设：0-1变变量量 xi=1(Ai 点点被被选选取取)或或 0(Ai 点点没没被被选选取取)。这么我们可建立以下数学模型：这么我们可建立以下数学模型：Max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t.100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1+x2+x3 2 x4+x5 1 x6+x7 1 x8+x9+x10 2 xi 0 且且xi 为为0-1变量变量，i=1,2,3,10在东区由A1，A2，A3 三个点至多项选择择两个；在西区由A4，A5 两个点中最少选一个；在南区由A6，A7 两个点中最少选一个；在北区由A8，A9，A10 三个点中最少选两个第15页补补充充例例、处处理理某某市市消消防防站站布布点点问问题题，该该城城市市有有6个个区区，每每个个区区都都能能够够建建消消防防站站。市市政政府府希希望望设设置置消消防防站站最最少少，但但必必须须满满足足在在城城市市任任何何地地域域发发生生火火警警时时，消消防防车车要要在在15分分钟钟内内赶赶到到现现场场。据据实实地地测测定定，各各区区之之间间消消防防车车行行驶驶时时间间以以下下表表所所表表示示，请请帮帮助助该该市市制制订订一一个最省计划。个最省计划。1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0第16页 设设 xi=1,0;1i 区区建建消消防防站站，0i 区区不不建建消消防站，防站，i=1,6min z=x1+x2+x3+x4+x5+x6约束方程确保每个地域都有一个消防站在约束方程确保每个地域都有一个消防站在15分钟行程内。分钟行程内。将将6个地域条件分别列出：个地域条件分别列出：s.t.x1+x2 1,x1+x2+x6 1 x3+x4 1,x3+x4+x5 1 x4+x5+x6 1,x2+x5+x6 1 xi=0,1;i=1,6 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0第17页18 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0第第2个地域建一个（地域个地域建一个（地域1、2、6都处理了）都处理了）第第4个地域建一个（地域个地域建一个（地域3、4、5都处理了）都处理了）第18页二、二、背包问题背包问题（补充）（补充）背背包包可可装装入入8单单位位重重量量，10单单位位体体积积物物品品。若若背背包包中中每每件件物物品品至至多多只只能能装装一一个个，怎怎样样才才能能使使背背包包装物品价值最高。装物品价值最高。物品物品 名称名称 重量重量 体积体积 价值价值 1 书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4 10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 第19页解：解：xi为是否带第为是否带第 i 种物品种物品Max Z=20 x1+30 x2+10 x3+18x4+15x55x1+3x2+x3+2x4+4x5 82x1+x2+4x3+3x4+5x5 10 xi为为0,1物品物品 名称名称 重量重量 体积体积 价值价值 1 书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4 10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 第20页普通形式：普通形式：,整整数数 xi为是否携带第为是否携带第i 种物品种物品ai为为i 物品单位重量，物品单位重量，b为最大负重为最大负重ci为为i 物品主要性估价物品主要性估价第21页223 3 整数规划应用整数规划应用三、固定成本问题三、固定成本问题 例例5高高压压容容器器企企业业制制造造小小、中中、大大三三种种尺尺寸寸金金属属容容器器，所所用用资资源源为为金金属属板板、劳劳动动力力和和机机器器设设备备，制制造造一一个个容容器器所所需需各各种种资资源源数数量量如如表表所所表表示示。不不考考虑虑固固定定费费用用，每每种种容容器器售售出出一一只只所所得得利利润润分分别别为为 4万万元元、5万万元元、6万万元元，可可使使用用金金属属板板有有500吨吨，劳劳动动力力有有300人人/月月，机机器器有有100台台/月月，另另外外不不论论每每种种容容器器制制造造数数量量是是多多少少，都都要要支支付付一一笔笔固固定定费费用用：小小号号是是l00万万元元，中中号号为为 150 万万元元，大大号号为为200万万元。元。现在要制订一个生产计划，使取得利润为最大。现在要制订一个生产计划，使取得利润为最大。第22页23解：这是一个整数规划问题。解：这是一个整数规划问题。设设x1，x2，x3 分分别别为为小小号号容容器器、中中号号容容器器和和大大号号容容器器生生产产数数量量。各各种种容容器器固固定定费费用用只只有有在在生生产产该该种种容容器器时时才才投投入入，若若不不生生产产则则没没有有这这部部分分费费用用，为为了了说说明明固固定定费费用用这这种种性性质质，设设 yi=1(当当生生产产第第 i种种容容器器,即即 xi 0 时时)或或0（当当不不生生产产第第 i种种容容器器即即 xi=0 时）。时）。引引入入约约束束 xi M yi ，i=1，2，3，M充充分分大大，以确保当以确保当 yi =0 时，时，xi=0。3 3 整数规划应用整数规划应用即：不投入固即：不投入固定费用，是不定费用，是不能投入生产能投入生产第23页24这么我们可建立以下数学模型：这么我们可建立以下数学模型：Max z=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3 500 2x1+3x2+4x3 300 x1+2x2+3x3 100 xi M yi ，i=1，2，3，M充分大充分大 xj 0 yj 为为0-1变量变量，i=1,2,33 3 整数规划应用整数规划应用没有固定投入，就不生产没有固定投入，就不生产.yi=0，则，则xi=0.xi是数量，是数量，M为一个充分大数。为一个充分大数。一个容器最少需要一个容器最少需要2个劳动个劳动力，共有力，共有300个劳动力，所个劳动力，所以容器数量不会超出以容器数量不会超出150.所所以当以当yi=1时，时，M可取可取150投入固定费用，投入固定费用，生产小号容器生产小号容器y1y2y3第24页25三、指派问题三、指派问题 有有 n n 项项不不一一样样任任务务，恰恰好好 n n 个个人人可可分分别别负负担担这这些些任任务务，但但因因为为每每人人专专长长不不一一样样，完完成成各各项项任任务务效效率率等等情情况况也也不不一一样样。现现假假设设必必须须指指派派每每个个人人去去完完成成一一项项任任务务，怎怎样样把把 n n 项项任任务务指指派派给给n n个个人人，使使得得完完成成 n n 项项任任务务总总效率最高效率最高，这就是，这就是指派问题。指派问题。3 3 整数规划应用整数规划应用第25页26例例6 6有有四四个个工工人人，要要分分别别指指派派他他们们完完成成四四项项不不一一样样工工作作，每每人人做做各各项项工工作作所所消消耗耗时时间间以以下下表表所所表表示示，问问应应怎怎样样指指派派工工作作，才才能能使使总总消耗时间为最少消耗时间为最少。3 3 整数规划应用整数规划应用第26页27解：引入解：引入01变量变量 xij，并令并令 xij=1(当当指指派派第第 i人人去去完完成成第第j项项工工作作时时)或或0(当当不不指指派派第第i人人去去完完成成第第j项项工工作作时时)这这能能够够表表示示为为一一个个0-1整数规划问题：整数规划问题：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x443 3 整数规划应用整数规划应用第27页28整数规划模型为：整数规划模型为：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1 (甲只能干一项工作甲只能干一项工作)x21+x22+x23+x24=1 (乙只能干一项工作乙只能干一项工作)x31+x32+x33+x34=1 (丙只能干一项工作丙只能干一项工作)x41+x42+x43+x44=1 (丁只能干一项工作丁只能干一项工作)x11+x21+x31+x41=1 (A工作只能一人干工作只能一人干)x12+x22+x32+x42=1 (B工作只能一人干工作只能一人干)x13+x23+x33+x43=1 (C工作只能一人干工作只能一人干)x14+x24+x34+x44=1 (D工作只能一人干工作只能一人干)xij 为为0-1变量变量，i,j=1,2,3,43 3 整数规划应用整数规划应用每人只每人只能干一能干一项工作项工作一项工一项工作只能作只能由一个由一个人干人干第28页对于有对于有m个人完成个人完成n项任务普通指派问题，项任务普通指派问题，设：设：29m不一定等于不一定等于n，当当mn时，有人时，有人没有任务。没有任务。第第i个人完成任务个人完成任务且最多负担一项且最多负担一项第第j项工作恰好有一项工作恰好有一人负担人负担注意：当注意：当m0yi=0时，当不利用第时，当不利用第i种设备生产时，此时对应种设备生产时，此时对应Xi=0目标函数为：目标函数为：Min Z=7x1+2x2+5x3+100y1+300y2+200y358第58页(1)约束条件约束条件X1 800，X2 1200，X3 1400，X1+X2+X3=(改大于等于结果相同改大于等于结果相同)0.5X1+1.8X2+1.0X3 还得确保还得确保Yi=0时，时，Xi=0.(没有准备费就不启没有准备费就不启用该设备用该设备)，引入一个很大，引入一个很大MXi M Yi（i=1,2,3）Xi 0,（i=1,2,3）Yi（i=1,2,3）是）是0-1变量变量59第59页（2）约束条件改为0.5X1+1.8X2+1.0X3 250060第60页（3）约束条件改为0.5X1+1.8X2+1.0X3 280061第61页（4）去掉电量约束条件62第62页第第5题题635：二二第63页50080070064yi是是0-1变量，变量，yi=0，相当于该，相当于该库房不存在库房不存在需求量需求量上海上海y2，武汉，武汉y40,10,01,1最多最多2个库房个库房武汉和广州不能同时建武汉和广州不能同时建i=1,2,3,4北京北京上海上海广州广州武汉武汉华北华北华中华中华南华南2第64页第第6题：指派问题题：指派问题（1）引入引入01变量变量 xij，并令并令 xij=1(当指派第当指派第i人去完成第人去完成第j项工作时项工作时)0(当不指派第当不指派第i人去完成第人去完成第j项工作时项工作时)目标函数 Min Z=20 x11+19x12+20 x13+28x14+18x21+24x22+27x23+20 x24+26x31+16x32+15x33+18x34+17x41+20 x42+24x43+19x4465第65页 x11+x12+x13+x14=1 (甲只能干一项工作甲只能干一项工作)x21+x22+x23+x24=1 (乙只能干一项工作乙只能干一项工作)x31+x32+x33+x34=1 (丙只能干一项工作丙只能干一项工作)x41+x42+x43+x44=1 (丁只能干一项工作丁只能干一项工作)x11+x21+x31+x41=1 (A工作只能一人干工作只能一人干)x12+x22+x32+x42=1 (B工作只能一人干工作只能一人干)x13+x23+x33+x43=1 (C工作只能一人干工作只能一人干)x14+x24+x34+x44=1 (D工作只能一人干工作只能一人干)66第66页（2）把目标函数改为求最大值即可，即：）把目标函数改为求最大值即可，即：Max Z=20 x11+19x12+20 x13+28x14+18x21+24x22+27x23+20 x24+26x31+16x32+15x33+18x34+17x41+20 x42+24x43+19x44约束条件不变约束条件不变67第67页（3）增加了一项工作增加了一项工作E，问应指派，问应指派四个人干四个人干哪四项工作哪四项工作，共有五项工作，则结果中必定，共有五项工作，则结果中必定有一项工作无人做。有一项工作无人做。mn，人数少于任务数。此时，添加虚拟，人数少于任务数。此时，添加虚拟人数人数n-m=1个，该人是虚拟，所以完成各项个，该人是虚拟，所以完成各项工作所需时间都设为工作所需时间都设为0.此时变为此时变为5个人完成个人完成5项工作问题了。项工作问题了。Min Z=20 x11+19x12+20 x13+28x14+17x15+18x21+24x22+27x23+20 x24+20 x25+26x31+16x32+15x33+18x34+15x35+17x41+20 x42+24x43+19x44+16x45+0 x51+0 x52+0 x53+0 x54+0 x5568甲乙丙甲乙丙丁每个丁每个人做第人做第5项工作项工作时间时间第68页约束条件 x11+x12+x13+x14+x15=1 x21+x22+x23+x24+x25=1 x31+x32+x33+x34+x35=1 x41+x42+x43+x44+x45=1 x51+x52+x53+x54+x55=1 x11+x21+x31+x41+x51=1 x12+x22+x32+x42+x52=1 x13+x23+x33+x43+x53=1 x14+x24+x34+x44+x54=1 x15+x25+x35+x45+x55=169结果中安排第结果中安排第5个虚拟人去个虚拟人去做哪项工作，做哪项工作，表明实际中该表明实际中该项工作无人做项工作无人做第69页70方法二：方法二：x11+x12+x13+x14+x15=1 (甲只能干一项工作甲只能干一项工作)x21+x22+x23+x24+x25=1 (乙只能干一项工作乙只能干一项工作)x31+x32+x33+x34+x35=1 (丙只能干一项工作丙只能干一项工作)x41+x42+x43+x44+x45=1 (丁只能干一项工作丁只能干一项工作)x11+x21+x31+x41 1 (A工作工作)x12+x22+x32+x42 1 (B工作工作)x13+x23+x33+x43 1 (C工作工作)x14+x24+x34+x44 1 (D工作工作)x15+x25+x35+x45 1 (E工作工作)Min Z=20 x11+19x12+20 x13+28x14+17x15+18x21+24x22+27x23+20 x24+20 x25+26x31+16x32+15x33+18x34+15x35+17x41+20 x42+24x43+19x44+16x45 用用普通线性规普通线性规划模块划模块求解求解第70页（4）增加了一个人，问应指派哪四个人去）增加了一个人，问应指派哪四个人去干这四项工作，必定有一个人没有工作做。干这四项工作，必定有一个人没有工作做。目标函数目标函数 Min Z=20 x11+19x12+20 x13+28x14+18x21+24x22+27x23+20 x24+26x31+16x32+15x33+18x34+17x41+20 x42+24x43+19x44+16x51+17x52+20 x53+21x5471第71页方法一：虚设一个工作，每个人完成此项工方法一：虚设一个工作，每个人完成此项工作时间设为作时间设为0.72x11+x12+x13+x14+x15=1 x21+x22+x23+x24+x25=1x31+x32+x33+x34+x35=1x41+x42+x43+x44+x45=1x51+x52+x53+x54+x55=1x11+x21+x31+x41+x51=1x12+x22+x32+x42+x52=1x13+x23+x33+x43+x53=1x14+x24+x34+x44+x54=1x15+x25+x35+x45+x55=1Min Z=20 x11+19x12+20 x13+28x14+0 x15+18x21+24x22+27x23+20 x24+0 x25+26x31+16x32+15x33+18x34+0 x35+17x41+20 x42+24x43+19x44+0 x45+16x51+17x52+20 x53+21x54+0 x55用用指派问题指派问题求求解结论解结论第72页方法二：方法二：x11+x12+x13+x14 1 (甲至多干一项工作甲至多干一项工作)x21+x22+x23+x24 1 (乙至多干一项工作乙至多干一项工作)x31+x32+x33+x34 1 (丙至多干一项工作丙至多干一项工作)x41+x42+x43+x44 1 (丁至多干一项工作丁至多干一项工作)x51+x52+x53+x54 1 (戊至多干一项工作戊至多干一项工作)x11+x21+x31+x41+x51=1 (A工作只能一人干工作只能一人干)x12+x22+x32+x42+x52=1 (B工作只能一人干工作只能一人干)x13+x23+x33+x43+x53=1 (C工作只能一人干工作只能一人干)x14+x24+x34+x44+x54=1 (D工作只能一人干工作只能一人干)73用用普通线性规划普通线性规划模块模块求解结论求解结论松弛变量为松弛变量为0，对偶价格，对偶价格也为也为0，所以，所以不止一组最不止一组最优解优解第73页第第7题题分城市讨论74 起飞起飞抵达抵达1019:0010210:0010315:0010420:0010522:00106 7:002*2x=4x3*3x=9x8*8x=64x13*13x=169x15*15x=225x10714:0019*19x=361x(次日)20*20 x=400 x(次日)25*25x=625x(次日)6*6x=36x8*8x=64x10818:0015*15x=225x(次日)16*16x=256x(次日)21*21x=441x(次日)2*2x=4x4*4x=16x10911:0022*22x=484x(次日)23*23x=529x(次日)4*4x=16x9*9x=81x11*11x=121x11019:0014*14x=196x(次日)15*15x=225x(次日)20*20 x=400 x(次日)25*25x=625x(次日)3*3x=9x101102103104105106107108109110例：例：106航班航班7:00到达到达A，让，让102航班航班10:00起飞起飞对于城市对于城市A停留停留1小时费用为小时费用为x元元第74页依此分析城市依此分析城市B，城市，城市C依据上一航班抵达时间与下一航班起飞时间依据上一航班抵达时间与下一航班起飞时间时间差，假如大于时间差，假如大于2小时，当日可起飞，不小时，当日可起飞，不然，只能次日起飞。依据停留时间，计算出然，只能次日起飞。依据停留时间，计算出每一个情况停留损失费，填入矩阵中即可利每一个情况停留损失费，填入矩阵中即可利用用“指派问题指派问题”求解。求解。最优值一定，最优解或许不唯一。最优值一定，最优解或许不唯一。75第75页