系列文章

【管理運(yùn)籌學(xué)】第 8 章 | 動(dòng)態(tài)規(guī)劃（1，多階段決策過(guò)程與動(dòng)態(tài)規(guī)劃基本概念）
【管理運(yùn)籌學(xué)】第 8 章 | 動(dòng)態(tài)規(guī)劃（2，動(dòng)態(tài)規(guī)劃的基本思想與模型求解）
【管理運(yùn)籌學(xué)】第 8 章 | 動(dòng)態(tài)規(guī)劃（3，資源分配問(wèn)題）
【管理運(yùn)籌學(xué)】第 8 章 | 動(dòng)態(tài)規(guī)劃（4，生產(chǎn)與儲(chǔ)存問(wèn)題）
【管理運(yùn)籌學(xué)】第 8 章 | 動(dòng)態(tài)規(guī)劃（5，設(shè)備更新問(wèn)題）

引言

倒回來(lái)學(xué)動(dòng)態(tài)規(guī)劃，網(wǎng)絡(luò)計(jì)劃和排隊(duì)論先放到后面吧。

動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法。該方法由美國(guó)數(shù)學(xué)家貝爾曼等人在 20 世紀(jì) 50 年代初提出。

動(dòng)態(tài)規(guī)劃可用于解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃與庫(kù)存問(wèn)題、投資問(wèn)題等。由于它獨(dú)特的求解思路，常比線性規(guī)劃或非線性規(guī)劃方法更有效。

動(dòng)態(tài)規(guī)劃模型的分類，根據(jù)決策過(guò)程的時(shí)間參數(shù)是離散的還是連續(xù)的，過(guò)程的演變是確定的還是隨機(jī)的，可以組合成離散確定型、連續(xù)隨機(jī)型等 4 中類型。其中，離散確定型是最基本的，也是本系列文章主要介紹的問(wèn)題。

一、多階段決策過(guò)程及實(shí)例

在生產(chǎn)和科學(xué)實(shí)驗(yàn)中，有一類活動(dòng)的過(guò)程，由于其特殊性，可將過(guò)程分為若干個(gè)相互聯(lián)系的階段，在它的每一個(gè)階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。

因此，各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成了一個(gè)決策序列，因而也就決定了整個(gè)過(guò)程的一條活動(dòng)路線。

這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為多階段決策過(guò)程，也稱為序貫決策過(guò)程（如下圖所示）。這種問(wèn)題就稱為多階段決策問(wèn)題。

在多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義。因此，把處理它的方法稱為動(dòng)態(tài)規(guī)劃方法。

但是，一些與時(shí)間沒(méi)有關(guān)系的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃等）問(wèn)題，只要人為地引進(jìn)“時(shí)間”因素，也可以把它視為多階段決策問(wèn)題，用動(dòng)態(tài)規(guī)劃方法去處理。

我們上一章在圖論中，學(xué)習(xí)的最短路問(wèn)題，就可以看成是多階段決策問(wèn)題，每個(gè)階段都去尋找最短路。如下圖，可以看成是一個(gè) 4 階段決策問(wèn)題。

二、動(dòng)態(tài)規(guī)劃的基本概念和方法

2.1 動(dòng)態(tài)規(guī)劃的基本概念

1.階段（Stage）

將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解為若干相互聯(lián)系的階段，以便按順序去求解每階段的解，常用字母 $k$ 表示階段變量。

上面提到的 4 階段求最短路問(wèn)題中，第一階段包括（A, B1）, （A, B2）。第四階段包括（D1, E）, （D2, E）, （D3, E）。其余階段以此類推。

北交大的書(shū)規(guī)定，$k=1$ 表示實(shí)際問(wèn)題中的第 1 決策階段。在一個(gè) $n$ 階段決策問(wèn)題中，$k=n$ 表示最后一個(gè)決策階段。

2.狀態(tài)（State）

各階段開(kāi)始時(shí)的客觀條件叫作狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用 $s_k$ 表示第 $k$ 階段的狀態(tài)變量，狀態(tài)變量 $s_k$ 的取值集合稱為狀態(tài)集合 $S_k$ 。

如上面最短路的例子中，第一階段為狀態(tài) A ，第二階段有兩個(gè)狀態(tài)：B1, B2 。狀態(tài)變量集合 S 1 = { A } S_1=\{A\} S1?={A} ，后面各階段的狀態(tài)集合分別為： S 2 = { B 1 , B 2 } , S 3 = { C 1 , C 2 , C 3 , C 4 } , S 4 = { D 1 , D 2 , D 3 } S_2=\{B1,B2\},S_3=\{C1,C2,C3,C4\},S_4=\{D1,D2,D3\} S2?={B1,B2},S3?={C1,C2,C3,C4},S4?={D1,D2,D3} 。

動(dòng)態(tài)規(guī)劃的狀態(tài)應(yīng)具有如下性質(zhì)：當(dāng)某階段狀態(tài)給定以后，在這階段以后的過(guò)程的發(fā)展不受這段以前狀態(tài)的影響。也就是說(shuō)，過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前狀態(tài)去影響它未來(lái)的發(fā)展，這稱為無(wú)后效性。

如果所選定的變量不具備無(wú)后效性，就不能作為這個(gè)狀態(tài)變量來(lái)構(gòu)成動(dòng)態(tài)規(guī)劃模型。

3.決策和策略（Decision and Policy）

當(dāng)各階段的狀態(tài)確定以后，就可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。表示決策的變量稱為決策變量，常用 $u_k(s_k)$ 表示第 $k$ 階段當(dāng)狀態(tài)為 $s_k$ 時(shí)的決策變量。

實(shí)際問(wèn)題中，決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合，常用 $D_k(s_k)$ 表示第 $k$ 階段從狀態(tài) $s_k$ 出發(fā)的允許決策集合，顯然，有 $u_k(s_k)\in D_k(s_k)$ 。

例如，前面最短路問(wèn)題圖中，狀態(tài)集合 S 2 = { B 1 , B 2 } S_2=\{B1,B2\} S2?={B1,B2} ，從狀態(tài) $B1$ 出發(fā)，有 3 條路可走，即其決策集合為 D 2 ( B 1 ) = { C 1 , C 2 , C 3 } D_2(B_1)=\{C1,C_2,C_3\} D2?(B1?)={C1,C2?,C3?} ，如果走去 $C3$ ，則此時(shí)決策變量可表示為 $u_2(B1)=C3$ 。

各段決策確定后，整個(gè)問(wèn)題的決策序列就構(gòu)成一個(gè)策略，用 $p_{1,n}(u_1,u_2,?,u_n)$ 表示。對(duì)每個(gè)實(shí)際問(wèn)題，可供選擇的策略有一定范圍，稱為允許策略集合，用 $P$ 表示。使得整個(gè)問(wèn)題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。

4.狀態(tài)轉(zhuǎn)移方程

動(dòng)態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段決策的結(jié)果。如果給定了第 $k$ 階段的狀態(tài) $s_k$ ，本階段決策為 $u_k(s_k)$ ，則第 $k+1$ 階段的狀態(tài) $s_{k+1}$ 也就完全確定，它們的關(guān)系可用公式 $$s_{k+1}=T_k(s_k,u_k)$$ 表示，由于其表示了由 $k$ 階段到 $k+1$ 階段的狀態(tài)轉(zhuǎn)移規(guī)律，所以稱為狀態(tài)轉(zhuǎn)移方程。

前面的最短路問(wèn)題中，$s_{k+1}=u_k$ 。

5.指標(biāo)函數(shù)

用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)。一個(gè) $n$ 段決策過(guò)程中，從 1 到 n 叫作問(wèn)題的原過(guò)程，對(duì)于任意一個(gè)給定的 $k(1\le k\le n)$ ，從第 $k$ 階段到第 $n$ 階段的過(guò)程叫作原過(guò)程的一個(gè)后部子過(guò)程。$V_{1,n}(s_1,p_{1,n})$ 表示從初始狀態(tài) $s_1$ 采用策略 $p_{1,n}$ 時(shí)原過(guò)程的效益值，而 $V_{k,n}(s_k,p_{k,n})$ 表示在第 $k$ 階段狀態(tài)為 $s_k$ 采用策略 $p_{k,n}$ 時(shí)，后部子過(guò)程的效益值。

最優(yōu)指標(biāo)記為 $f_k(s_k)$ ，它表示從 $k$ 階段狀態(tài) $s_k$ 采用最優(yōu)策略 $p_{k,n}^{?}$ 時(shí)，后部子過(guò)程的最優(yōu)效益值。$f_k(s_k)$ 與 $V_{k,n}(s_k,p_{k,n})$ 間有關(guān)系：$$f_k(s_k)=V_{k,n}(s_k,p_{k,n}^{?})=op{t}_{p_{k,n}\in P_{k,n}}{V}_{k,n}(s_k,p_{k,n})$$ 注：$opt$ 全稱為 optimization ，表示最優(yōu)。

當(dāng) $k=1$ 時(shí)，$f_1(s_1)$ 就是從初始狀態(tài) $s_1$ 到全過(guò)程結(jié)束的整體最優(yōu)函數(shù)。

拿前面的最短路問(wèn)題舉例，指標(biāo)函數(shù)就是距離。比如在第二階段，狀態(tài)為 $B2$ 時(shí)，$V_{B_2,E}$ 就是 $B_2$ 到 $E$ 之間的可能走的某個(gè)距離，$f_2(B_2)$ 表示 $B_2$ 到 $E$ 之間的最短距離。

寫(xiě)在最后

光是基本概念的介紹，我就感受到強(qiáng)度了，不過(guò)沒(méi)關(guān)系，反復(fù)理解，多花些時(shí)間，相信也是沒(méi)問(wèn)題的。

下一篇，我們來(lái)學(xué)習(xí)關(guān)于動(dòng)態(tài)規(guī)劃的基本思想。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-856070.html

到了這里，關(guān)于【管理運(yùn)籌學(xué)】第 8 章 | 動(dòng)態(tài)規(guī)劃（1，多階段決策過(guò)程與動(dòng)態(tài)規(guī)劃基本概念）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！