15、考虑拥有如下所示的成本表的指派问题（单位：美元）：
工作 被指派者 A B C D 到每一个顾客的单位净利润（美元） 1 8 6 7 6 2 6 5 8 7 3 5 3 4 5 4 7 4 6 6
（1）画出这个问题的网络表示图。
（2）在电子表格上对这个问题进行描述，并使用Excel得到最优解。
16、四艘货船要从一个码头向其他的四个码头运货（分别积为1、2、3、4）。每一艘船都能
够运送到任何一个码头。但是，由于货船和货物的不同，装船、运输和卸货成本都有些不同。如下表所示（单位：美元）：
码头 货船 A B C D 相关成本（美元） 1 2 3 4 700 500 600 600 500 400 600 600 600 700 700 500 700 500 400 600
目标是要把这四个不同的码头指派给四艘货船，使总运输成本最小。 （1）请解释为什么这个问题符合指派问题模型。 （2）在电子表格中描述这个问题并求解。
17、张、王、李、赵4位教师被
分配教语文、数学、物理、化学4门课程，每位老师教一门课程，一门课程由一位老师教。根据这四位老师以往教课的情况，他们分别教这四门课程的平均成绩如下表： 四位教师每人只能教一门课，每一门课只能由一个教师来教，要确定哪一位教师上哪一门课，使四门课
张 王 李 赵 语文 数学 物理 化学 92 68 85 76 82 91 77 63 83 90 74 65 93 61 83 75 的平均成绩之和为最高。用Excel Solver求此指派问题的最优解。
四、网络最优化问题
1、运用贪婪算法，找出由下面的节点和供选择的边组成的网络的最小支撑树。每两个节点
13
间的虚线代表备选边，虚线旁边的数字代表把这个边插入到网络中的成本（单位：千元）。
2、速达（Speedy）航空公司中有一架班机将从西雅图直飞伦敦。由于天气因素的影响，在
明确选择路线时存在一定的灵活性。下面的网络模型提供了所能考虑到的一些可能航线。节点SE与LN分别代表了西雅图与伦敦。其它节点分别代表不同的途经地点。
3.5 3.4 3.64.7 A 4.6 D 3.4 SE 4.2 B 3.5 3.2 3.3 E 3.6 L3.8 3.4 C
F
风力对于飞行的时间（以及燃油的耗用）是有很大影响的。根据最新的气象报道，各条航线飞行时间（以小时计算）标注在弧线上，因为燃油十分昂贵，速达（Speedy）航空公司的管理层，需要制定一套方案，选择飞行时间最短的航线。
（1）在将此问题作为最短路问题时，什么代表路程？
（2）为这一问题建立电子表格模型并求解。
3、过纽约ALBANY的北——南高速公路，路况通过能力如下图所示，图中弧上数字单位：
千辆/小时，问该路段能否承受10000辆/小时的北——南向流量压力？
14
相关推荐：
loading