動態(tài)規(guī)劃 [兼容模式].pdf

《動態(tài)規(guī)劃 [兼容模式].pdf》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、動態(tài)規(guī)劃(Dynamicprogramming)動態(tài)規(guī)劃的基本思想最短路徑問題投資分配問題背包問題zhyw動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個n維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。zhyw動態(tài)決策問題的特點：系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素；即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策

2、；找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。多階段決策問題：是動態(tài)決策問題的一種特殊形式；在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間進程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段；每個階段都要進行決策,目的是使整個過程的決策達到最優(yōu)效果。zhyw決策決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)12?n多階段決策問題的典型例子：1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。2.機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，

3、產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u的關系為1g=g(u)1zhyw這時，機器的年完好率為a，即如果年初完好機器的數(shù)量為u，到年終完好的機器就為au,0

4、定航天飛機的飛行方向和速度（狀態(tài)），使之能最省燃料和實現(xiàn)目的（如軟著落問題）。不包含時間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。4.線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當?shù)匾腚A段的概念，應用動態(tài)規(guī)劃方法加以解決。zhyw5.最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最小）。C61128DE113B3135C25F625145AD1EG83222233B72C3336F662D3E8433C4123zhy

5、w456一、動態(tài)規(guī)劃的基本思想（一）、基本概念1、階段：把一個問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)時間和空間的自然特征來進行的，但要便于問題一個數(shù)、轉化為多階段決策。年、月、一組數(shù)、路段2、狀態(tài)：表示每個階段開始所處的一個向自然狀況或客觀條件。通常一個階段有若干個狀態(tài)量，描述過程狀態(tài)的變量稱為狀態(tài)變量。狀態(tài)變量的取值有一定的允許集合或范圍，此集合zhyw稱為狀態(tài)允許集合。3、決策：表示當過程處于某一階段的某個狀態(tài)時，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱

6、為決策。描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。4、多階段決策過程可以在各個階段進行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉移來實現(xiàn)的；系統(tǒng)在某一階段的狀態(tài)轉移不但與系統(tǒng)的當前的狀態(tài)和決策有關，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有zhyw關。其狀態(tài)轉移方程如下（一般形式）狀態(tài)轉移方程是確定s?T(s,u)過程由一個狀態(tài)到另2111s?T(s,u,s,u)一個狀態(tài)的演變過程。321122??如果第k階段狀態(tài)變

7、量s的值、該階段的決策s?T(s,u,s,u,?,s,u)kk?1k1122kk變量一經(jīng)確定，第k+1階段狀態(tài)變量s的值k+1圖示如下：也就確定。uuu12ksssss123kk+112?k能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。zhyw無后效性(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展；構造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求；如果狀態(tài)變量不能滿足無后效

8、性的要求，應適當?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉移方程如下