第三章 整数线性规划.ppt

1、运 筹 学 课 件,Integer Linear Programming,内蒙古科技大学理学院应用数学系,Ch3 整 数 规 划,3.1整数规划问题与模型 3.2整数规划算法 3.3计算软件 3.4应用案例,3.1整数规划问题与模型,应用案例 特点 模型分类,应用案例,投资组合问题 旅游售货员问题 背包问题,投资组合问题,背 景 实 例 模 型,背 景,证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。 项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。,案 例,某财团有B 万元的资金，经考察选中n个投资项目，每个项目只能投资一个。其中第j 个项目需投资金

2、额为 万元，预计5年后获利 （ j=1,2,n ） 万元，问应如何选择项目使得5年后总收益最大？,模 型,变量每个项目是否投资 约束总金额不超过限制 目标总收益最大,旅游售货员问题,背景 案例 模型,背 景,旅游线路安排 预定景点走且只走一次 路上时间最短 配送线路货郎担问题 送货地到达一次 总路程最短,案 例,有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？,模 型,变量是否从i第个城市到第j个城市 约束 每个城市只能到达一次、离开一次,避免出现断裂 每个点给个位势 , 除了初始点外要求前点比后点大,目标总费用最小,背包问题,背景 案例 模型,背 景,邮

3、递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品,实 例,某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,问题分析,变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包

4、裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中,约束,包裹容量限制,必带物品限制,选带物品限制,目标函数未带物品购买费用最小,模 型,特征变量整数性要求 来源 问题本身的要求 引入的逻辑变量的需要 性质可行域是离散集合,特点,线性整数规划模型分类,一般整数规划模型 0-1整数规划模型 混合整数规划模型,一般整数规划模型,0-1整数规划模型,混合整数规划模型,2.2 整数线性规划算法,与线性规划的关系 分支定界算法 割平面算法 近似算法,与线性

5、规划的关系,整数规划,放松的线性规划,可行解是放松问题的可行解,最优值大于等于放松问题的最优值,注 释,最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 整数可行解远多于顶点，枚举法不可取,分支定界算法,算法思想 算法步骤 算例 注释,算 法 思 想,隐枚举法 求解放松问题,最优值比界坏,分 支,边 界,分 支,舍 弃,分支的方法,定 界,当前得到的最好整数解的目标函数值 分支后计算放松的线性规划的最优解 整数解且目标值小于原有最好解的值则替代原有最好解 整数解且目标值大于原有最好解的值则 删除该分支其中无最优解 非整数解且目标值小于原有最好解的值则继续分支 非整数解且目标值

6、大于等于原有最好解的值则删除该分支其中无最优解,一般步骤：记整数规划问题为A,松弛问题为B。,解问题B， 得下列几种情况： B无可行解，则问题A也无可行解，Stop B有最优解，且满足整数条件，也是A的最优解，Stop B有最优解x，但不满足整数条件。转步骤2。 2. 用观察法或在x的邻域找出A的可行解，作为当前的最优解，记目标函数值为zb,转步骤3。,3. 对于问题B，任选一个不符合整数条件的变量xj=bj，对问题B进行分支，增加两个约束条件： xjbj 和 xjbj +1，形成两个后继问题B1 和B2 ,求它们的松弛问题，得到目标函数值的上界。转步骤4 。 4. 考察所有后继问题， (a)

7、如果它的目标函数值的上界不如zb，舍去该支，转步骤4 。 (b)如果没有后继问题, 则当前最优解就是原问题的最优解，stop。 (c)寻找目标函数值的界最好的后继问题,转步骤5。,5. 处理某一个后继问题Bi，(a)如果它的最优解满足整数条件，且优于zb，则用它更新zb，转步骤4。 (b)如果它的最优解不满足整数条件，转步骤3。 也可用下面框图表示：,算 例,Min-(x1+x2),注 释,求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。,0-1变量及其应用： 0-1变量可表示逻辑关系： x=1: 采取方案。 x=0:不采取方案。 若需要从p个约束条件中， 恰好选择q个，则可引入p

8、个0-1变量：,yi=0:选择i个约束条件。 yi=1:不选择i个约束条件 那么，约束条件组为：Mi是充分大的数,0-1型整数规划的解法,n个变量有2n种组合，采用隐枚举法。 列出2n种组合，先求出一个可行解，计算目标函数值，作为当前的最优解。对于其它组合，先计算目标函数值，若不如当前的最优解，就不必检验它的可行性。 否则，如果是可行解，则把更新为当前的最优解。 采用分支定界法，搜索更快。,对0-1整数规划分支时,算法思想 算法步骤 算例,割平面算法,算 法 思 想,由放松问题的可行域向整数规划的可行域逼近 方法利用超平面切除 要求 整数解保留 放松问题最优值增加,割平面生成方法,条件-保留整

9、数解删除最优解,整数可行解,最优基可行解,算 法 步 骤,算 例,3.3计 算 软 件,整数变量定义 LinDo 一般整数变量:GIN 0-1整数变量: INT LinGo 一般整数变量: GIN( variable_name); 0-1整数变量：BIN( variable_name); 算例,算 例,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,3.4 应用案例分析,人力资源分配问题 应急设施选址问题,人力资源分配问题,某个中型百货商场对售货人

10、员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,模型假设,每天工作8小时，不考虑夜班的情况； 每个人的休息时间为连续的两天时间； 每天安排的人员数不得低于需求量，但可以超过需求量,问 题 分 析,因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用； 方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。 变量：每天开始休息的人数

11、约束条件 ： 1.每人休息时间2天，自然满足。 2. 每天工作人数不低于需求量，第i天工作的人数就是从第i-2天往前数5天内开始工作的人数，所以有约束：,3.变量非负约束：,目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于,模 型,注 解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。 定义整数变量用函数gin(x1) gin(x7); 0-1整数变量为bin(x1),应急选址问题,某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到个备选地的距离为 为了使得各

12、小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。,问题分析,该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。 变量：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设,问题分析,为了便于说明问题引入间接变量，第i小区是否由第j个中心服务 以及最远的距离 约束条件 小区服务约束,问 题 分 析,最远距离约束 中心个数约束 目标函数：最远距离 最小,模 型,隐枚举法,整数规划有时只有少数个可行解，枚举法求出最优解z*。 分支定界法：把原问题的可行解分成若干支，分别求出各支最优解，比较后可得最优解z*。假使已经求出一个可行解z ，把它作为界限z z*,如果可以判断某支的最优解不如z，那么该支中不存在最优解，不必在该支中搜索。,分支定界法的要点： 1