运筹学导论第八版 运输模型.ppt

1 第5章各种运输模型 2 运输模型是一类特殊的线性规划 研究如何把商品从起点 如工厂 运算到终点 如商场 目标是确定一项运输计划 在满足供需约束的条件下 使得总的运输费用最小 运输模型的应用可以扩展到库存控制 招聘计划 人员指派等领域 3 5 1运输模型的定义 每单位运输费用cij 运输量xij 起点i的供应量为ai 终点j的需求量为bj 该模型的目标是确定未知变量xij 在满足供应量和需求量约束的情况下 使得总的运输费用最小 4 MG汽车有3个工厂 分布位于洛杉矶 底特律和新奥尔良 这三个工厂下季度的生产能力分别是1000 1500 1200辆汽车 在丹佛和迈阿密有2个主要分销中心 其季度需求为2300和1400辆汽车 汽车厂与销售中心的距离里程 下左 与对应的价格 下右 如表 运输里程 运输价格 例5 1 1 5 本问题的线性规划模型为 6 因为3个起点的总供给量 1000 1500 1200 3700辆 等于2个分销中心的总需求 2300 1400辆 这些约束都是等式 这个线性规划模型可以用单纯形方法求解 然而由于特殊的结构可以采用运输表的方法来求解该问题 7 运输模型的平衡运输算法假定模型是平衡的 即总需求等于总供给 如果模型不平衡 我们可以通过增加一个虚设起点或一个虚设终点以使得模型达到平衡 在MG汽车模型中 假设底特律汽车生产量为1300 而非1500 总供应量 3500 小于总需求 3700 这意味着丹佛和迈阿密的部分需求得不到满足 由于需求量大于供应量 我们增加一个生产能力为200辆 3700 3500 的虚拟工厂来平衡运输模型 因为该工厂不存在 单位运输费用从起点到终点的运输费为0 8 9 类似地 如果供应量大于需求量 假设丹佛的需求只有1900 我增加一个虚拟的分销中心来 接收多余 的汽车 假设运输费用为0 10 习题有3个发电厂向3个城市供电 其发电量为25 40和30兆千瓦时 3个城市的最大需求量为30 35和25兆千瓦 这3个城市的每兆千瓦电价如表所示 在8月份期间 这个城市的每一个都会增加20 的用电需求 这部分的电量可以从别的电网以每兆千瓦1000的价格额外采购 这个电网不与第3个城市相连 电力公司希望确定增加爱电量的最经济的销售和采购计划 a 把此问题表达为一个运输模型 b 为电力公司制定一个最优销售计划 c 确定3个城市每个额外购电费用 11 5 2非传统运输模型 运输模型不仅限于起讫点之间的货物运输 它还可以在生产 库存控制等领域 例5 2 1 生产 库存 Boralis公司生产专业徒步背包 产品需求通常出现在3 6月 该公司估计这4个月的需求为100 200 180和300个 由于该公司雇用兼职人员生产背包 因此每个月生产能力不一样 3 6月期间能够生产50 180 280 270个 因为各月的生产能力和需求不匹配 各月份需求可以通过如下办法满足 1 当月生产 40元 个 2 以前某个月剩余的产品 存储费用0 5元 个 月 3 以后某个月多余的产品 延期交货 惩罚费用2元 个 月 确定Boralis公司的最优生产计划 12 通过找出生产 控制问题与运输模型要素之间的对应关系 把该问题建立为一个运输模型 13 下表给出了建立的运输模型 从周期i到周期j的单位 运输 费用可以计算为 14 最优解如下图所示 虚线表示延期交货 红色点线表示为后期生产 实线表示为本周期生产 15 锯木厂由于锯木的品种差异 其需要的锯片需求表如下 工厂可以通过以下方式满足每天需求 1 以每片12元的价格购买新锯片 2 利用一种通宵打磨服务 其打磨价格为6元 片 3 使用慢一点的2天打磨服务 打磨价格为3元 片 本问题可以表示成为8个起点和7终点的运输模型 终点表示一个星期的7天 模型的起点定义如下 起点1对应于购买新锯片 在极端情况下 可以提供足够多的锯片以满足所有7天的需求 24 22 124 起点2到8对应于一个星期中的7天 这些起点的供应量等于相应每天所使用锯片数量 16 17 例如 起点2 周一 可以提供用过的锯片数量等于周一对锯片的需求量 本模型中的单位 运输费用 依据是否购买新锯片 通宵打磨服务或晚2天打磨服务分别为12 6或3元 需要注意的是 通宵打磨服务意味着第i天结束时所用过的锯片可以在第 i 1 或 i 2 天的开始时使用 慢的打磨服务的锯片可以在 i 3 天的开始时使用 处理 列是平衡模型所需要的一个虚设终点 18 评注 上表的模型仅适用于第一个星期的运行 因为没有考虑每个星期每天轮流的特性 即这个星期的每一天可以作为下星期需求的起点和 处理 终点 总的费用为840元 19 总的费用为372元 20 习题未来4个月对某种已过期物品的需求量分别为400 300 420 380吨 相应这4个月的供应能力为500 600 200 300吨 每个月每吨的采购费不同 分别为100 140 120和150吨 由于物品容易过期 当月生产的物品必须在3个月内 包括生产月 消费完 每吨物品每月的存储费用为3元 这种物品不能延期交货 请确定未来4个月的最优生产安排 21 5 3运输算法 运输算法完全采用单纯形的步骤 但是由于运输模型的特殊结构 运输算法可以构造特殊形式 进行更为简单的求解 鉴于运输算法是早期建立的手工算法 目前计算式的使用 不在强调这些简单方法 例5 3 1 SunRay运输问题 SunRay运输公司从3个粮仓把粮食运到4个加工厂 运输费用和运输模型见下表 运输费用为cij 确定运输费用最低的运输计划量 22 23 运输算法运输算法的步骤与单纯形法完全一致第1步确定一个初始的基本可行解 转到第2步 第2步利用单纯形算法的最优性条件 在所有的非基变量中确定进基变量 如果最优性条件满足 停止 否则 转到第3步 第2步利用单纯形算法的可行性条件 在所有现有的基变量中确定离基变量 寻找新的基本解 返回第2步 24 5 3 1初始解的确定 一个具有m个起点和n个终点的一般运输模型包含 m n 个约束方程 每一个起点和终点都对应一个约束方程 然而 因为运输模型总是平衡的 供需相等 这些约束方程中有一个是冗余的 因此 运输模型有 m n 1 个独立的约束方程 即初始基本解由 m n 1 个基变量组成 因此在例5 3 1中有3 4 1个基变量 运输问题可以采用西北角法 左上角法 最小费用法 Vogel法 福格尔法 找到非人工的初始基本解 一般来说 Vogel法能够产生最好的初始基本解 25 西北角法 最后得的初始基可行解 3 4 4 2 2 2 2 3 3 6 6 总运费135 26 最小元素法 最后得的初始基可行解 3 1 1 4 4 3 6 3 3 3 3 总运费86 27 Vogel近似法 VAM 第1步对每一行 列 确定惩罚量 在每一行 列 中找到一个最小的以及次小的单位费用单元 惩罚量即为次小的单位费用减去最小的单位费用 第2步找出惩罚量最大的行或列 尽量分配给最小单位费用的单元最多的粮车 调整供应和需求 删去已满足的行或列 如果行和列同时满足 删去两者之一 分配给剩下的那个行 列 为零供应 需求 第3步 a 如果仅有一个未被删去的零供应的行或零需求的列 则停止 b 如果具有一个未被删去的大于零供应 需求 的行 列 那么采用最小费用方法确定行 列 的基变量 停止 c 如果所有的未被删除的行和列都有零供应和零需求 那么采用最小费用方法确定零基变量 停止 d 否则 转到第1步 28 Vogel法求初始解 求每行 列 次小和最小运价的差 7 2 5 1 2 1 1 2 3 差中最大的先安排 第一行的x11 x11 29 Vogel法求初始解 在最小运价的行或列中优先安排运量 3 6 5 1 4 5 2 2 5 2 1 8 1 5 3 3 1 5 30 Vogel法 Vogel法的初始运输方案总运价 3 4 5 3 1 5 11010088 31 5 3 2运输算法的迭代计算 确定初始解后 采用下面的算法确定最优解 第1步采用单纯形法的最优性条件 来确定能够改进解的作为当前非基变量的进基变量 如果最优性条件满足 停止 否则转第2步 第2步采用单纯形可行性条件确定离基变量 改变基 返回第1步 用乘子法计算z行的非基系数 来求出进基变量 在乘子法中 用ui和vi来表示运输表中第i行和第j列的乘子 对每一个现有的基变量xij 这些乘子满足ui vj cij 对于每一个基变量xij v1 v2 v3 v4 u1 0 u2 u3 33 u1 0 u2 5 u3 3v1 10 v3 4 v2 2 v4 15 进而使用ui和vj 计算每个非基变量的检验数ui vj cij的值 34 因为运输模型寻求最小化 进基变量是具有z行中最正系数的变量 因此 x31就是进基变量 35 上述过程通常在运输表上进行 这不需要直接写出 u v 方程 而是从设定u1 0开始 然后计算在第1行中有基变量的所有列的v值 即v1和v2 接下来 根据基变量x22的 u v 方程计算u2 有了u2 我们计算v3和v4 最后 用x33的基本方程确定出u3 当所有的u和v求出后 我们通过对每个非基变量xij计算ui vj cij来检查这些非基变量 检查过程见该表的左下角 v1 10 v2 2 v3 4 v4 15 u1 0 u2 5 u3 3 3 16 4 9 9 9 阴影部分的9是最正的数字 因此x31是进基变量 36 确定了进基变量以后 还需要确定离基变量 选择x31为进基变量 意味着路径 3 1 运输 单位 那么 的最大值基于下面两个条件确定 1 仍然满足供应上限和需求约束 2 通过所有的路径的运输量仍然非负 37 v1 10 v2 2 v3 4 v4 15 u1 0 u2 5 u3 3 3 16 4 9 9 9 这个两个条件觉得了 的最大值和离基变量 首先建立一个起点和终点都在基变量单元 3 1 的闭圈 这个闭圈仅由链接在一起的水平线段和垂直线段组成 不运行对角线 除进基单元外 闭圈的每个角都与一个基变量重合接下来 分配给 进基变量 3 1 在供应和需求约束仍然满足的条件下 每个角在增加个减少 之间必须调整 对于 0 变量新的值仍然是非负的 38 如果x11 5 0 x11 5 0 x11 10 0相应的 的最大值为5 此时x11和x22达到了0点 因为仅有一个现有的基变量离开基本解 我们选择x11和x22作为离基变量 随便选择x11离开基本解 39 根据 5 可以确定新的基解 结果如下 v1 1 v2 2 v3 4 v4 15 u1 0 u2 5 u3 3 40 v1 1 v2 2 v3 4 v4 15 u1 0 u2 5 u3 3 6 16 9 9 9 已知新的基本解以后 我们重复u和v的计算过程 发现最正系数为4 因此进基变量为x14 4 4 41 v1 1 v2 2 v3 4 v4 15 u1 0 u2 5 u3 3 6 16 9 9 9 计算 的最大值为10 闭圈表明x14 10 离基变量是x24 4 4 42 v1 1 v2 2 v3 4 v4 11 u1 0 u2 5 u3 7 6 16 5 5 9 计算 的最大值为10 闭圈表明x14 10 离基变量是x24上表中 产生的新解比上一个解减少费用4 10 40 因此新的解为475 40 435 新的ui vj cij对所有的非基xij都是非负的 因此 上表是最优的 4 43 确定行列乘子 计算检验数 确定进基变量 以离基变量为起终点的闭圈 确定离基变量 形成新解 检验数均非负 输出最优解 Y N 确定初始解 45 5 4指派模型 指派模型所要解决的问题是 派某人做合适的事情 指派模型的目标是实现最小的指派费用 一般来说 假设工人人数等于工作数量 如果不相等可以添加虚设的工作或者工人 令元素cij表示指派工人i做工作j的费用 并定义 46 因此 建立的模型有 47 匈牙利算法 例Klyne先生的3个孩子做家务 孩子们提交的投标方案价格如下 Klyne先生该如何分配任务 48 第1步对于初始的费用矩阵 找出每行最小值的元素 本行所有元素减去这个最小值第2步对于第1步得到的矩阵 找出每列最小值的元素 每列所有元素减去这个最小值第3步利用第2步得到的矩阵 由其值为零的元素确定最优解 匈牙利法的第1步 49 匈牙利法的第2步 匈牙利法的第3步 Klyne先生支出的费用为 10 9 8 27元 指派模型的最优解为在矩阵为零的单元恰好能够产生一个可行的指派方案 即每一个孩子得到了一份具体的工作 有时候仅仅第1步和第2步产生的零值单元不一定能直接得到一个可行解 还需要更多的步骤才能得到最优指派 50 例假设把上例的问题扩展到给4个孩子指派家务 孩子们提交的投标方案价格如下 用第1步和第2步处理上表 得到 51 零单元的位置并不能把这些单项工作分配给所