1、2022-4-191動態(tài)規(guī)劃動態(tài)規(guī)劃（Dynamic Programming） R. Bellman50年代執(zhí)教于普林斯頓和斯坦福大學，年代執(zhí)教于普林斯頓和斯坦福大學，后進入蘭德（后進入蘭德（Rand）研究所。）研究所。1957年發(fā)表年發(fā)表“Dynamic Programming”一書，標識動態(tài)規(guī)劃的正式誕生。一書，標識動態(tài)規(guī)劃的正式誕生。 動態(tài)規(guī)劃的研究對象和引例動態(tài)規(guī)劃的研究對象和引例動態(tài)規(guī)劃的理論基礎(chǔ)和具體迭代方動態(tài)規(guī)劃的理論基礎(chǔ)和具體迭代方 法法動態(tài)規(guī)劃的基本思想和基本方程動態(tài)規(guī)劃的基本思想和基本方程動態(tài)規(guī)劃的基本概念和定義動態(tài)規(guī)劃的基本概念和定義 動態(tài)規(guī)劃是解決復雜系統(tǒng)優(yōu)化問題的一種

2、方法。動態(tài)規(guī)劃是解決復雜系統(tǒng)優(yōu)化問題的一種方法。是解決是解決動態(tài)系統(tǒng)多階段動態(tài)系統(tǒng)多階段決策過程的基本方法之一。決策過程的基本方法之一。2022-4-192教學大綱教學大綱:理解理解:動態(tài)規(guī)劃基本概念、最優(yōu)化原理和動態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程，通過資源分配和生產(chǎn)與存儲基本方程，通過資源分配和生產(chǎn)與存儲等問題等問題,學習應用動態(tài)規(guī)劃解決多階段決學習應用動態(tài)規(guī)劃解決多階段決策問題。策問題。重點重點 : 掌握動態(tài)規(guī)劃掌握動態(tài)規(guī)劃模型結(jié)構(gòu)模型結(jié)構(gòu)、逆序法、逆序法算法原理算法原理、資源分配、設(shè)備更新、生產(chǎn)資源分配、設(shè)備更新、生產(chǎn)于存貯于存貯等問題。等問題。難點難點:為動態(tài)規(guī)劃中為動態(tài)規(guī)劃中狀態(tài)

3、變量狀態(tài)變量等的確定。等的確定。2022-4-19312345第一節(jié)第一節(jié) 動態(tài)規(guī)劃的研究對象和引例動態(tài)規(guī)劃的研究對象和引例引例引例1 最短路問題最短路問題A12345678E645877893389565621342022-4-194引例引例2：生產(chǎn)與存貯問題：生產(chǎn)與存貯問題某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后4個月市場需求預測如表2-1所示，每月生產(chǎn)單位產(chǎn)品的費用為0(0)( )(1,2,3,)jc jabjjmL其中為生產(chǎn)的固定費用，為可變生產(chǎn)費率，為生產(chǎn)能力。供應需求所剩余產(chǎn)品應存入倉庫，每月庫存單位產(chǎn)品的費用為( )*Ejcj（千元）2022-4-195計劃開始和計劃期末庫存量都是0。

4、試制定4個月的生產(chǎn)計劃，在滿足用戶需求的條件下使總費用最小。 i1234需求需求 2324iy2022-4-196 包含包含隨時間變化隨時間變化的因素和變量的系統(tǒng)。的因素和變量的系統(tǒng)。系統(tǒng)在某個時刻的狀態(tài)，往往要依某系統(tǒng)在某個時刻的狀態(tài)，往往要依某種形式受過去某些決策的影響；種形式受過去某些決策的影響；將時間作為決策變量之一的決策問將時間作為決策變量之一的決策問題稱為動態(tài)決策問題。題稱為動態(tài)決策問題。如經(jīng)濟系統(tǒng)如經(jīng)濟系統(tǒng),生產(chǎn)系統(tǒng)等生產(chǎn)系統(tǒng)等。動態(tài)系統(tǒng)動態(tài)系統(tǒng)： 線性系統(tǒng)、非線性系統(tǒng)。線性系統(tǒng)、非線性系統(tǒng)。動態(tài)系統(tǒng)動態(tài)系統(tǒng)的特點：的特點： 動態(tài)決策動態(tài)決策 問題：問題：而系統(tǒng)的當前狀態(tài)和決策又

5、會影響而系統(tǒng)的當前狀態(tài)和決策又會影響系統(tǒng)今后的發(fā)展。系統(tǒng)今后的發(fā)展。動態(tài)規(guī)劃的研究對象:2022-4-197即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；所處的狀態(tài)，不斷地做出決策；每個階段都要進行每個階段都要進行決策決策,目的是使整個過程的決策目的是使整個過程的決策 達到最優(yōu)效果。達到最優(yōu)效果。動態(tài)決策問題的特點：動態(tài)決策問題的特點：系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素；系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素；找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。多階段決策問題：多階段決

6、策問題：是動態(tài)決策問題的一種特殊形式；是動態(tài)決策問題的一種特殊形式；在多階段決策過程中在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間系統(tǒng)的動態(tài)過程可以按照時間進程分為進程分為狀態(tài)狀態(tài)相互相互聯(lián)系聯(lián)系而又相互而又相互區(qū)別區(qū)別的各個的各個階段階段；2022-4-198多階段決策問題的典型例子：多階段決策問題的典型例子： 1 . 生產(chǎn)決策問題：生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)

7、計劃。根據(jù)庫存和需求決定生產(chǎn)計劃。 2. 機器負荷分配問題：機器負荷分配問題：某種機器可以在高低某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量和投入生產(chǎn)的機器數(shù)量u1的關(guān)的關(guān)系為系為g=g(u1)12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策2022-4-199 這時，機器的年完好率為這時，機器的年完好率為a，即如果年初完好機，即如果年初完好機器的數(shù)量為器的數(shù)量為u，到年終完好的機器就為，到年終完好的機器就為au, 0a1。 在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量在低負荷下

8、生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生和投入生產(chǎn)的機器數(shù)量產(chǎn)的機器數(shù)量u2的關(guān)系為的關(guān)系為 h=h(u2) 假定開始生產(chǎn)時完好的機器數(shù)量為假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制。要求制定一個五年計劃，在定一個五年計劃，在每年開始時，決定如何重新每年開始時，決定如何重新分配分配完好的完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。 相應的機器年完好率相應的機器年完好率b, 0 b9/2)s(fxmax)s(fsx221011411 29100959994101121111100111100111 xss,xsxsmaxxsxmax)(f*xx0401010200100241011111211110011 *xx)(fx)(fx)xs(xmax)(f2229s)s(f 22222s)s(f 當當當當時時時時矛盾，舍去矛盾，舍去。（最優(yōu)決策）（最優(yōu)決策）S202022-4-1942動態(tài)規(guī)劃的優(yōu)缺點動態(tài)規(guī)劃的優(yōu)缺點優(yōu)點優(yōu)點: . 最優(yōu)解是全局最優(yōu)解。最優(yōu)解是全局最優(yōu)解。 . 能得到一系列（包括子過程）的最優(yōu)解。能得到一系列（包括子過程）的最優(yōu)解。 . 不需要對系統(tǒng)狀態(tài)轉(zhuǎn)移方程、階段效應函數(shù)不需要對系統(tǒng)