运筹学-第四章-运输问题和指派问题 PPT课件

第四章运输问题和指派问题 1 运输问题 提到运输问题 想到什么 服装专卖店的转运问题等 快递业的运输问题 实际生活中有哪些方面涉及运输问题 2 产销平衡和单位运价表 运输问题的提出 某公司经销甲产品 它下设三个工厂和四个销售点 各工厂每日的产量和各销售点每日的销量 以及从各工厂到销售点的单位产品运价如下表 问该公司应如何调运产品 在满足各销售点的需求量的前提下 使总运费为最小 运输的单位成本 供需平衡 3 运输问题的求解方法 计算过程 1 寻找初始可行解 2 检查是否已达到最优 若已是最优或无可行解 则结束 3 进一步改善目前的解 寻找初始可行解的方法 1 西北角方法 2 最小元素法 4 求平衡运输问题初始解方法 西北角方法 西北角方法 2 4 2 3 3 6 首先满足西北角上空格的需求 5 初始解 求平衡运输问题初始解方法 西北角方法 西北角方法 其余为0 总运费 3 3 4 11 2 9 2 2 3 10 6 5 135 元 6 求平衡运输问题初始解方法 最小元素法 求初始解 最小元素法 1 3 4 6 3 3 首先满足运费最小的空格 7 初始解 求平衡运输问题初始解方法 最小元素法 最小元素法 其余为0 总运费 4 3 3 10 3 1 1 2 6 4 3 5 86 元 8 两种方法结果比较 最小元素法 西北角方法 9 西北角法得到初始方案 总运费 3 3 4 11 2 9 2 2 3 10 6 5 135 元 最小元素法得到初始方案 总运费 4 3 3 10 3 1 1 2 6 4 3 5 86 元 10 最优解的检验 闭回路法 要判定运输问题的某个解是否为最优解 可仿照一般单纯形法 检验这个解的各非基变量 对应于运输表格中的空格 的检验数 若有某空格的检验数为负 则说明将变为基变量将使运费减少 故当前这个解不是最优解 若所有空格的检验数全非负 则不管怎样变换解均不能使运输费用减少 即为最优解 11 闭回路法 以最小元素法得到的解为初始可行解 1 1 1 1 检验第一个空格 此时 引起的运费变化为 3 1 2 3 1 0说明 该空格可以保持不变 即该运输路线不用安排运输 12 检验数 0表示 例如 A2 B4 如果增加A2到B4的1单位产品 将会降低1单位的运费 所以 该解不是最优解 13 解的改进 1 以为换入变量 找出它在运输表中的闭回路 2 以空格为第一个奇数顶点 沿闭回路的顺 或逆 时针方向前进 对闭回路上的顶点一次编号 3 在闭回路上的所有偶数顶点中 找出运输量最小的顶点 格子 以该格中的变量为换出变量 4 以为调整量 将该闭回路上所有奇数顶点处的运输量都增加这一数值 所有偶数顶点处的运输量都减去这一数值 从而得出一新的运输方案 5 然后 再对得到的新解进行最优性检验 如不是最优解 就重复以上步骤 直到有最优解 14 3 1 1 1 1 1 2 4 5 1 0 此时 总费用为 5 3 2 10 3 1 1 8 6 4 3 5 85 86 接下来 继续用闭回路法对新求得的解进行检验 如果还不是最优解 进行改进 如此循环往复 直至得到最优解 总费用为85 15 运输问题的建模和Excel规划求解 某公司经销甲产品 它下设三个工厂和三个销售点 各工厂每日的产量和各销售点每日的销量 以及从各工厂到销售点的单位产品运价如表 问该公司应如何调运产品 在满足各销售点的需求量的前提下 使总运费为最小 单位运输成本 供给 需求 16 一般运输问题的基本原则 最小化所有运输费用之和供给 需求产品是离散计量的要求运输量是整数个单位产品线性约束 先讨论产销平衡的运输问题 总供应量 总需求量 17 运输问题的一般模式 目标函数 供给约束 需求约束 非负约束 n表示物资的n个销地 m表示物资的m个产地 18 问题分析 决策变量目标函数约束条件 产量约束 销量约束 非负 决策变量 19 根据一般模式求解上述运输问题 得到 20 注意 由于供应量和需求量都是整数 任何有可行解的运输问题就必然有所有决策变量都是整数的最优解 所以无需设置有关整数解的约束条件 21 实际中 产销往往是不平衡的 可有两种情况 总产量小于总销量 供不应求 总产量大于总销量 供大于求 产销不平衡的运输问题 22 总产量小于总销量 供不应求 23 总产量大于总销量 供大于求 24 例4 2自来水输送问题 某市有甲乙丙丁四个居民区 自来水有A B C三个水库供应 四个居民区每天必须得到保证的基本生活用水量分别为30 70 10 10千吨 但由于水源紧张 三个水库每天最多只能分别供应50 60 50千吨自来水 由于地理位置的差别 自来水公司从各水库每天向各居民区供水所需付出的引水管理费用不同 见表格 其中水库C与丁区之间没有输水管道 其他管理费用都是450元 千吨 根据公司规定 各居民区用户按照统一标准900元 千吨收费 此外 四个居民区都向公司申请了额外用水量 分别为每天50 70 20 40千吨 25 问 1 该公司应如何分配供水量 才能获利最多 2 为了增加供水量 自来水公司正在考虑进行水库改造 使三个水库每天的最大供水量都提高一倍 问那时供水方案应如何改变 公司利润可增加多少 26 问题分析 决策变量目标函数约束条件 27 使用Excel求解送水问题1 供不应求的问题 28 使用Excel求解送水问题2 最大供水量增倍 供大于求的问题 29 4 3运输问题的变形 总供应量大于总需求总供应量小于总需求一个目的地同时存在着最小需求量和最大需求量 于是所有在这两个数值之间的数量都是可以接受的在运输中不能使用特定的出发地 目的地组合目标是使与运输量有关的总利润最大而不是使总成本最小 30 例4 3 某公司决定使用三个有生产余力的工厂进行四种新产品的生产 每单位产品需要等量的工作 所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量 见表格最右列 而每种产品每天有一定的需求量 见表格最后一行 除了工厂2不能生产产品3之外 每个工厂都可以生产这些产品 然而 每种产品在不同工厂中的单位成本是有差异的 见表 现在需要决定的是在哪个工厂生产那种产品 可以使总成本最小 某公司决定使用三个有生产余力的工厂进行四种新产品的生产 每单位产品需要等量的工作 所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量 见表格最右列 而每种产品每天有一定的需求量 见表格最后一行 除了工厂2不能生产产品3之外 每个工厂都可以生产这些产品 然而 每种产品在不同工厂中的单位成本是有差异的 见表 现在需要决定的是在哪个工厂生产那种产品 可以使总成本最小 31 问题分析 供大于求的问题决策变量目标函数约束条件 32 使用Excel求解 33 例4 4需求量存在最小需求量和最大需求量的问题 某公司在三个工厂中专门生产一种产品 在未来的四个月中 四个处于国内不同区域的潜在顾客很有可能有大量订购 顾客1是公司最好的顾客 所以他的订单要全部满足 顾客2和顾客3也是公司很重要的顾客 所以营销经理认为至少要满足他们订单的1 3 对于顾客4 营销经理认为并不需要特殊考虑 由于运输成本上的差异 销售一个产品得到的利润也不同 利润很大程度上取决于哪个工厂供应哪个顾客 见表格 问应向每个顾客供应多少产品 才能使公司的总利润最大 34 例4 4 35 问题分析 该问题要求满足不同顾客的需求 订购量 解决办法是 实际供应量 最少供应量实际供应量 要求订购量但条件是 最少供应量 7000 3000 2000 0 12000 总产量 8000 5000 7000 20000 要求订购总量 7000 9000 6000 8000 30000 36 问题分析 决策变量目标函数约束条件 37 使用Excel求解 38 4 5指派问题 问题的提出有n项不同的任务需要完成 而恰好有n个人 或n台设备 可以分别完成其中的一项工作 但由于任务的性质和个人的专长不同 因而不同的人去完成不同的工作的时间 或产生的效率 就不一样 那么 应派哪一个人去完成哪一项工作才能使总的时间最短 或效率最高 问题模型 平衡指派问题的假设 1 人的数量和任务的数量相等2 每个人只能完成一项任务3 每项任务只能由一个人来完成4 每个人和每项任务的组合都会有一个相关的成本5 目标是要确定如何指派才能使总成本最小 39 指派问题应用举例 某市计划在今年内修建4座厂房 发电厂 化肥厂 机械厂 食品厂 分别记为B1 B2 B3 B4 该市有4个大的建筑队A1 A2 A3 A4都可以承担这些厂房的建造任务 但由于各个建筑队的技术水平 管理水平等不同 它们完成每座厂房所需要的费用也不一样 为计算简单 设有关数据如下表所示 又因希望尽早把这4座厂房都建造好 故需把这4个建筑队都动用起来 即每个队分配一项任务 市政府经费紧张 于是提出研究下述问题 究竟应该指派哪个队修建哪个厂 才能使建造4座厂房所花的总费用最少 各建筑队完成每座厂房所需费用 万元 40 匈牙利解法的关键 利用了指派问题最优解的以下性质 若从指派问题的系数矩阵的某行 或某列 各元素分别减去一个常数 得到一个新的矩阵 则以和为系数矩阵的两个指派问题有相同的最优解 41 指派问题的匈牙利算法 系数矩阵 每行元素中减去该行的最小元素 每列元素中减去该列的最小元素 设是一个系数矩阵 对于前面的例子 得到如下的效率矩阵 42 指派问题的匈牙利算法 续 划去C中所有0元素所需要的最少直线数等于C中不同行不同列上0元素的个数 1在所有未划去数中找出最小数 设为d 2将所有未画去的数都减去d 而对位于两直线交点处的数则加上d 3得出最优指派方案 注 最优解不一定唯一 43 最优解 在系数矩阵中已经有4个独立零元素 故可确定指派问题的最优指派方案 本例的最优解为 44 最优指派方案是 最少费用为 2 5 4 5 16 45 运用Excel求解 46 例4 7 某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议 为了更好地安排这次会议 他安排小张 小王 小李 小刘四个人 每个人负责完成一项任务 A B C和D 由于每人完成每项任务的时间和工资不同 问公司应指派何人去完成任务 才能使总成本最少 47 分析问题 决策变量目标函数约束条件 48 运用Excel求解 49 4 6指派问题的变形 某人不能完成某项任务每个人只能完成一项任务 但任务数比人数多 因此其中有些任务会没人做 每项任务只由一个人完成 但是人数比任务数多 因此其中有些人会没事做 某人可以同时被指派多项任务 某事需要由多人共同完成 目标是与指派有关的总利润最大而不是总成本最小 实际需要完成的任务数不超过总人数也不超过总任务数 50 例4 8 例4 3改 某公司决定使用三个有生产余力的工厂进行四种新产品的生产 每单位产品需要等量的工作 所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量 见表格最右列 而每种产品每天有一定的需求量 见表格最后一行