运筹学-第3版-课件-第3章 整数线性规划

运筹帷幄之中决胜千里之外第3章整数线性规划IntegerLinearProgramming1第3章整数线性规划

整数规划是的发展也有一段历史啦。它是数学规划的一个重要分支，可分为：纯整数规划（所有变量都限制为整数）、混合整数规划（一部分变量限制为整数）、0-1规划（所有变量都限制取0或1）。本章讨论纯整数线性规划（ILP）及解此规划的割平面法和分枝定界法。ILP问题是NP-完全问题。整数线性规划问题整数线性规划算法计算软件应用案例2§3.1整数线性规划问题整数线性规划的模型分类

纯整数规划模型

0-1整数规划模型

混合整数规划模型实例

例3.1.1投资决策问题

例3.1.3旅行售货员问题

其他背包问题解整数线性规划的困难性3纯整数规划模型40-1整数规划模型5混合整数规划模型6例3.3.1投资组合问题1.背景：证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。某财团有万元的资金，经出其考察选中个投资项目，每个项目只能投资一个。其中第个项目需投资金额为万元，预计5年后获利（）万元，问应如何选择项目使得5年后总收益最大？2.问题：7变量—每个项目是否投资约束—总金额不超过限制目标—总收益最大例3.3.1投资组合问题3.分析：8例3.3.1投资组合问题4.数学模型：9例3.1.3旅行售货员问题（TSP）1.背景:旅游线路安排预定景点走且只走一次路上时间最短配送线路—货郎担问题送货地到达一次总路程最短10有一旅行团从出发要遍游城市，已知从到的旅费为，问应如何安排行程使总费用最小？例3.1.3旅行售货员问题2.问题：113.分析：变量—是否从i第个城市到第j个城市约束—每个城市只能到达一次、离开一次例3.1.3旅行售货员问题目标—总费用最小问：是否还需要其他约束条件？12例3.1.3旅行售货员问题4.数学模型：此约束是为了避免出现断裂，每个点给个位势，除了初始点外要求前点比后点大13背包问题背景案例模型14背景邮递包裹把形状可变的包裹用尽量少的车辆运走旅行背包容量一定的背包里装尽可能的多的物品15某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。

物品12345678910体积200350500430320120700420250100价格154510070507520090203016问题分析变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中17约束包裹容量限制必带物品限制选带物品限制18目标函数—未带物品购买费用最小19模型20特征—变量整数性要求来源

问题本身的要求引入的逻辑变量的需要性质—可行域是离散集合2.解整数线性规划的困难性21与线性规划的关系：整数规划可行解是松弛问题的可行解最优值大于等于松弛问题的最优值2.解整数线性规划的困难性松弛的线性规划问题222.解整数线性规划的困难性23最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多于松弛问题的顶点，枚举法不可取解ILP问题要远难于解松弛的LP问题如果松弛的LP问题无解，显然原ILP问题无解。反之，不一定成立。如果松弛的LP问题无界呢？可以证明原ILP问题也无界2.解整数线性规划的困难性结论24整数线性规划算法§3.2Gomory割平面算法§3.3分支定界算法近似算法25§3.2Gomory割平面算法割平面法是求解整数规划的一个最早提出的方法，基本思想是在与整数规划相对应的线性规划中逐步增加线性约束条件（称为割平面），每次增加一个割平面，都使线性规划的可行域缩小，同时保持整数规划的可行解集合不变；然后来求解增加约束后的线性规划，如果得到整数规划的最优解则停止；如果没有找到整数最优解，就再增加割平面，一直到得到或证明无整数最优解为止。26§3.2Gomory割平面算法整数规划松弛的线性规划问题(P)(P0)两个问题具有如下明显关系：(1)(P)的可行域(P0)的可行域;(2)若(P0)无可行解，则(P)无可行解；(3)(P0)的最优值是(P)的最优值得一个下界；(4)若(P0)的最优解是整数向量，则它也是(P)的最优解.271.算法的基本思想：由松弛问题的可行域向整数规划的可行域逼近方法—利用超平面切除要求整数解保留松弛问题最优值增加§3.2Gomory割平面算法28割

平

面

生

成

方

法条件--保留整数解删除最优解!!下面是求松弛问题的最后一张单纯形表：§3.2Gomory割平面算法29整数可行解最优基可行解30–加入松弛变量s—割平面31§3.2Gomory割平面算法32§3.2Gomory割平面算法33§3.2Gomory割平面算法34§3.2Gomory割平面算法35§3.2Gomory割平面算法36正则解§3.2Gomory割平面算法37算法步骤求松弛问题的最优基可行解判断是否为整数解是得到最优解否在单纯性表中加入一列利用对偶单纯性算法求最优解38算例(1,1.5)39算例40算例41算例42算例43算例44算例45§3.3分支定界法分枝定界法是一种隐枚举法，是一种“巧妙”地枚举整数规划问题的可行解的思想来设计算法的，其关键步骤是分枝和定界。分枝定界法可用于解纯整数或混合的整数规划问题。本世纪六十年代初由LandDoig和Dakin等人提出。由于这种方法灵活且便于用计算机求解，所以现在它是解整数规划的主要方法。461.算法思想隐枚举法求解松弛问题最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好分支边界分支舍弃§3.3分支定界法47§3.3分支定界法条件--保留整数解删除最优解!!下面是求松弛问题的最后一张单纯形表：48§3.3分支定界法2.分支的方法:49§3.3分支定界法3.分支方法的示意图:50定界当前得到的最好整数解的目标函数值分支后计算松弛的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解51选一分支写出并求解松弛问题，同时从分支集中删除该分支判定是否为整数解初始分支为可行解集，初始界为无穷大判定是否分支集空是当前最好解为最优解是否判定最优值是否小于当前界判定最优值是否小于当前界按非整数变量分支并加入分支集以最优解替代当前最好解最优值替代当前界否是是否52算例53545556注释求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。57对0-1整数规划分支时58计算软件整数变量定义

LinDo

一般整数变量:GIN<Variable>0-1整数变量:INT<Variable>

LinGo

一般整数变量:@GIN(variable_name);0-1整数变量：@BIN(variable_name);算例59算例

max3x1+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000endginx1ginx360应用案例分析人力资源分配问题应急设施选址问题61人力资源分配问题某个中型百货商场对售货人员（周工资200元）的需求经统计如下表

为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？星期一二三四五六七人数1215121416181962模型假设每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量63问题分析因素不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量每天开始休息的人数约束条件

1.每人休息时间2天，自然满足。

64

3.变量非负约束：65目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于66模型67注解该问题本质上是个整数规划问题，松弛的线性规划的最优解是个整数解，所以两规划等价。定义整数变量用函数@gin(x1)……@gin(x7);

0-1整数变量为@bin(x1)68应急选址问题

某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到个备选地的距离为为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。69问题分析

该问题与传统的选址问题的