運(yùn)籌說 第72期 | 算法介紹之動態(tài)規(guī)劃（二）
本期我們繼續(xù)進(jìn)行運(yùn)籌學(xué)之動態(tài)規(guī)劃算法的講解，我們將對動態(tài)規(guī)劃的基礎(chǔ)知識進(jìn)行一個簡單的回顧，并介紹求解動態(tài)規(guī)劃問題的MATLAB和Python相關(guān)代碼，以幫助大家利用工具快速求解動態(tài)規(guī)劃問題，做到事半功倍。由于篇幅有限，小編接下來只展示部分代碼，小伙伴們可以關(guān)注“運(yùn)籌說”公眾號→后臺回復(fù)“算法介紹之動態(tài)規(guī)劃（二）”獲取完整代碼。話不多說，我們一起來看看吧！
一、基礎(chǔ)知識
1、背包問題
★ 問題描述
?一位旅行者攜帶背包去登山,已知他所能承受的背包重量限度為akg ,現(xiàn)有n 種物品可供他選擇裝入背包,第i 種物品的單件重量為aikg ,其價值(可以是表明本物品對登山的重要性的數(shù)量指標(biāo))是攜帶數(shù)量xi 的函數(shù)ci(xi)??(i=1,2,?,n) ,問旅行者應(yīng)如何選擇攜帶各種物品的件數(shù),以使總價值最大?
背包問題等同于車、船、人造衛(wèi)星等工具的最優(yōu)裝載，有廣泛的實(shí)用意義。
★ 背包問題分類
根據(jù)物品可用數(shù)量的不同，背包問題可有如下分類：
0-1背包問題：每種物品均只有一件可用；
完全背包問題：每種物品都有無限件可用；
多維背包問題：第i 種物品最多有ni 件可用。
★ 完全背包問題的整數(shù)規(guī)劃模型
設(shè)xi 為第i 種物品裝入的件數(shù)，則背包問題可歸結(jié)為如下形式的整數(shù)規(guī)劃模型:
★ 動態(tài)規(guī)劃順序解法建模
階段k :將可裝入物品按1，2，?，n 排序，每段裝一種物品，共劃分為n 個階段，即k=1，2，?，n 。
狀態(tài)變量sk+1 ：在第k 段開始時，背包中允許裝入前k 種物品的總重量。
決策變量xk ：裝入第k 種物品的件數(shù)。
狀態(tài)轉(zhuǎn)移方程：
其中[sk+1/ak]表示不超過sk+1/ak 的最大整數(shù)。
最優(yōu)指標(biāo)函數(shù)fk(sk+1) 表示在背包中允許裝入物品的總重量不超過sk+1kg，采用最優(yōu)策略只裝前k 種物品時的最大使用價值。
則可得到動態(tài)規(guī)劃的順序遞推方程為
用順序解法逐步計算出f1(s2)，f2(s3)，?，fn(sn+1)及相應(yīng)的決策函數(shù)x1(s2)，x2(s3)，?，xn(sn+1)，最后得到的fn(a)即為所求的最大價值，相應(yīng)的最優(yōu)策略則由反推計算得出。
當(dāng)xi僅表示裝入(取1)和不裝(取0)第i種物品，則模型就成了0-1背包問題。
2、設(shè)備更新問題
★ 問題描述
企業(yè)中經(jīng)常會遇到一臺設(shè)備應(yīng)該使用多少年更新最合算的問題。一般來說，一臺設(shè)備在比較新時，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減少，故障變多維修費(fèi)用增加。如果更新可提高年凈收入，但是當(dāng)年要支出一筆數(shù)額較大的購買費(fèi)。設(shè)備更新問題的一般提法：在已知一臺設(shè)備的效益函數(shù)r(t)，維修費(fèi)用函數(shù)u(t) 及更新費(fèi)用函數(shù)c(t) 條件下，要求在n 年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更換一臺新的，使n 年總效益最大。
★ 動態(tài)規(guī)劃建模
設(shè)rk(t) ：在第k 年設(shè)備已使用過t 年(或稱役齡為t 年)，再使用1年時的效益。
uk(t) ：在第k 年設(shè)備役齡為t 年，再使用一年的維修費(fèi)用。
ck(t) ：在第k 年賣掉一臺役齡為t 年的設(shè)備，買進(jìn)一臺新設(shè)備的更新凈費(fèi)用。α 為折扣因子(0?α?1) ，表示一年以后的單位收人價值相當(dāng)于現(xiàn)年的α 單位。下面建立動態(tài)規(guī)劃模型。
階段k ：表示計劃使用該設(shè)備的年限數(shù)，(k=1，2，?，n) 。
狀態(tài)變量sk ：第k 年初，設(shè)備已使用過的年數(shù)，即役齡。
決策變量xk ：是第k 年初更新(replacement)，還是保留使用(keep)舊設(shè)備，分別用R 與K 表示。
狀態(tài)轉(zhuǎn)移方程為
? ? ? ? ? ? ? ? ? ?
實(shí)際上，
二、算法實(shí)現(xiàn)
1、背包問題
（1）完全背包問題
①例題介紹
有一輛最大貨運(yùn)量為10t的卡車，用以裝載4種貨物，每種貨物的單位重量及相應(yīng)單位價值如下表所示。每種貨物都有無限件，應(yīng)如何裝載可使總價值最大？
②平臺實(shí)現(xiàn)
我們以上述例題為例，借助Python介紹實(shí)現(xiàn)求解完全背包問題的相關(guān)代碼。
★ 代碼展示
★ 代碼調(diào)用
代碼運(yùn)行及最終結(jié)果展示如下，可以看到i=3有兩次，i=4有兩次，也就是第3種貨物被選擇了兩次，第4種貨物被選擇了兩次?？梢匝b載的總價值為16t。
（2）0-1背包問題
★ 例題介紹
有一輛最大貨運(yùn)量為10t的卡車，用以裝載4種貨物，每種貨物的單位重量及相應(yīng)單位價值如下表所示。每種貨物都只有1件，應(yīng)如何裝載可使總價值最大？
★ 平臺實(shí)現(xiàn)
我們以上述例題為例，借助MATLAB和Python介紹實(shí)現(xiàn)求解0-1背包問題的相關(guān)代碼。
①M(fèi)ATLAB
★ 代碼展示
★ 代碼調(diào)用
代碼運(yùn)行及最終結(jié)果展示如下，可以看到在每種貨物只有一種可以裝載的情況下，所裝貨物為第1個、第3個和第4個，可以裝載的總價值為12t。
②Python
★ 代碼展示
★ 代碼調(diào)用
代碼運(yùn)行及最終結(jié)果展示如下，可以看到在每種貨物只有一種可以裝載的情況下，所裝貨物為第1個、第3個和第4個，可以裝載的總價值為12t。
2、設(shè)備更新問題
（1）例題介紹
設(shè)某臺新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如下表所示。試確定今后5年內(nèi)的更新策略，使總收益最大（設(shè)α =1）。
（2）平臺實(shí)現(xiàn)
我們以上述例題為例，借助MATLAB介紹實(shí)現(xiàn)求解設(shè)備更新問題的相關(guān)代碼。
★ 代碼展示
★ 代碼調(diào)用
代碼運(yùn)行及最終結(jié)果展示如下，可得本例最優(yōu)策略為：（1，0，0，0，1），即（K,R,R,R,K）,也就是第1年初購買的設(shè)備到第2、3、4年年初各更新一次，用到第5年年末，其總效益為17萬元。
三、參考資料
【完全背包問題Python實(shí)現(xiàn)】
https://www.freesion.com/article/4764693393/
【0-1背包問題Python實(shí)現(xiàn)】
https://blog.csdn.net/qq_34178562/article/details/79959380
【0-1背包問題MATLAB實(shí)現(xiàn)】
https://blog.csdn.net/tsroad/article/details/52048562
本期的內(nèi)容就介紹到這里，想要進(jìn)一步了解運(yùn)籌學(xué)，關(guān)注本公眾號，快快學(xué)起來吧！
作者 | 尹萌娟 陳夢
責(zé)編 | 劉文志
審核 | 徐小峰
