运筹学运输问题(节).pptVIP

为了能够使用表上作业法对问题进行求解，可增加一个假想销地 Bn+1 ： （1）Bn+1 地的销量为 （2）ci,n+1 =0，i=1,…,m。（原因：销地 Bn+1 实际上并不存在，因而运往销地 Bn+1 的物资实际上就是在产地 Ai 存储起来。） 从而问题的模型变为： 为了能够使用表上作业法对问题进行求解，可增加一个假想产地 Am+1： （1）Am+1 地的产量为 （2）cm+1,j =0，j=1,…,n。（原因：产地 Am+1 实际上并不存在，因而由产地 Am+1 运出的物资实际上就是各销地 Bj 所需物资的欠缺额。） 从而问题的模型变为： 例 1 如下表所示的运输问题中，若产地 i 有一个单位物资未运出，则将发生存储费用。假定1，2，3产地单位物资存储费用分别为5，4，3。又假定产地 2 的物资至少运出 38 个单位，产地 3 的物资至少运出 27 个单位，试求解此运输问题的最优解。 解：总产量 = 90 总销量 = 70 故需增加虚拟销地 D，其销量为 90 – 70 = 20 将产地 2 分为 2’ 和 2’’ ，产量分别为 38 和 2。 将产地 3 分为 3’ 和 3’’ ，产量分别为 27 和 3。 产地 2’ 和 3’ 运出的物资不能发给虚拟销地 D。 运输费用为： 2×2 + 30×1 + 8×4 + 12×3 + 15×3 + 3×3 = 156 存储费用为： 18×5+2×4 = 98 总费用= 156 + 98 = 254 例 2 设有三个化肥厂（A、B、C）供应四个地区（I、II、III、IV）的农用化肥。各化肥厂年产量、各地区的需求量、单位化肥的运价如下表所示。求运费最省的调拨方案。 解： 总产量 = 50 + 60 + 50 = 160 万吨 最低需求量 = 30 + 70 + 0 + 10 = 110 万吨 最高需求量 = 无限 因为： IV 最多能分配到的化肥数量 =总产量 – I 地区最低需求量 – II 地区最低需求量 – III 地区最低需求量 = 160 – 30 – 70 - 0 = 60 万吨 所以： IV 地最多能分配到 60 万吨化肥。 即 IV 地的最高需求为 60 万吨。 从而运输问题变为： 例 3 某玩具公司分别生产三种新玩具，每月可供量分别为 1000 件，2000 件，2000 件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为 1500 件，由于经营方面原因，各商店销售不同玩具的盈利额不同（如下表）。 解：从盈利额中选取最大的数 16 ，用 16 减去表中的数据，从而将原问题转化为运输问题。 解：总供给量 = 1000 + 2000 + 2000 = 5000 总需求量 = 1500 + 1500 + 1500 = 4500 总供给量 总需求量 故需增加虚拟销售商店丁，其销售量 = 500 例 4 请证明：一个最大化运输问题等价于用最大运价减去各运价所得到的新运输表所形成的最小化运输问题。 例 1 已知某企业各季度的生产能力、每季度交货量、每台设备的生产成本如下表。 如果企业生产出来的设备当季不交货，则每台每个季度的存储维护费用为 0.15 万元。 求在满足合同的条件下，企业如何安排生产计划，才能使年生产和存储维护的总费用最低？ 例 2 某公司承担 4 条航线的运输任务，已知： （1）各条航线的起点城市和终点城市及每天的航班数，如表 1 所示； （2）各城市间的航行时间，如表 2 所示； （3）所有航线都使用同一种船只，每次装船和卸船时间均为 1 天。 问该公司至少配备多少条船才能满足所有航线运输的需要？ 表 1 表 2 解： （1）各条航线航行、装船、卸船所需船只数量。 （2）各港口之间调度所需的船只数量。 （1）A2 → B2 的单位运价 c22 在什么范围变化时，最优调运方案不变？ （2） A2 → B4 的单位运价 c24 变为何值时，有无穷多最优调运方案？至少再写出一个最优调运方案。 2 C B 2 1 F A 3 1 B D 4 3 D E 1 每天航班数量 终点城市 起点城市 航线 7 7 14 2 1 0 A 8 8 13 3 0 1 B 3 0 17 5 E 5 5 15 0 C 20 17 0 15 D 20 13 14 D 3 8 7 E 0 8 7 F 5 3 2 C F B A 57 3 19 17 1 1 1 10 2 5 3 1 1 2 1 1 航班数量 13 7 航行时间 15 9 总计 15 1 1 4 9 1 1 3 所需船只 卸船时间 装船时间 航线 为满足每天的装卸船和航行需求，共需配备 91 艘船。 每天到达 E C D 余缺数 每天需要 F B