運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃應(yīng)用舉例教學(xué)課件

第九章動(dòng)態(tài)規(guī)劃應(yīng)用舉傷s1資源分配問(wèn)題將一定的資源(原料,資金,機(jī)器設(shè)備等)恰當(dāng)?shù)姆峙浣o若干使用者,使總的目標(biāo)函數(shù)值為最優(yōu)。屬靜態(tài)規(guī)劃問(wèn)題,人為的引入階段因素。1.1一維資源分配問(wèn)題靜態(tài)規(guī)劃模型Mxz=81(x1)+2(x2)+8+x+耳1≥0i=1,2,…,n原料總數(shù)為a,用于生產(chǎn)n種產(chǎn)品,x為分配生產(chǎn)第i種產(chǎn)品的原料數(shù)量,收益為g1(x如何分配收益最大將n種產(chǎn)品(使用資源的對(duì)象、用戶)劃分為n個(gè)階段狀態(tài)變量s;分配給生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的原料數(shù)量;決策變量x(a:分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)量;狀態(tài)轉(zhuǎn)移方程狀態(tài)允許集合(約束條件):0<sa,sr=a決策允許集合:0<x≤Sk,xn=Sn動(dòng)態(tài)規(guī)劃遞推關(guān)系(s)=mNx{g(x)+f1(-x)}fn+(Sn+1)=0f(s)最大收益例5臺(tái)設(shè)備,3個(gè)工廠,可提供的盈利見(jiàn)下表,如何分配使利潤(rùn)最大?解甲,乙,丙三個(gè)工廠分別編號(hào)為1,2,3設(shè)x分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。甲乙丙設(shè)備臺(tái)數(shù)7639111212靜態(tài)規(guī)劃模型MaxZ=p,(x,)+p2(x2)+p3(xy)≥0整數(shù)p(x)xk臺(tái)設(shè)備分配到第k個(gè)工廠的盈利數(shù)資源分配問(wèn)題的階段劃分原則有幾個(gè)用戶就把問(wèn)題分成幾個(gè)階段。本題按工廠的個(gè)數(shù),分為3個(gè)階段分析:k=3,把第3階段初所擁有的所有設(shè)備全部分給工廠3(單一用戶分配);k=2,把第2階段初所擁有的所有設(shè)備全部分給工廠2和工廠3(2個(gè)用戶分配);k=1,把第1階段初所擁有的5臺(tái)設(shè)備全部分給工廠1,工廠2和工廠3(3個(gè)用戶分配)狀態(tài)變量:分配給第k個(gè)工廠至第3個(gè)工廠的設(shè)備臺(tái)數(shù);0≤s<5,sn=5決策變量x:分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù);0狀態(tài)轉(zhuǎn)移方程:S1=SxhS1分配給第k+個(gè)工廠至第3個(gè)工廠的設(shè)備臺(tái)數(shù)最優(yōu)值函數(shù)fk(sk)s臺(tái)設(shè)備分配給第k個(gè)工廠至第3個(gè)工廠的最大盈利值。遞推基本方程f()=mx{p(x)+f(5)}f4(S4)=0k=30<s<5s取值范圍=0,1,2,3,4,5x取值范圍將x的值逐個(gè)代入基本方程,計(jì)算結(jié)果填入表中f3(s3)=mx[p3(x3)+f4(S)]=mxp2(x)13=S323000S0461112122k=20≤s2≤5,s2取值范圍S2=0,1,2,3,4,5對(duì)s2的每取值,確定x2取值范圍0≤x2≤S2根據(jù)狀態(tài)轉(zhuǎn)移方程S3=,確定S0=2x2=01,2=2,1,0S2=3,x2=0,L,