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

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

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

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

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

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

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

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

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

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

設(shè)備分配問(wèn)題100臺(tái)相同的機(jī)器被分配來(lái)加工兩種不同的產(chǎn)品A和B；已知：加工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元；問(wèn)采取怎樣的分配方案可使四周內(nèi)總收益最大？第一階段（即第一周）機(jī)器總臺(tái)數(shù)為設(shè)用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)求得第一階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)動(dòng)態(tài)規(guī)劃的順序法：第二階段（即第二周）機(jī)器總臺(tái)數(shù)為設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)求得該階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)第三階段（即第三周）機(jī)器總臺(tái)數(shù)為設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)求得該階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)第四階段（即第四周）機(jī)器總臺(tái)數(shù)為設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)求得該階段的總收益為則用于加工B產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)綜上所述每一階段開(kāi)始時(shí)機(jī)器總臺(tái)數(shù)為設(shè)該階段用于加工A產(chǎn)品的機(jī)器臺(tái)數(shù)為臺(tái)該階