运筹学整数线性规划.pptx

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