第十八章動態(tài)規(guī)劃

1、第十八章：動態(tài)規(guī)劃本章內(nèi)容：18.1 最短路徑問題18.2 動能規(guī)劃專用符號18.3 背包問題18.4 生產(chǎn)及存貨控制問題動態(tài)規(guī)劃的意義動態(tài)模型可依時間因素劃分為幾個時期，或依其他因素（例如地區(qū)）劃分為幾個階段，而在每個時期或階段均需做成決策；每一個決策又連帶的影響了下一期的決策，因此形成一連串的相關(guān)決策(a series of interrelated decisions)。此類問題，如果在第一個決策就挑選了該時期的最適決策，並不能保證為全面的最適解，因為前一期的決策，限制了下一期的選擇範圍，以致未能選得最適決策。換言之，局部性的最適解，並不能獲致全面性或整個系統(tǒng)的最適解。因此動態(tài)模型必需由

2、整個系統(tǒng)的觀點來著手，事實上，一個企業(yè)的管理人員在從事經(jīng)營決策或長期規(guī)劃(long-range planning)時所需要的就是這種邏輯性的或系統(tǒng)性的思考方式。18.1 最短路徑問題以圖18.1的網(wǎng)路圖為例，假設(shè)弧上的數(shù)字代表兩節(jié)點之間的距離，找出從節(jié)點1到10的最短路徑。1310426578925112106413121139658105214距離第4階段第3階段第2階段第1階段圖18.1 最短路徑問題的網(wǎng)路圖第1階段的結(jié)果如下：輸入節(jié)點弧(決策)到節(jié)點10最短距離88-10599-102第2階段的結(jié)果如下：輸入節(jié)點弧(決策)輸出節(jié)點到節(jié)點10最短距離55-88866-99777-9912第

3、3階段的結(jié)果如下：輸入節(jié)點弧(決策)輸出節(jié)點到節(jié)點10最短距離22-661933-551444-55201310426578925112106413121139658105214528712第4階段第3階段第2階段第1階段圖18.2 最短路徑問題使用動態(tài)規(guī)劃的中間解131042657892511210641312113965810521452871220141919第4階段第3階段第2階段第1階段圖18.3 最短路徑問題使用動態(tài)規(guī)劃的最終解第4階段的結(jié)果如下：節(jié)點1可選的弧到節(jié)點10的完整路徑距離1-21-2-6-9-10201-31-3-5-8-10101-41-4-5-8-1022最適選擇

4、18.3 背包問題例:假設(shè)有一個製造部門的經(jīng)理，必須從4類的工作中選出要進行的工作，這些工作要在兩週內(nèi)完成(背包的容量等於10天)，而且總價值為最高。各工作價值的尺度是從1至20，1表示價值最低，20表示最有價值。等待處理的工作見表18.2。表18.2 生產(chǎn)作業(yè)的工作資料工作類別待處理工作量(件)完工時間(天)/件工作價值141223383241142720解:本問題的動態(tài)規(guī)劃有4個階段。在階段1，必須決策第1類的工作要處理多少；在階段2，必須決策第2類的工作要處理多少。令dn=第n類工作選擇幾個（在階段n的決策變數(shù)）xn=在階段n開始時，剩餘的工作天數(shù) (階段n狀態(tài)變數(shù))因此在2週的生產(chǎn)期間

5、，x410代表總共可用來處理工作的時間。階段狀態(tài)決策價值x1*d 1f1(x1)0001122243364485486487488489481048階段x2 d 2r2(x2,d2)+ f1(x1)*d 2決策價值0123f2(x2)x100001021204236180481101581122681421607816218188162202981622324010816243261階段x3 d 3r3(x3,d3)+ f2(x2)*d 3決策價值012f3(x3)x2000010212042308341011105121131615016671811938202122209230,2249,

6、11026261276階段x4 d 4*d 4r4(x4,d4)+ f3(x3)決策價值01f4(x4)x310271283因為我們知道只有10天的時間可以使用，因此階段4的輸入為x4=10。所以在階段4的表中只有1列必須考慮。此製造程序的最適策略為：*d 1決 策回 報*d 2 =00*d 3 =18*d 4=00 =120合計28假設(shè)只有安排8天期的工作，我們只需要把第4階段重新計算即可。階段4的新表如下：x4 d 4r4(x4,d4)+ f3(x3)*d 4決策價值01f4(x4)x3822220,1228,1第1個最適解是令=0：*d 1決 策回 報*d 2 =00*d 3 =00*d

7、 4 =222 =00合計22第2個最適解是令=1： 決 策回 報*d 2*d 1=12*d 3=00*d 4=00=120合計22例：臺北電器公司共有五名推銷人員，該公司將臺北市劃分為東、北、南三個地區(qū)，假設(shè)這五個人的工作效率大致相同(即不論分配至任何地區(qū)，工作績效均相同)。本例題目標為追求最大利潤，但分配在各地區(qū)時，由於市場因素的限制和報酬遞增及遞減的不同階段，每區(qū)配備人數(shù)不同時所能獲得的利潤貢獻並非直線關(guān)係，經(jīng)過分析後，估計得各地區(qū)配置不同人數(shù)之利潤貢獻如下表：各區(qū)不同銷售員人數(shù)之利潤貢獻人數(shù)北區(qū)南區(qū)東區(qū)0 0 0 01 45 20 502 70 45 703 90 75 8041051

8、101005120150130解：東區(qū)決策分析表s0001 5012 7023 8034100451305南區(qū)決策分析表 s=0123450000150205002707045700或13809095759524100100115125110125351301201251451601501604北區(qū)決策分析表s=01234551601701651601551201701例：某電子公司發(fā)展出一種新型的計算機，預(yù)計未來五年內(nèi)不會有競爭產(chǎn)品出現(xiàn)，故該公司可以任意設(shè)定價格。行銷部經(jīng)理決定每個年度價格之幅度不超過50元，假定他選定四種價格策略：$300,$350,$400及$450，經(jīng)過詳細評估後每個年度依照不同價格所能獲得之淨(jìng)利如下表所示，試問應(yīng)如何決定每個年度的價格使得五年之全部報酬最大？定價策略各年度報酬資料表(單位：百萬元)年度價格12345$3008525405080$3507040802040$4005535907030$4508575256035解：第四年之最適策略分析表 年度價格12345$300130808525405080$350100407040802040$400110305535907030$45095358575256035最適定價策略分析表 年度價格12345$3003352351701308085254