動態(tài)規(guī)劃的應(yīng)用

劉鳳鳴

（浙江海洋學(xué)院 數(shù)理與信息學(xué)院，浙江 舟山 316000）

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

多階段決策過程，是指一類特殊的過程，它們可以按時間順序分解成若干個相互聯(lián)系的階段，稱為“時段”，在每個時段都要做決策，全部過程的決策是一個決策序列。多階段決策問題也稱為序貫決策問題。

多階段決策問題的目標(biāo)是要達到整個活動過程的總體最優(yōu)。在每個階段進行決策時不應(yīng)僅考慮本階段最優(yōu)，尤其應(yīng)考慮對最終目標(biāo)的影響，從而做出對全局來說最優(yōu)的決策。動態(tài)規(guī)劃是符合這種要求的一種決策方法。

動態(tài)規(guī)劃開始只是應(yīng)用于多階段決策性問題，后來漸漸被發(fā)展為解決離散最優(yōu)化問題的有效手段，進一步應(yīng)用于一些連續(xù)性問題上。然而，動態(tài)規(guī)劃更像是一種思想而非算法，它沒有固定的數(shù)學(xué)模型，沒有固定的實現(xiàn)方法，其正確性也缺乏嚴格的理論證明。因此，一直以來動態(tài)規(guī)劃的數(shù)學(xué)理論模型是一個研究的熱點。一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下基本要素：階段、狀態(tài)、決策、策略、狀態(tài)轉(zhuǎn)移方程、指標(biāo)函數(shù)和最優(yōu)值函數(shù)，在建立動態(tài)規(guī)劃數(shù)學(xué)模型時，主要是確定這些動態(tài)規(guī)劃的基本要素。

2 動態(tài)規(guī)劃算法的基本步驟

2.1 劃分階段

應(yīng)將實際問題恰當(dāng)?shù)胤指畛蒼個子問題(n個階段)。通常是根據(jù)時間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數(shù)n，即k=n。

2.2 選擇狀態(tài)

正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性.動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的。

2.3 確定決策并寫出狀態(tài)轉(zhuǎn)移方程

之所以把這兩步放在一起，是因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。

2.4 寫出規(guī)劃方程（包括邊界條件）

動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。

3 動態(tài)規(guī)劃應(yīng)用問題

3.1 資源分配問題

例：某物流公司每天要給3家公司運送6車貨物，如果各公司獲得這些貨物之后獲得的盈利如表1所示，則這車貨物如何分配給各工廠才能使盈利最大。

表1

解：將問題按公司分為3個階段，甲、乙、丙三個公司分別編號為1、2、3

設(shè)sk表示為分配給第k個公司至第n個公司的貨物車數(shù)

xk表示為分配給第k個公司的貨物數(shù)量

則sk+1=sk-xk為分配給第k+1個公司至第n個公司的貨物車數(shù)

pk（xk）表示為xk車貨物分配到第k個公司所得的盈利值

fk（sk）表示為sk車貨物分配給第k個公司至第n個公司時所得到的最大盈利值

根據(jù)逆推關(guān)系式

fk（sk）=max｛pk（xk）+fk+1（sk-xk）｝，k=3，2，1

0≤xk≤sk

f4（s4）=0

所以從最后一個階段開始向前逆推計算

第三階段：

設(shè)將 s3 車貨物（s3=0，1，2，3，4，5，6）全部分配給公司丙時，最大盈利值為

f3（s3）=max［p3（x3）］

其中 x3=s3=0，1，2，3，4，5，6

因為此時只有一個公司，有多少車貨物就全部分配給公司丙，故它的盈利值就是該段的最大盈利值，其數(shù)值計算如表2所示。

第二階段：

k=2 時，設(shè)把 s2 車貨物（s2=0，1，2，3，4，5，6）分配給公司乙和丙時，對每個s2值有一種最優(yōu)分配方案，使最大盈利值為

表2

表中，x3*表示使f3（x3）為最大值時的最優(yōu)決策。

表3

f2（s2）=max［p2（x2）+f3（s2-x2）］

其中 s2=0，1，2，3，4，5，6

因為乙公司x2車，其盈利為p2（x2），余下的s2-x2車就給丙公司，則它的盈利最大值為 f3（s2-x2）。 現(xiàn)在選擇x2的值，使 p2（x2）+f3（s2-x2）取最大值，其數(shù)值計算如表3所示。

第一階段：

k=1時，設(shè)把s1車（這里只有s1=6的情況）貨物分配給甲、乙、丙三個公司時，最大盈利值為

f1（6）=max［p1（x1）+f2（6-x1）］

其中 x1=0，1，2，3，4，5，6

因為給甲公司x1車，其盈利為p1（x1），剩下的6-x1車就分給乙和丙兩個公司，則它的盈利最大值為f2（6-x1），現(xiàn)選擇 x1值，使p1（x1）+f2（6-x1）取最大值，它就是所求的總盈利最大值，其數(shù)值計算如表4所示。

表4

根據(jù)計算表格的順序反推算，可知最優(yōu)分配方案為：

x1*=1，由于s2=s1-x1*=6-1=5，查第二個表可知x2*=5，s3=s2-x2*=5-5=0

即得甲公司分配1車，乙公司分配5車，丙公司不分配，總盈利為17。

3.2 設(shè)備更新問題

現(xiàn)以一臺機器設(shè)備為例，在使用過程中，每年都面臨繼續(xù)使用或更新的決策，要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺新的，使n年內(nèi)總效益最大。

n為設(shè)備計劃使用年數(shù)。

Ik（t）為第k年（階段）機器役齡為t年的一臺機器運行（在使用一年）所得的收入。

Ok（t）為第k年機器役齡為t年的一臺機器運行（再使用一年）時所需運行的費用（或維修費用）。

Ck（t）為第k年機器役齡為t年的一臺機器更新時所需的凈費用（處理一臺役齡為t的舊設(shè)備，買進一臺新設(shè)備的更新凈費用）。

a為折扣因子，表示一年以后的收入是上一年的a單位。

T為在第一年開始正在使用的機器的役齡。

最優(yōu)指標(biāo)函數(shù)gk（t）：表示第k年初，使用一臺已用了t年的設(shè)備，到第n年末的最大收益。

xk（t）表示給出 gk（t）時，在第 k 年開始時的決策（保留或更新）建立動態(tài)規(guī)劃模型如下：

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

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

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

例：假設(shè)n=5，a=1，T=1，某臺新設(shè)備的年收入及運行費用、更新費用如表5，試確定五年內(nèi)的更新策略，使總效益達到最大。

表5

解：因第k年開始機齡為t年的機器，其制造年序應(yīng)為k-t年，因此，I5（0）為第五年新產(chǎn)品的收入，即 I5（0）=43，I3（2）為第一年的產(chǎn)品其機齡為 2年的收入，即I3（2）=30，C5（1）是第五年機齡為1年的機器（應(yīng)為第四年的產(chǎn)品）的更新費用，即C5（1）=41，其余同理類推。

當(dāng)k=1時，由于設(shè)T=1，所以從第五年開始計算時，機器使用了1、2、3、4、5 年，根據(jù)遞推關(guān)系式

最后根據(jù)上面的結(jié)果反推之，可求得最優(yōu)策略為

第一年機齡為1，最佳策略為K

第二年機齡為2，最佳策略為R

第三年機齡為1，最佳策略為K

第四年機齡為2，最佳策略為K

第五年機齡為3，最佳策略為K

最大收益為99。

4 總結(jié)

動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最?。┲档慕?。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，在動態(tài)規(guī)劃的設(shè)計過程中，階段的劃分和狀態(tài)的表示是非常重要的兩步，這兩步會直接影響該問題的計算復(fù)雜性，有時候階段劃分或狀態(tài)表示的不合理還會使得動態(tài)規(guī)劃法不適用。動態(tài)規(guī)劃的優(yōu)點是最優(yōu)解是全局最優(yōu)解，能得到一系列（包括子過程）的最優(yōu)解，不需要對系統(tǒng)狀態(tài)轉(zhuǎn)移方程、階段效應(yīng)函數(shù)等的解析性質(zhì)作任何假設(shè)。缺點是沒有統(tǒng)一的標(biāo)準模型和標(biāo)準的算法可供使用，應(yīng)用有局限性。

［1］運籌學(xué)[M].3版.清華大學(xué)出版社

［2］動態(tài)規(guī)劃案例[OL].百度文庫.

［3］運籌學(xué)動態(tài)規(guī)劃[OL].百度文庫.