《运筹学》教学课件 第3章 整数线性规划.ppt

运 筹 帷 幄 之 中;第3章 整数线性规划;§3.1 整数线性规划问题;纯整数规划模型;0-1整数规划模型;混合整数规划模型;例3.3.1 投资组合问题;变量—每个工程是否投资 约束—总金额不超过限制 目标—总收益最大;例3.3.1 投资组合问题;例3.1.3 旅行售货员问题〔TSP〕; 有一旅行团从 出发要遍游城市 ，从 到 的旅费为 ，问应如何安排行程使总费用最小？;3.分析：;例3.1.3 旅行售货员问题;背包问题;背 景;某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、〔单位毫升〕。尚有10件可带可不带物品，如果不带将在目的地购置，通过网络查询可以得知其在目的地的价格〔单位美元〕。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。 ;问题分析;约束;目标函数—未带物品购置费用最小;模 型;特征—变量整数性要求 来源 问题本身的要求 引入的逻辑变量的需要 性质—可行域是离散集合;与线性规划的关系：;2. 解整数线性规划的困难性;最优解不一定在顶点上到达 最优解不一定是松弛问题最优解的邻近整数解 整数可行解远多于松弛问题的顶点，枚举法不可取 解ILP问题要远难于解松弛的LP问题 如果松弛的LP问题无解，显然原ILP问题无解。反之，不一定成立。 如果松弛的LP问题无界呢？可以证明原ILP问题也无界;整数线性规划算法;§3.2 Gomory割平面算法;§3.2 Gomory割平面算法;1. 算法的根本思想：;割平面生成方法;整数可行解;–;§3.2 Gomory割平面算法;§3.2 Gomory割平面算法;§3.2 Gomory割平面算法;§3.2 Gomory割平面算法;§3.2 Gomory割平面算法;正则解;算 法 步 骤;算 例;算 例;算 例;算 例;算 例;算 例;算 例;§3.3 分支定界法;1. 算法思想;§3.3 分支定界法;§3.3 分支定界法;§3.3 分支定界法;定 界;选一分支写出并求解松弛问题， 同时从分支集中删除该分支;算 例;注 释;对0-1整数规划分支时;计 算 软 件;算 例;应用案例分析;人力资源分???问题;模型假设;问题分析; 3.变量非负约束：;目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于;模 型;注 解;应急选址问题;问题分析;问题分析;问 题 分 析;模 型