散文網(wǎng) » 生活 »日常 » 運(yùn)籌說第70期 | 算法介紹之動態(tài)規(guī)劃（一）

運(yùn)籌說第70期 | 算法介紹之動態(tài)規(guī)劃（一）

2022-07-15 17:30 作者:運(yùn)籌說 0人讀過 | 我要投稿

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

本期我們進(jìn)行運(yùn)籌學(xué)之動態(tài)規(guī)劃算法的講解，我們將對動態(tài)規(guī)劃的基礎(chǔ)知識進(jìn)行一個簡單的回顧，并介紹求解動態(tài)規(guī)劃問題的MATLAB、Python和C++相關(guān)代碼，以幫助大家利用工具快速求解動態(tài)規(guī)劃問題，做到事半功倍。由于篇幅有限，小編接下來只展示部分代碼，小伙伴們可以關(guān)注“運(yùn)籌說”公眾號→后臺回復(fù)“算法介紹之動態(tài)規(guī)劃（一）”獲取完整代碼。話不多說，我們一起來看看吧！

一、基礎(chǔ)知識

1、多階段決策的特點(diǎn)

（1）多階段決策是與時間相關(guān)的；

（2）多階段決策依賴于當(dāng)前的狀態(tài)；

（3）每一個時段都要作出決策；

（4）全部過程的決策是一個決策序列；

（5）本段決策的執(zhí)行將影響下一階段的決策；

（6）不僅要考慮本階段最優(yōu)，更要考慮全局最優(yōu)。

2、動態(tài)規(guī)劃的基本概念

使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實(shí)際問題寫成動態(tài)規(guī)劃模型，此時要用到以下概念：

3、動態(tài)規(guī)劃的基本思想與最優(yōu)化原理

★ 最優(yōu)化原理

最優(yōu)化原理可以表述為：“一個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后的所有決策應(yīng)構(gòu)成最優(yōu)策略。”

★ 基本思想

（1）將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)，從而把問題化成一族同類型的子問題，然后逐個求解。

（2）求解時從邊界條件開始，逆（或順）過程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解。

（3）動態(tài)規(guī)劃方法是既把當(dāng)前一段與未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。

★ 動態(tài)規(guī)劃的基本方程

★ 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系

4、動態(tài)規(guī)劃模型的建立與求解

★ 使用動態(tài)規(guī)劃的一般前提

（1）滿足動態(tài)規(guī)劃的最優(yōu)化原理；

（2）滿足動態(tài)規(guī)劃的無后效性原則，即某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。

★ 動態(tài)規(guī)劃模型的建立

★ 逆序解法與順序解法

逆序解法：尋優(yōu)的方向與多階段決策過程的實(shí)際行進(jìn)方向相反，從最后一段開始計(jì)算逐段前推，求得全過程的最優(yōu)策略，稱為逆序解法。

順序解法：尋優(yōu)方向與過程的行進(jìn)方向相同，計(jì)算時從第一段開始逐段向后遞推，計(jì)算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果就是全過程的最優(yōu)結(jié)果。

順序解法與逆序解法本質(zhì)上并無區(qū)別，一般來說，當(dāng)初始狀態(tài)給定時可用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時可用順序解法。若問題給定了一個初始狀態(tài)與一個終止?fàn)顟B(tài)，則兩種方法均可使用。

★ 逆序解法與順序解法在建模時的區(qū)別

二、算法實(shí)現(xiàn)

1、例題介紹

如圖所示，給定一個線路網(wǎng)絡(luò)圖，要從A地向F地鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問應(yīng)選擇什么路線，可使總距離最短？

2、平臺實(shí)現(xiàn)

我們以上述例題為例，借助MATLAB、Python和C++介紹實(shí)現(xiàn)求解動態(tài)規(guī)劃問題的相關(guān)代碼。

（1）順序解法

① Python

★ 代碼展示

如圖所示，在編寫代碼時用0替換A，用1替換B1，依次類推……用12替換F。

★ 代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，最短路長為17，最短路徑為0→1→4→8→11→12，即對應(yīng)例題中的A→B1→C2→D2→E2→F。

②C++

★ 平臺介紹

C++代碼的編寫依靠Lightly平臺來實(shí)現(xiàn)，Lightly支持C++工程項(xiàng)目開發(fā)，支持CMake，可選不同C++語言標(biāo)準(zhǔn)，語法高亮，智能提示，自動補(bǔ)全。它可以自動構(gòu)建環(huán)境，實(shí)時同步資源到云端，支持多人協(xié)作，支持在線C++代碼編輯、編譯、運(yùn)行。

輸入項(xiàng)目名稱，點(diǎn)擊新建項(xiàng)目，開始編寫代碼。