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

一、计算题

1． 某工程公司在未来L4月份内需完成三项工程:第一项工程的工期为1-3月份，总计需劳动力80人月; 第二项工程的工期为1-4月份，总计需劳动力100人月; 第三项工程的工期为3一4月份，总计需劳动力120人月。 该公司每月可用劳力为80人，但任一项工程上投入的劳动力任一月内不准超过印人。问该工程公司能否按期完 成上述三项工程任务，应如何安排劳力? （请将该问题归结为网络最大流问题求解）

【答案】可以构建图所示的网络图（弧上数字为最大流量）。

图

其中，结点1、2、3、4分别代表l 、2、3、4月份，结点5、6、7分别代表第一、二、三项工程。通过标号 与调整，得到的最大流如图所示。

图

该最大流问题有多重最优解，上图仅给出一种。

所以该公司能按期完成上述三项工程任务，安排劳力的方案可以为:1月份，安排60人做第一项任务、20 人做第二项任务; 2月份，安排60人做第二项任务; 3月份，安排60人做第三项任务、20

人做第一项任务; 4 月份，安排60人做第四项任务、20人做第三项任务。 2． 某规划问题

，

试用0一1变量将上述规划问题描述成一个完整的模型。 【答案】

设则得规划模型：

3． 求图中，从任意一点到另外任一点的最短路。

【答案】用Dijtstra 算法寻求最短路，计算结果如表所示。

表

从表可以得出任意一点到另外任一点的最短路。 （l ）从v 1开始到各点的最短路。

（2）从v 2开始到v j 的最短路。

V 2不能到达v l ，故对v 2而言，v 1为不可达点。 （3）从v 3出发到各点的最短路。

v 3不能到达v l 和v 2，故v 1，v 2为v 3的不可达点。

，且d （v 4，v 6）=3。 （4）从v 4出发，只有一条路（v 4，v 6）

，且d （v 5，v 6）=6。 （5）从v 5出发，只有一条路（v 5，v 6）（6）从v 6出发，则无路。 4． 用共扼梯度法求解问题:【答案】（1）

，取初始点

。