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

1、動(dòng)態(tài)規(guī)劃方法的matlab實(shí)現(xiàn)及其應(yīng)用（龍京鵬，張華慶，羅明良，劉水林）(南昌航空大學(xué)，數(shù)學(xué)與信息科學(xué)學(xué)院，江西，南昌)摘要：本文運(yùn)用matlab語(yǔ)言實(shí)現(xiàn)了動(dòng)態(tài)規(guī)劃的逆序算法，根據(jù)狀態(tài)變量的維數(shù)，編寫了指標(biāo)函數(shù)最小值的逆序算法遞歸計(jì)算程序。兩個(gè)實(shí)例的應(yīng)用檢驗(yàn)了該程序的有效性，同時(shí)也表明了該算法程序?qū)Ρ姸囝惖湫偷膭?dòng)態(tài)規(guī)劃應(yīng)用問題尤其是確定離散型的應(yīng)用問題的通用性，提供了求解各種動(dòng)態(tài)規(guī)劃問題的有效工具。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃基本方程的逆序算法MA

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

3、ithmofdynamicprogrammingbyusingthematlablanguage，preparestherecursivecalculationprogramofreversealgithmwhichthetargetfunctionvalueisthesmallest.Theapplicationoftwoexamplesshowthattheprogramiseffective，thisalgithmprogrami

4、sgeneraltomanytypicalapplicationofdynamicprogrammingespeciallytheapplicationofdeterministicdiscrete.Thisalgithmprogramprovidesaeffectivetooltothesolutionofavarietyofdynamicprogrammingproblems.Keywds:dynamicprogramming；re

5、versealgithm；Matlabachievement動(dòng)態(tài)規(guī)劃是一類解決多階段決策問題的數(shù)學(xué)方法在工程技術(shù)、科學(xué)管理、工農(nóng)業(yè)生產(chǎn)及軍事等領(lǐng)域都有廣泛的應(yīng)用。在理論上動(dòng)態(tài)規(guī)劃是求解這類問題全局最優(yōu)解的一種有效方法特別是對(duì)于實(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)用中需要具體

6、問題具體分析。動(dòng)態(tài)規(guī)劃模型的求解問題是影響動(dòng)態(tài)規(guī)劃理論和方法應(yīng)用的關(guān)鍵所在而子問題的求解和大量結(jié)果的存儲(chǔ)、調(diào)用更是一個(gè)難點(diǎn)所在。然而隨著計(jì)算機(jī)技術(shù)的快速發(fā)展特別是內(nèi)存容量和計(jì)算速度的增加使求解較小規(guī)模的動(dòng)態(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)大功能對(duì)動(dòng)態(tài)規(guī)劃模型的求解

7、方法做了嘗試編寫出了動(dòng)態(tài)規(guī)劃逆序算法的matlab程序，并結(jié)合“生產(chǎn)與存儲(chǔ)問題”[1]和“背包問題”[1]進(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è)階段。這些階段必須是有序的或者是可排序的(即無后向性)否則應(yīng)用無效。②選擇狀態(tài)將問題發(fā)展到各個(gè)階段時(shí)所處的各種客觀情況用不同的狀態(tài)表示即稱為狀態(tài)。狀態(tài)的選擇要滿足

8、無后效性和可知性即狀態(tài)不僅依賴于狀態(tài)的轉(zhuǎn)移規(guī)律還依賴于允許決策集合和指標(biāo)函數(shù)結(jié)構(gòu)。③確定決策變量與狀態(tài)轉(zhuǎn)移方程當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)可以做出不同的決策描述決策的變量稱為決策變量。在決策過程中由一個(gè)狀態(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ī)劃基本方程的逆序形式為