第14章-動(dòng)態(tài)規(guī)劃

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第14章 動(dòng)態(tài)規(guī)劃本章通過將實(shí)際問題當(dāng)作多階段決策過程來建立數(shù)學(xué)模型，學(xué)習(xí)和掌握動(dòng)態(tài)規(guī)劃的相關(guān)知識(shí)及其求解的逆序算法，并結(jié)合計(jì)算機(jī)編程解決實(shí)際問題。14.1 引例：生產(chǎn)計(jì)劃的制定某工廠與用戶訂立合同，在四個(gè)月內(nèi)出售一定數(shù)量的某種產(chǎn)品，產(chǎn)量限制為10的倍數(shù)，工廠每月最多生產(chǎn)100件，產(chǎn)品可以存儲(chǔ)，存儲(chǔ)費(fèi)用為每臺(tái)2百元，每個(gè)月的需求量及每件產(chǎn)品的生產(chǎn)成本見表14.1。表14.1 生產(chǎn)成本和需要量月份每件生產(chǎn)成本（元）需要量（件）170602727038012047660現(xiàn)在分別在（1）一月初沒有存貨可用和（2）一月初有20件存貨可用這兩種情況下確定每月的出產(chǎn)量，要求既能滿

2、足每月的合同需求量，又使生產(chǎn)成本和存儲(chǔ)費(fèi)用達(dá)到最小。靜態(tài)的看，本引例是一個(gè)整數(shù)規(guī)劃問題，但這里我們可以把這個(gè)問題的解決動(dòng)態(tài)地視為各月（一般稱為階段）先后作出決策（這里指生產(chǎn)量）的過程多階段的決策過程，而在每個(gè)月作決策時(shí)，不能僅考慮本月的費(fèi)用（一般稱為階段指標(biāo)）因?yàn)楸驹碌臎Q策會(huì)對以后各月的決策產(chǎn)生影響，因此應(yīng)考慮從本月直到第四月末的總費(fèi)用（總指標(biāo)），而每月的決策依賴于各月初倉庫的存貨量（一般稱為始端）和以前各月如何造成這貨存量的情況無關(guān)（稱為無后效性）。在例2中我們將計(jì)算一月初無存貨可用時(shí)的最優(yōu)決策見表2表14.2 最優(yōu)生產(chǎn)計(jì)劃1月2月3月4月月初存儲(chǔ)量（件）040700產(chǎn)量（件）1001005

3、060則第四月的決策即為月初倉儲(chǔ)數(shù)為0時(shí)的最優(yōu)決策，第三、四月的決策即為第三月初倉儲(chǔ)數(shù)為70時(shí)的最優(yōu)決策，以及第二、三、四月的決策即為第二月初倉儲(chǔ)數(shù)為40時(shí)的最優(yōu)決策。因?yàn)槿舨蝗?，如對?yīng)于第三月初倉儲(chǔ)數(shù)為70時(shí)，第三、四月的最優(yōu)決策是分別生產(chǎn)80件和30件（即這樣的費(fèi)用比分別生產(chǎn)50件和60件更省），則我們保留第一、二月的生產(chǎn)數(shù)，而把第三第四月分別改為80件和30件，這個(gè)方案顯然優(yōu)于原來的方案，這和原來的方案是最優(yōu)相矛盾。這個(gè)性質(zhì)可以簡述為：最優(yōu)決策的任何截?cái)嗳允亲顑?yōu)的（最優(yōu)性原理）。把這一最優(yōu)化問題視為符合最優(yōu)性原理、無后效性的多階段決策過程并進(jìn)行求解的方法稱為動(dòng)態(tài)規(guī)劃方法。14.2 動(dòng)態(tài)規(guī)

4、劃的基本理論復(fù)習(xí)14.2.1基本思想與逆序解法的直觀回顧前面我們已簡單介紹了動(dòng)態(tài)規(guī)劃。為了更便于 了解動(dòng)態(tài)規(guī)劃的基本思想、描述方式和逆序解法，我們來看一個(gè)確定網(wǎng)絡(luò)最短路徑問題的例子。例1：（最短路徑的確定）以下是一個(gè)賦權(quán)圖，兩頂點(diǎn)連線上的數(shù)字表示距離，確定一條從始點(diǎn)到終點(diǎn)鋪設(shè)管道并使總距離最短的路線。 V4 1 6 2 V11 3 V2 3 3 V8 2 5 V14 4 5 6 V5 5 8 1 V12 2 5 3 V16V1 3 V9 2 6 6 V15 3 8 7 V6 3 V13 V3 6 8 3 V10 3 V7 4 圖14.1直觀上我們有這樣一個(gè)重要常識(shí)：如果由起點(diǎn)經(jīng)過點(diǎn)和點(diǎn)而到達(dá)終

5、點(diǎn)是一條最短路線，則由點(diǎn)出發(fā)經(jīng)過點(diǎn)到達(dá)終點(diǎn)的這條路線，對于從點(diǎn)出發(fā) 到達(dá)終點(diǎn)的所有可能選擇的不同路線來說，必定也是最短路線。例如在最短路線問題中，若找到了是由點(diǎn)到點(diǎn)最短路線，則應(yīng)該是由點(diǎn)出發(fā)到達(dá)終點(diǎn)的所有可能選擇的不同路線中最短路線。這一特征即為上面所提到的最優(yōu)性原理：最優(yōu)性決策的任何截?cái)嗳允亲顑?yōu)的，這是動(dòng)態(tài)規(guī)劃的基本原理。根據(jù)最優(yōu)性原理，尋找最短路線可從最后一段開始，用由后向前逐步遞推的方法，求出各點(diǎn)到點(diǎn)的最短路線，最后求得由點(diǎn)到點(diǎn)的最短路線，所以動(dòng)態(tài)規(guī)劃的逆序求解方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方法。下面逐段完成計(jì)算。例1當(dāng)然可以用圖與網(wǎng)絡(luò)實(shí)驗(yàn)中介紹的Dijkstra算法來求解

6、，但這里我們將把該問題看成6個(gè)階段的決策過程，并逆序逐段求解，從而較直觀地揭示動(dòng)態(tài)規(guī)劃的基本思想。時(shí)，以表示由到的最短距離，以表示由到的最短距離，則，。時(shí)，出發(fā)點(diǎn)有三個(gè)、和。若從出發(fā)有和兩個(gè)選擇，以表示由到的最短距離，表示由到的距離，表示由到的距離，表示相應(yīng)的選擇或決策，則：可見，其最短路徑為。同理，從出發(fā)也有和兩個(gè)選擇，、和意義與上面相似，則：可見，其最短路徑為。從出發(fā)，同樣有：可見，其最短路徑為。時(shí)，有三個(gè)出發(fā)點(diǎn)、和，同樣計(jì)算如下：可見，其最短路徑為?？梢姡渥疃搪窂綖椤？梢?，其最短路徑為。時(shí)，同樣計(jì)算有：，；，；，時(shí)，同樣計(jì)算有：，；，時(shí)，只有一個(gè)出發(fā)點(diǎn)，則：可見，所以本題的最短路徑為。

7、14.2.2 動(dòng)態(tài)規(guī)劃的基本概念及其數(shù)學(xué)描述（1）階段 整個(gè)問題的解決可分為若干個(gè)相互聯(lián)系的階段依次進(jìn)行。通常按時(shí)間或空間劃分階段，描述階段的變量稱為階段變量，計(jì)為。（2）狀態(tài) 狀態(tài)表示每個(gè)階段開始所處的自然狀況或客觀條件，它描述了研究問題過程的狀況。個(gè)階段的狀態(tài)通常用狀態(tài)變量描述。常用表示第階段的狀態(tài)變量。個(gè)階段的決策過程有個(gè)狀態(tài)。用規(guī)劃方法解決多階段決策問題時(shí)，要求整個(gè)過程具有無后效性，即：如果某階段的狀態(tài)給定，則此階段以后過程的發(fā)展不受以前狀態(tài)的影響，未來狀態(tài)只依賴于當(dāng)前狀態(tài)。（3）決策 某一階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段某一狀態(tài)，這種選擇手段稱為決策。描述決策的變

8、量稱為決策變量。決策變量限制的取值范圍稱為允許決策集合。用表示第階段處于狀態(tài)時(shí)的決策變量，它是的函數(shù)，用表示的允許決策的集合。比如在例1中，。（4）策略 一個(gè)由每個(gè)階段的決策按順序排列組組成的集合稱為策略，用表示。即。由第階段的狀態(tài)開始到終止?fàn)顟B(tài)的后部子過程的策略記為，即。在實(shí)際問題中，可供選擇的策略有一定范圍，此范圍稱為允許策略集合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程 如果第個(gè)階段狀態(tài)變量為，作出的決策，那么第階段的狀態(tài)變量也被完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，寫作。（6）指標(biāo)函數(shù)和最優(yōu)值函數(shù) 指標(biāo)函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生結(jié)果的數(shù)量表示，是用來衡量策

9、略優(yōu)劣的數(shù)量指標(biāo)，它定義在全過程和所有后部子過程上，分別用和表示。即和。過程在某個(gè)階段的階段指標(biāo)函數(shù)（或階段效益）是衡量該階段決策優(yōu)劣的數(shù)量指標(biāo)，它取決于狀態(tài)和決策，用表示。如例1中兩頂點(diǎn)間的距離是階段指標(biāo)函數(shù)，而指標(biāo)函數(shù)則是直到終點(diǎn)的距離的和。根據(jù)不同的實(shí)際問題，效益可以是利潤、距離、產(chǎn)量或資源等。指標(biāo)函數(shù)往往是各階段效益的某種形式。指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)函數(shù)。（7）最優(yōu)策略和最優(yōu)軌線 使指標(biāo)函數(shù)達(dá)到最優(yōu)值的策略是從階段開始的后部子過程的最優(yōu)策略，記為。是全過程的最優(yōu)策略，簡稱為最優(yōu)策略。從初始狀態(tài)出發(fā)，過程按照和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列稱為最優(yōu)軌線。14.3 動(dòng)態(tài)規(guī)劃逆序算法的M

10、ATLAB程序14.3.1逆序算法的基本方程由例1的求解過程可以看出下面的方程在動(dòng)態(tài)規(guī)劃逆序求解中起著本質(zhì)的作用稱此為動(dòng)態(tài)規(guī)劃逆序求解的基本方程?？梢园呀?dòng)態(tài)規(guī)劃模型歸納成以下幾個(gè)步驟（1）將問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)階段；（2）正確選擇狀態(tài)變量，使它既能描述過程的演變，又滿足無后效性；（3）規(guī)定決策變量，確定每個(gè)階段允許決策集合；（4）寫出狀態(tài)轉(zhuǎn)移方程；（5）確定個(gè)階段各種決策的階段指標(biāo)，列出計(jì)算各階段最優(yōu)后部策略指標(biāo)的基本方程。14.3.2動(dòng)態(tài)規(guī)劃逆序算法的MATLAB程序Dynprog.m%M函數(shù)dynprog.mfunctionp_opt,fval=dynprog(x,DecisFun,

11、ObjFun,TransFun)% p_opt,fval =dynprog(x,DecisFun,ObjFun,TransFun)% 自由始端和終端的動(dòng)態(tài)規(guī)劃，求指標(biāo)函數(shù)最小值的逆序算法遞歸計(jì)算程序。x是狀態(tài)變量，一列代表一個(gè)階段狀態(tài)；% M函數(shù)DecisFun（k,x）由階段k的狀態(tài)變量x求出相應(yīng)的允許決策變量；% M函數(shù)ObjFun(k,x,u)是階段指標(biāo)函數(shù)，M函數(shù)TransFun(k,x,u)是狀態(tài)轉(zhuǎn)移函數(shù)，其中x 是階段k的某狀態(tài)變量，u是相應(yīng)的決策變量；% 輸出p_opt由4列構(gòu)成，p_opt=序號(hào)組；最優(yōu)軌線組；最優(yōu)策略組；% 指標(biāo)函數(shù)組;fval是一個(gè)列向量，各元素分別表示p_

12、opt各最優(yōu)策略組對應(yīng)始端狀態(tài)x的最優(yōu)函數(shù)組；k=length(x(1,:); f_opt=nan*ones(size(x); d_opt=f_opt;t_vubm=inf*ones(size(x); x_isnan=isnan(x); t_vub=inf;% 計(jì)算終端相關(guān)值tmpl=find(x_isnan(:,k);tmp2=length(tmpl);for I=1:tmp2 u=feval(DecisFun,k,x(i,k); tmp3=length(u); for j=1:tmp3 tmp=feval(ObjFun,k,x(tmpl(i),k), u(j); if tmp<=t_

13、vub, f_opt(i,k)=tmp; d_opt(i,k)=u(j); t_vub=tmp;end;end;end%逆推計(jì)算各階段的遞歸調(diào)用程序for ii=k-1:-1:1 tmp10=find(x_isnan(:,ii);tmp20=length(tmp10); for i=1:tmp20 u=feval(DecisFun,ii,x(i,ii);tmp30=length(u); for j=1:tmp30 tmp00=feval(ObjFun,ii,x(tmp10(i),ii),u(j); tmp40=feval(TransFun,ii,x(tmp10(i),ii),u(j); tmp

14、50=x(:,ii+1)-tmp40; tmp60=find(tmp50= =0); ifisempty(tmp60), tmp00=tmp00+f_opt(tmp60(1),ii+1); if tmp00<=t_vubm(i,ii) f_opt(i,ii)=tmp00; d_opt(i,ii)=u(j); t_vubm(i,ii)=tmp00;end;end;end;end;end;fval=f_opt(tmp1,1);% 記錄最優(yōu)決策、最優(yōu)軌線和相應(yīng)指標(biāo)函數(shù)值p_opt=;tmpx=;tmpd=;tmpf=;tmp0=find(x_isnan(;,1);tmp01=length(tm

15、p0);for i=1:tmp01, tmpd(i)=d_opt(tmp0(i),1); tmpx(i)=x(tmp0(i),1); tmpf(i)=feval(ObjFun,1,tmpx(i),tmpd(i); p_opt(k*(I-1)+1,1,2,3,4)=1,tmpx(i),tmpd(i),tmpf(i); for ii=2:k tmpx(i)=feval(TransFun,ii-1,tmpx(i),tmpd(i); tmp1=x(:,ii)-tmpx(i); tmp2=find(tmp1= =0); ifisempty(tmp2) tmpd(i)=d_opt(tmp2(1),ii);

16、 end; tmpf(i)=feval(ObjFun,ii,tmpx(i),tmpd(i); p_opt(k*(i-1)+ii,1,2,3,4)=ii,tmpx(i),tmpd(i),tmpf(i);end;end;14.4 例題下面將就動(dòng)態(tài)規(guī)劃的幾個(gè)典型應(yīng)用問題分別舉例計(jì)算。例2：（生產(chǎn)計(jì)劃制定）解：這是一個(gè)4階段動(dòng)態(tài)規(guī)劃問題。如果用逆序法解題，第1階段是1月份，第4階段是4月份。記第階段開始的產(chǎn)品存儲(chǔ)數(shù)（狀態(tài)變量）；第階段的產(chǎn)量（決策變量）；第階段每件產(chǎn)品的生產(chǎn)成本；第階段的需求量；階段指標(biāo)的函數(shù)為：；狀態(tài)轉(zhuǎn)移方程為：；基本方程為：對于本例的問題（1）：一月初無存貨，可首先分析出各月的最大

17、存貨量和產(chǎn)量。如對4月初，前三個(gè)月的最大產(chǎn)量為300件（每月最大產(chǎn)量為100件），實(shí)際需求量為60+70+120=250（件）。所以四月初的最大存儲(chǔ)量為300-250=50（件）因產(chǎn)量限制為10的倍數(shù)，4月初的存貨量只可能是0、10、20、30、40、50、這六種。而4月份的實(shí)際需要量為60件，因此第一階段的產(chǎn)量（決策）相應(yīng)為60、50、40、30、20、10，進(jìn)而計(jì)算，再分析3月初情況等等，如此可仿例1逐段手工計(jì)算求出最優(yōu)決策。下面將調(diào)用參考程序dynprog.m進(jìn)行計(jì)算。由于計(jì)算機(jī)的優(yōu)勢，這里將就1月初存貨分別為0、10、20、30、40、50、60的所有可能情況進(jìn)行計(jì)算。把此問題作為自由

18、始端動(dòng)態(tài)規(guī)劃考慮，此時(shí)個(gè)階段的最大存貨出現(xiàn)在時(shí)，經(jīng)分析可知，考慮到產(chǎn)量是10的倍數(shù)，根據(jù)上面所述的階段指標(biāo)函數(shù)、狀態(tài)轉(zhuǎn)移方程和基本方程，寫出下面的3個(gè)M函數(shù)以備計(jì)算時(shí)調(diào)用，函數(shù)意義見函數(shù)的說明部分。%M函數(shù)eg13f1_2.mfunction u=DecisF_1(k,x)% 在階段k由狀態(tài)變量x的值求出相應(yīng)的決策變量所有的取值c=70,72,80,76;q=10*6,7,12,6;if q(k)-x<0,u=0:100; %決策變量不能取為負(fù)值else,u=q(k)-x:100;end; % 產(chǎn)量滿足需求且不超過100u=u(:);%M函數(shù)eg13f2_2.mfunction v=Ob

19、jF_1(k,x,u)% 階段k的指標(biāo)函數(shù)c=70,72.80,76;v=c(k)*u+2*x;%M函數(shù)eg13f3_2.mfunction y=TransF_1(k,x,u)% 狀態(tài)轉(zhuǎn)移方程q=10*6,7,12,6;y=x+u-q(k); 調(diào)用dynprog.m計(jì)算如下>>clear;x=nan*ones(14,4); %x是10的倍數(shù)，最大范圍,% 因此x=0,1,，13,所以x初始化取14行，nan表示無意義元素>>x(1:7,1)=10*(0:6); %按月定義x的可能取值>>x(1:11,2)=10*(0:10); x(1:12,3)=10*(2

20、:13);>>x(1:7,4)=10*(0:6);>>p,f=dynprog(x,eg13f1_2,eg13f2_2,eg13f3_2)p= %輸出結(jié)果1 0 100 70002 40 100 72803 70 50 41404 0 60 45601 10 100 7020 2 50 100 73003 80 40 33604 0 60 45601 20 100 70402 60 100 73203 90 30 25804 0 60 45601 30 100 70602 70 100 73403 100 20 18004 0 60 45601 40 100 7080 2

21、 80 100 73603 110 10 10204 0 60 45601 50 100 71002 90 100 73803 120 0 2404 0 60 45601 60 100 71202 100 100 74003 130 0 2604 10 50 3820f=22980222402150020760200201928018600由p 第一和第三個(gè)4行可以看出一月初無存貨和有存貨20件的最優(yōu)決策，現(xiàn)將其列成下表，以供對比理解。表14.31月初的存貨量階段序號(hào)最優(yōu)軌線(存儲(chǔ)量)最優(yōu)決策(產(chǎn)量)階段指標(biāo)函數(shù)值(成本)0(件)10100700024010072803705041404060

22、456020(件)1201007040260100732039030258040604560由f的第1、3行可以看出對應(yīng)四個(gè)月的總成本分別為22980和21500。例3：調(diào)用dymprog.m計(jì)算例1中網(wǎng)絡(luò)的最短路徑。解：首先編寫3個(gè)M函數(shù)。以供計(jì)算時(shí)調(diào)用。由表1可知狀態(tài)變量有7個(gè)，并可寫出下面的函數(shù)。%M函數(shù)eg13f1_3.mfunction u=eg13f1_3(k,x)% 在階段k由狀態(tài)變量x的值求出其相應(yīng)的決策變量所有的取值% 這里求出了所有狀態(tài)x對應(yīng)的決策變量值uif x= =1,u=2;3;elseif x= =2,u=4;5;6;elseif x= =3,u=5;6;7;els

23、eif(x= =4)|(x= =5),u=8;9;elseif(x= =6)|(x= =7),u=9;10; elseif x= =8,u=11,12;elseif(x= =9)|(x= =10),u=12;13;elseif(x= =11)|(x= =12)|(x= =13),u=14,15;elseif(x= =14)|(x= =15),u=16;elseif x= =16,u=16;end %M函數(shù)eg13f2_3.mfunction v=eg13f2_3(k,x,u)% 各階段指標(biāo)函數(shù)值，如x=1,u=2時(shí)v=5。tt=5;3;1;3;6;8;7;6;6;8;3;5;3;3;8;4;2

24、;2;1;2;3;3;3;3;5;5;2;6;6;4;3;tmp=x= =1&u= =2,x= =1&u= =3,x= =2&u= =4,x= =2&u= =5,x= =2&u= =6, x= =3&u= =5, x= =3&u= =6, x= =3&u= =7,x= =4&u= =8, x= =4&u= =9, x= =5&u= =8, x= =5&u= =9,x= =6&u= =9,x= =6&u= =10, x= =7&u= =9, x= =7&u= =10,x

25、= =8&u= =11, x= =8&u= =12, x= =9&u= =12, x= =9&u= =13,x= =10&u= =12, x= =10&u= =13, x= =11&u= =14, x= =11&u= =15,x= =12&u= =14, x= =12&u= =15, x= =13&u= =14, x= =13&u= =15,x= =14&u= =16, x= =15&u= =16;v=tmp*tt;%M函數(shù)eg13f3_3.mfunction y= eg13f3_3

26、(k,x,u)y=u; %狀態(tài)轉(zhuǎn)移方程計(jì)算如下：>>clear; x=nan*ones(4,7); % 初始化，nan為無意義元素 % 7個(gè)狀態(tài)變量，每個(gè)最多4種取值>>x(1,1)=1;x(1:2,2)=2;3; %逐列定義x,其值為頂點(diǎn)的序號(hào)>>x(1:4,3)=(4:7);x(1:3,4)=(8:10);x(1:3,5)=(11:13);>>x(1:2,6)=14;15; x(1,7)=16;>>p,f=dynprog(x,eg13f1_3,eg13f2_3, eg13f3_3)p= %輸出結(jié)果 1 1 2 52 2 5 33

27、5 8 34 8 12 25 12 15 2 6 15 16 37 16 16 0f=18 %最短路徑距離可見最短路徑按頂點(diǎn)序號(hào)為1 2 5 8 12 15 16。例4：某工業(yè)部門根據(jù)國家計(jì)劃的安排，擬將5臺(tái)某種高效率的設(shè)備，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國家提供的盈利如下面的表。問：這5臺(tái)設(shè)備如何分配給各工廠才能使國家得到的盈利最大？解：將問題按工廠分為三個(gè)階段，甲、乙和丙3個(gè)工廠分別編號(hào)為1、2和3。設(shè)狀態(tài)變量表示分配給第個(gè)工廠至第個(gè)工廠的設(shè)備臺(tái)數(shù)。決策變量表示分配給第個(gè)工廠的設(shè)備臺(tái)數(shù)。則狀態(tài)轉(zhuǎn)移方程為分配給第個(gè)工廠至第個(gè)工廠的設(shè)備臺(tái)數(shù)。階段指標(biāo)函數(shù)表示臺(tái)設(shè)備分配到第個(gè)工廠所獲得的盈利值。表示臺(tái)設(shè)備分配給第個(gè)工廠至第個(gè)工廠所獲得的最大盈利值。則基本方程為表14.4設(shè)備數(shù)甲乙丙000013542710639111141211125131112利用計(jì)算機(jī)計(jì)算的優(yōu)勢，可根據(jù)上表將本問題視為自由始端，即初始狀態(tài)的動(dòng)態(tài)規(guī)劃問題求解。由此可以寫出下面3個(gè)M函數(shù)，以供計(jì)算時(shí)調(diào)用。%M函數(shù)eg13f1_4.