运筹学中的运输问题ppt.ppt

运输问题和指派问题TheTransportation andAssignmentProblems 本章内容要点 运输问题的基本概念及其各种变形的建模与应用 指派问题的基本概念及其各种变形的建模与应用 本章节内容 1运输问题基本概念2运输问题数学模型和电子表格模型3各种变形的运输问题建模4运输问题应用举例5指派问题6各种变形的指派问题建模 产大于销 总产量大于总销量 运输问题数学模型和电子表格模型 各种变形的建模 应用举例 指派问题数学模型和电子表格模型 本章主要内容框架图 产销平衡 总产量等于总销量 销大于产 总产量小于总销量 运输问题和指派问题 平衡指派问题 总人数等于总任务数 各种变形的建模 1运输问题 运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方 要求所采用的运输路线或运输方案是最经济或成本最低的 这就成为了一个运筹学问题 随着经济的不断发展 现代物流业蓬勃发展 如何充分利用时间 信息 仓储 配送和联运体系创造更多的价值 向运筹学提出了更高的挑战 要求科学地组织货源 运输和配送使得运输问题变得日益复杂 但是其基本思想仍然是实现现有资源的最优化配置 1运输问题基本概念 一般的运输问题就是解决如何把某种产品从若干个产地调运到若干个销地 在每个产地的供应量和每个销地的需求量已知 并知道各地之间的运输单价的前提下 如何确定一个使得总的运输费用最小的方案 平衡运输问题的条件 1 明确出发地 产地 目的地 销地 供应量 产量 需求量 销量 和单位成本 2 需求假设 每一个出发地都有一个固定的供应量 所有的供应量都必须配送到目的地 与之类似 每一个目的地都有一个固定的需求量 整个需求量都必须由出发地满足 即 总供应 总需求 3 成本假设 从任何一个出发地到任何一个目的地的货物配送成本与所配送的数量成线性比例关系 因此成本就等于配送的单位成本乘以所配送的数量 目标函数是线性的 1运输问题基本概念 例1某公司有三个加工厂A1 A2 A3生产某产品 每日的产量分别为 7吨 4吨 9吨 该公司把这些产品分别运往四个销售点B1 B2 B3 B4 各销售点每日销量分别为 3吨 6吨 5吨 6吨 从各工厂到各销售点的单位产品运价如表1所示 问该公司应如何调运这些产品 在满足各销售点的需要量的前提下 使总运费最少 表1各工厂到各销售点的单位产品运价 元 吨 B1 B2 B3 B4 产量 吨 749 A1A2A3销量 吨 3173 11946 32105 10856 对于例1 其数学模型如下 首先 三个产地A1 A2 A3的总产量为7 4 9 20 四个销地B1 B2 B3 B4的总销量为3 6 5 6 20 由于总产量等于总销量 故该问题是一个产销平衡的运输问题 1 决策变量 设xij为从产地Ai运往销地Bj的运输量 i 1 2 3 j 1 2 3 4 2 目标函数 本问题的目标是使得总运输费最小 Minz 3x11 11x12 3x13 10 x14 x21 9x22 2x23 8x24 7x31 4x32 10 x33 5x34 3 约束条件 满足产地产量 3个产地的产品都要全部配送出去 满足销地销量 4个销地的产品都要全部得到满足 非负 2运输问题数学模型和电子表格模型 运输问题是一种特殊的线性规划问题 一般采用 表上作业法 求解运输问题 但Excel的 规划求解 工具还是采用 单纯形法 来求解 例1的电子表格模型 2运输问题数学模型和电子表格模型 1 产销平衡运输问题的数学模型具有m个产地Ai i 1 2 m 和n个销地Bj j 1 2 n 的运输问题的数学模型为 2运输问题数学模型和电子表格模型 需要注意的是 运输问题有这样一个性质 整数解性质 只要它的供应量和需求量都是整数 任何有可行解的运输问题必然有所有决策变量都是整数的最优解 因此 没有必要加上所有变量都是整数的约束条件 由于运输量经常以卡车 集装箱等为单位 如果卡车不能装满的话 就很不经济了 整数解性质就避免了运输量 运输方案 为小数的麻烦 以满足小的产量为准 ij 3 销大于产 供不应求 运输问题 2运输问题数学模型和电子表格模型例2某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如表所示 如果生产出来的柴油机当季不交货的 每台每积压一个季度需储存 维护等费用1500元 要求在完成合同的情况下 做出使该厂全年生产 包括储存 维护 费用最小的决策 各季度的生产能力及生产每台柴油机的成本 季度 生产能力 台 单位成本 万元 1234 25353010 10 811 111 011 3 2运输问题数学模型和电子表格模型 解 这是一个生产与储存 库存 问题 可以转化为运输问题来做 由于每个季度生产出来的柴油机不一定当季交货 所以设xij为第i季度生产的第j季度交货的柴油机数 则第i季度生产的第j季度交货的每台柴油机的实际成 本cij为 cij 第i季度每台的生产成本 0 15 j i 储存 维护等费用 把第i季度生产的柴油机数看作第i个生产厂商的产量 把第j季度交货的柴油机数看作第j个销售点的销量 生产成本加储存 维护等费用看作运费 将生产与储存问题转化为运输问题 相关数据见表 2运输问题数学模型和电子表格模型柴油机生产的相关数据 由表可知 总产量 生产能力 为25 35 30 10 100 总销量 需求量 为10 15 25 20 70 因此是产大于销的运输问题 1 2 3 4 生产能力 10 8 10 9511 10 123 11 1011 2511 00 11 2511 4011 15 253530 4 11 30 10 需求量 10 15 25 20 该生产与储存问题 转化为产大于销的运输问题 的数学模型为 2运输问题数学模型和电子表格模型Minz 10 80 x11 10 95x12 11 10 x13 11 25x14 11 10 x22 11 25x23 11 40 x24 11 00 x33 11 15x34 11 30 x44 2运输问题数学模型和电子表格模型 例2的电子表格模型 2运输问题数学模型和电子表格模型例3某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如表所示 问应如何调运 可使得总运输费最小 例3运输费用表 B1 B2 B3 产量 A1A2销量 131153 152936 122265 7845 销大于产 2运输问题数学模型和电子表格模型 解 由表知 总产量为78 45 123 总销量为 53 36 65 154 销大于产 供不应求 数学模型如下 设xij为产地Ai运往销地Bj的物品数量 2运输问题数学模型和电子表格模型 例3的电子表格模型 3各种变形的运输问题建模 现实生活中符合产销平衡运输问题每一个条件的情况很少 一个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件的运输问题却经常出现 下面是要讨论的一些特征 1 总供应大于总需求 每一个供应量 产量 代表了从其出发地中配送出去的最大数量 而不是一个固定的数值 2 总供应小于总需求 每一个需求量 销量 代表了在其目的地中所接收到的最大数量 而不是一个固定的数值 3 一个目的地同时存在着最小需求和最大需求 于是所有在这两个数值之间的数量都是可以接收的 4 在配送中不能使用特定的出发地 目的地组合 xij 0 5 目标是使与配送数量有关的总利润最大而不是使总成本最小 Min Max 3各种变形的运输问题建模例4某公司决定使用三个有生产余力的工厂进行四种新产品的生产 每单位产品需要等量的工作 所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量 见表的最右列 而每种产品每天有一定的需求量 见表的最后一行 每家工厂都可以制造这些产品 除了工厂2不能生产产品3以外 然而 每种产品在不同工厂中的单位成本是有差异的 如表所示 现在需要决定的是在哪个工厂生产哪种产品 可使总成本最小 表产品生产的有关数据单位成本 元 生产能力 产品1 产品2 产品3 产品4 757545 工厂1工厂2工厂3需求量 41403720 27293030 28 2730 24232140 2020 3 17 25 可编辑 解 指定工厂生产产品可以看作运输问题来求解 本题中 工厂2不能生产产品3 这样可以增加约束条件 并且 总供应x23 0 75 75 45 195 总需求 20 30 30 40 120 其数学模型如下 设xij为工厂i生产产品j的数量 3各种变形的运输问题建模 3各种变形的运输问题建模 例4的电子表格模型 产品4分在2个工厂生产 3各种变形的运输问题建模例5某公司在3个工厂中专门生产一种产品 在未来的4个月中 有四个处于国内不同区域的潜在顾客 批发商 很可能大量订购 顾客1是公司最好的顾客 所以他的全部订购量都应该满足 顾客2和顾客3也是公司很重要的顾客 所以营销经理认为作为最低限度至少要满足他们订单的1 3 对于顾客4 销售经理认为并不需要进行特殊考虑 由于运输成本上的差异 销售一个产品得到的净利润也不同 很大程度上取决于哪个工厂供应哪个顾客 见表 问应向每一个顾客供应多少货物 以使公司总利润最大 表4 8工厂供应顾客的相关数据 产量 单位利润 元 顾客1顾客2 顾客3 顾客4 800050007000 工厂1工厂2工厂3最小采购量最大采购量 55372970007000 42185930009000 46325120006000 53483508000 3各种变形的运输问题建模 解 该问题要求满足不同顾客的需求 采购量 解决办法 实际供给量 最小采购量实际供给量 最大采购量目标是利润最大 而不是成本最小 其数学模型如下 设xij为工厂i供应给顾客j的产品数量 3各种变形的运输问题建模 例5的电子表格模型 4运输问题应用举例例6某厂生产设备是以销定产的 已知1 6月份各月的生产能力 合同销量和单台设备平均生产费用 如表所示 已知上年末库存103台 如果当月生产出来的设备当月不交货 则需要运到分厂库房 每台增加运输成本0 1万元 每台设备每月的平均仓储费 维护费为0 2万元 7 8月份为销售淡季 全厂停产1个月 因此在6月份完成销售合同后还要留出库存80台 加班生产设备每台增加成本1万元 问应如何安排1 6月份的生产 使总的生产 包括运输 仓储 维护 费用最少 月份1月2月3月4月5月6月 正常生产能力 台 60509010010080 加班生产能力 台 101020404040 合同销量 台 1047511516010370 单台费用 万元 151413 5131313 5 4运输问题应用举例 例7华中金刚石锯片厂有两条生产线 分别生产直径900 1800mm大锯片基体20000片 直径350 800mm中小锯片基体40000片 公司在全国有25个销售网点 主要销售区域集中在福建 广东 广西 四川 山东5个石材主产区 为完成总厂的要求 公司决定一方面拿出10 的产量稳定与前期各个客户的联系以保证将来的市场区域份额 另一方面 面临如何将剩余的90 的产量合理分配给五个石材主产区和其他省区 以获取最大的利润 各个销售区的最低需求 销售固定费用 每片平均运费 每片从总厂库房的购进价与当地的销售价差贡献等自然情况见表 问应如何分配给各个销售区 才能使得总利润为最大 4运输问题应用举例 5指派问题 在现实生活中 经常会遇到指派人员做某项工作 任务 的情况 指派问题的许多应用是用来帮助管理人员解决如何为一项即将开展的工作指派人员的问题 其他的一些应用如为工作指派机器 设备或工厂等 指派问题也称分配问题 主要研究人和工作 任务 间如何匹配 以使所有工作完成的效率实现最优化 形式上 指派问题给定了一系列所要完成的工作以及一系列完成工作的人员 所需要解决的问题就是要确定出指派哪个人去完成哪项工作 5指派问题 指派问题的假设 1 人的数量和工作的数量相等 2 每个人只能完成一项工作 3 每项工作只能由一个人来完成 4 每个人和每项工作的组合都会有一个相关的成本 单位成本 5 目标是要确定如何指派才能使总成本最小 设决策变量xij为第i个人做第j项工作 而已知 5指派问题 目标函数系数cij为第i个人完成第j项工作所需 要的单位成本 平衡指派问题的数学模型为 5指派问题 需要说明的是 指派问题实际上是一种特殊的运输问题 其中出发地是人 目的地是工作 只不过 每一个出发地的供应量都为1 因为每个人都要完成一项工作 每一个目的地的需求量都为1 因为每项工作都要完成 由于运输问题有 整数解性质 因此 没有必要加上所有决策变量都是0 1变量的约束 指派问题是一种特殊的线性规划问题 有一种快捷的求解方法 匈牙利方法 HungarianMethod 但Excel的 规划求解 工具还是采用 单纯形法 来求解 5指派问题例8某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议 为了更好地安排这次会议 他安排小张 小王 小李 小刘等四个人 每个人负责完成下面的一项工作 A B C和D 由于每个人完成每项任务的时间和工资不同 如表所示 问如何指派 可使总成本最小 人员 每小时工资 元 每一项工作所需要的时间 小时 工作A工作B工作C工作D 小张小王小李小刘 35473932 41455651 27323625 40514346 14121315 5指派问题 解 该问题是一个典型的指派问题 单位成本为每个人做每项工作的总 工资 目标是要确定哪个人做哪一项工作 使总成本最小 供应量为1代表每个人都只能完成一 项工作 需求量为1代表每项工作也只能有一 个人来完成 总人数 4人 和总任务数 4项 相等 5指派问题数学模型 设xij为指派人员i去做工作j i j 1 2 3 4 5指派问题 电子表格模型 6各种变形的指派问题建模 经常会遇到指派问题的变形 之所以称它们为变形 是因为它们都不满足平衡指派问题所有假设之中的一个或者多个 一般考虑下面的一些特征 1 有些人并不能进行某项工作 相应的xij 0 2 虽然每个人完成一项任务 但是任务比人多 人少事多 3 虽然每一项任务只由一个人完成 但是人比任务多 人多事少 4 某人可以同时被指派给多个任务 一人可做几件事 5 某事可以由多人共同完成 一事可由多人完成 6 目标是与指派有关的总利润最大而不是使总成本最小 7 实际需要完成任务数不超过总人数也不超过总任务数 6各种变形的指派问题建模 例9题目见例4 即某公司需要安排三个工厂来生产四种新产品 相关的数据在例4表4中已经给出 在例4中 允许产品生产分解 但这将产生与产品生产分解相关的隐性成本 包括额外的设置 配送和管理成本等 因此 管理人员决定在禁止产品生产分解发生的情况下对问题进行分析 新问题描述为 已知如表所示的