基于Matlab的動態(tài)規(guī)劃問題

《基于Matlab的動態(tài)規(guī)劃問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第22卷第5期重慶工學(xué)院學(xué)報(自然科學(xué))2008年5月V01．22No．5JournalofChongqingInstituteofTechnology(NaturalScience)May2008---●_-_--●_●-●--__●__-_●__-_____lIll_______-__________●___-_●_●●_-_●__●●-●I-_-_●_●●-l_--__-●●●●_-●-__●-__---_-基于Matlab的動態(tài)規(guī)劃問題+鄭怡，趙海良，徐永(西南交通大學(xué)數(shù)學(xué)系，成都610031)Matlab-basedDynainicProgrammi

2、ngZHENGYi，ZHAOHai—liang，XUYong(DepartmentofMathematics，SouthwestJiaotongUniversity，Chengdu610031，China)Abstract：Thispaperintroducesthebasictheoryofdynamicprogramming，includingthebasiceonceptsandbasicideas，analyzestheallocationofresourcesindynamicprogrammingwithMatlab，andeonducmproce

3、duredesignsandcomputationwithMaflab，simplifyingcomplexissuesandavoidingtheeulnbersomecalculationstomakemoreconvenientsolutionstoproblems．Keywords：dynamicprogramming；allocationofl'esoul把es；Matlablanguage動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法．該方法是由美國數(shù)學(xué)家貝爾曼(R．Bellm肌)等人在20世紀50年代初提出的．他們針對多階段決策問題的特點，提出

4、了解決這類問題的最優(yōu)化原理，并成功地解決了生產(chǎn)管理、資源分配等方面的許多實際問題，從而建立了運籌學(xué)的一個新分支——動態(tài)規(guī)劃?1．動態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于解決最優(yōu)路徑、資源分配、生產(chǎn)計劃與庫存、投資、裝載、排序等問題，還可用于生產(chǎn)過程的最優(yōu)控制等．由于它有獨特的解題思路，因而在處理某些優(yōu)化問題時，比線性規(guī)劃或非線性規(guī)劃方法更有效．而Mat．1ab是一個功能強大的用于基于矩陣運算的強大數(shù)值計算軟件[2

5、．將Matlab語言應(yīng)用到動態(tài)規(guī)劃中去，對實際問題進行程序設(shè)計和計算，可以達到計算簡便的目的．1動態(tài)規(guī)劃的基本理論1．1動態(tài)規(guī)劃的基本概念

6、使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實際問題寫成動態(tài)規(guī)劃模型，此時要用到·收稿日期：2008—03—06作者簡介：鄭怡(1983一)，男，浙江衢州人，碩士研究生，主要從事模糊智能控制、優(yōu)化與決策研究；趙海良(1962一)，男，教授，主要從事模糊控制與智能控制、模糊信息處理研究．鄭怡，等：基于Matlab的動態(tài)規(guī)劃問題153以下概念：1)階段．將所給問題的過程，按時間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求解每階段的解，每個階段就是一個子問題，常用字母k表示階段變量．2)狀態(tài)．各階段開始時的客觀條件叫做狀態(tài)．描述各階段狀態(tài)的變量稱為狀態(tài)變量，常

7、用甄表示第k階段的狀態(tài)變量．狀態(tài)變量s。的取值集合稱為狀態(tài)集合，用S^表示．3)決策和策略．當各段的狀態(tài)取定以后，就可以作出不同的決策(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策．表示決策的變量稱為決策變量，常用‰(吼)表示第k階段當狀態(tài)為吼時的決策變量．在實際問題中，決策變量的取值往往限制在一定范圍內(nèi)，稱此范圍為允許決策集合，常用D＆(％)表示第五階段從狀態(tài)船出發(fā)的允許決策集合，顯然有M^∈D＆(％)．4)狀態(tài)轉(zhuǎn)移．動態(tài)規(guī)劃中本階段往往是上一階段狀態(tài)和上一階段的決策進行綜合的結(jié)果．如果給定了第k段的狀態(tài)s＆，且該階段決策為‰(札)，則第k+1段的狀態(tài)

8、s＆+l也就完全確定．它們的關(guān)系可表示為：軋+1=Tk(Sk，Uk)由于上式表示了由k段到k+1段的狀態(tài)轉(zhuǎn)移規(guī)律，所以稱該式為狀態(tài)轉(zhuǎn)移方程．5)指標函數(shù)．用于衡量所選定策略優(yōu)劣的數(shù)量指標稱為指標函數(shù)．一個／7,階段決策過程，從1到／'t叫作問題的原過程．對于任意一個給定的k(1≤k≤n)，從第k階段到第／'t階段的過程稱為原過程的一個后部子過程．y1．。(s1，Pl，。)表示初始狀態(tài)為s。采用策略Pl,n時原過程的指標函數(shù)值，而既．。(％，以，。)表示在第k階段，狀態(tài)為軋采用策略pk,n時后部子過程的指標函數(shù)值．最優(yōu)指標函數(shù)記為以(釓)，它表示從第k階段狀態(tài)船

9、采用最優(yōu)策略pt。到過程終止時的最佳效