數模一個大佬的博客

【動態規劃】

1.1 動態規劃的研究內容與學習方法

把多階段過程轉化為一系列單階段問題再逐個求解；
一些與時間無關的靜態規劃（如線性規劃、非線性規劃），只要人為地引進時間因素，把它視為多階段決策過程，！也可以用動態規劃方法方便地求解，但是要必須對具體問題進行具體分析處理。可用于求解最短路線問題、 生產計劃問題、資源分配問題等多階段決策的優化問題；

它不象線性規劃那樣有一個標準的數學表達式和明確定義的一組規則，而必須對具體問題進行具體分析處理。
因此，在學習 時，除了要對基本概念和方法正確理解外，應以豐富的想象力去建立模型，用創造性的 技巧去求解。（巧妙！）

1.2 典型例題

根據過程的時間變量是離散的還是連續的，分為離散時間決策過程（discrete-timedecision process）和連續時間決策過程（continuous-time decision process）；根據過程的演變是確定的還是隨機的，分為確定性決策過程分為確定性決策過程（deterministic decision process）和隨機性決策過程（stochastic decision process），其中應用最廣的是確定性多階段決策過程。

例 1 最短路線問題

例 2 生產計劃問題

工廠生產某種產品，每單位（千件）的成本為 1（千元），每次開工的固定成本為 3 （千元），工廠每季度的最大生產能力為 6（千件）。經調查，市場對該產品的需求量第 一、二、三、四季度分別為 2，3，2，4（千件）。如果工廠在第一、二季度將全年的需 求都生產出來，自然可以降低成本（少付固定成本費），但是對于第三、四季度才能上 市的產品需付存儲費，每季每千件的存儲費為 0.5（千元）。還規定年初和年末這種產品 均無庫存。試制定一個生產計劃，即安排每個季度的產量，使一年的總費用（生產成本 和存儲費）最少。

2. 基本方程和計算方法

2.1 動態規劃的基本概念和基本方程

一個多階段決策過程最優化問題的動態規劃模型通常包含以下要素。

2.1.1 階段

階段(step)是對整個過程的自然劃分。通常根據時間順序或空間順序特征來劃分階段，以便按階段的次序解優化問題。階段變量一般用k = 1,2,…,n 表示。

在例 1 中由 A 出發為 k = 1，由 (i = 1,2) 出發為 k = 2 ，依此下去從 (i = 1,2) 出發為 k = 6 ，共 n = 6個階段。在例 2 中按照第一、二、三、四季度分為k = 1,2,3,4，共四個階段。

2.1.2 狀態

狀態（state）表示每個階段開始時過程所處的自然狀況。它應能描述過程的特征并 且無后效性，即當某階段的狀態變量給定時，這個階段以后過程的演變與該階段以前各 階段的狀態無關。通常還要求狀態是直接或間接可以觀測的。

根據過程演變的具體情況，狀態變量可以是離散的或連續的。為了計算的方便有時 將連續變量離散化；為了分析的方便有時又將離散變量視為連續的。 狀態變量簡稱為狀態。

2.1.3 決策

當一個階段的狀態確定后，可以作出各種選擇從而演變到下一階段的某個狀態，這 種選擇手段稱為決策（decision），在最優控制問題中也稱為控制（control）。

決策變量簡稱決策。
2.1.4 策略


2.1.5. 狀態轉移方程
在確定性過程中，一旦某階段的狀態和決策為已知，下階段的狀態便完全確定。用 狀態轉移方程（equation of state transition）表示這種演變規律，寫作

2.1.6. 指標函數和最優值函數

2.1.7 最優策略和最優軌線

2.1.8 遞歸方程

3.用 lingo 求解例 1 最短路線問題。

model: Title Dynamic Programming; sets: vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L; road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4, C1 D1,C1 D2,C2 D1,C2 D2,C3 D2,C3 D3,C4 D2,C4 D3, D1 E1,D1 E2,D2 E2,D2 E3,D3 E2,D3 E3, E1 F1,E1 F2,E2 F1,E2 F2,E3 F1,E3 F2,F1 G,F2 G/:D; endsets data: D=5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3; L=0,,,,,,,,,,,,,,,; enddata @for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i))); end

本節的動態規劃基本思想和一些經典例題就先寫到這里。

參考文獻

總結

以上是生活随笔為你收集整理的数学建模算法之动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。