信息系統(tǒng)項(xiàng)目管理師運(yùn)籌學(xué)與數(shù)量經(jīng)濟(jì)試題連載系列：

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

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

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

信管網(wǎng)解析：

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

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

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

信管網(wǎng)參考答案：C