動態(tài)規(guī)劃的基本方法ppt課件.ppt

《動態(tài)規(guī)劃的基本方法ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、動態(tài)規(guī)劃的基本思想及應(yīng)用(Dynamicprogramming)5.1動態(tài)規(guī)劃的實例5.2動態(tài)規(guī)劃的基本概念5.4資源分配問題5.5背包問題5.3動態(tài)規(guī)劃方法的基本思想*5.6排序問題1動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個n維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。5.1動態(tài)規(guī)劃的實例2

2、即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；每個階段都要進行決策,目的是使整個過程的決策達(dá)到最優(yōu)效果。動態(tài)決策問題的特點：系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素；找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。多階段決策問題：是動態(tài)決策問題的一種特殊形式；在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間進程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段；3多階段決策問題的典型例子：1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季

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

4、產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。相應(yīng)的機器年完好率b,0

5、絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664371、階段：把一個問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)時間和空間的自然特征來進行的，但要便于問題轉(zhuǎn)化為多階段決策。2、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)

6、變量。年、月、路段一個數(shù)、一組數(shù)、一個向量狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。5.2動態(tài)規(guī)劃的基本概念83、決策：表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。4、多階段決策過程

7、可以在各個階段進行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；9圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）12k?s1u1s2u2s3skuksk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。10動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下無后效性

8、(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求；如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。115、策略：是一個按順序排列的