列表

详情


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

 

A. 28

B. 31

C. 33

D. 34

参考答案: C

详细解析:

从图论上看,本题就是求节点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到终点的路径中,最长的路径,并标记出来:
1-3-8-9-12(33)。以上推算过程中的路径可以图示如下。

于是,从起点1到终点12的最长路径为1-3-8-9-12,总长度为33,也就是说该企业每件产品的总利润为33元。

上一题