管理运筹学课件第4章-整数规划与分配问题.ppt

管理运筹学课件 1 2020 4 1 教学目标与要求 教学目标 通过本章学习 了解求解整数规划 分枝定界法 的其中思路 掌握0 1变量在数学建模中的应用 熟练掌握 匈牙利法 至少掌握一种软件求得整数规划及分配问题的最优解 知识结构 管理运筹学课件 2 2020 4 1 本章主要内容 4 1整数规划4 1 1整数规划的概念4 1 2分枝定界法的基本思路 4 20 1规划4 2 10 1规划的概念4 2 20 1规划的隐枚举法简介 4 2 40 1变量在数学建模中的用途案例4 1球队队员筛选案例4 2选址问题案例4 3集合覆盖问题4 3分配问题4 3 1分配问题数学模型4 3 2分配问题的解题方法 匈牙利法案例4 4任务分派本章小结 管理运筹学课件 3 2020 4 1 导入案例 集装箱托运计划 某厂拟用集装箱托运甲 乙两种货物 每箱的体积 质量 可获得的利润以及托运所受到的限制如表4 1所示 问怎样安排托运计划 可使利润最大 设x1 x2表示两种货物装载数量 整数 依题意有如下数学模型 在实际中 许多要求变量取整的数学模型 称为整数规划 本章将讨论整数规划求解的基本思路 0 1变量的用法 分配问题及匈牙利法 以及利用Excel Lingo WinQSB求解的演示 管理运筹学课件 4 2020 4 1 4 1 1整数规划的基本概念 整数规划 integerprogramming IP 是指一类要求问题中的全部或一部分变量为整数的数学规划 在整数规划中 依决策变量的取值不同 又可进一步划分 如果所有变量都限制为整数 则称为纯整数规划 PureIntegerProgramming PIP 如果仅一部分变量限制为整数 则称为混合整数规划 MixedIntegerProgramming MIP 变量取二进制的整数规划则称为0 1规划 BinaryIntegerProgramming BIP 管理运筹学课件 5 2020 4 1 4 1 2分枝定界法的基本思路 例4 1 用图解法求解整数规划 分枝定界法 BranchandBoundMethod 用于求解整数规划问题 是在20世纪60年代初 由LandDoig和Dakin等人提出的 解 1 绘制直角坐标系 图示约束条件 图示目标函数一根基线 z 30 使其平行移动 求得非整数最优解 该解的坐标为 72 23 88 23 不在网格线的交叉点上 非整数解 非可行解 2 对 解1 分枝定界 选取x1进行分枝定界 在原模型的基础上 分别添加x1 3 x1 4 优化结果 解2 X 3 31 8 z 38 25 解3 X 4 8 3 z 36 均为非整数 非可行解 3 先对 解2 分枝定界 解2 的坐标为 3 31 8 分别添加x2 3 x2 4 优化结果 解4 X 3 3 z 33 为可行解 解5 X 8 3 4 z 37 33 为非可行解 4 再对 解3 分枝定界 解3 的坐标 为非整数 添加x2 2 x2 3为非可行域 优化结果为X 9 2 2 z 34 5 再添加x1 4 x1 5 解得整数解X 4 2 z 32和非整数解X 21 4 1 目标值z 31 25 整数解目标值大于非整数解 取 4 2 得 解6 2 9 2 z 34 5 解3 4 8 3 解1 72 23 88 23 解2 3 31 8 5x1 6x2 30 解4 3 3 z 33 解5 8 3 4 z 37 33 解6 4 2 z 32 5 对 解5 分枝定界 解5 的坐标 8 3 4 为非整数 添加x1 2 x1 3为非可行域 优化结果为X 2 17 4 再添加x2 4和x2 5 求得整数解 2 4 目标值34 整数解 0 5 目标值30 取 2 4 如图 解7 解7 2 4 z 34 6 剪枝 上述有三个区域的整数解分别为 解4 X 3 3 z 33 解6 X 4 2 z 32 解7 X 2 4 z 34 相比较 目标值最大的为34 对应的最优方案 演示 利用WinQSB ExcelORM 规划求解 ExcelORM Lingo求例4 1 管理运筹学课件 6 2020 4 1 4 2 10 1规划的概念 0 1规划是一种特殊类型的整数规划 即决策变量只取0或1 0 1规划在整数规划中占有重要地位 许多实际问题 例如指派问题 选址问题 送货问题都可归结为此类规划 求解0 1规划的常用方法是隐枚举法 对各种特殊问题还有一些特殊方法 例如求解指派问题用匈牙利方法就比较方便 0 1规划的数学模型为 管理运筹学课件 7 2020 4 1 4 2 2隐枚举法简介 1 化成标准形式 1 目标函数 min cj 0 2 目标若max 目标系数改变符号 变为min 2 若cj 0 令yj 1 xj使其变正 3 目标函数中 变量按目标系数从小到大排列 约束条件中也跟着相应改变 2 令标准化后的0 1问题所有变量为0 若满足约束 即为最优 否则转下步 3 按目标函数中排列顺序依次令各变量分别取1或0 进行枚举 管理运筹学课件 8 2020 4 1 4 2 40 1变量在数学建模中的应用 管理运筹学课件 9 2020 4 1 案例4 1球队队员筛选 某校篮球队准备从以下6名预备队员中选拔3名为正式队员 并使平均的身高尽可能高 这六名预备队员情况如表所示 队员的挑选要满足下列条件 1 6位预备队员选3名 2 至少补充1名后卫人员 3 B或E中间最多入选1名 4 最多补充1名中锋 5 无论B或D入选 F都不能入选 管理运筹学课件 10 2020 4 1 案例4 2选址问题 某公司在城市东 西 南三区拟建立门市部 计划有7个位置 点 Aj j 1 7 可供选择 规定 在东区 由A1 A2 A3三个点至多选两个 在西区 由A4 A5两个点至少选一个 在南区 由A6 A7两个点至少选一个 设各位置建点的成本与预计利润见表 若建点总成本控制在100万元以内 试问应该选取哪几个点可使年利润为最大 数学模型为 管理运筹学课件 11 2020 4 1 案例4 3集合覆盖问题 某区有6个街道 这个区必须确定在什么地方修建消防站 在保证至少有一个消防站在每个街道的15min行驶时间内的情况下 这个区希望修建的消防站最少 各街道间行驶时间如表 管理运筹学课件 12 2020 4 1 4 3 1分配问题数学模型 在管理活动中 人们会经常遇到这样的问题 某单位有n n 1 项工作任务 需要m n 1 个人去完成 并且每个人只干一件工作 每项工作都必须有人干 通过权衡 合理分派任务 使总的消耗 或收益 达到最小 或最大 的0 1规划问题 称为分配问题 AssignmentProblem AP 导入案例运动项目分配问题某游泳队有四名运动员 其平时训练成绩 s 50m 如表所示 问如何安排可使总成绩最好 管理运筹学课件 13 2020 4 1 4 3 1分配问题数学模型 管理运筹学课件 14 2020 4 1 4 3 2匈牙利法 管理运筹学课件 15 2020 4 1 4 3 2匈牙利法 例4 7 用匈牙利法求引例中的最小化分配问题 管理运筹学课件 16 2020 4 1 4 3 2匈牙利法 例4 8 用匈牙利法求引例中的最小化分配问题 k 2 管理运筹学课件 17 2020 4 1 案例4 4任务分派