第十八章动态规划dynamicmodel.doc

第十八章：動態規劃本章內容：18.1 動態規劃的意義18.2 驛馬車問題問題18.3 背包問題18.4 推銷人員問題 18.5 價格決策問題動態規劃的意義動態模型可依時間因素劃分為幾個時期，或依其他因素（例如地區）劃分為幾個階段，而在每個時期或階段均需做成決策；每一個決策又連帶的影響了下一期的決策，因此形成一連串的相關決策(A series of interrelated decisions)。此類問題，如果在第一個決策就挑選了該時期的最適決策，並不能保證為全面的最適解，因為前一期的決策，限制了下一期的選擇範圍，以致未能選得最適決策。換言之，局部性的最適解，並不能獲致全面性或整個系統的最適解。因此動態模型必需由整個系統的觀點來著手，事實上，一個企業的管理人員在從事經營決策或長期規劃(Long-range planning)時所需要的就是這種邏輯性的或系統性的思考方式。驛馬車問題(Stagecoach) 設某電器公司在台北縣製造彩色電視機，該公司接到美國中部某成大型百貨公司的採購訂單。管理當局希望能以最低成本將產品由工廠運送至目的地，所有可能的運送路線，經企劃部門分析如下：由工廠以貨櫃卡車運送產品至輸出港口：基隆、台中或高雄，然後交由船運至美國西海岸的西雅圖、舊金山或洛杉磯等三個城市，接著以火車運至芝加哥或聖路易，最後再以卡車運抵目的地，為了便於討論，我們先將以上城市編號後，可將所有路線列為如下頁的圖的網狀圖 起運港 卸貨港BE 轉運城市H 動 態 規 劃 網 狀 圖第四階段第三階段第二階段第一階段G工廠ACJID 基隆 西雅圖 目的地F 芝加哥 台中 舊金山 聖地牙哥 高雄 洛杉磯至於各轉送點之間的運輸成本經估計如下： 各運送途徑成本表(單位：千元)43363343423647324 西雅圖 舊金山 洛杉磯 芝加哥 聖地牙哥 目的地 E F G H I J 基隆 台中 高雄(d)(c) (b)(a)HIEFGBCDA B C D562註一：階段編號的次序亦有由後往前倒推者，見本節第四個性質問題的性質：1、 此類問題可以劃分成為許多不同階段(stages)。以本例題而言，即指運程的不同階段，例如： 階段一：由工廠至起運港口 階段二：由起運港口至美國西海岸 階段三：由西海岸到內陸兩大轉運城市 階段四：由轉運城市到目的地就其他題目而言，階段可能是指不同的時期，例如企業生產決策，本月份須決定生產量，緊接著又需對下個月來決定適當的生產量，這種情況即可分為兩個階段來討論。階段也可能是指連續決策的不同步驟，例如將銷售人力分配予三個區域，一個區域分配人力之多寡將連帶影響其他兩個地區之分配，此種情況可以分為三個階段的決策來探討。此外，還有許多不同的劃分方式，完全要看題目的性質來決定如何劃分。 在每一個階段均需作成決策，以本例題來說，就是貨品要運往何處，前一階段的決策將限制後面階段的可行方案，所以做成決策之前應該考量整體的系統。2、 動態問題的第二性質就是至少有一個階段存在幾個不同的狀態，例如第一個階段即有三個不同的起運港口(即狀態)可供選擇，而第二個階段亦有三個到達港口可供選擇3、 在每一個階段的任何狀態，均有對於其剩餘各階段達到最後目的地之最適政策，換言之，再任何一點(狀態)之最適策略與其以前所做的決策無關，此一狀態稱之為最適化原理，這是動態規劃問題求解的最基本原理。例如本例題第三個階段開始的一個狀態城市E，不論由起運點如何運送至這個城市，它對於其剩餘途徑必存在一個最適解，因城市E至目的地有EHJ及EIJ。兩個途徑，其中以EHJ之$30003000=$6000成本最低，此即其最適解4、 因為最適化原理的性質，所以動態問題求解的時候是從後面往前面推倒，由最後一個階段的決策開始，逐步往前面的階段倒推回表，第一個階段是放在最後來求解的 決策問題對於某一特定投入城市，我們應如何選擇以抵達階段4之城市 投入 產出 決策準則 城市E、 城市H以最小成本抵達目的地 F或G 或I 以符號的方式來表達則為： X3=階段3之投入，即階段3開始之城市E、F或G，讀者請注意階段3的投入實際階段2的產出 d3=階段3之決策變數 X4=階段3之產出，即考慮X3及d3後所抵達之城市H或I。符號定義如下： (S,Xn)=在S狀態及Xn階段下，最適策略之總成本，此一成本之計算包括兩個部份，一是本階段之成本，另一個是達到本階段以前決策之最低總成本。在求極大問題時，報酬函數亦可同理表示之 =可使fn(S,Xn)最小之 (S) =表示 (S,)之最小值，即 (S) = (S,)我們的目的是要找(S)，動態規劃的辦法是逆序尋找(S)，(S)，(S)，最後找(S)本例題的解法 第四階段決策分析表 s(S)HI34JJ 第三階段最適決策分析表 s(S,)=+() (S)HIE6 (3+3)8 (4+4)6HF9 (6+3)7 (3+4)7IG6 (3+3)7 (3+4)6H第二階段最適決策分析表 s(S,)=+() (S)EFGB13 (7+6)11 (4+7)12 (6+6)11FC9 (3+6)9 (2+7)10 (4+6)9E 或FD12 (6+6)9 (2+7)11 (5+6)9F第一階段最適決策分析表 s(S,)=+() (S)BCDA13 (2+11)13 (4+9)12 (3+9)12D最適途徑為 A-D-F-I-J，此時總成本為$12,000背包問題(Knapsack Problem) 設有一個登山人員在出發前考慮攜帶物品之種類及重量，若背包重量限制為24公斤，他考慮帶六件物品，每一種物品的重量及其效用，經估計如下表，試問他應攜帶什麼物品才能獲致最大效用目標？背包問題資料表物品編號重量效用1832135362494552673解： 本題目共有六個階段。至於輸入，則為剩餘可供裝載的重量限制，因為物品有一定的重量，所以輸出數目由0，1，2，至24公斤。以第一階段為例，可能的輸入約可畫畫分為四個(見下表)，由於第六號物品單位重量為7公斤，故在0-6公斤的剩餘重量下無法攜帶，當然其效用為0，如果勝於重量為7-13，則可攜帶一件，所產生效用為3，佔用的重量為7，最後一欄的Q是將重量還原為件數。六號物品決策分析表狀態效用重量件數()0-60007-1337114-20614221-249213第二階段(五號物品決策分析)如下表： (,)+()()051015200-400005-6022517-93230010-11324410212-133545511465460015-16654660,150,317-1865767102196876851206876885,201,4219876890022-239879890,150,324981098101021. 若輸入為 0-4 ，則本階段及次階段皆無法分配，效用為 0。2. 當剩餘重量為 5-6 公斤，可帶一件，產生效用等於2。3. 當剩餘重量為 7-9 公斤時，有兩個交替方案，一是不帶 5 號物品而帶 6 號物品，效用為3；另一個方案是帶一件 5 號物品，但此時剩餘重量不能攜帶 6 號物品，此案效用為 2，兩者比較，以前者為佳，分配重量及件數均為 0。其餘以此類推，請自行練習。第三階段(四號物品決策分析)如下表： (,)+()()09180-400005-622007-8330093449110-114440,90,112-135450014-156660,90,11667791177770,90,118778818219-2088880,9,180,1,221-2299890,90,12391010109,181,224101010100,9,180,1,2第四階段(三號物品決策分析)如下表： (,)+()()061218240-400005220062220,60,17-8323009-1042400114440,60,1125445001355450,60,1146546001566460,60,1167647001776670018876680019877680020887680,60,121988690022998690,60,123109881000241010988100,60,1第五階段(二號物品決策分析)如下表： (,)+()()050-400005-622006-833009-114400125500135550,130,114-156560016-177570018-1987800208880,130,12198900229990,130,123-241091000第六階段(一號物品決策分析)如下表： (,)+()()08162424101099100,80,1本例題有六個最適答案，以重量而言，各階段分配數為：A方案：0 0001014B方案：0 061800C方案：0 009014D方案：0 009150E方案：0 001850F方案：8 00907以攜帶件數表示為：A方案：0 00022B方案：0 01200C方案：0 00102D方案：0 00130E方案：0 00210F方案：1 00101六個方案所產生之效用均為0以上是假設可以重複攜帶物品而分析的，倘若物品不得重複，此時，每一個階段只有二個決策，即帶或不帶。如果不帶，重量為0；帶則為各物品之單位重量，因為物品攜帶並無先後次序關係，本例題將改1號物品先分配，換言之，即視1號物品為第一階段，2號物品為第二階段等等。第一階段(一號物品決策分析)如下表：()080-78-2400-3030801本階段輸入可分為二種可能，當輸入為0-7時無法攜帶1號物品，效用為0；若輸入為8-24，亦僅能攜帶一件效用為3。第二階段(二號物品決策分析)如下表： ()0130-78-1213-2021-240333-5803580013130011本階段輸入有四種可能： 1.當輸入為0-7時，本階段及次階段均不足分配，故效用為0。2.當輸入為8-12時，可攜帶一件1號物品，效用為3。3.當輸入為13-20時，如果本階段不分配，次階段只能帶一件1號物品，次階段不能攜帶1號物品，此方案效用為5。4.當輸入為21-24時，本階段不分配方案，產生效用為3；另一方案為1號及2號物品各帶一件，效用為8。倣照同樣方式，自行練習求解，答案應為攜帶1號、4號及6號物品各一件，產生效用為10。推銷人員問題：台北電器公司共有五名推銷人員，該公司將台北市劃分為東、北、南三個地區，假設這五個人的工作效率大致相同(即不論分配至任何地區，工作績效均相同)。本例題目標為追求最大利潤，但分配在各地區時，由於市場因素的限制和報酬遞增及遞減的不同階段，每區配備人數不同時所能獲得的利潤貢獻並非直線關係，經過分析後，估計得各地區配置不同人數之利潤貢獻如下表：各區不同銷售員人數之利潤貢獻人數北區南區東區0 0 0 01 45 20 502 70 45 703 90 75 8041051101005120150130解：東區決策分析表S0001 5012 7023 8034100451305南區決策分析表 S=0123450000150205002707045700或13809095759524100100115125110125351301201251451601501604北區決策分析表S=01234551601701651601551201701價格決策：某電子公司發展出一種新型的計算機，預計未來五年內不會有競爭產品出現，故該公司可以任意設定價格。行銷部經理決定每個年度價格之幅度不超過50元，假定他選定四種價格策略：$300,$350,$400及$450，經過詳細評估後每個年度依照不同價格所能獲得之淨利如下表所示，試問應如何決定每個年度的價格使得五年之全部報酬最大？定價策略各年度報酬資料表(單位：百萬元)年度價格12345$3008525405080$3507040802040$4005535907030$4508575256035解：第四年之最適策略分析表 年度價格12345$300130808525405080$350100407040802040$400110305535907030$45095358575256035最適定價策略分析表 年度價格12345$300335235170130808525405080$350320250210100407040802040$400330245200110305535907030$45036027513595358575256035結論：各年價格策略依次為：$450$450$400$400$350總利潤為8575907040=360。