數(shù)學(xué)建模講座(康愷)(修改).ppt

《數(shù)學(xué)建模講座(康愷)(修改).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

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

3、這時，機器的年完好率為a，即如果年初完好機器的數(shù)量為u，到年終完好的機器就為au,0

4、質(zhì)上是一次決策問題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。4.線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動態(tài)規(guī)劃方法加以解決。5.最短路問題：給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643（一）、基本概念1、階段：把一個問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)

5、時間和空間的自然特征來進(jìn)行的，但要便于問題轉(zhuǎn)化為多階段決策。2、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量。年、月、路段一個數(shù)、一組數(shù)、一個向量狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。一、動態(tài)規(guī)劃的基本思想3、決策：表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)

6、移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。4、多階段決策過程可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；圖示如下：狀態(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ī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。動態(tài)規(guī)劃

7、中能處理的狀態(tài)轉(zhuǎn)移方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下無后效性(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求；5、策略：是一個按順序排列的決策組成的集合。在實際問題中，可供選擇的策略有一定的范圍，稱為允許策略集合。從允許策略集合中找出達(dá)到最