求解一維非線性規劃問題的改進動態規劃算法

馮婧 周楊

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

關鍵詞：動態規劃 優化 運籌學 例題求解

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

1 問題的提出

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

2 動態規劃模型的建立與求解

2.1 動態規劃方法介紹

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

動態規劃用來描述多階段決策問題的基本概念[3，4]有：階段與階段變量k，狀態與狀態變量sk，決策與決策變量xk（sk），策略p1，n（s1）與最優策略p*1，n（s1），指標函數V1，n與最優指標函數fk（sk），階段指標（階段效益）vk（sk，xk），狀態轉移方程sk+1=Tk（sk，xk）等。

2.2 模型建立

4 結語

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

參考文獻

[1] 倫·庫柏，瑪麗·W·庫柏.動態規劃導論[M].北京：國防工業出版社，1985：7.

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