第一節(jié)多階段決策過程的最優(yōu)化

1、第七章第七章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃7.17.1 多階段決策過程的最優(yōu)化7.27.2 動(dòng)態(tài)規(guī)劃的基本概念和求解思路7.3 7.3 離散型動(dòng)態(tài)規(guī)劃問題7.4 7.4 連續(xù)型動(dòng)態(tài)規(guī)劃問題7.5 7.5 動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例7.1 多階段決策過程的最優(yōu)化動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的重要分支，他的研究對(duì)象是多階段決策問題。所謂多階段決策問題，是指問題本身可以按照時(shí)間、空間等劃分為若干個(gè)相互聯(lián)系的階段動(dòng)態(tài)規(guī)劃模型的分類：連續(xù)型 與 離散型確定型 與 隨機(jī)型時(shí)間的 與 空間的 實(shí)際問題常常是復(fù)合的。本章主要研究動(dòng)態(tài)與靜態(tài)確定型的決策過程。7.17.1.1.1 多階段決策問題動(dòng)態(tài)規(guī)劃的研究對(duì)象是多階段決策問題。對(duì)于多階段決

2、策問題，根據(jù)問題本身的特點(diǎn)可以將其求解過程劃分為若干個(gè)相互聯(lián)系的階段。每個(gè)階段都有若干個(gè)方案可供選擇，因此每一階段都需要做出決策。各個(gè)階段確定的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略在所有可供選擇的策略中，對(duì)應(yīng)效果最好的策略稱為最優(yōu)策略。7.17.1.2.2 多階段決策問題舉例（1）工廠生產(chǎn)過程（2）設(shè)備更新問題（3）連續(xù)生產(chǎn)過程的控制問題（1）資源分配問題（2）運(yùn)輸網(wǎng)絡(luò)問題 與時(shí)間有關(guān)與時(shí)間無關(guān)7.17.1.3.3 動(dòng)態(tài)規(guī)劃求解的多階段決策問題的特點(diǎn) 一般來說，系統(tǒng)在某個(gè)階段的狀態(tài)可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關(guān) 能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策問題必須具有“無后效性”的特點(diǎn)。 所謂“無后效性

3、”，即過去的歷史不影響未來的發(fā)展 過往的歷史僅僅體現(xiàn)在本階段的初始狀態(tài)上例例 最短線路問題A1B2B1C2C3C1D2DE3333444455666774從 地到 地鋪設(shè)一條管道，中間經(jīng)過三個(gè)中間站；第一中間站可選 或 ，第二中間站可選 、 或 ，第三中間站可選 或 ，問如何選擇可使管線最短？A1B2B1C2C3C1D2DE7.17.1.3.3 動(dòng)態(tài)規(guī)劃方法導(dǎo)引枚枚舉舉法法A12BB 123CCC 12DD E123CCC 12DD 12DD 12DD 12DD 12DD EEEEEEEEEEE171916172017171914151815 221ABCDE局部最優(yōu)法局部最優(yōu)法A1B2B1C

4、2C3C1D2DE3333444455666774（貪婪算法）（貪婪算法）（動(dòng)態(tài)規(guī)劃的逆序法）：1.先確定第四個(gè)階段的最短子路線1:DE2:DE1(,)3d DE 2(,)4d DE 記作：4142()3()4fDfD 其中， 表示從第k 階段的起點(diǎn) X 到終點(diǎn)E 的最短路線.()kfXA1B2B1C2C3C1D2DE3333444455666774（分四個(gè)階段）動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法2.再確定最后兩個(gè)階段的最短子路線11:CDE11411242(,)()min(,)()d CDfDd CDfD 313233()()()fCfCfC 53min64 8 21412242(,)()min(,)()

5、d CDfDd CDfD 43min44 7 31413242(,)()min(,)()d CDfDd CDfD 73min34 7 21:CDE32:CDE31()8fC 32()7fC 33()7fC A1B2B1C2C3C1D2DE33334444556667743.確定后三個(gè)階段的最短子路線113112321333(,)()min(,)()(,)()d B CfCd B CfCd B CfC 2122()()fBfB 68min 6777 13 121:BCDE21()13fB 22()10fB 213122322333(,)()min(,)()(,)()d B CfCd B CfCd

6、 B CfC 58min 3747 10 221:BCDEA1B2B1C2C3C1D2DE33334444556667743.綜合四個(gè)階段的最短子路線121222(,)()min(,)()d A BfBd A BfB 1()fA 313min410 14 221:ABCDE1()14fA A1B2B1C2C3C1D2DE3333444455666774分析：2211:()14ABCDEfA 1212122122:()13:()10BCDEfBBCDEfB 141242:()3:()4DEfDDEfD 113121323233:()8:()7:()7CDEfCCDEfCCDEfC 第四階段的最短

7、子路線三四階段的最短子路線二三四 階段的一至四 階段的動(dòng)態(tài)規(guī)劃法的基本思路:把復(fù)雜問題分解為一系列同類型的便于求解的子問題動(dòng)態(tài)規(guī)劃法的特點(diǎn)/ /優(yōu)點(diǎn):整體最優(yōu)蘊(yùn)含階段最優(yōu)例例 設(shè)備分配問題100臺(tái)相同的機(jī)器被分配來加工兩種不同的產(chǎn)品A 和B；已知：11015加工A產(chǎn)品時(shí)，機(jī)器每周的損壞率為 ，加工B產(chǎn)品時(shí)，機(jī)器每周的損壞率為 ；生產(chǎn)A產(chǎn)品時(shí)，每臺(tái)每周的收益為1000元，B產(chǎn)品每臺(tái)每周的收益為700元；問采取怎樣的分配方案可使四周內(nèi)總收益最大？第一階段（即第一周）第一階段（即第一周）機(jī)器總臺(tái)數(shù)為1100s 設(shè)用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)求得第一階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)1x

8、1100 x g sxxsx 111111(,)1000700()11700300sx 動(dòng)態(tài)規(guī)劃的順序法：第二階段（即第二周）第二階段（即第二周）機(jī)器總臺(tái)數(shù)為2s 設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)求得該階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)gsxxsx 222222(,)1000700()22700300sx 111()10sx 1115sx 2x22sx 11911010sx 第三階段（即第三周）第三階段（即第三周）機(jī)器總臺(tái)數(shù)為3s 設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)求得該階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)gsxxsx 333333(,)1000700()337

9、00300sx 221()10sx 2215sx 3x33sx 22911010sx 第四階段（即第四周）第四階段（即第四周）機(jī)器總臺(tái)數(shù)為4s 設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)求得該階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)gsxxsx 444444(,)1000700()44700300sx 331()10sx 3315sx 4x44sx 33911010sx 綜上所述綜上所述每一階段開始時(shí)機(jī)器總臺(tái)數(shù)為1191 (2,3,4)1010iiissxi 設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)該階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為 臺(tái)iiiiig sxsx (,)700300ixiisx 1100s 四個(gè)階段的總收益為iiiiiiiRg sxsx 4411(,)7003001234()x x x x, , , , , ,問題就變?yōu)椋簡栴}就變?yōu)椋捍_定這四個(gè)階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)1234xxxx、使得四個(gè)階段的總收益為最大iiiiiiiRg sxsx 4411(,)700300人有了知識(shí)，就會(huì)具備各種分析能力