运筹学 整数线性规划.ppt

第,*,页,运 筹 帷 幄 之 中,决 胜 千 里 之 外,运 筹 学 课 件,整数线性规划,Integer Linear Programming,1,整 数 规 划,整数规划问题与模型,整数规划算法,计算软件,应用案例,2,整数规划问题,实例,特点,模型分类,3,应用案例,投资组合问题,旅游售货员问题,背包问题,4,投资组合问题,背 景,实 例,模 型,5,背 景,证券投资,：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。,项目投资,：财团或银行把资金投入到若干项目中以获得中长期的收益最大,。,6,案 例,某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 （）万元，问应如何选择项目使得5年后总收益最大？,7,模 型,变量,每,个项目是否投资,约束,总,金额不超过限制,目标,总收益最大,8,9,旅游售货员问题,背景,案例,模型,10,背 景,旅游线路安排,预定景点走且只走一次,路上时间最短,配送线路货郎担问题,送货地到达一次,总路程最短,11,案 例,有一旅行团从 出发要遍游城市,，已知从 到 的旅费为 ，问应如何安排行程使总费用最小,？,12,模 型,变量,是,否从,i,第个城市到第,j,个城市,约束,每个城市只能到达一次、离开一次,13,避免出现断裂,每个点给个位势 除了初始点外要求前点比后点大,14,目标,总,费用最小,15,16,背包问题,背景,案例,模型,17,背 景,邮递包裹,把形状可变的包裹用尽量少的车辆运走,旅行背包,容量一定的背包里装尽可能的多的物品,18,实 例,某人出国留学打点行李，现有三个旅行包，容积大小分别为1,000,毫升、1,500,毫升和2,000,毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有,7,件，其体积大小分别为,400,、,300,、,150,、,250,、,450,、,760,、,190,、（单位毫升）。尚有,10,件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,19,物品,1,2,3,4,5,6,7,8,9,10,体积,200,350,500,430,320,120,700,420,250,100,价格,15,45,100,70,50,75,200,90,20,30,20,问题分析,变量,对,每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为,第,i,个物品是否放在,第,j,个包裹,中,21,约束,包裹容量限制,必带物品限制,选带物品限制,22,目标函数,未,带物品购买费用最小,23,模 型,24,特征,变,量整数性要求,来源,问题本身的要求,引入的逻辑变量的需要,性质,可,行域是离散集合,25,26,线性整数规划模型,一般整数规划模型,0-1整数规划模型,混合整数规划模型,27,一般整数规划模型,28,0-1整数规划模型,29,混合整数规划模型,30,算 法,与线性规划的关系,分支定界算法,割平面算法,近似算法,31,与线性规划的关系,整数规划,放松的线性规划,可行解是放松问题的可行解,最优值大于等于放松问题的最优值,32,33,34,注 释,最优解不一定在顶点上达到,最优解不一定是放松问题最优解的邻近整数解,整数可行解远多余于顶点，枚举法不可取,35,分支定界算法,算法思想,算法步骤,算例,注释,36,算 法 思 想,隐枚举法,求解放松问题,最优值比界坏,最优解为整数最优值比界好,最优解为非整,数最优值比界好,分 支,边,界,分 支,舍 弃,37,分支的方法,38,39,40,定 界,当前得到的最好整数解的目标函数值,分支后计算放松的线性规划的最优解,整数解且目标值小于原有最好解的值则替代原有最好解,整数解且目标值大于原有最好解的值则 删除该分支其中无最优解,非整数解且目标值小于原有最好解的值则继续分支,非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解,41,选一分支写出并求解,放松问题，同时从分,支集中删除该分支,判,定是否,为整数,解,初始分支为可行解,集，初始界为无穷大,判,定是否,分支集,空,是,停止,当前最好解,为最优解,是,否,42,判定最,优值是否,小于,当前界,判定最,优值是否,小于,当前界,是,否,按非整数变量分,支并加入分支集,否,是,以最优解替代当前最,好解最优值替代当前界,43,算 例,44,45,46,47,注 释,求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。,48,对0-1整数规划分支时,49,算法思想,算法步骤,算例,割平面算法,50,算 法 思 想,由放松问题的可行域向整数规划的可行域逼近,方法,利,用超平面切除,要求,整数解保留,放松问题最优值增加,51,割平面生成方法,条件,-保留整数解删除最优,解,52,整数可行解,最优基可行解,53,54,55,56,57,58,正则解,59,算 法 步 骤,求放松问题的,最优基可行解,判断是否,为整数解,是,停止,得到最优解,否,在单纯性表中加入,一列利用对偶单纯,性算法求最优解,60,算,例,(1,1.5),61,62,63,64,65,66,67,计 算 软 件,整数变量定义,LinDo,一般整数变量:,GIN,0-1,整数变量:,INT,LinGo,一般整数变量:,GIN(variable_name);,0-1,整数变量：,BIN(variable_name);,算例,68,算 例,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=2000,end,gin x1,gin x3,69,应用案例分析,人力资源分配问题,应急设施选址问题,70,人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表,为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,星期,一,二,三,四,五,六,七,人数,12,15,12,14,16,18,19,71,模型假设,每天工作8小时，不考虑夜班的情况；,每个人的休息时间为连续的两天时间；,每天安排的人员数不得低于需求量，但可以超过需求量,72,问题分析,因素,不可变因素,：需求量、休息时间、单位费用；,可变因素,：安排的人数、每人工作的时间、总费用；,方案,确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。,变量,每天开始休息的人数,约束条件,1.,每人休息时间,2,天，自然满足。,73,3.变量非负约束：,74,目标函数,：,总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于,75,模 型,76,注 解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。,定义整数变量用函数,gin,(x1),gin,(x7);,0-1,整数变量为,bin(x1,),77,应急选址问题,某城市要在市区设置,k,个,应急服务中心,经过初步筛选确定了,m,个备选地，现已知共有,n,个居民小区，各小区到个备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。,78,问题分析,该问题与传统的选址问题的,主要区别,在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。,变量,：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设,79,问题分析,为了便于说明问题引入间接变量，第,i,小区是否由第,j,个中心服务,以及最远的距离,约束条件,小区服务约束,80,问 题 分 析,最远距离约束,中心个数约束,目标函数,：最远距离 最小,81,模 型,82,