运23P315-323第九章习题.docVIP

问题 1.在下面的运输网络中找到从节点到其他节点的最短路线。 2.对于戈曼建设公司的问题（见图9-1），如果我们现在假定节点7是公司的仓库和供给中心。每天几次往返都会发生在节点7和其他节点或建筑工地之间，把节点7看做是起始节点，在网络中找到从此节点到其他节点的最短路线。 3.在原存的戈曼建筑公司问题中，我们找到了从总部到其他任一节点的最短距离。因为一些路线是公路而另一些是城市街道，所以在总部与工地之间的最短路线并不必然是需要最少时间的路线。下面是一张戈曼网络公路图。所标数据为时间而不是距离，如果我们现所要达到的目的是尽量减少往返时间，那么请找到从戈曼总部到其他任一建筑工地的最短路线。 4.在下面的网络中找到从节点1到节点8的最短路线。 5.在下面的网络中找到从节点1到节点10的最短路线。 6.摩根运输公司在4个州的范围即芝加哥和10个其他城市之间经营一项特殊的快速投递服务。当摩根收到服务要求时，它会尽可能快速地派遣一辆车从芝加哥赶往所需服务城市。对把快速服务与最低往返成本作为目标的摩根公司来说，所派车辆选择从芝加哥到所需服务城市的最短路线尤为重要。假定下面标有距离的网络图表示此问题的公路网络，请找到从芝加哥到其他所有几个城市的最短路线。 7.城市出租车公司在纽约市为出租车司机已确定了10个搭乘车站。为了减少运行时间，提高服务质量以及最大化利用公司的车队，管理方希望出租车司机尽可能地选择最短路线。使用下面公路与街道的网络图，请说明司机从车站1到车站10应选择什么样的路线。运行时间如图所示（单位：分钟） 8.韦斯曼糖果公司生产几种糖果制品。公司的货车直接送货物到零售商手中。当生意小时，卡车司机们在其运送货物时可以自由决定选择什么样的路线到达零售地点。然而，当生意增大后，运输与投递成本已变得很高。为了提高投递效率，韦斯曼管理者将会决定出零售点之间的最短路线。例如，下面的网络展示了从节点1到节点11之间可能被选择的路线。现在决定一辆卡车从节点1到节点11的最短路线。 9.下面网络中的5个节点表示的是1~4年的时间段。每个节点表示的是当做出保持或是替代公司电脑设备决定时时间。如果决定替换电脑设备，那么同时也要决定这些新的设备要用多久，从节点0到节点1的弧代表持有现有设备1年并且到年底替换。从节点0到节点2的线段表示保持现有设备2年并且到2年末替换。弧上的数字指与替换设备有关的总成本。这些成本包括打折后的购买价、折合价、运营成本和维修成本。决定4年内的最小设备替换成本。 10.俄亥俄州近来购买了一片土地用于设一个新州公园。公园设计者已经为住宿地点、茅屋、野餐园、船坞和景点确定了地点。这些位置如下图网络中的节点所示。网络上的弧表示的是公园中可能的路线连接。如果此州公园的设计者想要使公园中所需修建的路长达到最小同时仍可达到所有节点，那么那些路线应如何修建？ 11.为下面的紧急联络网络确定最小支撑树解决办法。 12.在大的肥皂品工厂中，质检员会从不同的生产区中选取不同产品的样品，带到实验室中进行分析。检查过程是缓慢的。质检员要花费大量的时间把样品从生产区带到实验室。公司正在考虑建立一个可以在生产区与实验室之间运送样品的管道运输系统。下面的网络系统展示了选取样品的实验室与生产区的地点。那些弧是被考虑的用于运输系统可选路线。可以使所有生产区选送样品到实验室的路线最短的运输系统的布局是怎样的？ 13.中西部大学正在安装一个电子邮件系统。下面的网络展示了办公室之间可以实现电子链接。办公室之间的距离以几千英尺计（如图所示）。为此办公室联络系统的设计必须可使所有办公室都拥有电子邮件服务，假定此设计满足连接8个办公室线路最短的要求。 14.地下光缆公司刚刚接到通知，允许其在田纳西州孟菲斯市郊区提供有线电视服务。下图网络中的节点展示了公司电缆线所必须要达到的分支点。网络弧上标出了分支点之间的英里数。确定可以使该公司到达所有分支点的缆线的最小长度的方法。 15.通过纽约州奥尔巴尼的南北向公路系统可以满足下图提到的运输能力的要求。 此公路系统可以适应每小时南北向10000的车流量吗？ 16.如果问题15中所说的奥尔巴马公路系统改变了其流量，如下图所示。那么每小时通过此系统的最大流量为多少？为了达到最大流量，每小时应有多少辆车通过每条公路？ 17.一个长途电话公司使用光缆网络在不同地方传递电话和其他信息。电话通过电话线与转换点传递。该公司的部分传送网络如下图所示。每条弧上的数字表示的是通过网络传递信息量的能力。 为了跟上原点与目的地之间信息传递容量，使用网络来确定可能从节点1到节点7之间传递的最大信息量。 18.高价油公司拥有一个从采集地到几个储存点