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

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

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

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

3、度地根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃。2.機(jī)器負(fù)荷分配問(wèn)題：某種機(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)12n?狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策4這時(shí)，機(jī)器的年完好率為a,0

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

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

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

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

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