資源描述：
《動態(tài)規(guī)劃的基本概念和基本定》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、引言動態(tài)規(guī)劃(DynamicProgramming)是解決多階段決策問題最優(yōu)化的一種數(shù)學(xué)方法.1951年,美國數(shù)學(xué)家貝爾曼(R.Bellman)等人提出了“最優(yōu)化原理”,把多階段決策問題變換為一系列相互聯(lián)系的單階段決策問題，逐階段加以求解,創(chuàng)建了動態(tài)規(guī)劃方法.名著《動態(tài)規(guī)劃》于1957年出版,是該領(lǐng)域的第一本著作.動態(tài)規(guī)劃應(yīng)用廣泛.如求解最短路問題、生產(chǎn)計劃問題、存儲問題、資源分配問題、推銷商問題等.第11章動態(tài)規(guī)劃的基本概念和基本定理1?動態(tài)決策問題分類1.按數(shù)據(jù)給出的形式分為：?離散型動態(tài)決策問題?連續(xù)型動態(tài)決策問題2.按決策過
2、程演變的性質(zhì)分為：?確定型動態(tài)決策問題?隨機型動態(tài)決策問題引言第11章動態(tài)規(guī)劃的基本概念和基本定理2AB1B2B3C1C2C3D1D2E243952351715364275§11.2動態(tài)規(guī)劃的基本概念和模型構(gòu)成一、動態(tài)規(guī)劃的基本概念以求最短路為例1.階段（stage）通常根據(jù)時間順序或空間特征把所給問題的全過程恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段,以便按階段的次序逐段解決整個過程的優(yōu)化問題.3AB1B2B3C1C2C3D1D2E243952351715364275一、動態(tài)規(guī)劃的基本概念以求最短路為例1.階段（stage）通常根據(jù)時間順序或
3、空間特征把所給問題的全過程恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段,以便按階段的次序逐段解決整個過程的優(yōu)化問題.描述階段的變量稱為階段變量,通常用k表示,k=1,…,n4一、動態(tài)規(guī)劃的基本概念1.階段（stage）通常根據(jù)時間順序或空間特征把所給問題的全過程恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段,以便按階段的次序逐段解決整個過程的優(yōu)化問題.描述階段的變量稱為階段變量,用k表示,k=1,…,n2.狀態(tài)（state）描述每個階段開始時所處的自然狀況或客觀條件.描述狀態(tài)的變量稱為狀態(tài)變量,用xk表示第k階段的狀態(tài)變量.第k階段所有狀態(tài)的集合稱為第k階段可達(dá)
4、狀態(tài)的集合,用Xk表示.如X3={C1,C2,C3}5一、動態(tài)規(guī)劃的基本概念1.階段（stage）2.狀態(tài)（state）描述每個階段開始時所處的自然狀況或客觀條件.描述狀態(tài)的變量稱為狀態(tài)變量,用xk表示第k階段的狀態(tài)變量.第k階段所有狀態(tài)的集合稱為第k階段可達(dá)狀態(tài)集合,用Xk表示.如X3={C1,C2,C3}3.決策（decision）決策的實質(zhì)是關(guān)于狀態(tài)的選擇,是從一個階段某狀態(tài)演變到下一個階段某狀態(tài)的選擇.決策變量—uk(xk),如u2(B1)=C26一、動態(tài)規(guī)劃的基本概念1.階段（stage）2.狀態(tài)（state）3.決策（d
5、ecision）決策的實質(zhì)是關(guān)于狀態(tài)的選擇,是從一個階段某狀態(tài)演變到下一個階段某狀態(tài)的選擇.4.策略（policy）策略也叫決策序列.從第1階段至第n階段的一個策略稱為全過程子策略,簡稱策略,記作p1,n(x1).從第k階段至第n階段的一個策略稱為后部子策略,記作pk,n(xk).7一、動態(tài)規(guī)劃的基本概念1.階段（stage）2.狀態(tài)（state）3.決策（decision）4.策略（policy）全過程子策略,簡稱策略,記作p1,n(x1).后部子策略,記作pk,n(xk).5.指標(biāo)函數(shù)（objectivefunction）用來衡
6、量決策或策略效果的某種數(shù)量指標(biāo),稱為指標(biāo)函數(shù).第k階段的指標(biāo)函數(shù)記作vk(xk,uk,).從第k階段至第n階段的指標(biāo)函數(shù)記作Vk,n(xk,pk,n).從第1階段至第n階段的指標(biāo)函數(shù)記作V1,n(x1,p1,n).8一、動態(tài)規(guī)劃的基本概念1.階段（stage）2.狀態(tài)（state）3.決策（decision）4.策略（policy）5.指標(biāo)函數(shù)（objectivefunction）用來衡量決策或策略效果的某種數(shù)量指標(biāo),稱為指標(biāo)函數(shù).第k階段的指標(biāo)函數(shù)記作vk(xk,uk,).從第k階段至第n階段的指標(biāo)函數(shù)記作Vk,n(xk,pk,n
7、).從第1階段至第n階段的指標(biāo)函數(shù)記作V1,n(x1,p1,n).指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)指標(biāo)函數(shù),記作fk(xk)或f1(x1).9二、動態(tài)規(guī)劃的模型構(gòu)成1.正確選擇階段變量k;2.正確選擇狀態(tài)變量xk——要保證無后效性,即某階段的狀態(tài)一旦確定,則此后過程的演變不受此前各狀態(tài)及決策的影響;3.正確選擇決策變量uk;4.列出狀態(tài)轉(zhuǎn)移方程xk+1=Tk(xk,uk);5.列出指標(biāo)函數(shù)Vk,n——要滿足按階段可分性,并滿足遞推關(guān)系Vk,n=Vk,n(xk,pk,n)=vk(xk,uk,)+Vk+1,n(xk+1,pk+1,n)10§11
8、.3基本理論和基本方程一、最優(yōu)化原理最優(yōu)策略的任一后部子策略都是最優(yōu)的.二、基本方程1.逆序遞推的基本方程(以求min為例)x11u1x2u22x3...xkukkxk+1...xnunnxn+1f1(x1)f2(x2)fk(xk)f
