趙娟 樊超

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

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

中圖分類號(hào)：N032 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）02-28-03

0 引言

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

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

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

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

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

⑶ 確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來(lái)確定決策方法和狀態(tài)轉(zhuǎn)移方程。

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

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

2.1 貨郎擔(dān)問(wèn)題

2.2 多段圖的最短路徑問(wèn)題

多段圖的最短路徑問(wèn)題，是求從源點(diǎn)s到達(dá)收點(diǎn)t的最小花費(fèi)的通路。

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

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

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

2.4 設(shè)備更新問(wèn)題

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

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 鄭宗漢，鄭曉明編著.算法分析與設(shè)計(jì)[M].清華大學(xué)出版社，2005.

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

[3] 夏紅霞，宋華珠，鐘珞.算法分析與設(shè)計(jì)[M].武漢大學(xué)出版車，2007.6.

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

[5] 梁修鋒.動(dòng)態(tài)規(guī)劃在設(shè)備更新中的應(yīng)用[J].中國(guó)地質(zhì)經(jīng)濟(jì)，1992.10.

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