動態規劃方法的應用研究

趙娟 樊超

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

關鍵詞： 動態規劃； 最短路線； 資源分配； 設備更新

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

0 引言

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

1 動態規劃方法的求解步驟

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

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

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

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

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

2 動態規劃方法的應用

2.1 貨郎擔問題

2.2 多段圖的最短路徑問題

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

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

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

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

2.4 設備更新問題

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

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

3 結束語

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

參考文獻：

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

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

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

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

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

[6] 劉鳳鳴.動態規劃的應用[J].科技視界，2013.7.