运筹与决策之4整数规划（PPT46页).ppt

1 1绪论 Introduction2线性规划 LinearProgramming3运输与指派问题 TransportationModels4整数规划 IntegerProgramming5网络模型 NetworkModels6项目计划 PERT CPM7排队论 QueueingModels8模拟 Simulation9决策分析 DecisionTheory10多目标决策 Multi objectiveDecision 管理数量方法 目录 2 授课内容 Case 分销系统设计 P192 整数规划图解法及分枝定界法MS6 0软件求解整数规划应用举例银行选址P209 讲义 消防站选址 案例讨论 课本出版P222 3 Questions 整数规划IP与线性规划LP有何不同 整数规划的分类 整数规划的求解方法 分枝定界法的基本思路 分枝问题解可能出现的情况 4 Q1 整数规划与线性规划LP区别 要求所有xj的解为整数 或者要求部分xj的解为整数 1 一般整数规划 要求所有xj的解为整数 称为纯整数规划 或者要求部分xj的解为整数 称为混合整数规划 2 0 1整数规划 它规定整数变量只能有两个值 0或1 5 Q2 整数规划的解法 图解法穷举法分枝定界法 BranchandMethod 割平面法 6 Q3 分枝定界法的基本思路 B 为 A 的线性规划松弛问题 7 C D X 最优解为非整数解 则对 B 每次分两枝 每枝多一个约束条件 8 Q4 分枝问题解可能出现的情况 如何回答 9 表分枝问题解可能出现的情况 情况2 4 5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留 用于以后与问题2的后续分枝的整数解进行比较 结论如情况4 结果 10 1绪论 Introduction2线性规划 LinearProgramming3运输问题 TransportationModels4整数规划 IntegerProgramming5网络模型 NetworkModels6项目计划 PERT CPM7排队论 QueueingModels8模拟 Simulation9决策分析 DecisionTheory10多目标决策 Multi objectiveDecision 管理数量方法 目录 11 授课内容 整数规划图解法及分枝定界法MS6 0软件求解整数规划应用举例银行选址P230 讲义 消防站选址 案例讨论 课本出版P242 12 整数规划举例 例1 家具厂生产计划问题 桌 椅各生产多少 可获最大利润 13 图解法求最优解 解 X 15 7 5 Zmax 975该解是否符合实际要求 如何求解整数解 14 4整数规划 整数规划的难度远大于一般线性规划 15 整数规划简介 要求所有xj的解为整数 称为纯整数规划要求部分xj的解为整数 称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的 最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解 16 整数规划的解法 图解法穷举法分枝定界法割平面法 17 4 1整数规划的穷举法 穷举法 可以通过计算和比较所有整数格点的值来求解 18 枚举法 x1 1 x2 1 x3 1 x4 0 枚举法 19 2100个整数解 用最现代化的计算机也要算上几亿亿年 穷举法是无法用来求解实际问题 最优解经过四舍五入的方法是否可以 若该整数规划问题有100个0 1整数变量 那么整数解有多少个 如何回答 20 4 2分枝定界法的基本思路 B 为 A 的线性规划松弛问题 21 C D X 最优解为非整数解 则对 B 每次分两枝 每枝多一个约束条件 22 分枝定界法的步骤 思路 暂不考虑整数条件 用单纯形法求解 得整数解 停 不是整数解 分枝 分枝 每次分两枝 每枝多一个约束条件 每个节点代表一个子问题 停止分枝条件 1 子问题无可行解 2 子问题得整数解 3 子问题的目标值比下界差 maxZ定界 1 初始整数规划的松弛问题的最优值是上界 2 子问题得整数解的最优值是一个下界 23 分枝问题解可能出现的情况 如何回答 24 表分枝问题解可能出现的情况 情况2 4 5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留 用于以后与问题2的后续分枝的整数解进行比较 结论如情况4 结果 25 举例 如何回答 26 松弛问题Z0 5 545X1 1 477X2 4 068 子问题1Z1 5 333X1 1X2 4 333 子问题2Z2 4 5X1 2X2 2 5 子问题3Z3 5X1 1X2 4 子问题4无可行解 分枝定界法求解过程 最优整数解X1 1X2 4最优目标函数值Z 5 27 0 1Programming BinaryIP 0 1整数规划 决策变量取值0或1 称0 1或二进制变量 0 1变量可数量化地描述诸如开与关 取与弃 有与无等现象所反映的离散变量间的逻辑关系 顺序关系以及互斥的约束条件0 1规划应用 如工厂选址 生产计划安排 旅行购物 背包问题 人员安排 代码选取 线路设计 可靠性等 28 4 3整数规划建模应用举例 0 1变量的作用 1 Xj 3 从N个方案中最多选中3个 2 从N个方案中必须选中一个 29 特殊约束的处理 1 只有方案J选中时 方案I才可能被选中 如何表示 xi xj2 方案I与方案J是否选中是同时的 xi xj3 矛盾约束 f x 5 0与f x 0 f x 5 M 1 y 与f x MyM表示很大的数 y为0 1变量 如何回答 30 特殊约束的处理 4 多个选一 fi x 0 I 1 2 n 如何表示 5 逻辑关系约束 若f x 无限制 则g x 0 若f x 0不成立 则g x 无限制 如何表示 fi x M 1 yi I 1 2 n y1 y2 yn 1 f x M 1 y g x My M表示很大的数 y为0 1变量 31 0 1整数规划模型及其应用 8 3 1资金预算 投资决策 问题8 3 2固定成本问题8 3 3配送系统设计8 3 4银行选址 覆盖问题 8 3 5产品设计与市场份额优化 32 整数规划应用举例 例华美公司有5个项目被列入投资计划 各项目的投资额和期望的投资收益见下表 该公司只有600万元资金可用于投资 由于技术上的原因 投资受到以下约束 1 在项目1 2和3中必须 只 有一项被选中 2 项目3和4只能选中一项 必须选一项 3 项目5被选中的前提是项目1必须被选中 如何在上述条件下选择一个最好的投资方案 使投资收益最大 33 项目投资收益表 Xj 1表项目j选中 Xj 0表项目j未选中 j 1 2 3 4 5 约束条件如何表示 34 计算过程 解 Xj 1表项目j选中 Xj 0表项目j未选中 j 1 2 3 4 5 Z表示总收益 则模型如下 MaxZ 150X1 210X2 60X3 80X4 180X5s t 210X1 300X2 100X3 130X4 260X5 600X1 X2 X3 1X3 X4 1X5 X1Xj 0或1 j 1 2 3 4 5 35 例解决某市消防站的布点问题 该城市共有6个区 每个都可以建消防站 市政府希望建设的消防站最少 但必须满足在城市任何地区发生火警时 消防车要在15分钟内赶到现场 据实地测定 各区之间消防车行驶的时间见下表 请帮助该市制定一个最节省的计划 消防车在各区行驶距离表 Howtosolve 36 计算过程 解 Xj 1表地区设消防站 Xj 0表地区不设消防站 Z 消防站总数 则模型如下 MinZ X1 X2 X3 X4 X5 X6s t X1 X2 1X1 X2 X6 1X3 X4 1X3 X4 X5 1X4 X5 X6 1X2 X5 X6 1Xj 0或1 j 1 2 3 4 5 6 37 银行选址P209 俄亥俄信托公司 OhioTrustCompany 希望在俄亥俄西北部20个县进行选址 该地区还没有首席业务处 PrincipalPlaceofbusinessPPB 根据俄亥俄州的银行法 如果金融企业在任何一个县设立PPB 就可以在该县及其比邻的县设立分支机构 俄亥俄信托公司想知道在那些县设立PPB会使其数量最少 38 表俄亥俄信托公司考虑的各县邻居 39 整数规划选址模型 使用OR软件对该问题进行求解 我们得出需要3个PPB 他们应分别选址在7 11 12 40 例红光服装厂可生产三种服装 西服 衬衫和羽绒服 生产不同种类的服装要使用不同的设备 红光服装厂可从专业租赁公司租用这些设备 设备租金和其他经济参数见下表 假定市场需求不成问题 服装厂每月可用工人工时为2000小时 该厂如何安排生产可使每月的利润最大 41 表产品经济参数 42 解 1 目标函数是什么 每月的利润最大 收入 租金 生产成本 2 决策变量是什么 租用与不租用设备 与租用后产品生产量是多少 3 约束条件是什么 人工工时只有2000小时 设备工时约束 43 Yj 租用第j种设备 Xj 第 种产品生产量 MaxZ 400X1 40X2 300X3 280X1 30X2 200X3 5000Y1 2000Y2 3000Y3s t 5X1 X2 4X3 20003X1 300Y10 5X2 300y22X3 300Y3Xj 0 且为整数 j 1 2 3 Yj 0或1 j 1 2 3 44 案例1课本出版P222 整数规划模型 45 课本出版计算结果 现状优化结果x2 x5 x6 1 预期销