十動態(tài)規(guī)劃的應用-資源分配問題

設有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi

用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)，問應如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？

資源分配問題1資源平行分配問題MaxZ=g1(x1)+g2(x2)++gn(xn)

s.t.

x1+x2+

+

xn=axi0i=1,2,

,n靜態(tài)規(guī)劃模型不考慮回收

例3

某公司擬將5臺某種設備分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設備，可以為公司提供的盈利如表。問：這五臺設備如何分配給各工廠，才能使公司得到的盈利最大。046111212051011111103791213012345丙乙甲工廠盈利設備臺數(shù)

甲乙丙012345037912130510111111046111212如何劃分階段s1的可達狀態(tài)集合s2的可達狀態(tài)集合s3的可達狀態(tài)集合決策變量uk(sk)0sk3個階段xk狀態(tài)轉移方程？甲乙丙012345037912130510111111046111212s1s2s3321x1x2x3基本方程?指標函數(shù)gk(xk)?s4解：將問題按工廠分為三個階段，甲、乙、丙分別編號為1，2，3。決策變量xk::

分配給生產(chǎn)第k

個工廠的設備數(shù)量

分配給第k個工廠至第3

個工廠的設備數(shù)量（第k階段開始剩余的設備數(shù)量）。狀態(tài)變量sk:甲乙丙012345037912130510111111046111212Dk(sk)={uk|0uk=

xksk}基本方程：數(shù)量為sk的設備分配給第k個工廠至第3個工廠所得到的最大總收益狀態(tài)轉移方程:sk+1=sk-

xkxk的取值范圍？甲乙丙012345037912130510111111046111212x3*(0)

=0x3*(1)

=1x3*(2)

=2x3*(3)

=3k=3，s3=0,1,2,3,4,5，0x3s3s3=0s3=3甲乙丙012345037912130510111111046111212046111212s3=2s3=1甲乙丙012345037912130510111111046111212x3*(5)

=4,5x3*(4)

=4046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5結果可寫成表格的形式:s3=4s3=5甲乙丙012345037912130510111111046111212

k=2，s3=s2-x2，s2=0,1,2,3,4,5，0x2s2，有x2*(0)

=0s2=0x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(1)

=1s2=1甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(2)

=2s2=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(3)

=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5s2=3甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(4)

=1,2s2=4s2=5甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(5)

=2結果列于下表：x2s2g2(x2)+f3(s2-x2)f2(s2)x*20123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+0051014162101221,22k=1時，s2=s1-x1，

s1=5，0x1s1，有x2s2f2(s2)x*2012345051014162101221,22x1*(5)

=0,2甲乙丙012345037912130510111111046111212結果可寫成表格的形式x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234550+213+167+149+1012+513+0210,2最優(yōu)分配方案一：由x1*=0，根據(jù)s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。即得甲工廠分配0臺，乙工廠分配2臺，丙工廠分配3臺。最優(yōu)分配方案？

最優(yōu)分配方案二：由x1*=2，根據(jù)s2=s1-x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工廠分配2臺，乙工廠分配2臺，丙工廠分配1臺。以上兩個分配方案所得到的總盈利均為21萬元。問題：如果原設備臺數(shù)是4臺，求最優(yōu)分配方案？如果原設備臺數(shù)是3臺，求最優(yōu)分配方案？設備臺數(shù)是4臺，x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234540+163+147+109+512+013+0171,2

最優(yōu)分配方案一：由x1*=1，根據(jù)s2=s1-x1*=4-1=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工廠分配1臺，乙工廠分配2臺，丙工廠分配1臺，總盈利為17萬元。

最優(yōu)分配方案二：由x1*=2，根據(jù)s2=s1-x1*=4-2=2，查表知x2*=2，由s3=s2-x2*=2-2=0，故x3*=s3=0。即得甲工廠分配2臺，乙工廠分配2臺，丙工廠分配0臺，總盈利為17萬元。設備臺數(shù)是3臺，x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234530+143+107+59+012+013+0140

最優(yōu)分配方案一：由x1*=0，根據(jù)s2=s1-x1*=3-0=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工廠分配0臺，乙工廠分配2臺，丙工廠分配1臺，總盈利為14萬元。2資源連續(xù)分配問題A種生產(chǎn)數(shù)量u1投入收益g(u1)

年終資源回收率a

B種生產(chǎn)數(shù)量s1-u1收益h(s1-u1)年終資源回收率b資源數(shù)量s1第一年資源數(shù)量s2=au1+b(s1-u1)第二年

A種生產(chǎn)數(shù)量u2投入;收益g(u2);年終資源回收率aB種生產(chǎn)數(shù)量s2-u2;收益h(s2-u2);年終資源回收率b到n年

如此進行n年，如何確定投入A的資源量u1、…、un，使總收入最大？此問題的靜態(tài)規(guī)劃問題模型為：高負荷:產(chǎn)量函數(shù)g=8x，年完好率為a=0.7，機器例4機器負荷分配問題假定開始生產(chǎn)時完好機器的數(shù)量為1000臺。

低負荷:產(chǎn)量函數(shù)h=5y，年完好率為b=0.9。

試問每年如何安排機器在高低兩種負荷下的生產(chǎn)，可使5年內生產(chǎn)的產(chǎn)品總產(chǎn)量最高?投入生產(chǎn)的機器數(shù)量

狀態(tài)變量sk狀態(tài)轉移方程決策(變量)

uk第k年初擁有的完好機器臺數(shù)第k年高負荷下投入的機器數(shù)sk+1=auk+b(sk-

uk)=0.7uk+0.9(sk-uk)0uksk分析：第k年低負荷下投入的機器數(shù)sk–uk階段？動態(tài)規(guī)劃基本（遞推）方程？指標函數(shù)第k年度產(chǎn)量為fk(sk)=max{8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}0