動態(tài)規(guī)劃方法的matlab實現(xiàn)及其應用

1、動態(tài)規(guī)劃方法的matlab實現(xiàn)及其應用（龍京鵬，張華慶，羅明良，劉水林）(南昌航空大學，數學與信息科學學院，江西，南昌)摘要：本文運用matlab語言實現(xiàn)了動態(tài)規(guī)劃的逆序算法，根據狀態(tài)變量的維數，編寫了指標函數最小值的逆序算法遞歸計算程序。兩個實例的應用檢驗了該程序的有效性，同時也表明了該算法程序對眾多類典型的動態(tài)規(guī)劃應用問題尤其是確定離散型的應用問題的通用性，提供了求解各種動態(tài)規(guī)劃問題的有效工具。關鍵詞：動態(tài)規(guī)劃基本方程的逆序算法MA

2、TLAB實現(xiàn)MATLABAchieveFDynamicProgrammingItsApplication(JingpengLong，HuaqingZhang，MingliangLuo，ShuilinLiu)（SchoolofMathematicsInfmationScienceNanchangHangkongUniversityNanchangChina）Abstract:Thisarticleachievesthereversealg

3、ithmofdynamicprogrammingbyusingthematlablanguage，preparestherecursivecalculationprogramofreversealgithmwhichthetargetfunctionvalueisthesmallest.Theapplicationoftwoexamplesshowthattheprogramiseffective，thisalgithmprogrami

4、sgeneraltomanytypicalapplicationofdynamicprogrammingespeciallytheapplicationofdeterministicdiscrete.Thisalgithmprogramprovidesaeffectivetooltothesolutionofavarietyofdynamicprogrammingproblems.Keywds:dynamicprogramming；re

5、versealgithm；Matlabachievement動態(tài)規(guī)劃是一類解決多階段決策問題的數學方法在工程技術、科學管理、工農業(yè)生產及軍事等領域都有廣泛的應用。在理論上動態(tài)規(guī)劃是求解這類問題全局最優(yōu)解的一種有效方法特別是對于實際中某些非線性規(guī)劃問題可能是最優(yōu)解的唯一方法。然而動態(tài)規(guī)劃僅僅決多階段決策問題的一種方法或者說是考查問題的一種途徑而不是一種具體的算法。就目前而言動態(tài)規(guī)劃沒有統(tǒng)一的標準模型其解法也沒有標準算法在實際應用中需要具體

6、問題具體分析。動態(tài)規(guī)劃模型的求解問題是影響動態(tài)規(guī)劃理論和方法應用的關鍵所在而子問題的求解和大量結果的存儲、調用更是一個難點所在。然而隨著計算機技術的快速發(fā)展特別是內存容量和計算速度的增加使求解較小規(guī)模的動態(tài)規(guī)劃問題成為可能從而使得動態(tài)規(guī)劃的理論和方法在實際中的應用范圍迅速增加。目前在計算機上實現(xiàn)動態(tài)規(guī)劃的一般求解方法并不多見尤其是用來解決較復雜的具體問題的成果甚少。本文從實際出發(fā)利用數學工具軟件matlab的強大功能對動態(tài)規(guī)劃模型的求解

7、方法做了嘗試編寫出了動態(tài)規(guī)劃逆序算法的matlab程序，并結合“生產與存儲問題”[1]和“背包問題”[1]進行了應用與檢驗實際證明結果是令人滿意的。1動態(tài)規(guī)劃的基本模型實際中要構造一個標準的動態(tài)規(guī)劃模型通常需要采用以下幾個步驟:①劃分階段按照問題的時間或空間特征把問題分為若干個階段。這些階段必須是有序的或者是可排序的(即無后向性)否則應用無效。②選擇狀態(tài)將問題發(fā)展到各個階段時所處的各種客觀情況用不同的狀態(tài)表示即稱為狀態(tài)。狀態(tài)的選擇要滿足

8、無后效性和可知性即狀態(tài)不僅依賴于狀態(tài)的轉移規(guī)律還依賴于允許決策集合和指標函數結構。③確定決策變量與狀態(tài)轉移方程當過程處于某一階段的某個狀態(tài)時可以做出不同的決策描述決策的變量稱為決策變量。在決策過程中由一個狀態(tài)到另一個狀態(tài)的演變過程稱為狀態(tài)轉移。狀態(tài)轉移就是根據上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。④寫出動態(tài)規(guī)劃的基本方程動態(tài)規(guī)劃的基本方程一般根據實際問題可分為兩種形式逆序形式和順序形式。這里只考慮逆序形式。動態(tài)規(guī)劃基本方程的逆序形式為