趙娟 樊超

摘 要： 動態(tài)規(guī)劃是運籌學的一個分支，是求解決策過程最優(yōu)化的數學方法，其最終目的是確定各決策變量的取值，以使目標函數達到極大或極小。動態(tài)規(guī)劃在工程技術、經濟管理等社會各個領域有著廣泛的應用，并且獲得了顯著的效果，是經濟管理中一種重要的決策技術。文章例舉了動態(tài)規(guī)劃在最短路線、資源分配、設備更新、排序、裝載等方面的應用。通過求解不同的實例，總結出用動態(tài)規(guī)劃方法比用其他方法求解更容易、效率更高，并且所得到的解信息更豐富。

關鍵詞： 動態(tài)規(guī)劃； 最短路線； 資源分配； 設備更新

中圖分類號：N032 文獻標志碼：A 文章編號：1006-8228（2014）02-28-03

0 引言

動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數量方法。其特點在于，它可以把一個n維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。所以必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。

1 動態(tài)規(guī)劃方法的求解步驟

動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線（通常是求最優(yōu)的活動路線）。動態(tài)規(guī)劃的設計都有著一定的模式，一般要經歷如圖1所示的幾個步驟[1]。

⑴ 劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。

⑵ 確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。

⑶ 確定決策并寫出狀態(tài)轉移方程：因為決策和狀態(tài)轉移有著天然的聯系，狀態(tài)轉移就是根據上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態(tài)之間的關系來確定決策方法和狀態(tài)轉移方程。

⑷ 尋找邊界條件：給出的狀態(tài)轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

2 動態(tài)規(guī)劃方法的應用

2.1 貨郎擔問題

2.2 多段圖的最短路徑問題

多段圖的最短路徑問題，是求從源點s到達收點t的最小花費的通路。

數組元素cost[i]存放頂點i到達收點t的最小花費；數組元素path[i]存放頂點i到達收點t的最小花費通路上的前方頂點編號；數組route[n]存放從源點s出發(fā)，到達收點t的最長通路上的頂點編號。第一階段，確定第k-1段的所有頂點到達收點t的花費最大的通路。第二階段，用第一階段的信息，確定第k-2段的所有頂點到達收點t的花費最大的通路。

當gi（xi）都是線性函數時，它是一個線性規(guī)劃問題；當gi（xi）是非線性函數時，它是一個非線性規(guī)劃問題。但當n比較大時，具體求解是比較麻煩的。然而，由于這類問題的特殊結構，可以將它看成一個多階段決策問題，并利用動態(tài)規(guī)劃的遞推關系來求解[4]。

在應用動態(tài)規(guī)劃方法處理這類“靜態(tài)規(guī)劃”問題時，通常以把資源分配給一個或幾個使用者的過程作為一個階段，把問題中的變量xi選為決策變量，將累計的量或隨遞推過程變化的量選為狀態(tài)變量。

2.4 設備更新問題

設備的更新問題是確定設備的最優(yōu)更新策略，使得在一個確定期限里，為公司創(chuàng)造最大的利潤。

假定，設備更新問題的有關數據如表1所示。其中，i=0列，表明現有設備的有關數據；i=1列，表示第一年購買的設備的有關數據；其余類推。使用年限中的第0列，表示當年的有關數據，第1列表示使用一年后的有關數據，其余類推；利潤、維修費用、更新費用等行分別表示：在第i年購買的設備使用了j年后，可創(chuàng)造的利潤、必須付出的維修費用以及更新時需要付出的費用[5]。

3 結束語

動態(tài)規(guī)劃是求解最優(yōu)化問題的一種途徑、一種方法，往往是針對一種最優(yōu)化問題，由于各種問題的性質不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設計方法對不同的問題，有各具特色的解題方法。本文詳細介紹了動態(tài)規(guī)劃在最短路線、資源分配、設備更新、排序、裝載等方面的應用。通過求解不同的實例，總結出用動態(tài)規(guī)劃方法比用其他方法求解更容易、效率更高，并且得到的解的信息更豐富。下一步要對動態(tài)規(guī)劃方法沒有統(tǒng)一的標準模型問題加以研究，爭取得到在求解同一類問題時能有一個標準模型。

參考文獻：

[1] 鄭宗漢，鄭曉明編著.算法分析與設計[M].清華大學出版社，2005.

[2] 王志和，凌云.Dijkstra最短路徑算法的優(yōu)化及其實現[J].微計算機信息，2007：11-3

[3] 夏紅霞，宋華珠，鐘珞.算法分析與設計[M].武漢大學出版車，2007.6.

[4] 吳慶豐，劉兵兵.利用動態(tài)規(guī)劃求解資源分配的問題[J].安慶師范學院學報，2008.2.

[5] 梁修鋒.動態(tài)規(guī)劃在設備更新中的應用[J].中國地質經濟，1992.10.

[6] 劉鳳鳴.動態(tài)規(guī)劃的應用[J].科技視界，2013.7.