信息系統(tǒng)項目管理師運籌學與數量經濟試題連載系列：

2008年下半年信息系統(tǒng)項目管理師真題第70題

制造某種產品需要四道工序，每道工序可選用多種方法。下圖列出了制造這種產品各道工序可選用的不同方法：從節(jié)點1開始，連續(xù)經過4條線段(表示4道工序所 選用的方法)，組成一條線路，直到節(jié)點12結束。每條線段上標記的數字表示利用相應方法每件產品可以獲得的利潤(元)。企業(yè)為了獲取最大利潤，需要找出從 節(jié)點1到節(jié)點12的一條線路，使其對應的各道工序的利潤之和達到最大。利用運籌方法計算后可知，制造每件產品可以獲得的最大利潤是（70）元。

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

信管網解析：

從圖論上看，本題就是求節(jié)點1 到節(jié)點12 的最長路徑。其算法類似于求最短路徑的方法。以下我們采用倒推標記方法進行推算。

先找出離終點只有一步的節(jié)點9, 10, 11，分別標記其到達終點的路徑與長度。
再找出前往節(jié)點9, 10, 11只有一步的節(jié)點5,6,7,8，對其中每個節(jié)點，找出其到終點的最長路徑，分別將其路徑與長度標記出來。這些節(jié)點到達終點的最長路徑以及長度值如下：5-9-12 (15), 6-11-12(13), 7-11-12 (16), 8-9-12 (19）。
再找前往節(jié)點5 , 6 , 7 , 8 只有一步的節(jié)點2 , 3 , 4，對其中每個節(jié)點，找出其到終點的最長路徑（注意，由于后續(xù)的最長路徑已經標記出來，所以應利用它來簡化計算）, 分別將其路徑與長度標記出來。這些節(jié)點到達終點的最長路徑以及長度值如下：2-8-9-12 (26) , 3-8-9-12 (29) , 4-8-9-12 (23）。
最后，找出節(jié)點1 通過節(jié)點2 , 3 , 4 到終點的路徑中，最長的路徑，并標記出來：l-3-8-9-12 (33）。

以上推算過程中的路徑如圖所示。
于是，從起點1 到終點12 的最長路徑為1-3-8-9-12，總長度為33 ，也就是說該企業(yè)每件產品的總利潤為33元。

信管網參考答案：C