馮婧 周楊

摘 要：該文基于常規(guī)動態(tài)規(guī)劃解法，采用將各階段決策變量在其可行域內(nèi)充分離散的方法來求解各狀態(tài)變量下的最優(yōu)目標(biāo)函數(shù)值。該方法可通用于求解最大及最小目標(biāo)函數(shù)值，同時避免了由于狀態(tài)變量離散步長不同而導(dǎo)致目標(biāo)值精度不高的問題。

關(guān)鍵詞：動態(tài)規(guī)劃 優(yōu)化 運籌學(xué) 例題求解

中圖分類號：O221.2 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2015）12（a）-0264-02

1 問題的提出

目前，動態(tài)規(guī)劃算法在解決多決策問題中的應(yīng)用比較普遍。但是，在遇到求解最小目標(biāo)函數(shù)（最大化約束條件）時，狀態(tài)變量在各階段的離散不盡相同，且當(dāng)狀態(tài)變量離散步長過大時，會導(dǎo)致最優(yōu)目標(biāo)函數(shù)值精度不高，不利于應(yīng)用到實際問題中來。

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

2.1 動態(tài)規(guī)劃方法介紹

動態(tài)規(guī)劃是運籌學(xué)的一個分支，是求解多階段決策問題的最優(yōu)化方法。根據(jù)Bellman的最優(yōu)化原理（對最優(yōu)策略來說，無論過去狀態(tài)和決策如何，從前面諸決策所形成的狀態(tài)出發(fā)，相應(yīng)的剩余決策序列構(gòu)成最優(yōu)子策略），利用逆推（初始狀態(tài)給定）和順推方法（終止?fàn)顟B(tài)給定）可求出最優(yōu)決策和最優(yōu)值[2]。它的主要解題思路：在階段可分的前提下，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解。應(yīng)指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考慮問題的一種途徑，而不是一種特殊算法。

動態(tài)規(guī)劃用來描述多階段決策問題的基本概念[3，4]有：階段與階段變量k，狀態(tài)與狀態(tài)變量sk，決策與決策變量xk（sk），策略p1，n（s1）與最優(yōu)策略p*1，n（s1），指標(biāo)函數(shù)V1，n與最優(yōu)指標(biāo)函數(shù)fk（sk），階段指標(biāo)（階段效益）vk（sk，xk），狀態(tài)轉(zhuǎn)移方程sk+1=Tk（sk，xk）等。

2.2 模型建立

4 結(jié)語

該動態(tài)規(guī)劃解法在求解最小值目標(biāo)函數(shù)時，可避開各階段狀態(tài)變量的離散域問題，直接從決策變量的離散域角度考慮狀態(tài)變量的離散范圍，最終由各決策變量構(gòu)成的約束域來確定滿足總約束條件的最優(yōu)目標(biāo)函數(shù)值，并由此求得最優(yōu)路徑。

參考文獻(xiàn)

[1] 倫·庫柏，瑪麗·W·庫柏.動態(tài)規(guī)劃導(dǎo)論[M].北京：國防工業(yè)出版社，1985：7.

[2] 吳慶豐，劉兵兵.利用動態(tài)規(guī)劃求解資源分配問題[J].安慶師范學(xué)院學(xué)報：自然科學(xué)版，2008，14（2）：74-75.