数学建模

案例7 最短路网络（路通公司）

路通公司是一个在美国各州都有分公司的搬家公司。公司目前所面临的一个

布特

问题是将家居用品从华盛顿州的西雅图运送到德克萨斯州的埃尔帕索。

由于平均行驶速度合理以及驾驶性能好，Fairway Van Lines的运输车辆几乎

可以在任何高速公路上行驶。这次搬运将在夏天进行，所以天气因素也不必考虑。

下图显示了Fairway Van Lines的运输车运输时可以通行的高速公路网。公司管理层希望找到从西雅图到埃尔帕索的最短路线。

案例8 转运问题（极致供应）

极致供应在华盛顿特区拥有6家商店。周六晚上，福尔丘奇和班切斯塔的商店发现他们将要在周日华盛顿邮报刊登广告的阿卡迪亚65A型工作站缺少库存。两家商店分别需要补充12和13部该型工作站以应对广告登出后可能增加的客户需求。

管理层确认位于亚历山大和查维切斯的商店分别可以提供10部和17部工作站。但是，两家商店只能把目前运送其它货物的运输车上的空间腾出来运送工作站。图4.17标出了两个商店之间单位产品的运输成本以及所能运送的工作站数量上限。极致供应希望以最小运输成本将工作站从亚历山大和查维切斯运送到福尔丘奇和班切斯塔。

数学建模

供应节点

中转结点需求结点

弧的上方是单位运费

弧下方是弧上流量的上限

案例9 指派模型（博斯坦电子设备公司）

Ballston电子设备公司专门生产小型电子设备。公司购买了一处旧仓库并将其改造为公司主要的生产工厂。旧建筑的构造和空间没有留给公司的厂房设计部门多少余地来重新设计公司的五条组装线和五个产品检验及库存区域的位置。但是最终，在现有建筑里，这些区域都在固定的位置内建好。

下面是简化的博斯坦的生产流程。不同产品在各个装配线上同时生产。当产品在装配线上完成后，它们暂时被储存在组装线末端的一个容器（中等大小的储物箱）中。每30分钟，容器被送至厂房内五个检验区中的一个。通过检验的产品储存在检验区后部，未通过检验的产品则被放入检验站的回收容器中。

由于不同的装配线上生产的产品数量不同，同时，从各装配线到检验区的距离也不同，将不同产品在装配线和检验区之间传送所用的时间也不同。企业必须为每个装配线指定各自的检验区。

公司的一名工程师进行的调研得出了完工产品从装配线到各检验区的传送时间（见表）。

目前公司的实际操作是将组装线1、2、3、4和5上完成的产品分别运至检验区A、B、C、D和E。这种1-A、2-B、3-C、4-D、5-E的安排每隔半个小时就需要10＋7＋12＋17＋19＝65人分钟来运送产品。由于Ballston的平均人工成本为每小时12美元，因此Ballston每半小时就要付出（12美元）（65/60）＝13美元的运送费用。