馮婧 周楊

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

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

中圖分類號：O221.2 文獻標識碼：A 文章編號：1672-3791（2015）12（a）-0264-02

1 問題的提出

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

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

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

動態(tài)規(guī)劃是運籌學的一個分支，是求解多階段決策問題的最優(yōu)化方法。根據Bellman的最優(yōu)化原理（對最優(yōu)策略來說，無論過去狀態(tài)和決策如何，從前面諸決策所形成的狀態(tài)出發(fā)，相應的剩余決策序列構成最優(yōu)子策略），利用逆推（初始狀態(tài)給定）和順推方法（終止狀態(tài)給定）可求出最優(yōu)決策和最優(yōu)值[2]。它的主要解題思路：在階段可分的前提下，把多階段過程轉化為一系列單階段問題，逐個求解。應指出，動態(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），指標函數V1，n與最優(yōu)指標函數fk（sk），階段指標（階段效益）vk（sk，xk），狀態(tài)轉移方程sk+1=Tk（sk，xk）等。

2.2 模型建立

4 結語

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

參考文獻

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

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