整数规划实例.ppt

1、整 数 规 划,整数规划,整数规划问题与模型 整数规划算法 计算软件 应用案例,运筹学课件,整数规划,整数规划问题,实例 特点 模型分类,运筹学课件,整数规划,应用案例,投资组合问题 旅游售货员问题 背包问题,整数规划,投资组合问题,背 景 实 例 模 型,整数规划,背景,证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润 项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。,整数规划,案例,某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 万元 ，问应如何选择项目使得5年后总收益最大？,

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

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

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

5、模型,返回,算 法,与线性规划的关系 分支定界算法 割平面算法 近似算法,返回,与线性规划的关系,整数规划,放松的线性规划,可行解是放松问题的可行解,最优值大于等于放松问题的最优值,注释,最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 整数可行解远多余于顶点，枚举法不可取,分支定界算法,算法思想 算法步骤 算例 注释,算法思想,隐枚举法 分支 求解放松问题 舍弃 变界 分支,最优值比界坏,最优解为整数最优值比界好,最优解为非整数最优值比界好,分支的方法,定界,当前得到的最好整数解的目标函数值 分支后计算放松的线性规划的最优解 整数解且目标值小于原有最好解的值则替代原有最好解

6、 整数解且目标值大于原有最好解的值则 删除该分支其中无最优解 非整数解且目标值小于原有最好解的值则继续分支 非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解,选一分支写出并求解 放松问题，同时从分支集 中删除该分支,判定是否 为整数解,初始分支为可行解 集，初始界为无穷大,判定是否 分支集空,是停止,当前最好解 为最优解,是,否,判定最优值是否 小于当前界,判定最优值是否 小于当前界,是,否,按非整数变量分 支并加入分支集,否,是,以最优解替代当前最 好解最优值替代当前界,算例,注释,求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。,对0-1整数规划分支时,算法思想

7、算法步骤 算例,割平面算法,算法思想,由放松问题的可行域向整数规划的可行域逼近 方法利用超平面切除 要求 整数解保留 放松问题最优值增加,返回,割平面生成方法,条件-保留整数解删除最优解,整数可行解,最优基可行解,正则解,算法步骤,求放松问题的 最优基可行解,判断是否 为整数解,是停止,得到最优解,否,在单纯性表中加入一列 利用对偶单纯性算法 求最优解,算 例,(1,1.5),计算软件,整数变量定义 LinDo 一般整数变量:GIN 0-1整数变量: INT LinGo 一般整数变量: GIN( variable_name); 0-1整数变量：BIN( variable_name); 算例,算

8、 例,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,model: max=3*x1+5*x2+4*x3; 2*x1+3*x2=1500; 2*x2+4*x3=800; 3*x1+2*x2+5*x3=2000; gin(x1); gin(x3); end,Global optimal solution found at iteration: 3 Objective value: 2675.000 Variable Value Reduced Cos

9、t X1 375.0000 0.3333333 X2 250.0000 0.000000 X3 75.00000 -4.000000,应用案例分析,人力资源分配问题 应急设施选址问题,人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,返回,模型假设,每天工作8小时，不考虑夜班的情况； 每个人的休息时间为连续的两天时间； 每天安排的人员数不得低于需求量，但可以超过需求量,问题分析,因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人

10、数、每人工作的时间、总费用； 方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。 变量：每天开始休息的人数 约束条件 ： 1.每人休息时间2天，自然满足。,3.变量非负约束：,目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于,模型,计算,model: min=200*x1+200*x2+200*x3+200*x4+200*x5+200*x6+200*x7; x2+x3+x4+x5+x6=12; x3+x4+x5+x6+x7=

11、15; x1+x4+x5+x6+x7=12; x1+x2+x5+x6+x7=14; x1+x2+x3+x6+x7=16; x1+x2+x3+x4+x7=18; x1+x2+x3+x4+x5=19; gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7); End,返回,Global optimal solution found at iteration: 9 Objective value: 4400.000 Variable Value Reduced Cost X1 5.000000 0.000000 X2 2.000000 0.00

12、0000 X3 8.000000 0.000000 X4 0.000000 0.000000 X5 4.000000 0.000000 X6 0.000000 66.66667 X7 3.000000 0.000000,注解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。 定义整数变量用函数gin(x1) gin(x7); 0-1整数变量为bin(x1),应急选址问题,某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到个备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。,问题分析,该问题与传统的选址问题的主要区别在于其