動(dòng)態(tài)規(guī)劃求解方法的Matlab實(shí)現(xiàn)及應(yīng)用

1、 收稿日期 :2004-06-16 修回日期 :2005-05-08 作者簡介 :于 斌 (1982- , 男 , 江蘇姜堰人 , 信息工程大學(xué)碩士研究生 , 主要研究方向?yàn)橥ㄐ殴こ獭?dòng)態(tài)規(guī)劃求解方法的 Matlab 實(shí)現(xiàn)及應(yīng)用于 斌 , 劉姝麗 , 韓中庚(信息工程大學(xué) 信息工程學(xué)院 , 河南 鄭州 450002摘要 :文章對動(dòng)態(tài)規(guī)劃問題的求解方法進(jìn)行了分析研究 , 根據(jù)問題的特點(diǎn) 、 難點(diǎn)和關(guān)鍵點(diǎn)做了 針對性的處理 , 然后用 Matlab 做了實(shí)現(xiàn)嘗試 , 從而實(shí)現(xiàn)了 “最佳組隊(duì)” 和 “最短路線” 等問題的 求解 。 實(shí)踐證明所采用方法和程序都是有效的 。 關(guān)鍵詞 :動(dòng)態(tài)規(guī)劃 ; 基本

2、方程 ; Matlab 實(shí)現(xiàn) ; 最佳組隊(duì)中圖分類號 :O221. 3文獻(xiàn)標(biāo)識碼 :A文章編號 :1671-0673(2005 03-0095-04Matlab R ealization of the Dynamic Programming and Y U Bin , LI U Shu 2li , (Institute of In formation Engineering , In , Zhengzhou 450002, China Abstract :By analyzing and approach , an effective disposal has been d one accor

3、ding to pt on the problems of “ Best team 2forming ” and “ Sh ortest path ” has by Matlab. It is proved that the meth od and programme are effective. K ey w ords :programming ; basic equation ; Matlab ; best team 2forming problem0 引言動(dòng)態(tài)規(guī)劃是一類解決多階段決策問題的數(shù)學(xué) 方法 , 在工程技術(shù) 、 科學(xué)管理 、 工農(nóng)業(yè)生產(chǎn)及軍事等 領(lǐng)域都有廣泛的應(yīng)用 。 在理論上

4、, 動(dòng)態(tài)規(guī)劃是求解 這類問題全局最優(yōu)解的一種有效方法 , 特別是對于 實(shí)際中的某些非線性規(guī)劃問題可能是最優(yōu)解的唯 一方法 。 然而 , 動(dòng)態(tài)規(guī)劃僅僅是解決多階段決策問 題的一種方法 , 或者說是考查問題的一種途徑 , 而 不是一種具體的算法 。 就目前而言 , 動(dòng)態(tài)規(guī)劃沒有 統(tǒng)一的標(biāo)準(zhǔn)模型 , 其解法也沒有標(biāo)準(zhǔn)算法 , 在實(shí)際 應(yīng)用中 , 需要具體問題具體分析 。 動(dòng)態(tài)規(guī)劃模型的 求解問題是影響動(dòng)態(tài)規(guī)劃理論和方法應(yīng)用的關(guān)鍵 所在 , 而子問題的求解和大量結(jié)果的存儲 、 調(diào)用更 是一個(gè)難點(diǎn)所在 。 然而 , 隨著計(jì)算機(jī)技術(shù)的快速發(fā) 展 , 特別是內(nèi)存容量和計(jì)算速度的增加 , 使求解較 小規(guī)模的動(dòng)

5、態(tài)規(guī)劃問題成為可能 , 從而使得動(dòng)態(tài)規(guī)劃的理論和方法在實(shí)際中的應(yīng)用范圍迅速增加 。目前 , 在計(jì)算機(jī)上實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的一般求解方 法并不多見 , 尤其是用來解決較復(fù)雜的具體問題的 成果甚少 。本文從實(shí)際出發(fā) , 利用數(shù)學(xué)工具軟件 Matlab 的強(qiáng)大功能 , 對動(dòng)態(tài)規(guī)劃模型的求解方法做了嘗試 , 并結(jié)合 “ 最佳組隊(duì)問題” 1 和最短路問題 2進(jìn)行了應(yīng)用檢驗(yàn) , 實(shí)際證明結(jié)果是令人滿意的 。1 動(dòng)態(tài)規(guī)劃的基本模型實(shí)際中 , 要構(gòu)造一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃模型 , 通 常需要采用以下幾個(gè)步驟 : 劃分階段 按照問題的時(shí)間或空間特征 , 把 問題分為若干個(gè)階段 。這些階段必須是有序的或 者是可排序的 (即

6、無后向性 , 否則 , 應(yīng)用無效 。 選擇狀態(tài) 將問題發(fā)展到各個(gè)階段時(shí)所處 的各種客觀情況用不同的狀態(tài)表示 , 即稱為狀態(tài) 。 狀態(tài)的選擇要滿足無后效性和可知性 , 即狀態(tài)不僅第 6卷 第 3期 信 息 工 程 大 學(xué) 學(xué) 報(bào) Vol. 6No. 3 2005年 9月 Journal of In formation Engineering University Sep. 2005依賴于狀態(tài)的轉(zhuǎn)移規(guī)律 , 還依賴于允許決策集合和 指標(biāo)函數(shù)結(jié)構(gòu) 。 確定決策變量與狀態(tài)轉(zhuǎn)移方程 當(dāng)過程處 于某一階段的某個(gè)狀態(tài)時(shí) , 可以做出不同的決策 , 描述決策的變量稱為決策變量 。 在決策過程中 , 由 一個(gè)狀

7、態(tài)到另一個(gè)狀態(tài)的演變過程稱為狀態(tài)轉(zhuǎn)移 。 狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出 本階段的狀態(tài) 。 寫出動(dòng)態(tài)規(guī)劃的基本方程 動(dòng)態(tài)規(guī)劃的基 本方程一般根據(jù)實(shí)際問題可分為兩種形式 , 逆序形 式和順序形式 。 動(dòng)態(tài)規(guī)劃基本方程的逆序形式為f k (s k =opt x k D k (s kv k (s k , x k +f k +1(s k +1 , k =n , n -1, , 2, 1邊界條件 :fn +1(s n +1 =0或 f n (s n =v n (s n , x n (1其中第 k 階段的狀態(tài)為 s k , 其決策變量 x k 表示狀 態(tài)處于 s k +1的決策 , 狀態(tài)轉(zhuǎn)移方

8、程為 s k +1=T k (s k ,x k , k 階段的允許決策集合記為 D k (s k , v k (s k , x k 為指標(biāo)函數(shù) 。當(dāng)求解時(shí) , 由邊界條件從 前逆推 , , 直 到最后求出 f 1(s 1。類似的 , f k (s k +1 =opt x k D rk (sk +1v k (s k +1, x k +f k -1(s k , k =1, 2, , n -1, n邊界條件 :f0(s 1 = (2其中狀態(tài)轉(zhuǎn)移方程為 s k =T rk(s k +1, x k , k 階段的 允許決策集合為 D rk(s k +1 , 指標(biāo)函數(shù)為 v k (s k +1, x k

9、。 當(dāng)求解時(shí) , 由邊界條件從 k =1開始 , 由前向后順推 , 逐階段求出最優(yōu)決策和過程的最優(yōu)值 , 直 到最后求出 f n (s n +1 即得到問題的最優(yōu)解 。2 基本方程求解的 Matlab 實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃沒有統(tǒng)一的標(biāo)準(zhǔn)模型 , 對于基本方程(1 和 (2 的求解也沒有統(tǒng)一的標(biāo)準(zhǔn)算法 。但是 , 我們分析用動(dòng)態(tài)規(guī)劃解決問題的思想方法 , 會發(fā)現(xiàn)一個(gè)共同的明顯特征 , 這就是將所研究的問題分為關(guān) 聯(lián)著的多個(gè)階段后 , 每個(gè)階段都有若干個(gè)對應(yīng)的子 問題 , 求解問題的關(guān)鍵就是按階段次序求解大量子 問題的最優(yōu)解 。而且對于每一個(gè)子問題的求解結(jié) 果都必須完整貯存下來 , 上一階段子問題的結(jié)果將

10、 對下一階段產(chǎn)生一定的影響 , 即對全局最優(yōu)決策也 產(chǎn)生影響 。 如何處理好所有各階段的大量子問題 的求解及結(jié)果的貯存和調(diào)用等 , 這是編程求解動(dòng)態(tài) 規(guī)劃問題的難點(diǎn)所在 , 也是必須要解決的問題 。2. 1 Matlab 實(shí)現(xiàn)方法綜述在這里僅就動(dòng)態(tài)規(guī)劃基本方程的逆序形式進(jìn)行討論 , 順序形式也類似 。 對于各個(gè)階段的子問題 的求解方法基本都是相同的 , 在當(dāng)前階段的所有子 問題求得最優(yōu)決策以后 , 通過狀態(tài)轉(zhuǎn)移方程可以確 定出下一階段的狀態(tài)和允許狀態(tài)集合 , 從而可以在 決策集合上來尋求這個(gè)新階段的最優(yōu)決策 。從第 n 個(gè)階段出發(fā) , 直到第一個(gè)階段為止 , 即可得到全 過程的最優(yōu)決策 。因此

11、 , 在具體實(shí)現(xiàn)的過程中 , 針 對每一個(gè)狀態(tài)編寫一個(gè)相對通用的函數(shù) , 然后在主 程序中循環(huán)調(diào)用該函數(shù) , 以實(shí)現(xiàn)任意狀態(tài)下的最優(yōu) 決策 。 問題的主體程序框圖如圖 1所示 。圖 1 主程序框圖2. 2 具體程序?qū)崿F(xiàn)按照如上的程序框圖 , 編寫相關(guān)程序 , 主要由 5個(gè)子程序構(gòu)成 : 主函數(shù) function pai, zhi =main (s , W 輸入狀態(tài)向量 s 和相關(guān)指標(biāo)矩陣 W , 返回最優(yōu)策略 和相應(yīng)指標(biāo)值 ; 用全局變量 x , xx , xxx , 分別記錄指 標(biāo)值 、 狀態(tài)地址和相應(yīng)決策 。 狀態(tài)計(jì)算子函數(shù) f unction ff (n , ss , val 計(jì) 算相應(yīng)

12、狀態(tài)下的最優(yōu)決策 , 并存儲 ; n 為目前階段 數(shù) ,ss 為前一階段某個(gè)狀態(tài)的最優(yōu)決策 ,val 為相應(yīng) 指標(biāo)值 。 輔助計(jì)算子函數(shù) f unction ser , d =prep (s , tot , n ,ser 確定變量 xx ; 在某個(gè)階段 , 對該階段所 有狀態(tài)進(jìn)行預(yù)排列 , 并在 xx 中記錄狀態(tài)的相對位 置 ;n 表示本次是第幾次調(diào)用 ,tot 表示排列的數(shù)目 ; 在主函數(shù)中調(diào)用 。69 信 息 工 程 大 學(xué) 學(xué) 報(bào) 2005年 查找子函數(shù) f unction m =serc (ss 根據(jù) 輔助計(jì)算子函數(shù)在 xx 中記錄的位置 , 在某個(gè)階段 中查找相應(yīng)狀態(tài)的地址 ; ss

13、 為待查尋的狀態(tài) ; 在子 函數(shù) 2中調(diào)用。 指標(biāo)計(jì)算子函數(shù) f unction f=vv (參數(shù) 計(jì)算所確定決策的指標(biāo)值。2. 3 計(jì)算結(jié)果的存儲方法在實(shí)際計(jì)算過程中 , 對于中間的階段性結(jié)果必 須要進(jìn)行存儲 , 也是為后續(xù)計(jì)算的基礎(chǔ) , 這是求解 動(dòng)態(tài)規(guī)劃問題的主要特征體現(xiàn) , 而與存儲相關(guān)的問 題也是動(dòng)態(tài)規(guī)劃編程實(shí)現(xiàn)的難點(diǎn)之一 。在具體操 作中 , 將每個(gè)階段的最優(yōu)值的計(jì)算結(jié)果都要保存下 來 , 在計(jì)算結(jié)束后就可以得到一族最優(yōu)決策 , 通過 比較各策略的優(yōu)劣 , 從而可以得到問題的全局最優(yōu) 決策 。同時(shí) , 因?yàn)榇鎯α亢艽?, 在計(jì)算過程中要注 意內(nèi)存變量的替換 , 以節(jié)省內(nèi)存空間 。

14、具體做法可 有兩種 :一是將所有決策結(jié)果綜合比較后得到最優(yōu) 解 , 然后直接一次性存儲 ;果都與上次存儲的結(jié)果進(jìn)行比較 ,于在許多實(shí)際問題中 , , , 該狀態(tài)下 。 因此 , 只能采用第 二種方法實(shí)現(xiàn) 。 方法如下 : 將需要存儲的數(shù)據(jù)置為全局變量 , 每個(gè)階段 對應(yīng)一個(gè)數(shù)組 , 每個(gè)狀態(tài)對應(yīng)該數(shù)組中的一個(gè)元 素 , 并賦初值為零 ; 當(dāng)?shù)玫侥硞€(gè)允許決策時(shí) , 確定其對應(yīng)的狀 態(tài) , 尋找相應(yīng)的存儲空間 ; 計(jì)算該決策的指標(biāo)函數(shù)值 , 并與原來的存儲 結(jié)果比較 , 然后擇優(yōu)存儲 。值得說明的是 , 在一些復(fù)雜的問題中 , 在允許 狀態(tài)集合中尋求相應(yīng)的狀態(tài)和對應(yīng)的決策是一個(gè) 難點(diǎn) 。 如果對于

15、某個(gè)階段的允許狀態(tài)集合的元素 (即狀態(tài) 很多 , 如何快速找到相應(yīng)的狀態(tài)及存儲空 間 ? 一般不能采用循環(huán)搜索的方法 , 因?yàn)樗暮臅r(shí) 是不可忍受的 。 這在實(shí)際計(jì)算中是非常重要的 , 應(yīng) 該具體問題采取具體的方法 。 另外 , 計(jì)算結(jié)果的存 儲必須包括指標(biāo)值的存儲和決策變量的存儲 , 因 此 , 還需要定義一個(gè)用于存儲最優(yōu)決策全局變量 , 而且兩個(gè)全局變量的讀 、 寫也必須是同步的 。3 求解方法的實(shí)踐與應(yīng)用3. 1 最佳組隊(duì)問題 1在文獻(xiàn) 1中的第 3個(gè)問題 :“ 確定最佳組隊(duì)問 題 , 即要求給出 18名隊(duì)員組成 6個(gè)隊(duì)的組隊(duì)方案 , 使整體競賽水平最高 , 并給出每個(gè)隊(duì)的競賽水平” 。

16、 文獻(xiàn) 1建立了最佳組隊(duì)的動(dòng)態(tài)規(guī)劃模型 , 其 模型的基本方程以逆序形式給出 , 即f k (S k =maxxk Dkv k (S k , X k +f k +1(S k -1 , k =5, 4, 3, 2, 1 f 6(S 6 =v 6=0. 0563246 (L , G, S 隊(duì)的技術(shù)水平指標(biāo) 其中決策變量為 X k =(x , y , z k , 即任取 3名隊(duì)員 (x , y , z 所組成的一個(gè)組隊(duì)方案 ; 狀態(tài)變量為 S k , 即從第 k 個(gè)到第 5個(gè)組隊(duì)的組隊(duì)方案所包含的隊(duì) 員 , S 1=A , B , C , , T; 狀態(tài)轉(zhuǎn)移方程為 S k +1= S k -X k

17、; 允許決策集合為 D k =(x , y , z ; x , y , z S k , v k (x , y , z W(k =1, 2, 3, 4, 5 ; 指標(biāo)函數(shù)為 v k (S k , X k 表示決策 X k (一個(gè)組隊(duì) 關(guān)于狀態(tài) S k 的 技術(shù)水平指標(biāo) ; 最優(yōu)值函數(shù) f k (S k 表示在狀態(tài) S k 下確定的 k (1 k 5的最大值 。, 其狀 , 3個(gè)變量構(gòu)成 , 而 。決策過程分為 5個(gè)階 , 5個(gè)隊(duì)的組隊(duì)方案 , 在除了一個(gè)最 佳組隊(duì)的 3名隊(duì)員 (L , G , S 1外的 15名隊(duì)員中組 成 5個(gè)隊(duì) , 每一階段確定一個(gè)隊(duì) 。第一階段有 C 315個(gè)狀態(tài) ,C

18、315個(gè)子決策 ; 第二階段有 C 615個(gè)狀態(tài) ,C 615個(gè) 子決策 ; 第 3階段有 C 915個(gè)狀態(tài) ,C 915個(gè)子決策 ; 第 4階段有 C 1215個(gè)狀態(tài) ,C 1215個(gè)子決策 ; 第 5階段有 1個(gè)狀 態(tài) ,1個(gè)決策 (即最優(yōu)策略 。參考 2. 2, 編寫相關(guān)程序 , 運(yùn)行可以得最佳的 決策方案 , 即最佳的組隊(duì)方案為 , (K , L , Q , (D , M , R , (B , C , O , (F , J , P , (A , E , N , 其整體競 賽水平指標(biāo)為 0. 3241。由此結(jié)果可以看出 , 求解結(jié)果 (即組隊(duì)方案 優(yōu) 于文獻(xiàn) 1中的結(jié)果 , 從而也說明了

19、文獻(xiàn) 1的解是 局部最優(yōu)解 , 并非全局最優(yōu)解 。3. 2 最短路線問題 2對于最短路線問題 2也是一類非常有代表性 的問題 , 即對于給定的網(wǎng)絡(luò) , 從 A 點(diǎn)到 G 點(diǎn)尋求一 條最短的路線 。其問題可以歸結(jié)為 6個(gè)階段的動(dòng) , 即基本方程的逆序形式為 :f k (s k =minxk Dk(skd k (s k , x k (s k +f k +1(s k +1 , k =6, 5 , 4, 3, 2, 1f 7(s 7 =0, 或 f 6(s 6 =d 6(s 6, G 編寫程序 , 求解可以得到最短路線為 A B 1 C 2 D 1 E 2 F 2 G , 其最短距離為 18。此結(jié)果與

20、 直接計(jì)算的最優(yōu)結(jié)果完全一致 , 充分說明該求解方 法的有效性 。4 結(jié)果的分析與說明根據(jù)前面的分析和實(shí)際應(yīng)用結(jié)果 , 可以充分地 79第 3期 于 斌等 :動(dòng)態(tài)規(guī)劃求解方法的 Matlab 實(shí)現(xiàn)及應(yīng)用 證明 , 我們采用的求解動(dòng)態(tài)規(guī)劃問題的方法和 Mat 2 lab 實(shí)現(xiàn)程序是有效可行的 , 由此可以求得問題的 全局最優(yōu)解 。 特別是在變量的使用和存貯處理上 , 所采用的方法使得利用現(xiàn)有計(jì)算機(jī)資源求解一般 性的動(dòng)態(tài)規(guī)劃問題成為可能 。 但值得注意的是 :在 很多情況下 , 在確定某階段狀態(tài)時(shí) , 首先要獲取前 一階段的決策 , 因此 , 需將每個(gè)階段的最優(yōu)子決策 和指標(biāo)值記錄并保存 。當(dāng)每個(gè)

21、階段都有多個(gè)狀態(tài) 時(shí) , 則須計(jì)算該狀態(tài)下的所有可能決策 。 為了快速 尋找并調(diào)用相應(yīng)計(jì)算結(jié)果 , 有必要對各階段的所有 狀態(tài)進(jìn)行唯一 、 簡單的標(biāo)識 , 并記錄其存儲地址 。 根據(jù)目前的計(jì)算機(jī)技術(shù)水平 , 這種方法也不是 對任何動(dòng)態(tài)規(guī)劃問題都能解決 , 當(dāng)問題的階段數(shù)和 各階段的狀態(tài)數(shù)很大時(shí) , 從理論上是可行的 , 但實(shí) 際是無法做到的 。這里我們可以做一個(gè)初步的估 算 , 譬如 :就最佳組隊(duì)問題 , 其時(shí)間和空間復(fù)雜度都 是 O (e n , 按照 15個(gè)人的情況來計(jì)算 , 每個(gè)狀態(tài)至 少需要 80Bytes 儲 , 那么 , 不難得到解決不同規(guī)模的問題需消耗的 資源見表 1。表 1 不

22、同分組人數(shù)需消耗資源分組人數(shù) 1518212427狀態(tài)數(shù) 10k 100k 700k 5. 4M 50M 所需內(nèi)存 800kB 8M B 56M B 432M B 4G B 計(jì)算時(shí)間 10min 100min 700min 100h 1000h 可見 , 人數(shù)多于 24(包括 24 時(shí)問題的求解幾 乎是不可能的了 。參考文獻(xiàn) :1韓中庚 . 最佳組隊(duì)方案及模型 J.數(shù)學(xué)的實(shí)踐與認(rèn)識 , 1997, 27(2 :133-140.2編寫組 . 運(yùn)籌學(xué) (修訂版 M.:清華大學(xué)出版社 , 1994.3. M 版 :北京航空航天(上接第 94頁 P 1P 2P 3P 4P 5P 6 u 18. 08. 26. 96. 38. 94. 5 u 27. 29. 07. 45. 89. 25. 5 u 317197. 96. 56. 18. 55. 2 u 328. 48. 26. 95