制造某种产品需要4道工序,每道工序可选用多种方法。图5—3列出了制造这种产品各道工序可选用的不同

16 查阅

制造某种产品需要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。依此

软考高级