第一節(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)用舉例第七章動態(tài)規(guī)劃7.1多階段決策過程的最優(yōu)化17.1多階段決策過程的最優(yōu)化動態(tài)規(guī)劃是運籌學的重要分支，他的研究對象是多階段決策問題。所謂多階段決策問題，是指問題本身可以按照時間、空間等劃分為若干個相互聯(lián)系的階段．7.1多階段決策過程的最優(yōu)化動態(tài)規(guī)劃是運籌學的重要分支2動態(tài)規(guī)劃模型的分類：連續(xù)型與離散型確定型與隨機型時間的與空間的…………實際問題常常是復合的。本章主要研究動態(tài)與靜態(tài)確定型的決策過程。動態(tài)規(guī)劃模型的分類：連續(xù)型與離散型確定型與隨機型時間37.1.1

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

多階段決策問題舉例（1）工廠生產(chǎn)過程（2）設(shè)備更新問題（3）連續(xù)生產(chǎn)過程的控制問題（1）資源分配問題（2）運輸網(wǎng)絡(luò)問題與時間有關(guān)與時間無關(guān)7.1.2多階段決策問題舉例（1）工廠生產(chǎn)過程（2）設(shè)備更57.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)上．7.1.3動態(tài)規(guī)劃求解的多階段決策問題的特點一般來說6例

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

動態(tài)規(guī)劃方法導引例最短線路問題從地到地鋪設(shè)一條管道，中間經(jīng)過三個中間站7枚舉法枚舉法8局部最優(yōu)法（貪婪算法）局部最優(yōu)法（貪婪算法）9（動態(tài)規(guī)劃的逆序法）：1.先確定第四個階段的最短子路線記作：其中，表示從第k階段的起點X

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

設(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è)備分配問題100臺相同的機器被分配來加工兩種不同的產(chǎn)品16第一階段（即第一周）機器總臺數(shù)為設(shè)用于加工A產(chǎn)品的機器臺數(shù)為臺求得第一階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺動態(tài)規(guī)劃的順序法：第一階段（即第一周）機器總臺數(shù)為設(shè)用于加工A產(chǎn)品的機器臺數(shù)為17第二階段（即第二周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺第二階段（即第二周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器18第三階段（即第三周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺第三階段（即第三周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器19第四階段（即第四周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺第四階段（即第四周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器20綜上所述每一階段開始時機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺四個階段的總收益為綜上所述每一階段開始時機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機21問題就變?yōu)椋捍_定這四個階段用于加工A產(chǎn)品的機器臺數(shù)使得四個階段的總收益為最大．問題就變?yōu)椋捍_定這四個階段用于加工A產(chǎn)品的機器臺數(shù)使得四個階22第七章動態(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)用舉例第七章動態(tài)規(guī)劃7.1多階段決策過程的最優(yōu)化237.1多階段決策過程的最優(yōu)化動態(tài)規(guī)劃是運籌學的重要分支，他的研究對象是多階段決策問題。所謂多階段決策問題，是指問題本身可以按照時間、空間等劃分為若干個相互聯(lián)系的階段．7.1多階段決策過程的最優(yōu)化動態(tài)規(guī)劃是運籌學的重要分支24動態(tài)規(guī)劃模型的分類：連續(xù)型與離散型確定型與隨機型時間的與空間的…………實際問題常常是復合的。本章主要研究動態(tài)與靜態(tài)確定型的決策過程。動態(tài)規(guī)劃模型的分類：連續(xù)型與離散型確定型與隨機型時間257.1.1

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

多階段決策問題舉例（1）工廠生產(chǎn)過程（2）設(shè)備更新問題（3）連續(xù)生產(chǎn)過程的控制問題（1）資源分配問題（2）運輸網(wǎng)絡(luò)問題與時間有關(guān)與時間無關(guān)7.1.2多階段決策問題舉例（1）工廠生產(chǎn)過程（2）設(shè)備更277.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)上．7.1.3動態(tài)規(guī)劃求解的多階段決策問題的特點一般來說28例

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

動態(tài)規(guī)劃方法導引例最短線路問題從地到地鋪設(shè)一條管道，中間經(jīng)過三個中間站29枚舉法枚舉法30局部最優(yōu)法（貪婪算法）局部最優(yōu)法（貪婪算法）31（動態(tài)規(guī)劃的逆序法）：1.先確定第四個階段的最短子路線記作：其中，表示從第k階段的起點X

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

設(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è)備分配問題100臺相同的機器被分配來加工兩種不同的產(chǎn)品38第一階段（即第一周）機器總臺數(shù)為設(shè)用于加工A產(chǎn)品的機器臺數(shù)為臺求得第一階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺動態(tài)規(guī)劃的順序法：第一階段（即第一周）機器總臺數(shù)為設(shè)用于加工A產(chǎn)品的機器臺數(shù)為39第二階段（即第二周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺第二階段（即第二周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器40第三階段（即第三周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為臺第三階段（即第三周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器41第四階段（即第四周）機器總臺數(shù)為設(shè)該階段用于加工A產(chǎn)品的機器臺數(shù)為臺求得該階段的總收益為則用于加工B產(chǎn)品的機器臺數(shù)為