2026/1/261資源分配問題生產(chǎn)與存貯問題設(shè)備更新問題動(dòng)態(tài)規(guī)劃應(yīng)用舉例/sundae_meng2026/1/26/sundae_meng26.3資源分配問題

6.3.1一維離散資源分配問題設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)問應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？

將數(shù)量一定的一種或若干種資源，恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，使目標(biāo)函數(shù)為最優(yōu)。MAX=g1(x1)+g2(x2)+‥‥+gn(xn)x1+x2+…+xn=axi≥0i=1,2,…,ns.t.2026/1/26/sundae_meng3決策集合：Dk(sk)={uk|0

uk=xk

sk}uk:分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)量，即uk=xk；sk:分配給用于生產(chǎn)第k種至第n種產(chǎn)品的原料數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk-uk=sk-xk最優(yōu)值函數(shù)fk(sk):數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收益，動(dòng)態(tài)規(guī)劃的遞推關(guān)系為：2026/1/26/sundae_meng4工業(yè)部擬將5臺(tái)某種設(shè)備分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備，可以為公司提供的盈利如表。

問：這五臺(tái)設(shè)備如何分配給各工廠，才能使公司得到的盈利最大。例1解：將問題按工廠分為三個(gè)階段，甲、乙、丙分別編號(hào)為1，2，3。逆推法﹗2026/1/26/sundae_meng5k=3時(shí)，0

s35，0

x3

s3可分配的機(jī)器數(shù)量分配的機(jī)器數(shù)量

sk+1=sk-uk=sk-xkf3(s3)=max﹝g3﹙x3﹚﹞0≤x3≤s3f4(s4)=0S3=?g3(0)g3(1)

=4x3*(1)=1=g3﹙0﹚=0S3=0,f3(0)=max｛g3﹙x3﹚+f4(s4)｝

0≤x3≤s3x3*(0)=0=max

x3=0,1S3=1,f3(1)=max｛g3﹙x3﹚+f4(s4)｝0≤x3≤s32026/1/26/sundae_meng62026/1/26/sundae_meng72026/1/26/sundae_meng8當(dāng)階段k=2時(shí)，s3=s2-x2，

0

s25，0

x2

s2，有2026/1/26/sundae_meng92026/1/26/sundae_meng102026/1/26/sundae_meng112026/1/26/sundae_meng12結(jié)果列于下表：f3(1-0)=f3(1)=4

f3(5-3)=f3(2)2026/1/26/sundae_meng13當(dāng)階段k=1時(shí)，s2=s1-x1，

s1=5，0x1s1，有S1=5,f1(S1)=max｛g1﹙x1﹚+f2(s2)｝0≤x1≤s1=max｛g1﹙x1﹚+f2(s1-x1)｝x1=0,1,2,3,4,5=maxg1(0)+f2(5)g1(1)+f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)+f2(1)g1(5)+f2(0)

x1*(5)=0,20+213+167+149+1012+513+0=

max2026/1/26/sundae_meng14結(jié)果可寫成表格的形式S2*=s1*-x1*=5-0=5S3*=s2*-x2*=5-2=3max逆推到第一張表2026/1/26/sundae_meng15S3*=s2*-x2*=5-2=3x3*=3x2*=22026/1/26/sundae_meng16按計(jì)算表格的順序逆推，可知最優(yōu)分配方案有兩個(gè)：甲工廠分配0臺(tái)，乙工廠分配2臺(tái),丙工廠分配3臺(tái)。甲工廠分配2臺(tái)，乙工廠分配2臺(tái)，丙工廠分配1臺(tái)。以上兩個(gè)分配方案所得到的總盈利均為21萬元問題：如果原設(shè)備臺(tái)數(shù)是4臺(tái)，求最優(yōu)分配方案？如果原設(shè)備臺(tái)數(shù)是3臺(tái)，求最優(yōu)分配方案？2026/1/26/sundae_meng176.3.2一維連續(xù)資源分配問題:一般問題的提法是

A種生產(chǎn)數(shù)量u1投入收益g(u1)

年終資源回收率a如此進(jìn)行n年，如何確定投入A的資源量u1、…、un，使總收入最大？

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);年終回收率a

B種生產(chǎn)數(shù)量s2-u2;收益h(s2-u2);年終回收率b到n年2026/1/26/sundae_meng18此問題的靜態(tài)規(guī)劃問題模型為：動(dòng)態(tài)規(guī)劃的逆推關(guān)系方程為：最后求得f1(s1)即為所求問題的最大收入。2026/1/26/sundae_meng19

高負(fù)荷:產(chǎn)量函數(shù)g=8u1,u1是投入生產(chǎn)的機(jī)器數(shù)量，年完好率為a=0.7，低負(fù)荷:產(chǎn)量函數(shù)h=5y，y是投入生產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開始生產(chǎn)時(shí)完好機(jī)器的數(shù)量為1000臺(tái)。

機(jī)器

例2機(jī)器負(fù)荷分配問題解：設(shè)階段數(shù)k表示年度。

試問每年如何安排機(jī)器在高低兩種負(fù)荷下的生產(chǎn)，可使5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。狀態(tài)變量sk為第k年度初擁有的完好機(jī)器臺(tái)數(shù)；

決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器臺(tái)數(shù)。低負(fù)荷下生產(chǎn)的機(jī)器臺(tái)數(shù)是sk-uk。2026/1/26/sundae_meng20

狀態(tài)轉(zhuǎn)移方程第k年度產(chǎn)量為

遞推方程為指標(biāo)函數(shù)為允許決策集合0

uk

sk2026/1/26/sundae_meng21當(dāng)k=5時(shí),f5(s5)=max﹛8u5+5﹙s5-u5﹚

+f6(s6)﹜0≤u5≤s5=max﹛3u5+5s5﹜0≤u5≤s5u5*=s5,f5(s5)=8s5當(dāng)k=4時(shí),

f4(s4)=max﹛8u4+5(s4–u4)

+f5(0.7u4+0.9(s4–u4))﹜0≤u4≤s4=max﹛13.6u4+12.2(s4-u4)﹜0≤u4≤s4=max﹛1.4u4+12.2s4﹜0≤u4≤s4u4*=

s4,f4(s4)=13.6s42026/1/26/sundae_meng22依次類推可得，u3*=s3f3(s3)=17.5s3

u2*=0

f2(s2)=20.8s2

u1*=0

f1(s1)=23.7s1

最高產(chǎn)量為23700。因此最優(yōu)策略為:

u1*=0,u1*=0,u3*=s3,u4*=s4u5*=s5,u5*=s5,f5(s5)=8s5u4*=

s4,f4(s4)=13.6s42026/1/26/sundae_meng23作業(yè)：如規(guī)定在第五年結(jié)束時(shí)完好機(jī)器數(shù)為500臺(tái)，該如何安排生產(chǎn)？S6=5002026/1/26/sundae_meng24

在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到要合理安排生產(chǎn)（或購買）與庫存的問題，達(dá)到既要滿足社會(huì)的需要，又要盡量降低成本費(fèi)用。因此，正確指定生產(chǎn)（或采購）策略，確定不同時(shí)期的生產(chǎn)量（或購買量）和庫存量，以使總的生產(chǎn)成本費(fèi)用和庫存費(fèi)用之和最小，這就是生產(chǎn)與存儲(chǔ)問題的最優(yōu)化目標(biāo)。

設(shè)某公司對(duì)某種產(chǎn)品要制定一項(xiàng)n個(gè)階段的生產(chǎn)計(jì)劃。已知它的初始庫存量為零，每階段生產(chǎn)該產(chǎn)品的數(shù)量有上限的限制；每階段社會(huì)對(duì)該產(chǎn)品的需求量是已知的，公司保證供應(yīng)；在n階段末的終結(jié)庫存量為零。問該公司如何制定每個(gè)階段的生產(chǎn)計(jì)劃，從而使總成本最??？第二節(jié)生產(chǎn)與存貯問題

2026/1/26/sundae_meng25用動(dòng)態(tài)規(guī)劃方法來求解，把它看作一個(gè)n階段決策問題。令：sk為狀態(tài)變量，它表示第k階段開始時(shí)的庫存量。xk為決策變量，它表示第k階段的生產(chǎn)量。則狀態(tài)轉(zhuǎn)移方程為：

sk

+1=sk+xk-dk

第k階段的成本費(fèi)用包括生產(chǎn)成本和存貯費(fèi)用兩項(xiàng)：2026/1/26/sundae_meng26Ck(xk)表示第k階段生產(chǎn)產(chǎn)品xk時(shí)的成本費(fèi)用，包括生產(chǎn)準(zhǔn)備成本k和產(chǎn)品成本axk（其中a為單位生產(chǎn)成本）hk(xk)表示在第k階段結(jié)束時(shí)庫存量所需的的費(fèi)用。最優(yōu)值函數(shù)fk（sk）表示從第k階段初庫存量為sk到第n階段末庫存量為0時(shí)的最小總費(fèi)用。則基本方程為:

(k=n,n-1，…,1)

2026/1/26/sundae_meng27其中。這是因?yàn)橐环矫婷侩A段生產(chǎn)的上限為m；另一方面保證第n階段結(jié)束時(shí)庫存量可以取0。而這是因?yàn)闉榱吮ＷC第k階段能滿足需求。2026/1/26/sundae_meng28月1234（需求）2324例：

某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后4個(gè)月市場(chǎng)需求預(yù)測(cè)如表所示

。并且有如下假定：固定成本為3千元，若不生產(chǎn)就為0；每單位產(chǎn)品成本為1千元；每個(gè)月生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個(gè)單位；每個(gè)月末未售出的產(chǎn)品，每單位需付存儲(chǔ)費(fèi)0.5千元。還假定在第一個(gè)月的初始庫存量為0，第四個(gè)月末的庫存量也為0。問：如何安排各月的生產(chǎn)與庫存，使總成本最小。

2026/1/26/sundae_meng29用動(dòng)態(tài)規(guī)劃方法來求解：按四個(gè)月份將問題分為四個(gè)階段，則在第k月的生產(chǎn)成本為：2026/1/26/sundae_meng30第k時(shí)期末庫存量為sk+1時(shí)的存儲(chǔ)費(fèi)用為，故第k時(shí)期內(nèi)的總成本為，而動(dòng)態(tài)規(guī)劃的基本方程為：（k＝4，3，2，1）

其中

2026/1/26/sundae_meng31下面從最后一個(gè)階段開始向前逆推計(jì)算。當(dāng)k=4時(shí)，s4∈{0，1，2，3，4}，由于第4月末的庫存量為0，第4階段的生產(chǎn)量x4必為x4=d4-s4，其計(jì)算如下表：

4321076540765

4001234432102026/1/26/sundae_meng32當(dāng)k＝3時(shí)，由于第三、第四階段的需求量分別為2、4，為了保證最后庫存量能取0，s3的允許狀態(tài)集合為{0，1，2，3，4，5，6}而，其中，。其計(jì)算如下表：2026/1/26/sundae_meng336500000111076.565.529＋2------------------------8＋5.58＋2--------------------7＋67＋5.57＋2----------------6＋6.56＋66＋5.56＋2------------5＋75＋6.55＋65＋5.55＋2------------4＋74＋6.54＋64＋5.54＋2------------0＋70＋6.50＋60＋5.50＋2012345665432102026/1/26/sundae_meng34當(dāng)k=2時(shí)，由于第一階段的需求為2，而每階段的最大生產(chǎn)能力為6，S2的最大取值為4，因此s2∈{0，1，2，3，4}，而，其中，。其計(jì)算如下表：2026/1/26/sundae_meng35543001615141110.59＋89＋89＋89＋5----8＋88＋88＋88＋88＋57＋10.57＋87＋87＋87＋86＋116＋10.56＋86＋86＋8----5＋115＋10.55＋85＋8--------4＋114＋10.54＋8------------0＋110＋10.50123465432102026/1/26/sundae_meng36當(dāng)k＝1時(shí)，s1=0，。其計(jì)算如下表所示。520.59+2+10.58+1.5+117+1+146+0.5+155+16065432再按計(jì)算的順序反推算，可找出每個(gè)月的最優(yōu)生產(chǎn)決策為：其相應(yīng)的最小總成本為20.5千元。2026/1/26/sundae_meng37

個(gè)人、單位等隨時(shí)均有設(shè)備更新問題。彩電、設(shè)備隨著使用年限的增加而設(shè)備陳舊，處理價(jià)格愈低，因此需要維修和更新的費(fèi)用增加。處于各種階段的設(shè)備總是面臨保留還是更新問題。保留還是更新，應(yīng)該從整個(gè)計(jì)劃期間的總回收額來考慮，而不能從局部的某個(gè)階段的回收額來考慮，是一個(gè)多階段的決策問題。設(shè)備更新問題提法如下（以一臺(tái)機(jī)器為例）：

n為計(jì)劃設(shè)備使用年數(shù)。

Ik(t)為第k年（階段）機(jī)器役齡為t年的一臺(tái)機(jī)器運(yùn)行（再使用一年）所得的收入。

Ok(t)為第k年機(jī)器役齡為t年的一臺(tái)機(jī)器運(yùn)行（再使用一年）時(shí)所需運(yùn)行的費(fèi)用（或維修費(fèi)用）。

Ck(t)為第k年機(jī)器役齡為t年的一臺(tái)機(jī)器更新時(shí)所需更新的凈