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

《動(dòng)態(tài)規(guī)劃方法matlab實(shí)現(xiàn)應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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)用問(wèn)題尤其是確定離散型的應(yīng)用問(wèn)題的通用性，提供了求解各種動(dòng)態(tài)規(guī)劃問(wèn)題的有效工具。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃基本方程的逆序算法MATLAB實(shí)現(xiàn)MATLABAchieveForDynamicProg

2、rammingandItsApplication(JingpengLong，HuaqingZhang，MingliangLuo，ShuilinLiu)（SchoolofMathematicsandInformationScience,NanchangHangkongUniversity,Nanchang,China）Abstract:Thisarticleachievesthereversealgorithmofdynamicprogrammingbyusingthematlablanguage，and

3、preparestherecursivecalculationprogramofreversealgorithmwhichthetargetfunctionvalueisthesmallest.Theapplicationoftwoexamplesshowthattheprogramiseffective，andthisalgorithmprogramisgeneraltomanytypicalapplicationofdynamicprogramming,especiallytheapplicatio

4、nofdeterministicdiscrete.Thisalgorithmprogramprovidesaeffectivetooltothesolutionofavarietyofdynamicprogrammingproblems.Keywords:dynamicprogramming；reversealgorithm；Matlabachievement...動(dòng)態(tài)規(guī)劃是一類解決多階段決策問(wèn)題的數(shù)學(xué)方法,在工程技術(shù)、科學(xué)管理、工農(nóng)業(yè)生產(chǎn)及軍事等領(lǐng)域都有廣泛的應(yīng)用。在理論上,動(dòng)態(tài)規(guī)劃是求解這類問(wèn)題全局

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

6、的理論和方法在實(shí)際中的應(yīng)用范圍迅速增加。目前,在計(jì)算機(jī)上實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的一般求解方法并不多見(jiàn),尤其是用來(lái)解決較復(fù)雜的具體問(wèn)題的成果甚少。本文從實(shí)際出發(fā),利用數(shù)學(xué)工具軟件matlab的強(qiáng)大功能,對(duì)動(dòng)態(tài)規(guī)劃模型的求解方法做了嘗試,編寫出了動(dòng)態(tài)規(guī)劃逆序算法的matlab程序，并結(jié)合“生產(chǎn)與存儲(chǔ)問(wèn)題”[1]和“背包問(wèn)題”[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è)步驟:①劃分階段按照問(wèn)題的時(shí)間或空間特征,把問(wèn)題分為若干個(gè)階段。這些

7、階段必須是有序的或者是可排序的(即無(wú)后向性),否則,應(yīng)用無(wú)效。②選擇狀態(tài)將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處的各種客觀情況用不同的狀態(tài)表示,即稱為狀態(tài)。狀態(tài)的選擇要滿足無(wú)后效性和可知性,即狀態(tài)不僅依賴于狀態(tài)的轉(zhuǎn)移規(guī)律,還依賴于允許決策集合和指標(biāo)函數(shù)結(jié)構(gòu)。③確定決策變量與狀態(tài)轉(zhuǎn)移方程當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí),可以做出不同的決策,描述決策的變量稱為決策變量。在決策過(guò)程中,由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程稱為狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。④寫出動(dòng)態(tài)規(guī)劃的基本方程動(dòng)態(tài)規(guī)劃的基本方

8、程一般根據(jù)實(shí)際問(wèn)題可分為兩種形式,逆序形式和順序形式。這里只考慮逆序形式。動(dòng)態(tài)規(guī)劃基本方程的逆序形式為fskk()=optgvsx{(kkk(,)+fsk+1(k+1))}xDsk∈kk()knn=,?1,?,1邊界條件fsn+1(n+1)=0或fsvsxnn()=nnn(,)其中第k階段的狀態(tài)為sk,其決策變量xk表示狀sk的決策,狀態(tài)轉(zhuǎn)移方程為sk+1=Tsxkkk(,),態(tài)處于k階段的允許決策集合記為Dskk(),vsxkkk(,)為