《运筹学导论第八版 5运输模型讲解》由会员分享，可在线阅读，更多相关《运筹学导论第八版 5运输模型讲解（53页珍藏版）》请在金锄头文库上搜索。
1、1 第5章 各种运输模型 2 运输模型是一类特殊的线性规划，研究如何把商品 从起点（如工厂）运算到终点（如商场），目标是 确定一项运输计划，在满足供需约束的条件下，使 得总的运输费用最小。运输模型的应用可以扩展到 库存控制、招聘计划、人员指派等领域。 3 5.1 运输模型的定义 1 2 m 1 2 m 每单位运输费用cij，运输量xij。起点i的供应量为ai，终点j的 需求量为bj。该模型的目标是确定未知变量xij，在满足供应 量和需求量约束的情况下，使得总的运输费用最小。 4 MG汽车有3个工厂，分布位于洛杉矶、底特律和新奥尔良， 这三个工厂下季度的生产能力分别是1000，1500，1200
2、辆 汽车。在丹佛和迈阿密有2个主要分销中心，其季度需求为 2300和1400辆汽车。汽车厂与销售中心的距离里程（下左 ）与对应的价格（下右）如表 运输距 离 丹佛 迈阿 密 洛杉矶10002690 底特律12501350 新奥尔良1275850 运车单 价 丹佛 迈阿 密 洛杉矶80215 底特律100108 新奥尔良10268 运输里程 运输价格 例5.1-1 5 本问题的线性规划模型为 6 因为3个起点的总供给量(=1000+1500+1200=3700辆)等于2 个分销中心的总需求(=2300+1400辆)，这些约束都是等式。 这个线性规划模型可以用单纯形方法求解，然而由于特殊的 结构可
3、以采用运输表的方法来求解该问题 运车单 价丹佛迈阿密供应量 洛杉矶 80 x11 215 x12 1000 底特律100 x21 108 x221500 新奥尔良 102 x31 68 x32 1200 需求量23001400 1 2 m 1 2 洛杉矶 底特律 新奥尔良 7 运输模型的平衡 运输算法假定模型是平衡的，即总需求等 于总供给。如果模型不平衡，我们可以通过增加一个虚设起 点或一个虚设终点以使得模型达到平衡。 在MG汽车模型中，假设底特律汽车生产量为1300（而非 1500）。总供应量(=3500)小于总需求(=3700),这意味着丹佛 和迈阿密的部分需求得不到满足。 由于需求量大于
4、供应量，我们增加一个生产能力为200辆 (3700-3500)的虚拟工厂来平衡运输模型。因为该工厂不存在 ，单位运输费用从起点到终点的运输费为0. 8 运车单 价丹佛迈阿密供应量 洛杉矶 80 1000 215 1000 底特律100 1300 108 1500 新奥尔良 102 68 1200 1200 虚拟工厂 0 0 200 200 需求量23001400 9 类似地，如果供应量大于需求量，假设丹佛的需求只有1900 ，我增加一个虚拟的分销中心来“接收多余”的汽车。假设运 输费用为0。 运车单 价丹佛迈阿密虚设终 点供应量 洛杉矶 80 1000 215 0 1000 底特律100 90
5、0 108 200 0 4001500 新奥尔良 10268 1200 0 1200 需求量19001400400 10 习题 有3个发电厂向3个城市供电，其发电量为25，40和30兆千瓦时。3个城 市的最大需求量为30，35和25兆千瓦。这3个城市的每兆千瓦电价如表 所示. 城市 电 厂 123 1600700400 2320300350 3500480450 在8月份期间，这个城市的每一个都会增加20%的用电需求，这部分的电 量可以从别的电网以每兆千瓦1000的价格额外采购。这个电网不与第3个 城市相连，电力公司希望确定增加爱电量的最经济的销售和采购计划。 (a) 把此问题表达为一个运输模
6、型 (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元/个/
7、月 (3) 以后某个月多余的产品(延期交货)，惩 罚费用2元/个/月。 确定Boralis公司的最优生产计划。 12 通过找出生产-控制问题与运输模型要素之间的对应关系，把 该问题建立为一个运输模型： 运输输生产库产库 存 (1) 起点 i(1) 生产周期 i (2) 终点 j(2) 需求周期 j (3) 起点 i 的供应量(3) 生产周期 i 的生产能力 (4) 终点 j 的需求量(4) 需求周期 j 的需求量 (5) 从起点 i 终点 j 的单 位运输费 用 (5) 周期 i 为周期 j 的生产的单 位费用(生产+库存+惩罚 ) 13 下表给出了建立的运输模型 1234生产能力 14040
8、.54141.550 2424040.541180 344424040.5280 446444240270 需求量100200180300 从周期 i 到周期 j 的单位“运输”费用可以计算为 14 1 2 234 431 供应周期 需求周期 供应 需求 50180280270 100200180300 50 50 130 70 180 30270 最优解如下图所示。虚线表示延期交货，红色点线表示为后 期生产，实线表示为本周期生产。 15 锯木厂由于锯木的品种差异，其需要的锯片需求表如下： 日周一 周二 周三 周四 周五 周六 周日 锯片需求量24121420181422 工厂可以通过以下方式
9、满足每天需求: (1)以每片12元的价格 购买新锯片；(2)利用一种通宵打磨服务，其打磨价格为6元/ 片；(3)使用慢一点的2天打磨服务，打磨价格为3元/片. 本问题可以表示成为8个起点和7终点的运输模型。终点表示 一个星期的7天。模型的起点定义如下：起点1对应于购买新 锯片，在极端情况下，可以提供足够多的锯片以满足所有7天 的需求(=24+22=124). 起点2到8对应于一个星期中的7天. 这些起点的供应量等于相应每天所使用锯片数量. 16 12345678 周一周二周三周四周五周六周日处理 1新锯片 12 24 12 2 12121212120 98 124 2周一M 6 10 6 8
10、3 6 3330 24 3周二MM 6 6 63 6 330 12 4周三MMM 6 14 6330 14 5周四MMMM 6 12 630 20 6周五MMMMM 6 14 6 0 18 7周六MMMMMM 6 14 0 14 8周日MMMMMMM 0 22 22 24121420181422124 17 例如，起点2(周一)可以提供用过的锯片数量等于周一对 锯片的需求量. 本模型中的单位“运输费用”，依据是否购 买新锯片、 通宵打磨服务或晚2天打磨服务分别为12，6 或3元。需要注意的是，通宵打磨服务意味着第i天结束时 所用过的锯片可以在第(i+1)或(i+2)天的开始时使用，慢的 打磨服
11、务的锯片可以在(i+3)天的开始时使用。“处理”列是 平衡模型所需要的一个虚设终点。 18 星期 锯片数（当前日） 处理 新锯片通宵磨2天磨 周一24(一) 10 (一) +8 (三 ) 6 (四)0 周二2 (二)6 (三)6 (五)0 周三014 (四)00 周四012 (五)8 (五)0 周五014 (六)04 周六014 (日)00 周日00022 评注：上表的模型仅适用于第一个星期的运行，因为没有考虑 每个星期每天轮流的特性，即这个星期的每一天可以作为下星 期需求的起点和“处理”终点. 总的费用为840元 19 第 i 周 第 i 周 总计 周一周二周三周四周五周六周日 2周一M 6
12、63 6 333 18 24 3周二 3 M 663 8 33 4 12 4周三 3 12 3 M 663 2 3 14 5周四 3 8 3 12 3 M 663 20 6周五 3 4 33 14 3 M 6 6 18 7周六 6333 14 3 M 6 14 8周日 66333 10 3 12 M22 总计24121420181422 总的费用为372元 20 习题 未来4个月对某种已过期物品的需求量分别为400，300， 420，380吨，相应这4个月的供应能力为500，600，200 ，300吨. 每个月每吨的采购费不同，分别为100、140、 120和150吨. 由于物品容易过期，当月
13、生产的物品必须 在3个月内(包括生产月)消费完. 每吨物品每月的存储费用 为3元，这种物品不能延期交货。请确定未来4个月的最优 生产安排。 21 5.3 运输算法 运输算法完全采用单纯形的步骤，但是由于运输模型的特殊结 构，运输算法可以构造特殊形式，进行更为简单的求解。 鉴于运输算法是早期建立的手工算法，目前计算式的使用，不 在强调这些简单方法。 例5.3-1(SunRay运输问题) SunRay运输公司从3个粮仓把粮食运到4个加工厂。运输费用 和运输模型见下表，运输费用为cij，确定运输费用最低的运输 计划量 22 1234供应量 仓库 1 10 x11 2 x12 20 x13 11 x1
14、4 15 仓库 212 x21 7 x22 9 x23 20 x24 25 仓库 3 4 x31 4 x32 16 x33 18 x34 10 需求量5151515 23 运输算法 运输算法的步骤与单纯形法完全一致 第1步 确定一个初始的基本可行解，转到第2步. 第2步 利用单纯形算法的最优性条件，在所有的非基变量中 确定进基变量，如果最优性条件满足，停止。否则， 转到第3步。 第2步 利用单纯形算法的可行性条件，在所有现有的基变量 中确定离基变量，寻找新的基本解。返回第2步。 24 5.3.1 初始解的确定 一个具有m个起点和n个终点的一般运输模型包含(m+n)个约 束方程，每一个起点和终点
15、都对应一个约束方程。然而，因 为运输模型总是平衡的（供需相等），这些约束方程中有一 个是冗余的。因此，运输模型有(m+n-1)个独立的约束方程， 即初始基本解由(m+n-1)个基变量组成，因此在例5.3-1中有 3+4-1个基变量。 运输问题可以采用西北角法（左上角法）、最小费用法、 Vogel法（福格尔法）找到非人工的初始基本解 。 一般来说，Vogel法能够产生最好的初始基本解。 25 西北角法 最后得的初始基可行解。最后得的初始基可行解。 3 3 4 4 4 4 2 2 2 2 2 22 2 3 3 3 3 6 66 6 总运费总运费135135. . 26 最小元素法最小元素法 最后得
16、的初始基可行解。 3 3 1 1 1 1 4 4 4 4 3 3 6 6 3 3 3 3 3 3 3 3 总运费86. 27 Vogel近似法(VAM) 第1步 对每一行(列)确定惩罚量：在每一行(列)中找到一个最 小的以及次小的单位费用单元，惩罚量即为次小的单位费用减 去最小的单位费用。 第2步 找出惩罚量最大的行或列。尽量分配给最小单位费用的 单元最多的粮车，调整供应和需求，删去已满足的行或列。如 果行和列同时满足，删去两者之一，分配给剩下的那个行(列) 为零供应(需求)。 第3步 (a)如果仅有一个未被删去的零供应的行或零需求的列 ，则停止。 (b)如果具有一个未被删去的大于零供应(需求)的行(列)，那么 采用最小费用方法确定行(列)的基变量，停止 (c)如果所有的未被删除的行和列都有零供应和零需求，那么采 用最小费用方法确定零基变量。停止 (d)否则，转到第1步。 28 VogelVogel法求初始解法求初始解 求每行(列)次小和最小运价的差： 7-27-2 5 5 1 1 2 2 1 1 1 1 2 2 3 3 差中最大的先安排：第一行的x1
