信息系统项目管理师运筹学与数量经济试题连载系列：

2008年下半年信息系统项目管理师真题第70题

制造某种产品需要四道工序，每道工序可选用多种方法。下图列出了制造这种产品各道工序可选用的不同方法：从节点1开始，连续经过4条线段(表示4道工序所 选用的方法)，组成一条线路，直到节点12结束。每条线段上标记的数字表示利用相应方法每件产品可以获得的利润(元)。企业为了获取最大利润，需要找出从 节点1到节点12的一条线路，使其对应的各道工序的利润之和达到最大。利用运筹方法计算后可知，制造每件产品可以获得的最大利润是（70）元。

A. 28 　      
B. 31　        
C. 33         　
D. 34

信管网解析：

从图论上看，本题就是求节点1 到节点12 的最长路径。其算法类似于求最短路径的方法。以下我们采用倒推标记方法进行推算。

先找出离终点只有一步的节点9, 10, 11，分别标记其到达终点的路径与长度。
再找出前往节点9, 10, 11只有一步的节点5,6,7,8，对其中每个节点，找出其到终点的最长路径，分别将其路径与长度标记出来。这些节点到达终点的最长路径以及长度值如下：5-9-12 (15), 6-11-12(13), 7-11-12 (16), 8-9-12 (19）。
再找前往节点5 , 6 , 7 , 8 只有一步的节点2 , 3 , 4，对其中每个节点，找出其到终点的最长路径（注意，由于后续的最长路径已经标记出来，所以应利用它来简化计算）, 分别将其路径与长度标记出来。这些节点到达终点的最长路径以及长度值如下：2-8-9-12 (26) , 3-8-9-12 (29) , 4-8-9-12 (23）。
最后，找出节点1 通过节点2 , 3 , 4 到终点的路径中，最长的路径，并标记出来：l-3-8-9-12 (33）。

以上推算过程中的路径如图所示。
于是，从起点1 到终点12 的最长路径为1-3-8-9-12，总长度为33 ，也就是说该企业每件产品的总利润为33元。

信管网参考答案：C