2016年中国民航大学机场学院运筹学复试笔试仿真模拟题
● 摘要
一、计算题
1． 在图中，分别求v l 至v 6，v l 至V 4，v6至vZ 和vZ 至vs 的最短路和最短距离。
图
【答案】用Floyd 方法求解 令网络的权矩阵为
其中，
为
到
的距离
由表示从v i 到v j 点的或直接
有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得
表示从vi 到vj 点最多经v l ，v 2的最短路长，得
类推，
所以v l 至v 6的最短路是v 1一v 3一v 5一v 6，最短距离是-1; v l 至v 4的最短路是v 1一v 3一v 5一v 4，最短距离是3; v 6至v 2的最短路是v 6一v 4一v 2，最短距离是3: v 2至v 5的最短路是v 2一v3一v 5，最短距离1;
以此
2． 某公司在某地区采矿，拟建采矿点共有五个K 1、K 2、K 3、K 4和K 5，其相互之间距离如图所示。 该公司拟建四个冶炼车间F I 、F 2、F 3和F 4，其相互之间距离如图所示。所有采矿点所采的矿石都要通过公路运 往冶炼车间。采矿点K5与主干公路相连。其到两个公路连接点G l 和G 2的距离分别为15公里、8公里。冶炼车间F 4与主干公路相连，其到两个连接点G 3和G 4的距离分别为5公里、4公里。四个公路连接点G I 、G 2、G 3和 G 4之间都己经有公司相连，其距离如图所示。由于修建公路的费用非常巨大，所以公路建设方案必须保证建设 线路最短。同时，为了节省运费，矿石运距要尽可能缩短。请用图论的方法找出五个拟建采矿点之间的公路线路 建设最优方案，找出四个拟建冶炼车间之间的公路线建设最优方案，并指出矿石如何进行调运。
图
【答案】五个拟建采矿点之间，寻找最优建设方案，即寻求各点至ks 的最短距离。 采用逐次逼近法计算根据方程
开始令
则有：
所以最优建设方案如图所示
，即k 5与k j 无点时即直接连接时的距离。