決策樹網(wǎng)絡(luò)計劃動態(tài)規(guī)劃參考.ppt

1、第 四 章決策分析方法,4.1 管理決策概述,一、基本概念 定義 決策：它是決策者對系統(tǒng)方案所作決定的過程和結(jié)果，是決策者的行為和職責(zé)。,管理決策分析就是為幫助決策者在多變的環(huán)境條件下進(jìn)行正確決策而提供的一套推理方法、邏輯步驟和具體技術(shù)，以及利用這些技術(shù)和方法選擇滿意的行動方案的過程。,決策分析的過程 問題分析、診斷及信息活動。 對目標(biāo)、準(zhǔn)則及方案的設(shè)計活動。 對非劣備選方案進(jìn)行綜合分析、比較、評價的抉擇活動。 將決策結(jié)果付諸實施并進(jìn)行有效評估、反饋、跟蹤、學(xué)習(xí)的實施活動,三、決策分析類型 1 確定型決策分析 存在決策者希望達(dá)到的明確目標(biāo) （收益大或損失小等）； 存在確定的自然狀態(tài)；, 存在著

2、可供選擇的兩個以上的行動方案； 不同行動方案在確定狀態(tài)下的益損值可以計算出來。,確定型決策分析問題求解方法： 在方案數(shù)量較大時，常用運籌學(xué)中規(guī)劃論等方法來分析解決，如線性規(guī)劃、目標(biāo)規(guī)劃。 嚴(yán)格來講，確定型問題只是優(yōu)化計算問題，而不屬于真正的管理決策分析問題。,2風(fēng)險型決策分析 存在決策者希望達(dá)到的明確目標(biāo)（收益大或損失?。?存在兩個以上不以決策者主觀意志為轉(zhuǎn)移的自然狀態(tài)，但決策者或分析人員根據(jù)過去的經(jīng)驗和科學(xué)理論等可預(yù)先估算出自然狀態(tài)的概率值P ；, 存在兩個以上可供決策者選擇的行動方案； 不同行動方案在確定狀態(tài)下的益損值可以計算出來。,風(fēng)險型決策分析問題求解方法： 期望值、矩陣法、決策樹法

3、 風(fēng)險型決策問題是一般決策分析的主要內(nèi)容。在基本方法的基礎(chǔ)上，應(yīng)注意把握信息的價值及其分析和決策者的效用觀等重要問題。,3不確定型決策 存在決策者希望達(dá)到的明確目的 （收益大或損失?。?自然狀態(tài)不確定，且其出現(xiàn)的概率不可知；, 存在兩個以上可供決策者選擇的行動方案； 不同行動方案在確定狀態(tài)下的益損值可以計算出來。,不確定型決策分析問題的求解方法： 樂觀法（最大最大原則）、 悲觀法（最小最大原則）、 等概率法( Laplace 準(zhǔn)則，也是一種特殊的風(fēng)險型決策）、 后悔值法（SaVage準(zhǔn)則或后悔值最大最小原則）。,案例：某企業(yè)準(zhǔn)備生產(chǎn)一種新產(chǎn)品。估計該產(chǎn)品的銷售量有較高、一般、較低、很低四種情

4、況，而對每種狀態(tài)出現(xiàn)的概率則無法預(yù)測。為生產(chǎn)該產(chǎn)品，企業(yè)有三種實施方案：新建一個車間進(jìn)行生產(chǎn)；改造一個現(xiàn)有車間進(jìn)行生產(chǎn)；部分零件在現(xiàn)有車間生產(chǎn)，部分零件外購。該新產(chǎn)品企業(yè)準(zhǔn)備生產(chǎn)10年，10年內(nèi)在不同狀態(tài)下的損益值（扣除投資費用）如下表所示。請分別用樂觀法、悲觀法和后悔值法來決策實施方案。,解： （1）樂觀法 每個方案在不同狀態(tài)下的最大收益分別為： max 850，420，-150，-400=850 A1 max 600,400,-100,-350=600 A2 max 400,250,90,-50=400 A3 取各方案最大收益值中的最大值，可得： max850，600，400=850 對應(yīng)

5、實施方案為A1 ，即建新車間。,（2）悲觀法 每個方案在不同狀態(tài)下的最小收益分別為： min 850，420，-150，-400= -400 A1 min 600,400,-100,-350= -350 A2 min 400,250,90,-50= -50 A3 取各方案最小收益值中的最大值，可得： max-400，-350，-50 = -50 對應(yīng)實施方案為A3 ，即部分自己生產(chǎn)，部分外購。,（3）后悔值法,最后，找出最小后悔值300，對應(yīng)方案A2，即改造現(xiàn)有車間生產(chǎn)。,對于不確定型決策分析問題，若采用不同求解方法，則所得的結(jié)果也會有所不同，因為這些決策方法是各自從不同的決策準(zhǔn)則出發(fā)來選擇最

6、優(yōu)方案的。而具體采用何種方法，又視決策者的態(tài)度或效用觀而定，在理論上還不能證明哪種方法是最為合適的。,4對抗型決策 Wij = f(Ai,Bj) i=1,2,3m, j=1,2,n 式中A決策者的策略集； B競爭對手的策略集。 可采用對策論及其沖突分析等方法來分析解決。這類決策分析問題是當(dāng)前管理、經(jīng)濟(jì)界比較關(guān)注的問題。,5多目標(biāo)決策 由于系統(tǒng)工程所研究的大規(guī)模復(fù)雜系統(tǒng)一般具有屬性及目標(biāo)多樣化的特點，在管理決策時通常要考慮多個目標(biāo)，但它們在很多情況下又是相互消長或矛盾的，這就使得多目標(biāo)決策分析在管理決策分析中具有了日益重要的作用。,多目標(biāo)決策的理淪、方法與應(yīng)用，在國際上是最近二三十年才得到蓬勃發(fā)

7、展的，目前分析該類決策問題的方法已有不少，常用方法有：化多目標(biāo)為單目標(biāo)的方法（含系統(tǒng)評價中的加權(quán)和及各種確定目標(biāo)權(quán)重的方法）、重排次序法、目標(biāo)規(guī)劃法及層次分析（AHP ）方法等。,4.2 風(fēng)險型決策分析,一、基本方法 期望值法 E(X)=pixi Xi 隨機(jī)離散變量x的第i個取值， i=1,2,3m； pi x=xi時的概率,期望值法就是利用上述公式算出每個行動方案的益損期望值并加以比較。若采用決策目標(biāo)準(zhǔn)則是期望收益最大，則選擇收益期望值最大的行動方案；反之，采用費用期望值最小的方案為最優(yōu)。,案例一：某輕工企業(yè)要決定一輕工產(chǎn)品明年的產(chǎn)量，以便及早做好生產(chǎn)前的各項準(zhǔn)備工作。假設(shè)產(chǎn)量的大小主要根據(jù)

8、該產(chǎn)品的銷售價格好壞而定。根據(jù)以往市場銷售價格統(tǒng)計資料及市場預(yù)測信息得知：未來產(chǎn)品銷售價格出現(xiàn)上漲、價格不變和價格下跌三種狀態(tài)的概率分別為0.3 , 0.6 和0.1 。,若該產(chǎn)品按大、中、小三種不同批量（即三種不同方案）投產(chǎn)，則下一年度在不同價格狀態(tài)下的益損值可以估算出來，如表所示。現(xiàn)要求通過決策分析來確定下一年度的產(chǎn)量，使該產(chǎn)品能獲得的收益期望為最大。益損值表如下圖所示：,41,如何決策可以獲得最大的投資收益？,這是一個面臨三種自然狀態(tài)和三種行動方案的風(fēng)險型決策分析問題，可以利用前述的多種方法求解。 現(xiàn)運用期望值法求解如下：,( l）根據(jù)表41 所列各種自然狀態(tài)的概率和不同行動方案的益損值

9、，可用公式 E(X)=pixi， 計算出每種行動方案的益損期望值 如下：,(2）通過計算并比較后可知，方案A2的數(shù)學(xué)期望E(A2) = 33.6萬元，為最大，所以選擇行動方案A2為最優(yōu)方案。 也就是下一年度的產(chǎn)品產(chǎn)量按中批生產(chǎn)規(guī)模進(jìn)行生產(chǎn)所獲得的收益期望值最大。,決策樹法 所謂決策樹法，就是利用樹形圖模型來描述決策分析問題，并直接在決策樹圖上進(jìn)行決策分析其決策目標(biāo)（準(zhǔn)則）?？梢允且鎿p期望值或經(jīng)過變換的其他指標(biāo)值。 現(xiàn)仍以前例為例介紹決策樹法。,（1）繪制決策樹。 按表41 所示各種行動方案和自然狀態(tài)及其相應(yīng)的益損值和主觀概率等信息，按由左至右的順序畫出決策樹圖，如下圖所示：,圖42 決策樹模型

10、,圖中各節(jié)點的名稱及含義如下： “ ”表示決策節(jié)點，從它引出的分枝叫做方案分枝。分枝數(shù)量與行動方案數(shù)量相同。如前例有三個行動方案，則圖42 所示就有三個方案分枝。 決策節(jié)點表明，從它引出的行動方案需要進(jìn)行分析和決策。,“ ”表示狀態(tài)節(jié)點，從它引出的分枝叫做狀態(tài)分枝或概率分枝，在每一分枝處注明自然狀態(tài)名稱及概率狀態(tài)分枝數(shù)量與自然狀態(tài)數(shù)量相同。,“ ”表示結(jié)果節(jié)點，即將不同行動方案在不同自然狀態(tài)下的結(jié)果（如益損值）注明在結(jié)果節(jié)點的右端。,( 2 ）計算各行動方案的益損期望值，并將計算結(jié)果標(biāo)注在相應(yīng)的狀態(tài)節(jié)點上 。 圖43 所示為方案A2的益損期望值。,圖43,(3）將計算所得的各行動方案的益損期望

11、值加以比較，選擇其中最大的期望值并標(biāo)注在決策節(jié)點上方，如圖44 所示。,與最大期望值相對應(yīng)的是方案A2, 則A2即為最優(yōu)方案。然后，在其余的方案分枝上畫上“| ”符號，表明這些方案已被舍棄，圖44 所示即是一個經(jīng)過決策分析選擇行動方案A2為最優(yōu)方案的決策樹圖。,圖44 例41,多級決策樹 從例41中可知，如果只需作一次決策，其分析求解即告完成，則這種決策分析問題就叫做單級決策。反之，有些決策問題需要經(jīng)過多次決策才告完成，則這種決策問題就叫做多級決策問題。應(yīng)用決策樹法進(jìn)行多級決策分析叫做多級決策樹。,案例討論：某化妝品公司生產(chǎn)BF 型號護(hù)膚化妝品。由于現(xiàn)有生產(chǎn)工藝比較落后，產(chǎn)品質(zhì)量不易保證，且成

12、本較高，銷路受到影響。若產(chǎn)品價格保持現(xiàn)有水平無利可圖，若產(chǎn)品價格下降還要虧本，只是在產(chǎn)品價格上漲時才稍有盈利。,為此公司決定要對該產(chǎn)品生產(chǎn)工藝進(jìn)行改進(jìn)，提出兩種方案以供選擇：一是從國外引進(jìn)一條自動化程度較高的生產(chǎn)線；二是自行設(shè)計一條有一定水平的生產(chǎn)線。,根據(jù)公司以往引進(jìn)和自行設(shè)計的工作經(jīng)驗顯示，引進(jìn)生產(chǎn)線投資較大，但產(chǎn)品質(zhì)量好，且成本較低，年產(chǎn)量大，引進(jìn)技術(shù)的成功率為80。而自行設(shè)計生產(chǎn)線，投資相對較小，產(chǎn)品質(zhì)量也有保證，成本也較低，年產(chǎn)量也大，但自行設(shè)計的成功率只有60。,進(jìn)一步考慮到無論是引進(jìn)或自行設(shè)計生產(chǎn)線，產(chǎn)量都可能增加。因此，公司生產(chǎn)部門又制定了兩個生產(chǎn)方案：一是產(chǎn)量與過去相同（保持

13、不變）, 二是產(chǎn)量增加，為此又需要進(jìn)行決策。最后，若引進(jìn)或自行設(shè)計均不成功，公司只得仍采用原有生產(chǎn)工藝?yán)^續(xù)生產(chǎn)，產(chǎn)量自然保持不變。,公司打算該護(hù)膚化妝品生產(chǎn)5年。根據(jù)以往價格統(tǒng)計資料和市場預(yù)測信息，該類產(chǎn)品在今后5年內(nèi)價格下跌的概率為0.1，保持原價的概率為0.5，而漲價的概率為0.4。通過估算，可得各種方案在不同價格狀態(tài)下的益損值如下表所示。,表42 例42,討論 如何決策才能獲得最大的收益？,本例是個二級決策分析問題，今用多級決策樹進(jìn)行分析，其過程和結(jié)果如下圖所示：,a,b,c,d,e,h,i,f,j,k,g,-250,80,200,-400,100,300,-100,0,125,-250

14、,0,250,-350,-250,650,-100,0,125,引進(jìn),設(shè)計,Success,Failed,Normal,Increase,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Success,Failed,Normal,increase,0.8,0.2,0.6,0.4,0.1,0.5,0.4,0.1,0.5,0.4,0.1,0.1,0.1,0.1,0.5,0.4,0.5,0.4,0.5,0.4,0.5,0.4,112,95,130,40,13

15、0,112,75,100,40,100,76,圖45例42,二、信息的價值 信息和決策的關(guān)系十分密切。要獲得正確的決策，必須依賴足夠和可靠的信息。 決策所需信息的分類：一類是完全信息，即據(jù)此可以得到完全肯定的自然狀態(tài)，有助于正確的決策；一類是抽樣信息，這是一類不完全可靠的信息。,完全信息價值 案例分析 某化工廠生產(chǎn)一種化工產(chǎn)品。據(jù)對統(tǒng)計資料的分析表明，該產(chǎn)品的次品率可以分成五個等級（即五種狀態(tài)），每個等級（狀態(tài)）的概率如下表所示：,由進(jìn)一步的分析可知，產(chǎn)品次品率的高低與該產(chǎn)品所用主要原料的純度有關(guān)。今已知，化工原料純度高，次品率低（如S1為0.02），反之則次品率高。而化工原料的純度高低，又與

16、運輸、保存日期等因素有關(guān)。為此，工廠主管生產(chǎn)的部門建議在生產(chǎn)該產(chǎn)品前，先對該化工原料增加一道“提純”工序，通過提純工序，能使全部原料處于S1狀態(tài)，從而降低了次品率。但增加提純工序就增加了工序費用。,經(jīng)過核算可知，每批原料的提純費用為3400元。經(jīng)估算，在不同純度狀態(tài)下其益損值如下表所示。如果在生產(chǎn)前，先將化工原料檢驗一下，通過檢驗可以掌握每批化工原料處于何種純度狀態(tài)，這樣可以對不同純度的原料采用不同策略，即提純或不提純，從而使益損期望值為最大。,益損值表 (單位：元),要求：如何進(jìn)行決策才能獲得最好的投資收益？,【分析】：今用決策樹法對該問題進(jìn)行分析，具體過程和結(jié)果如圖所示。由下圖可知，通過檢

17、驗，當(dāng)某批原料純度處于S1、 S2或S3，狀態(tài)時，采用A2(不提純)方案，其益損值大于A1方案。反之若處于S4或S5狀態(tài)時，采用A1(提純)方案，這時其益損值大于A2方案。據(jù)此可計算益損期望值為2220元。與沒有經(jīng)過檢驗工序相比，由于通過檢驗完全知道原料純度的狀態(tài)信息，因此可得完全信息的價值為2220元 - 1760元 = 460元。,通過該例可知，為獲得完全信息所要付出的代價，不應(yīng)大于完全信息所能得到的收益期望，本例中不應(yīng)大于460元。本例如圖中提純方案分枝菱形內(nèi)的數(shù)字為50，即增加檢驗工序只花費250元，而能多獲得460元的收益。因此，增加檢驗工序是可取的。,抽樣信息價值 通過抽樣所獲得的

18、信息，用統(tǒng)計方法來推斷自然狀態(tài)出現(xiàn)的概率，據(jù)此來選擇行動方案。抽樣信息雖不十分可靠，但為獲得此類信息的代價也較少，且在多數(shù)情況下，也只可能獲得這類信息，以供決策之需,案例討論：某公司有50000元多余資金，如用于某項開發(fā)事業(yè)估計成功率為96%，成功時一年可獲利12%，但一旦失敗，有喪失全部資金的危險。如把資金存放到銀行中，則可穩(wěn)得年利6%。為獲取更多情報，該公司求助于咨詢服務(wù)，咨詢費用為500元，但咨詢意見只是提供參考。根據(jù)過去咨詢公司類似200例咨詢意見實施結(jié)果，情況見表所示：,試用決策樹法分析： (a)該公司是否值得求助于咨詢服務(wù)； (b)該公司多余資金應(yīng)如何合理使用?,解答要點： 多余資

19、金用于開發(fā)事業(yè)成功時可獲利6000元，若存人銀行可獲利3000元。 設(shè) T1咨詢公司意見可以投資 T2咨詢公司意見不宜投資 E1投資成功 E2投資失敗,P(E1/T1)0.987，P(E2/T1)0.013 P(El/T2)0.865，P(E2/T2)0.135 由題意知P(T1)0.78，P(T2)0.22， P(E1)0.96，P(E2)=0.04 因為P(E/T)P(T,E)P(T)， 又P(Tl，E1)0.77，P(T1,E2)0.01， P(T2，E1)0.19 ，P(T2，E2)0.03,故求得： P(E1/T1)0.987 P(E2/T1)0.013 P(El/T2)0.865

20、P(E2/T2)0.135,決策結(jié)論： (a)該公司應(yīng)求助于咨詢服務(wù)； (b)如咨詢意見可投資開發(fā)，可投資于開發(fā)事業(yè)，如咨詢意見不宜投資開發(fā)，應(yīng)將多余資金存入銀行。,三、效用曲線的應(yīng)用 風(fēng)險型決策分析的求解中，均是以益損期望值的大小作為在風(fēng)險情況下選擇最優(yōu)方案的準(zhǔn)則，僅代表大量實驗的平均值，卻不能表達(dá)決策者的主觀意圖和傾向及其滿意程度等。因此，效用曲線應(yīng)運而生。效用實質(zhì)上反映了決策者對風(fēng)險所抱的態(tài)度。,定義： 在直角坐標(biāo)系內(nèi)，用橫坐標(biāo)表示益損值，縱坐標(biāo)表示效用值，將決策者對風(fēng)險所持的態(tài)度的變化關(guān)系用曲線來反映。,用效用曲線進(jìn)行決策和計算的步驟 繪制決策者的效用曲線 據(jù)效用曲線找出各方案與益損值

21、相對應(yīng)的效用值。 根據(jù)效用曲線的效用期望值進(jìn)行計算和決策。,例.某制藥廠欲投產(chǎn)A、B兩種新藥，但受到資金及銷路限制，只能投產(chǎn)其中之一。若已知投產(chǎn)新藥A需要資金30萬元，投產(chǎn)新藥B只需資金16萬元，兩種新藥生產(chǎn)期均定為5年。估計在此期間，兩種新藥銷路好的概率為0.7，銷路差的概率為0.3。它們的益損值如下表所示。問究竟投產(chǎn)哪種新藥為宜?,益損值表：,采用益損值法，顯然以生產(chǎn)新藥A為最優(yōu)，決策樹如下圖,若用效用值作為決策準(zhǔn)則，其步驟如下： 繪制決策人的效用曲線。 據(jù)效用曲線找出方案與益損值相對應(yīng)的效用值。 利用效用值為決策準(zhǔn)則進(jìn)行計算和決策。,效用曲線,由此可見，若以效用值作為決策準(zhǔn)則，方案B優(yōu)于

22、方案A。這是因為決策人是個保守型人物。,第 五 章 網(wǎng)絡(luò)規(guī)劃模型,5.1 基本概念及其術(shù)語,一、概念 網(wǎng)絡(luò)圖：由具有始點和終點的有向曲線或線段組成的圖形。 網(wǎng)絡(luò)技術(shù)：一種新方法，是借助網(wǎng)絡(luò)圖表示一項工程中多項工作及計算相關(guān)參數(shù)，從而對工作進(jìn)行統(tǒng)籌安排的一種方法。,二、基本術(shù)語,工程：一個科研項目，一個工作任務(wù)。 作業(yè)：即工序。 緊前工序，緊后工序。 作業(yè)長度：表示工序所花時間。 結(jié)點：表示工序的開工和完工。 結(jié)點最早開工時間（ES）：即緊后工序最早開工時間。,結(jié)點最遲完工時間（LF）：即緊前工序允許的最遲完工時間。 關(guān)鍵路線：作業(yè)時差為零的路線。 關(guān)鍵工序：關(guān)鍵路線上的工序。 結(jié)點最早完工時間

23、（EF）。 結(jié)點最遲開工時間（LS）。,ES = 該事件所有緊前工序的EF的最大值； LF = 該事件所有緊后工序的LS的最小值； 作業(yè)時差 = 結(jié)點最遲結(jié)束時間 前一結(jié)點最早開工時間 工序時間；,三、兩種網(wǎng)絡(luò)圖模型 AOA AON,5.2 方法分析,1 某工廠要進(jìn)行生產(chǎn)線改造，其時間和進(jìn)度安排如下表所示： 要求：（1）畫出該工程作業(yè)的網(wǎng)絡(luò)圖； （2）計算最短工程時間。 （3）計算作業(yè)時差； （4）找出該工程的關(guān)鍵路線；,要求： （1）畫出該工程作業(yè)的網(wǎng)絡(luò)圖模型； （2）計算最短工程時間； （3）計算作業(yè)時差； （4）找出該工程的關(guān)鍵路線。,A,E,C,D,B,F,G,J,H,K,I,M,L,

24、N,P,0,208,8,8,0,288,280,248,280,248,208,213,16,310,296,288,312,248,233,213,20,320,320,316,316,312,A B. C. E. F B D C D D H I E H I F G G H H J,I J J K. L K M. N L M M P N P P,8 8 8 24 4 6 4,8 8 12 35 225 200 40 32,ES=largest EF of the immediate predecessors,LF=smallest LS of the immediate successors

25、,Thus, the critical path is AFGHJLMP,網(wǎng)絡(luò)圖如下圖所示。,結(jié)果關(guān)鍵路線為A-F-G-H-J-L-M-P； 最短工程時間為320小時。,案例分析二：某項工程（如新產(chǎn)品開發(fā)），安排如下：,要求： (1) 畫出網(wǎng)絡(luò)圖 (2) 計算工程時間 (3) 計算作業(yè)時差 (4) 找出關(guān)鍵路線,A,F,D,G,H,J,L,N,M,K,I,E,B,C,6,3,4,12,13,6,2,5,12,10,9,4,8,11,6,9,13,18,0,12,18,23,32,33,41,52,52,41,33,23,23,37,18,16,12,9,12,0,網(wǎng)絡(luò)圖如下：,關(guān)鍵路線工序：B

26、EHJLN 工程時間：52天,5.3 計算作業(yè)時間,一、根據(jù)實際情況中的定額、統(tǒng)計資料和類比資料來確定。 二、三種時間估計法 最樂觀時間，即在最順利情況下完成工序的最短時間，用a表示。 最保守時間，即在最不順利情況下完成工序的最長時間，用b表示。 最可能時間，即在一般情況下完成工序的時間，用c表示。,平均工序時間: t(a+b+4c)/6(經(jīng)驗公式) t 是一個平均值，其方差為： 2=(b-a)/6) 2 均方差：=(b-a)/6 ti=(ai+bi+4ci)/6，其中ti是隨機(jī)變量。 E(ti)= (ai+bi+4ci)/6,T=ti，總工程周期T是各個相互獨立的隨機(jī) 變量之和，所以當(dāng)工序很

27、多時，必然服從正態(tài)分布 TN（，）,所以 E(t)= TE= E(ti)= E(ti) = (ai+bi+4ci)/6) =(bi-ai)/6) 2) ,三、上述公式的意義 可用計算工程完工時間的概率。 可以計算具有一定概率值的工程實際完工時間。,案例研討1：已知建設(shè)一個汽車庫及引道的作業(yè)明細(xì)如下表所示（單位：天）,要 求： (1) 畫出網(wǎng)絡(luò)圖 (2) 計算工程時間 (3) 計算作業(yè)時差 (4) 找出關(guān)鍵路線,網(wǎng)絡(luò)圖如下圖所示：,關(guān)鍵路線為A-C-E-F-G-J-K-N； 最短工程時間為80天。,案例研討2：某一汽車制造企業(yè)為加快產(chǎn)品開發(fā)進(jìn)程，縮短產(chǎn)品的開發(fā)時間，現(xiàn)將其產(chǎn)品開發(fā)的工作任務(wù)分解安

28、排如下：,要求： (1) 建立網(wǎng)絡(luò)圖模型 (2) 計算工程時間 (3) 計算作業(yè)時差 (4) 找出關(guān)鍵路線,（1）建立網(wǎng)絡(luò)圖模型如下：,（2）計算每個節(jié)點的最早開工時間、最遲完工時間，得到工程總時間，工程時間61天 （3）計算作業(yè)時差，得到作業(yè)時差為零的工序集，即關(guān)鍵路線工序：BEHJLN 注：本題采用AOA方法，若使用AON方法也可以。,比較AON和AOA,案例研討三： 某工廠要進(jìn)行生產(chǎn)線改造，其時間和進(jìn)度安排如下表所示： 要求：（1）畫出該工程作業(yè)的網(wǎng)絡(luò)圖； （2）計算最短工程時間。 （3）計算作業(yè)時差； （4）找出該工程的關(guān)鍵路線；,要求： （1）畫出該工程作業(yè)的網(wǎng)絡(luò)圖模型； （2）計算

29、最短工程時間； （3）計算作業(yè)時差； （4）找出該工程的關(guān)鍵路線。,Solution: Construction of AON Network,Solution: Analysis of AON Network,第七章 動態(tài)規(guī)劃及其應(yīng)用,基本思想： 把某項決策過程在時間上（有時推廣到空間上）分成幾個相互聯(lián)系的階段，依次（順序或逆行）在每個階段上進(jìn)行決策，即采用多階段序貫決策的方法，從而找出一個整體的最有方案。,例6-1 某人從A城到K城，選擇最優(yōu)開車路線,解題的思路和模型,1. 階段的劃分,解題的思路和模型,2. 描述階段狀態(tài)和決策方案 Sn：第n階段狀態(tài)變量 Xn：第n階段決策方案 3.列出

30、效益函數(shù) Rn（Sn，Xn）:階段n狀態(tài)Sn決策方案Xn的效益函數(shù) 4. 建模，采用倒序的方法 Fn（Sn）min（Max）Rn（Sn，Xn）+Fn+1(Sn+1) 某階段最優(yōu)值 本階段效益值 后階段最優(yōu)值,解：階段IV F3（S4）minR4（S4，X4）+F5(S5) 某階段最優(yōu)值 本階段效益值 后階段最優(yōu)值 H點： Fh4（S4）minRh4（S4，X4）+F5(S5) =min(7+0)=7 I點： FI4（S4）minRI4（S4，X4）+F5(S5) =min(5+0)=5 J點： FJ4（S4）minRJ4（S4，X4）+F5(S5) =min(6+0)=6,解：階段III F3

31、（ S3 ）minR3（ S3 ，X3）+F4(S4) 某階段最優(yōu)值 本階段效益值 后階段最優(yōu)值 E點： FE3（S3）min(RE3（ S3 ，EH）+FH4(S4), (RE3（ S3 ，EI）+FI4(S4) =min(7+7,6+5)=11 F點： FF3（S3）min(RF3（ S3 ，F(xiàn)H）+FH4(S4), (RF3（ S3 ，F(xiàn)I）+FI4(S4), (RF3（ S3 ，F(xiàn)J）+FJ4(S4) =min（67，35，36）8 G點： FG3（S3）min(RG3（ S3 ，GI）+FI4(S4), (RG3（ S3 ，GJ）+FJ4(S4) min（25，46）7,解：階段II F2（ S2 ）minR2（ S2 ，X2）+F3(S3