基于matlab的動(dòng)態(tài)規(guī)劃逆序算法的實(shí)現(xiàn)

《基于matlab的動(dòng)態(tài)規(guī)劃逆序算法的實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第15卷第1期紡織高?；A(chǔ)科學(xué)學(xué)報(bào)Vol.15,No.12002年3月BASICSCIENCESJOURNALOFTEXTILEUNIVERSITIESMarch,2002基于MATLAB的動(dòng)態(tài)規(guī)劃逆序算法的實(shí)現(xiàn)孫曉君(東華大學(xué)應(yīng)用數(shù)學(xué)系,上海200051)摘要:運(yùn)用MATLAB編程實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃逆序算法.數(shù)值舉例驗(yàn)證了該實(shí)現(xiàn)方法的有效性,同時(shí)表明該程序?qū)η蠼鈩?dòng)態(tài)規(guī)劃的多類典型應(yīng)用問題是通用的,提供了求解各種動(dòng)態(tài)規(guī)劃問題的有效工具,豐富了MATLAB優(yōu)化工具箱.關(guān)鍵詞:MATLAB;動(dòng)態(tài)規(guī)劃;逆序算法中圖分類號(hào)

2、:O221.3;TP31文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1006-8341(2002)01-0038-04[1]動(dòng)態(tài)規(guī)劃(DynamicProgramming)是求解決策過程最優(yōu)化的有效數(shù)學(xué)方法.它是根據(jù)“最優(yōu)決策的任何截?cái)嗳允亲顑?yōu)的”這一原理,通過將多階段決策過程轉(zhuǎn)化為一系列單階段問題,逐個(gè)求解的優(yōu)化求解方法.自1957年R.E.Bellman教授出版動(dòng)態(tài)規(guī)劃的經(jīng)典專著“DynamicProgramming”以來,動(dòng)態(tài)規(guī)劃已在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等領(lǐng)域得到廣泛的應(yīng)用.逆序算法是動(dòng)態(tài)[2]規(guī)劃計(jì)算的

3、重要算法.MATLAB是美國MathWorks公司80年代中期推出的數(shù)學(xué)軟件,其中的優(yōu)化工具箱已被許多設(shè)計(jì)研究部門和科研工作者使用,成為決策系統(tǒng)的優(yōu)化計(jì)算和設(shè)計(jì)的有力工具,但該工具箱中尚無動(dòng)態(tài)規(guī)劃計(jì)算的程序文檔.1動(dòng)態(tài)規(guī)劃簡(jiǎn)介(1)階段整個(gè)問題的解決可分為若干個(gè)相互聯(lián)系的階段依次進(jìn)行.描述階段的變量稱為階段變量,記為k.(2)狀態(tài)狀態(tài)表示每個(gè)階段開始所處的自然狀況或客觀條件,它描述了研究問題過程的狀況.各階段狀態(tài)通常用狀態(tài)變量描述.用xk表示第k階段狀態(tài)變量,n個(gè)階段決策過程有n+1個(gè)狀態(tài).(3)決策從一確定

4、的狀態(tài)作出各種選擇從而演變到下一階段某一狀態(tài),這種選擇手段稱為決策.描述決策的變量稱為決策變量,決策變量限制的取值范圍稱為允許決策集合.用uk(xk)表示第k階段處于狀態(tài)xk時(shí)的決策變量,它是xk的函數(shù),用Dk(xk)表示xk的允許決策的集合.(4)策略每個(gè)階段的決策按順序組成的集合稱為策略.由第k階段的狀態(tài)xk開始到終止?fàn)顟B(tài)的后部子過程的策略記為{uk(xk),uk+1(xk+1),...,un(xn)}.可供選擇的策略的范圍稱為允許策略*集合,允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略.從初始狀態(tài)x1(

5、=x1)出發(fā),過程按照最優(yōu)***策略和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列{x1,x2,?,xn+1}稱為最優(yōu)軌線.(5)狀態(tài)轉(zhuǎn)移方程如果第k個(gè)階段狀態(tài)變量為xk,作出的決策為uk,那么第k+1階段的狀X收稿日期:2001-12-14作者簡(jiǎn)介:孫曉君(1965-),女,浙江省杭州市人,東華大學(xué)副教授,主要從事決策規(guī)劃與應(yīng)用,隨機(jī)分析與應(yīng)用等方面的研究.X第1期基于MATLAB的動(dòng)態(tài)規(guī)劃逆序算法的實(shí)現(xiàn)39態(tài)變量xk+1也被完全確定.用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律,記為xk+1=Tk(xk,uk).(6)指標(biāo)函數(shù)和最

6、優(yōu)值函數(shù)指標(biāo)函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生結(jié)果的數(shù)量表示,是衡量策略優(yōu)劣數(shù)量指標(biāo),它定義在全過程和所有后部子過程上.過程在某階段j的階段指標(biāo)函數(shù)是衡量該階段決策優(yōu)劣數(shù)量指標(biāo),取決于狀態(tài)xj和決策uj,用vj(uj,xj)表示.指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)函數(shù).2逆序算法及其MATLAB程序2.1逆序算法的基本方程[3]下面的遞歸方程在動(dòng)態(tài)規(guī)劃逆序算法中起著本質(zhì)的作用:fk(xk)=min{g(vk(xk,uk(xk)),fk+1(xk+1))?uk∈Dk(xk)},(1)fn+1(xn+1)=vk+1,xk+1=T

7、k(xk,uk),k=n,n-1,?,1.方程(1)稱為動(dòng)態(tài)規(guī)劃逆序求解的基本方程.2.2動(dòng)態(tài)規(guī)劃逆序算法的MATLAB程序自由始段和終端的動(dòng)態(tài)規(guī)劃,求指標(biāo)函數(shù)最小值的逆序(或后向)算法遞歸計(jì)算程序:function[popt,fval]=dynprog(x,DecisFun,SubObjFun,TransFun,ObjFun)其中x是狀態(tài)變量,一列代表一個(gè)階段狀態(tài);M-函數(shù)DecisFun(k,x)由階段k的狀態(tài)變量x求出相應(yīng)的允許決策變量;M-函數(shù)SubObjFun(k,x,u)是階段指標(biāo)函數(shù),M-函數(shù)T

8、ransFun(k,x,u)是狀態(tài)轉(zhuǎn)移函數(shù),其中x是階段k的某狀態(tài)變量,u是相應(yīng)的決策變量;M-函數(shù)ObjFun(v,f)是第k階段至最后階段指標(biāo)函數(shù),當(dāng)ObjFun(v,f)=v+f時(shí),輸入ObjFun可以省略.輸出popt由4列構(gòu)成,popt=[序號(hào)組;最優(yōu)策略組;最優(yōu)軌線組;指標(biāo)函數(shù)值組];fval是一個(gè)列向量,各元素分別表示popt各最優(yōu)策略組對(duì)應(yīng)始端狀態(tài)x的最優(yōu)函數(shù)值;～k=length(