運籌學S01E05——動態規劃

INTRODUCTION

在這之前我們講了線性規劃，整數規劃還有目標規劃。實際上後兩種可以視為線性規劃的變形。同時他們研究的對象都是與時間無關，我們稱之為靜態規劃。而今天講的動態規劃是與時間有關的，他是研究多決策過程的一類問題。下面我們進入正題：

5.1Example

假設你現在呆在A處，目標去G處。如果問你有幾種走法，那你會很快算出答案。但現在告訴你每條路上花費時間是不同的，問你如何找到一條最快的路線？你可能會說這也簡單，把每一條路線的時間都算出來，然後對比就可以得出。

但學過運籌學還要運用暴力破解法是可恥的行為。你稍加思索:「在每一次分叉點都選取最短的路徑，這樣就可以花最少的時間。」

可還是不對，但思路是正確的，我們需要分多階段進行決策。

這類問題就是動態規劃問題，下面介紹動態規劃的基本概念與符號。

5.2 definition

我們可以將每次決策分為一個階段，上例就可以分為A——G階段，在每個階段都有不同的選擇，我們將這些選擇稱為狀態，如點集合{ }為第二階段的可達狀態集合，也可以記為 ={1,2} 。

狀態需要滿足的一個特性是：當階段狀態給定後，以後的發展不受此階段之前各段的影響（跟人生不一樣），這一種性質稱為 無後效性（馬爾可夫性）。

在每一階段你可以做出不同的選擇，這種選擇叫做決策。由決策按順序組成的集合叫做策略。由第k階段到到終止階段為止的過程，稱為k子過程，記為 。在實際中，可供選擇的策略是有限的，這有限的集合叫允許策略集合。

然後又回到了那個運籌學的終極問題找最優解——在允許策略集合里找到最優策略。

假如我們知道了一個規劃問題當前的狀態和決策變數，那我們可以立即確定下一個狀態。記k階段的狀態變數為 決策變數為 。狀態轉移方程為 ,其中T稱為狀態轉移函數。

我們還需要一個函數來評價所選策略的優劣，我們稱之為指標函數，指標函數 ,該函數具有可分離性，並滿足遞推關係

。

形式一：過程的指標是他所包含的各個階段的指標之和

形式二：過程的指標是他所包含的各個階段的指標之積

指標值函數的最優值稱為最優值函數，記為 .

其中opt為optimization的縮寫，可以根據情況選擇min與max。

k階段與k+1階段存在著遞推關係：

同時它滿足邊界條件：

我們把上面的遞推關係式稱為動態規劃的基本方程，這就是動態規劃問題的模型。解決動態規劃問題也是通過寫基本遞推關係與邊界條件來完成的。

5.3最優性原理

對於最優策略來說有一個重要的特性：最優策略的子策略也一定是最優的。

其中子策略並不是指任意一段策略，而是指任意一個階段到最後一個階段的策略。

這一個性質很好證明:

我們假設子策略 並不是最優的。那麼存在一個策略 優於子策略 ，此時由原先最優策略的前半段與這一個策略 組成的新策略優於原先的策略。又因為原先策略是最優策略，產生矛盾。所以可知，最優策略的子策略一定也是最優的。

5.4 summary

本節介紹了動態規劃問題的基本概念與簡單性質，目前我們的運籌學專題已經將幾大規劃問題介紹完全，如果你產生興趣想深入學習，還請找專門書籍閱讀。可以參考此問題運籌學有哪些經典教材？運籌學第一季至此結束，謝謝大家支持~