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

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

admin2018-04-25  50
问题 制造某种产品需要4道工序，每道工序可选用多种方法。下图列出了制造这种产品各道工序可选用的不同方法：从节点1开始，连续经过4条线段(表示4道工序所选用的方法)，组成一条线路，直到节点12结束。每条线段上标记的数字表示利用相应方法每件产品可以获得的利润(元)。企业为了获取最大利润，需要找出从节点1到节点12的一条线路，使其对应的各道工序的利润之和达到最大。利用运筹方法计算后可知，制造每件产品可以获得的最大利润是(54)元。
选项 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元。
转载请注明原文地址:https://www.kaotiyun.com/show/v3LZ777K
本试题收录于： 系统分析师上午综合知识考试题库软考高级分类
0

系统分析师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)