運(yùn)籌動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃（DynamicProgramming）,動(dòng)態(tài)規(guī)劃是解決復(fù)雜系統(tǒng)優(yōu)化問題的一種方法。是解決動(dòng)態(tài)系統(tǒng)多階段決策過程的基本方法之一。,教學(xué)大綱:,理解動(dòng)態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程，通過資源分配和生產(chǎn)與存儲(chǔ)等問題,學(xué)習(xí)應(yīng)用動(dòng)態(tài)規(guī)劃解決多階段決策問題。重點(diǎn):掌握動(dòng)態(tài)規(guī)劃模型結(jié)構(gòu)、逆序法算法原理、資源分配、設(shè)備更新、生產(chǎn)于存貯等問題。難點(diǎn)為動(dòng)態(tài)規(guī)劃中狀態(tài)變量等的確定。,1.多階段的決策問題,引例1最短路問題,例2：生產(chǎn)與投入問題,例3：將一個(gè)單數(shù)C（C0)分成n個(gè)部分C1,C2,Cn之和，且Ci0（i=1,n），問如何分割使其乘積為最大,包含隨時(shí)間變化的因素和變量的系統(tǒng)。,系統(tǒng)在某個(gè)時(shí)刻的狀態(tài)，往往要依某種形式受過去某些決策的影響；,將時(shí)間作為決策變量之一的決策問題稱為動(dòng)態(tài)決策問題。,如經(jīng)濟(jì)系統(tǒng),生產(chǎn)系統(tǒng)等。,動(dòng)態(tài)系統(tǒng)：,線性系統(tǒng)、非線性系統(tǒng)。,動(dòng)態(tài)系統(tǒng)的特點(diǎn)：,動(dòng)態(tài)決策問題：,而系統(tǒng)的當(dāng)前狀態(tài)和決策又會(huì)影響系統(tǒng)今后的發(fā)展。,動(dòng)態(tài)規(guī)劃的研究對(duì)象,即在系統(tǒng)發(fā)展的不同時(shí)刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；,每個(gè)階段都要進(jìn)行決策,目的是使整個(gè)過程的決策達(dá)到最優(yōu)效果。,動(dòng)態(tài)決策問題的特點(diǎn)：,系統(tǒng)所處的狀態(tài)和時(shí)刻是進(jìn)行決策的重要因素；,找到不同時(shí)刻的最優(yōu)決策以及整個(gè)過程的最優(yōu)策略。,多階段決策問題：,是動(dòng)態(tài)決策問題的一種特殊形式；,在多階段決策過程中,系統(tǒng)的動(dòng)態(tài)過程可以按照時(shí)間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個(gè)階段；,多階段決策問題的典型例子：1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度地根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃。,2.機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1),這時(shí)，機(jī)器的年完好率為a，即如果年初完好機(jī)器的數(shù)量為u，到年終完好的機(jī)器就為au,0a1。,在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為h=h(u2),假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1。要求制定一個(gè)五年計(jì)劃，在每年開始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。,相應(yīng)的機(jī)器年完好率b,0b9/2,當(dāng),當(dāng),時(shí),時(shí),矛盾，舍去。,（最優(yōu)決策）,S20,一般動(dòng)態(tài)規(guī)劃應(yīng)用,精品課件！,精品課件！,動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn),優(yōu)點(diǎn):.最優(yōu)解是全局最優(yōu)解。.能得到一系列（包括子過程）的最優(yōu)解。.不需要對(duì)系統(tǒng)狀態(tài)轉(zhuǎn)移方程、階段效應(yīng)函數(shù)等的解析性質(zhì)作任何假