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

第七章動態(tài)規(guī)劃7.1

多階段決策過程的最優(yōu)化7.2

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

多階段決策問題動態(tài)規(guī)劃的研究對象是多階段決策問題。對于多階段決策問題，根據(jù)問題本身的特點可以將其求解過程劃分為若干個相互聯(lián)系的階段。每個階段都有若干個方案可供選擇，因此每一階段都需要做出決策。各個階段確定的決策構(gòu)成一個決策序列，稱為一個策略．在所有可供選擇的策略中，對應(yīng)效果最好的策略稱為最優(yōu)策略。7.1.2

多階段決策問題舉例（1）工廠生產(chǎn)過程（2）設(shè)備更新問題（3）連續(xù)生產(chǎn)過程的控制問題（1）資源分配問題（2）運輸網(wǎng)絡(luò)問題與時間有關(guān)與時間無關(guān)7.1.3

動態(tài)規(guī)劃求解的多階段決策問題的特點一般來說，系統(tǒng)在某個階段的狀態(tài)可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關(guān)．能用動態(tài)規(guī)劃方法求解的多階段決策問題必須具有“無后效性”的特點。所謂“無后效性”，即過去的歷史不影響未來的發(fā)展．過往的歷史僅僅體現(xiàn)在本階段的初始狀態(tài)上．例

最短線路問題從地到地鋪設(shè)一條管道，中間經(jīng)過三個中間站；第一中間站可選或，第二中間站可選、或，第三中間站可選或，問如何選擇可使管線最短？7.1.3

動態(tài)規(guī)劃方法導(dǎo)引枚舉法局部最優(yōu)法（貪婪算法）（動態(tài)規(guī)劃的逆序法）：1.先確定第四個階段的最短子路線記作：其中，表示從第k階段的起點X

到終點E的最短路線.（分四個階段）動態(tài)規(guī)劃法2.再確定最后兩個階段的最短子路線3.確定后三個階段的最短子路線3.綜合四個階段的最短子路線分析：第四階段的最短子路線三四階段的最短子路線二三四階段的…一至四階段的…√√√√動態(tài)規(guī)劃法的基本思路:把復(fù)雜問題分解為一系列同類型的便于求解的子問題動態(tài)規(guī)劃法的特點/優(yōu)點:整體最優(yōu)蘊含階段最優(yōu)例

設(shè)備分配問題100臺相同的機器被分配來加工兩種不同的產(chǎn)品A和B；已知：加工A產(chǎn)品時，機器每周的損壞率為，加工B產(chǎn)品時，機器每周的損壞率為；生產(chǎn)A產(chǎn)品時，每臺每周的收益為1000元，B產(chǎn)品每臺每周的收益為700元；問采取怎樣的分配方案可使四周內(nèi)總收益最大？第一階段（即第一周）機器總臺數(shù)為設(shè)用于加工A產(chǎn)品的機器臺數(shù)為臺求得第一階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺動態(tài)規(guī)劃的順序法：第二階段（即第二周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺第三階段（即第三周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺第四階段（即第四周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺綜上所述每一階段開始時機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺該階