西安電子科技大學(xué)數(shù)學(xué)建模講義第八講省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

主講人:穆學(xué)文西安電子科技大學(xué)數(shù)學(xué)系Email:mxw1334@126.com數(shù)學(xué)建模講義第1頁(yè)數(shù)學(xué)建模專(zhuān)題講座最優(yōu)化模型

---動(dòng)態(tài)規(guī)劃第2頁(yè)動(dòng)態(tài)規(guī)劃

1動(dòng)態(tài)規(guī)劃基本概念和方法基本概念與名詞解釋最優(yōu)化原理與動(dòng)態(tài)規(guī)劃基本方法2動(dòng)態(tài)規(guī)劃模型建立與求解步驟建立動(dòng)態(tài)規(guī)劃模型基本要求動(dòng)態(tài)規(guī)劃求解步驟

3動(dòng)態(tài)規(guī)劃應(yīng)用舉例定價(jià)問(wèn)題資源分配問(wèn)題生產(chǎn)存放問(wèn)題第3頁(yè)第一節(jié)動(dòng)態(tài)規(guī)劃基本概念與方法1動(dòng)態(tài)規(guī)劃基本概念一、動(dòng)態(tài)決議問(wèn)題：決議過(guò)程含有階段性和時(shí)序性(與時(shí)間相關(guān))決議問(wèn)題。即決議過(guò)程可劃分為顯著階段。二、什么叫動(dòng)態(tài)規(guī)劃(D.P.–DynamicProgram)：多階段決議問(wèn)題最優(yōu)化一個(gè)方法。廣泛應(yīng)用于工業(yè)技術(shù)、生產(chǎn)管理、企業(yè)管理、經(jīng)濟(jì)、軍事等領(lǐng)域。三、動(dòng)態(tài)規(guī)劃(D.P.)起源：

1951年,美國(guó)數(shù)學(xué)家R.Bellman(貝爾曼)等人提出最優(yōu)化原理，從而建立動(dòng)態(tài)規(guī)劃，他名著《動(dòng)態(tài)規(guī)劃》于1957年出版。第4頁(yè)四、動(dòng)態(tài)決議問(wèn)題分類(lèi)：1、按數(shù)據(jù)給出形式分為：

離散型動(dòng)態(tài)決議問(wèn)題。

連續(xù)型動(dòng)態(tài)決議問(wèn)題。2、按決議過(guò)程演變性質(zhì)分為：

確定型動(dòng)態(tài)決議問(wèn)題。

隨機(jī)型動(dòng)態(tài)決議問(wèn)題。第5頁(yè)名詞解釋例1某企業(yè)欲將一批貨物從城市A運(yùn)到城市E去，如圖所表示，走哪條路線最好？第6頁(yè)1、階段(stage)k：把所給問(wèn)題過(guò)程，恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)絡(luò)階段。描述階段變量稱(chēng)為階段變量，慣用k表示。k=1、2、3、4。2、狀態(tài)(state)Sk：狀態(tài)表示每個(gè)階段開(kāi)始所處狀態(tài),即是每一階段出發(fā)位置.階段起點(diǎn).通常一個(gè)階段有多個(gè)狀態(tài).記為Sk.

S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3},S4={D1,D2}。第7頁(yè)3、決議(decision)uk(sk)：從一個(gè)階段某狀態(tài)演變到下一個(gè)階段某狀態(tài)選擇.慣用uk(sk)表示第k階段當(dāng)狀態(tài)處于sk時(shí)決議變量.決議集用Dn(Sk)表示.就是階段終點(diǎn).D1(S1)={u1(A)}={B1,B2,B3}=S2，D2(S2)={U2(B1),U2(B2),U2(B3)}={C1,C2;C1,C2,C3;C2,C3}={C1,C2,C3}=S3，D3(S3)={U3(C1),U3(C2),U3(C3)}={D1,D2;D1,D2,D3;D1,D2,D3}={D1,D2,D3}=S4，D4(S4)={U4(D1),U4(D2),U4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5，D5(S5)={X5(E1),X5(E2)}={F;F}={F}。第8頁(yè)4、策略(policy)：全過(guò)程中各個(gè)階段決議Un組成有序總體{Un}.如A

B2

C1

D1

E5、子策略(sub-policy)

：剩下M個(gè)階段組成M子過(guò)程,對(duì)應(yīng)決議系列叫M子策略.如C1

D1

E6、狀態(tài)轉(zhuǎn)移方程：前一階段終點(diǎn)(決議)是后前一階段起點(diǎn)(狀態(tài)).Uk=Sk+17、指標(biāo)函數(shù)：各個(gè)階段數(shù)量指標(biāo),記為Vk,n(sk,Uk).如上例中,用dk(sk,Uk)表示距離.d2(B3,C2)=8,d3(C2,D2)=2等.8、目標(biāo)函數(shù):策略數(shù)量指標(biāo)值,記為Z=opt[v1(s1,u1)*…*vn(sn,un)].其中：opt為max或min，*為運(yùn)算符號(hào).如上例中，Z=min[d1(s1,u1)+…+dn(sn,un)]=min[d1+d2+…+

dn]第9頁(yè)一、R.Bellman最優(yōu)化原理：作為整個(gè)過(guò)程最優(yōu)策略，不論過(guò)去狀態(tài)和決議怎樣，對(duì)前面決議形成狀態(tài)而言，余下諸決議必組成最優(yōu)策略。即：若M是從A到B最優(yōu)路線上任一點(diǎn)，則從M到B路線也是最優(yōu)路線。A

MB最優(yōu)化原理第10頁(yè)二、指標(biāo)遞推方程：

fn*(Sn)=opt[vn(sn,un)*vn(sn,un)],xn∈Dn(Sn)如上例：fn*(Sn)=min[vn(sn,un)+fn+1*(Sn+1)],n=3、2、1xn∈Dn(Sn)f4*(S4)=min[v4(s4,u4)]x4∈D4(S4)三、求解過(guò)程：

用反向嵌套遞推法：從最終一個(gè)階段開(kāi)始，依次對(duì)各子過(guò)程尋優(yōu)，直至取得全過(guò)程最優(yōu)，形成最優(yōu)策略，取得最優(yōu)策略指標(biāo)值。第11頁(yè)一、建立動(dòng)態(tài)規(guī)劃模型基本要求將問(wèn)題劃分成若干階段。有問(wèn)題階段性很顯著，有則不顯著，需要分析后人為假設(shè)。確定各階段狀態(tài)變量，并給出狀態(tài)轉(zhuǎn)移方程，狀態(tài)轉(zhuǎn)移方程形式應(yīng)該與遞推次序一致。狀態(tài)變量應(yīng)該滿(mǎn)足無(wú)后效性要求。明確指標(biāo)函數(shù)，給出最優(yōu)函數(shù)遞推方程，遞推方程形式應(yīng)該與遞推次序一致。第12頁(yè)二、動(dòng)態(tài)規(guī)劃求解步驟正確劃分階段。確定狀態(tài)變量和決議變量，并給出狀態(tài)變量和決議變量可行集合。確定求解遞推次序，給出狀態(tài)轉(zhuǎn)移方程。確定階段、子過(guò)程(子策略)指標(biāo)函數(shù)，確定最優(yōu)值函數(shù)遞推方程和邊界條件。遞推求解。與遞推過(guò)程反向求出最優(yōu)策略(最優(yōu)決議變量值系列)和最優(yōu)狀態(tài)改變路線。第13頁(yè)例2：求以下圖中A到F最短路線及最短路線值。AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514第14頁(yè)AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、階段(stage)n：n=1、2、3、4、5。2、狀態(tài)(state)Sn：

S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。3、決議(decision)Xn：決議集Dn(Sn)。D1(S1)={X1(A)}={B1,B2,B3}=S2，D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2;C1,C2,C3;C2,C3}={C1,C2,C3}=S3，D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2;D1,D2,D3;D1,D2,D3}={D1,D2,D3}=S4，D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5，D5(S5)={X5(E1),X(E2)}={F;F}={F}。第15頁(yè)AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144、狀態(tài)轉(zhuǎn)移方程：Xn=Sn+15、指標(biāo)函數(shù)(距離)：dn(sn,xn).d2(B3,C2)=1,d3(C2,D3)=6等。6、指標(biāo)遞推方程：fn*(Sn)=min[dn(sn,Xn)+fn+1*(Sn+1)]，n=4、3、2、1Un∈Dn(Sn)f5*(S5)=min[V5(s5,X5)]X5∈D5(S5)第16頁(yè)AB1B2B3C1C2C3D1D2D3E1E2F3549543517158464422269751411F22F4+1=52+2=44E26+1=79+2=117E17+1=85+2=77E2第17頁(yè)AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141+4=55+7=12///5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16///14C14+5=93+11=145+8=139C1///1+11=127+8=1512C2第18頁(yè)AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143+14=175+9=144+12=1614B2最短路線值為：f1*(s1)=14最短路線求解以下：第19頁(yè)11F22F4+1=52+2=44E26+1=79+2=117E17+1=85+2=77E21+4=55+7=12///5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16///14C14+5=93+11=145+8=139C1///1+11=127+8=1512C23+14=175+9=144+12=1614B2第20頁(yè)AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即：A

B2

C1

D1

E2

F

第21頁(yè)第三節(jié)動(dòng)態(tài)規(guī)劃應(yīng)用舉例定價(jià)問(wèn)題資源分配問(wèn)題生產(chǎn)存放問(wèn)題第22頁(yè)一、定價(jià)問(wèn)題某企業(yè)考慮為某新產(chǎn)品定價(jià)，該產(chǎn)品單價(jià)擬從每件5元、6元、7元和8元這四個(gè)中選取一個(gè)，每年允許價(jià)格有1元幅度變動(dòng)，該產(chǎn)品預(yù)計(jì)暢銷(xiāo)五年，據(jù)預(yù)測(cè)不一樣價(jià)格下各年利潤(rùn)如表3-1所表示。表3-2每年預(yù)計(jì)利潤(rùn)額單價(jià)第一年第二年第三年第四年第五年5元6元7元8元1012141612131415151616152020181425241814第23頁(yè)建立數(shù)學(xué)模型按年劃分階段，k=1,2,...,5每階段狀態(tài)變量為本年(上一年已確定)價(jià)格，狀態(tài)變量可行集合Sk=(5,6,7,8)。決議變量為每年依據(jù)當(dāng)年價(jià)格為下一年度決定價(jià)格，依據(jù)題意決議變量可行集合是：采取逆序算法，所以狀態(tài)轉(zhuǎn)移方程是最優(yōu)值函數(shù)遞推方程為第24頁(yè)進(jìn)行各階段計(jì)算采取逆序法，設(shè)當(dāng)k=5時(shí)，S5=(5,6,7,8)，由表3-1得到當(dāng)k=4時(shí)，S4=(5,6,7,8)，由遞推方程得第25頁(yè)繼續(xù)求解同理得其它各階段最優(yōu)解第26頁(yè)反推得最優(yōu)路線按照與求最優(yōu)值函數(shù)方向相反次序求最優(yōu)狀態(tài)路線：最優(yōu)決議變量。即從第一年單價(jià)應(yīng)為8元開(kāi)始，向后推算。得第二年定價(jià)8元，第三年定價(jià)7元，第四年定價(jià)6元，第五年定價(jià)5元。最大利潤(rùn)值為92萬(wàn)元。第27頁(yè)也可用決議圖求解第28頁(yè)二、資源分配問(wèn)題某企業(yè)將5臺(tái)加工中心分配給甲、乙、丙、丁四個(gè)工廠，各工廠利用設(shè)備后可產(chǎn)生如表3-2所表示利潤(rùn)，應(yīng)怎么分配設(shè)備可使企業(yè)總利潤(rùn)最大？工廠設(shè)備數(shù)甲乙丙丁012345067101215037912130510111111046111212第29頁(yè)建立數(shù)學(xué)模型按工廠次序劃分階段，k=1，2，3，4狀態(tài)變量為各階段可用于分配設(shè)備總臺(tái)數(shù)決議變量是分配給第k工廠設(shè)備數(shù)采取逆序算法，狀態(tài)轉(zhuǎn)移方程最優(yōu)值函數(shù)遞推方程第30頁(yè)第4階段最優(yōu)解當(dāng)k=4時(shí)，S4=(0,1,2,3,4,5)012345012345046111212046111212012345第31頁(yè)第3階段最優(yōu)解當(dāng)k=3時(shí)，S3=(0,1,2)000000010105404551201205106406910102第32頁(yè)第3階段最優(yōu)解（續(xù)）當(dāng)k=3時(shí)，S3=3301230510111164011111411142第33頁(yè)第3階段最優(yōu)解（續(xù)）當(dāng)k=3時(shí)，S3=44012340510111112116401216161511161，2第34頁(yè)第3階段最優(yōu)解（續(xù)）當(dāng)k=3時(shí)，S3=550123450510111111121211640121721171511212第35頁(yè)第2階段最優(yōu)解當(dāng)k=2時(shí)，S2=(0,1,2)000000010103505350201203710501087100第36頁(yè)第2階段最優(yōu)解（續(xù)）k=2時(shí)，S2=33012303791410501413129140第37頁(yè)第2階段最優(yōu)解（續(xù)）當(dāng)k=2時(shí)，S2=4401234037912161410501617171412171，2第38頁(yè)第2階段最優(yōu)解（續(xù)）當(dāng)k=2時(shí)，S2=55012345037912132116141050211921191715210，2第39頁(yè)第1階段最優(yōu)解（續(xù)）當(dāng)k=1時(shí)，S1=5

50123450671012152117141050212321201715231第40頁(yè)反向求最正確狀態(tài)路線方案一方案二工廠名分配設(shè)備數(shù)工廠名分配設(shè)備數(shù)甲乙丙丁1121甲乙丙丁1220第41頁(yè)三、生產(chǎn)存放問(wèn)題某企業(yè)生產(chǎn)并銷(xiāo)售某產(chǎn)品。依據(jù)市場(chǎng)預(yù)測(cè)，今后四個(gè)月市場(chǎng)需求量如表3-7所表示。時(shí)期（月）需求量（dk）12342324第42頁(yè)已知其它條件已知生產(chǎn)一件產(chǎn)品成本是1千元，每批產(chǎn)品生產(chǎn)準(zhǔn)備成本是3千元，每個(gè)月僅能生產(chǎn)一批，每批6件。每件存放成本為0.5千元，且第一個(gè)月初無(wú)存貨，第四個(gè)月末存貨要求為零。求最優(yōu)生產(chǎn)計(jì)劃。設(shè)第k月生產(chǎn)量uk，存放量為Sk,則總成本為第43頁(yè)建立數(shù)學(xué)模型以月劃分階段，k=1,2,3,4各階段決議變量為該階段生產(chǎn)量uk，狀態(tài)變量為該階段存放量Sk。采取逆序算法，則狀態(tài)轉(zhuǎn)移方程為最低成本遞推公式是第44頁(yè)第四階段最優(yōu)解當(dāng)k=4時(shí)，d4=4,因第四階段末無(wú)存貨，所以S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生產(chǎn)存放01234432107654000.511.5276.565.52000000000076.565.52第45頁(yè)第三階段最優(yōu)解當(dāng)k=3時(shí)，因?yàn)椋业谌A段需求量d3=2，S3=(0,1,2,3,4,5,6)S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存放0234565678900000567890123476.565.521212.51313.511第46頁(yè)第三階段最優(yōu)解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存放112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第47頁(yè)第三階段最優(yōu)解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存放2012340456711111156780123476.565.52811.512.012.510.0第48頁(yè)第三階段最優(yōu)解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存放3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第49頁(yè)第三階段最優(yōu)解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存放501042.52.52.56.5345.5288.560033425第50頁(yè)第二階段最優(yōu)解當(dāng)k=2時(shí)，d2=3，因?yàn)樽畲笊a(chǎn)能力為6，而d1=2，所以S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存放03456678900006789012311.010.58.08.01717.51617第51頁(yè)第二階段最優(yōu)解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存放123456567890.50.50.50.50.55.56.57