制造某种产品需要4道工序，每道工序可选用多种方法。图5—3列出了制造这种产品各道工序可选用的不同方法：从节点1开始，连续经过4条线段(表示4道工序所选用的方法)组成一条线路，直到节点 12结束。每条线段上标记的数字表示利用相应方法每件产品可以获得的利润(元

admin2010-01-17 51

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

利用运筹方法计算后可知，制造每件产品可以获得的最大利润是(70)元。

选项 A、28
B、31
C、33
D、34

答案C

解析本题就是求节点1～节点12的最长路径，其算法类似于求最短路径的方法。采用倒推标记方法进行推算的解题步骤如下。
①先找出离终点只有一步的节点9、10、11，分别标记其到达终点的路径与长度。
②再找出前往节点9、10、11只有一步的节点5、6、7、8，对其中每个节点找出其到终点的最长路径，分别将其路径与长度标记出来。例如，节点5到达节点12可选的路径及长度值如下：5-9-12(8+7=15)， 5-10-12(4+3=7)，5-11-12(3+6=9)，由于15＞9＞7，因此选择路径5-9-12。依此类推，最后节点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到终点的路径中的最长路径，并标记出来，即1-3-8-9-12(33)，如图5-7所示。