通過(guò)前幾期的學(xué)習(xí)，我們已經(jīng)學(xué)會(huì)了動(dòng)態(tài)規(guī)劃的基本概念和基本原理，并且掌握了動(dòng)態(tài)規(guī)劃模型的建立和具體的求解方法，本期小編帶大家學(xué)習(xí)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用。

除了前面講到的最優(yōu)路徑、資源分配問(wèn)題外，動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中還有許多應(yīng)用，小編選擇了其中一些典型例子，包括背包問(wèn)題、生產(chǎn)經(jīng)營(yíng)問(wèn)題和設(shè)備更新問(wèn)題，進(jìn)行詳細(xì)講解。

1.背包問(wèn)題

接下來(lái)我們先從經(jīng)典的背包問(wèn)題開(kāi)始講起。

背包問(wèn)題又稱(chēng)裝載問(wèn)題，一般提法是：一位旅行者攜帶背包去登山，已知他所能承受的背包重量限度為akg，現(xiàn)有n種物品可供他選擇裝入背包，第i種物品的單件重量為aikg，其價(jià)值（可以是表明本物品對(duì)登山的重要性的數(shù)量指標(biāo)）是攜帶數(shù)量xi的函數(shù)ci(xi)（i=1,2,…,n），問(wèn)旅行者應(yīng)如何選擇攜帶各種物品的件數(shù)，以使總價(jià)值最大？

背包問(wèn)題等同于車(chē)、船、人造衛(wèi)星等工具的最優(yōu)裝載，有廣泛的實(shí)用意義。

設(shè)xi為第i種物品裝入的件數(shù)，則背包問(wèn)題可歸結(jié)為如下形式的整數(shù)規(guī)劃模型：

下面用動(dòng)態(tài)規(guī)劃順序解法來(lái)進(jìn)行建模求解。

階段k：將可裝入物品按1，2，…，n排序，每段裝一種物品，共劃分為n個(gè)階段，即k=1,2,…,n。

狀態(tài)變量sk+1：在第k段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重量。

決策變量xk：裝入第k種物品的件數(shù)。

狀態(tài)轉(zhuǎn)移方程：sk=sk+1-akxk

允許決策集合：

用順序解法逐步計(jì)算出f1(s2)，f2(s3)，…，fk(sk+1)及相應(yīng)的決策函數(shù)x1(s2)，x2(s3)，…，xn(sn+1)，最后得到的fn(a)即為所求的最大價(jià)值，相應(yīng)的最優(yōu)策略則由反推計(jì)算得出。

例1 背包問(wèn)題

有一輛最大貨運(yùn)量為10t的卡車(chē)，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值如下表所示。應(yīng)如何裝載可使總價(jià)值最大？

解：設(shè)第i種貨物裝載的件數(shù)為xi（i=1,2,3），則問(wèn)題可表示為：

可按前述方式建立動(dòng)態(tài)規(guī)劃模型，由于決策變量取離散值，所以可以用列表法求解。

當(dāng)k=1時(shí)，

計(jì)算結(jié)果如下表所示。

當(dāng)k=2時(shí)，

計(jì)算結(jié)果見(jiàn)下表。

當(dāng)k=3時(shí)，

此時(shí)有x3*=0，逆推可得全部策略為：

最大價(jià)值為13。

2.生產(chǎn)經(jīng)營(yíng)問(wèn)題

生產(chǎn)經(jīng)營(yíng)問(wèn)題又可以分為兩類(lèi)：生產(chǎn)與儲(chǔ)存問(wèn)題、采購(gòu)與銷(xiāo)售問(wèn)題，下面我們通過(guò)兩道例題來(lái)學(xué)習(xí)一下。

例2?生產(chǎn)與儲(chǔ)存問(wèn)題

某工廠生產(chǎn)并銷(xiāo)售某種產(chǎn)品，已知今后四個(gè)月市場(chǎng)需求預(yù)測(cè)如下表所示，又每月生產(chǎn)j單位產(chǎn)品費(fèi)用為

每月庫(kù)存j單位產(chǎn)品的費(fèi)用為E(j)=0.5j(千元)，該廠最大庫(kù)存容量為3單位，每月最大生產(chǎn)能力為6單位，計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量都是零。試制訂四個(gè)月的生產(chǎn)計(jì)劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第i+1個(gè)月的庫(kù)存量是第i個(gè)月可銷(xiāo)售量與該月用戶需求量之差；而第i個(gè)月的可銷(xiāo)售量是本月初庫(kù)存量與產(chǎn)量之和。

用動(dòng)態(tài)規(guī)劃法求解時(shí)，對(duì)有關(guān)概念做如下分析：

（1）階段：每個(gè)月為一個(gè)階段，k=1，2，3，4。

（2）狀態(tài)變量：sk為第k個(gè)月初的庫(kù)存量。

（3）決策變量：uk為第k個(gè)月的生產(chǎn)量。

（4）狀態(tài)轉(zhuǎn)移方程：sk+1=sk+uk-gk

（5）最優(yōu)指標(biāo)函數(shù)：fk(sk)表示第k月?tīng)顟B(tài)為sk時(shí)，采取最佳策略生產(chǎn)，從本月到計(jì)劃結(jié)束（第4月末）的生產(chǎn)與存儲(chǔ)最低費(fèi)用。

考慮k=4，因?yàn)橐笏脑碌讕?kù)存為零，本月需求為4，所以本月產(chǎn)量應(yīng)為u4=4-s4，由于庫(kù)存量最大為3，所以s4取值只能是0，1，2，3。

可以列出f4(s4)和u4(s4)，見(jiàn)表1。

表1

當(dāng)k=3時(shí)，先分析狀態(tài)變量s3的取值范圍，它與庫(kù)存能力、生產(chǎn)能力、需求量均有關(guān)，在此由最大庫(kù)存量決定s3={0，1，2，3}。再分析決策變量u3的允許決策集合，為滿足本月需求，產(chǎn)量u3至少為g3-s3=2-s3，若庫(kù)存量s3>2，則u3應(yīng)取0。為保證期末庫(kù)存量為零，u3不能超過(guò)g3+g4-s3=6-s3，另外u3還受最大庫(kù)存量3的限制，即不能超過(guò)g3+3-s3=5-s3，同時(shí)還受最大生產(chǎn)能力6的限制，總之有

我們對(duì)s3=0，1，2，3分別求出f3(s3)的值，當(dāng)s3=0時(shí)，

這就是說(shuō)，若第三個(gè)月初庫(kù)存為零，則三、四兩個(gè)月最低費(fèi)用為12(千元)，第三個(gè)月最優(yōu)產(chǎn)量為2個(gè)單位。依此類(lèi)推，可得表2。

表2

當(dāng)k=2時(shí)，有

其中狀態(tài)變量s2={0，1，2，3}。

決策變量u2為

本段計(jì)算結(jié)果如表3所示。

表3

當(dāng)k=1時(shí)，有

由于狀態(tài)s1=0，本月產(chǎn)量u1同樣要受本月需求量、最大庫(kù)存容量、最大生產(chǎn)能力等約束限制，應(yīng)為2?u1?5的整數(shù)，則

計(jì)算結(jié)果見(jiàn)表4。

表4

由上表可知，總最低費(fèi)用為f1(0)=21(千元)，第一個(gè)月最佳產(chǎn)量為2單位。而需求g1=2，所以第二個(gè)月初庫(kù)存量為零，再由表3中查s2=0列可得第二個(gè)月最佳產(chǎn)量為5單位，同理通過(guò)查表2、表1可得第三、第四月的最佳產(chǎn)量。

即最佳生產(chǎn)計(jì)劃為：第一個(gè)月生產(chǎn)2單位，第二個(gè)月生產(chǎn)5單位，第三個(gè)月不生產(chǎn)，第四個(gè)月生產(chǎn)4單位。

總結(jié)上述解題過(guò)程，可得此類(lèi)生產(chǎn)存儲(chǔ)問(wèn)題的基本方程為

若最大庫(kù)存量為q，每月最大生產(chǎn)能力為p，則狀態(tài)集合為

允許決策集合為

例3?采購(gòu)與銷(xiāo)售問(wèn)題

某商店在未來(lái)的4個(gè)月里，準(zhǔn)備利用它的一個(gè)倉(cāng)庫(kù)來(lái)專(zhuān)門(mén)經(jīng)銷(xiāo)某種商品，倉(cāng)庫(kù)最大容量能儲(chǔ)存這種商品1000單位。假定該商店每月只能賣(mài)倉(cāng)庫(kù)現(xiàn)有的貨。當(dāng)商店在某月購(gòu)貨時(shí)，下月初才能到貨。預(yù)測(cè)該商品未來(lái)四個(gè)月的買(mǎi)賣(mài)價(jià)格如下表所示，假定商店在1月開(kāi)始經(jīng)銷(xiāo)時(shí)，倉(cāng)庫(kù)儲(chǔ)有該商品500單位。試問(wèn)若不計(jì)庫(kù)存費(fèi)用，該商店應(yīng)如何制訂1月至4月的訂購(gòu)與銷(xiāo)售計(jì)劃，使預(yù)期獲利最大。

解：按月份劃分為4個(gè)階段，k=1，2，3，4

狀態(tài)變量sk：第k月初時(shí)倉(cāng)庫(kù)中的存貨量(含上月訂貨)。

決策變量xk：第k月賣(mài)出的貨物數(shù)量。

決策變量yk：第k月訂購(gòu)的貨物數(shù)量。

狀態(tài)轉(zhuǎn)移方程：sk+1=sk+yk-xk

最優(yōu)指標(biāo)函數(shù)fk(sk)：第k月初存貨量為sk時(shí)，從第k月到4月末所獲最大利潤(rùn)。則有逆序遞推關(guān)系式為

當(dāng)k=4時(shí)

顯然，決策應(yīng)取

才有最大值f4(s4)=17s4

當(dāng)k=3時(shí)

這個(gè)階段需求解一個(gè)線性規(guī)劃問(wèn)題：

當(dāng)滿足

有最大值f3(s3)=6000+13s3

當(dāng)k=2時(shí)

則求解線性規(guī)劃問(wèn)題：

得到

當(dāng)k=1時(shí)

解線性規(guī)劃問(wèn)題：

得決策

最優(yōu)策略如下表所示。最大利潤(rùn)為16000。

3.設(shè)備更新問(wèn)題

企業(yè)中經(jīng)常會(huì)遇到一臺(tái)設(shè)備應(yīng)該使用多少年更新最合算的問(wèn)題。一般來(lái)說(shuō)，一臺(tái)設(shè)備在比較新時(shí)，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收人減少，故障變多維修費(fèi)用增加。如果更新可提高年凈收入，但是當(dāng)年要支出一筆數(shù)額較大的購(gòu)買(mǎi)費(fèi)。設(shè)備更新問(wèn)題的一般提法：在已知一臺(tái)設(shè)備的效益函數(shù)r(t)，維修費(fèi)用函數(shù)u(t)及更新費(fèi)用函數(shù)c(t)條件下，要求在n年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更換一臺(tái)新的，使n年總效益最大。

設(shè)rk(t)：在第k年設(shè)備已使用過(guò)t年（或稱(chēng)役齡為t年），再使用1年時(shí)的效益。

uk(t)：在第k年設(shè)備役齡為t年，再使用一年的維修費(fèi)用。

ck(t)：在第k年賣(mài)掉一臺(tái)役齡為t年的設(shè)備，買(mǎi)進(jìn)一臺(tái)新設(shè)備的更新凈費(fèi)用。

α為折扣因子（0≤α≤1），表示一年以后的單位收入價(jià)值相當(dāng)于現(xiàn)年的α單位。

下面建立動(dòng)態(tài)規(guī)劃模型。

階段k（k=1，2，…，n）表示計(jì)劃使用該設(shè)備的年限數(shù)。

狀態(tài)變量sk：第k年年初，設(shè)備已使用過(guò)的年數(shù)，即役齡。

決策變量xk：是第k年年初更新，還是保留使用舊設(shè)備，分別用R與K表示。

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

階段指標(biāo)為

指標(biāo)函數(shù)為

最優(yōu)指標(biāo)函數(shù)fk(sk))表示第k年年初，擁有一臺(tái)役齡為sk年的設(shè)備，采用最優(yōu)更新策略時(shí)到第n年年末的最大收益，則可得如下的逆序動(dòng)態(tài)規(guī)劃方程：

實(shí)際上

例4 設(shè)備更新問(wèn)題

設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如下表所示。試確定今后5年內(nèi)的更新策略，使總收益最大（設(shè)α=1)。

如前所述建立動(dòng)態(tài)規(guī)劃模型，n=5。

當(dāng)k=5時(shí)，

狀態(tài)變量s5可取1，2，3，4。

當(dāng)k=4時(shí)，

這時(shí)狀態(tài)變量s4可取1，2，3。

當(dāng)k=3時(shí)，

此時(shí)s3可取1或2。

當(dāng)k=2時(shí)，

由于s2只能取1，所以

當(dāng)k=1時(shí)，

由于s1只能取0，所以

上述計(jì)算遞推回去，當(dāng)x1*(0)=K時(shí)，由狀態(tài)轉(zhuǎn)移方程

可知s2=1，查f2(1)得x2*=R時(shí)，則

推出s3=1，查f3(1)得：x3*=R

推出s4=1，查f4(1)得：x4*=R

狀態(tài)s5=1，查f5(1)得：x5*=K

可得本例最優(yōu)策略為：{K，R，R，R，K}，即第一年年初購(gòu)買(mǎi)的設(shè)備到第二、第三、第四年年初各更新一次，用到第5年年末，其總效益為17萬(wàn)元。

以上就是本期動(dòng)態(tài)規(guī)劃例題講解的全部?jī)?nèi)容啦，通過(guò)對(duì)這一期的學(xué)習(xí)，相信大家一定能夠加深對(duì)動(dòng)態(tài)規(guī)劃的理解，進(jìn)而在生活實(shí)踐中學(xué)會(huì)應(yīng)用！

作者 | 裴傳濤 陳志昂 林鑫

責(zé)編 | 劉文志

審核 | 徐小峰