当前位置：问答库＞考研试题

一、计算题

1． 己知图表示7个城市间拟建一条连接各个城市的通信线路，各边的权数表示两个城市之间的修建 费用，求连接各城市通信线路最小修建费用方案。

图

【答案】最优万案为:

可使修建费用为最少。

2． 己知有m 个生产地点A i ，i=1，…，m ，可供应某种物资，其供应量为a i ，i=1，…，m ; 有n 个销售地B j ，j=l，…，n ，需要该种物资，其需要量为b j ，j=l，…，n ; 从各生产点往需求点发运时，均需经过P 个中间编组站之一转运，若启用第k 个编组站，不管转运量多少，均发生固定费用f k ，而第k 个编组站的转运容量为Q k （k=1，…，p ）。从A i 到P k 及P k 到B i 运输单位物资的运价分别为c ik 和c kj ，

现要制定一个使总运费最小的调运方案。建立该问题的混合整数规划数学模型。

【答案】设

组站k 运往销售点j 的运量。则得模型

表示销售点i 运往编组站k 的运量，x kj 表示编

3． 在图中，分别求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;