十動(dòng)態(tài)規(guī)劃的應(yīng)用-生產(chǎn)與存儲(chǔ),設(shè)備更新問題

生產(chǎn)與存貯問題

生產(chǎn)周期分為n個(gè)階段，已知最初庫存量：x1

階段市場的需求：dk

生產(chǎn)的固定成本：K單位產(chǎn)品的消耗費(fèi)用：L

單位產(chǎn)品的階段庫存費(fèi)用：h倉庫容量：M

階段生產(chǎn)能力為B

一個(gè)生產(chǎn)部門，如何在已知生產(chǎn)成本、庫存費(fèi)用和各階段市場需求條件下，決定各階段產(chǎn)量，使計(jì)劃內(nèi)的費(fèi)用總和為最小的問題。

問如何安排各階段產(chǎn)量，使計(jì)劃周期內(nèi)的費(fèi)用總和最小。不能超過階段k至階段n的需求總量xkdk+dk+1++dn，k=1,2,,n階段k的初始庫存量，x1已知，xn+1=00xkmin{M，dk+dk+1++dn}，（k=1,2,,n）狀態(tài)變量xk：不能超過庫存容量M，決策變量uk：不超過生產(chǎn)能力階段k

的產(chǎn)量uk

dk+dk+1++dn-xk不小于該階段的需求和庫存量之差，

不超過kn

階段的總需求減去第k

階段初的庫存量，dk-xk

ukmin{B，dk+dk+1++dn-xk}

狀態(tài)轉(zhuǎn)移方程為階段生產(chǎn)費(fèi)用和庫存費(fèi)用之和，即階段k的生產(chǎn)費(fèi)用k階段末的庫存費(fèi)用動(dòng)態(tài)規(guī)劃基本方程階段效益fn+1（xn+1）=0，k=1,2,,ndk-xk

ukmin{B，dk+dk+1++dn-xk}例5

已知n=3，K=8，L=2，h=2，x1=1，M=4，x4=0，B=6，d1=3，d2=4，d3=3，求解生產(chǎn)與庫存問題。解：遞推方程f4(x4)=0，k=1,2,3當(dāng)時(shí)=8+2(3-x3)=14-2x3倉庫容量：4dk-xk

ukmin{B，dk+dk+1++dn-xk}若x3=0,

u*3(0)=3則f3(0)=14若x3=1,則f3(1)=12u*3(1)=2若x3=2,則f3(2)=10u*3(2)=1

若x3=3,則f3(3)=8u*3(0)=0f3(x3)=14-2x3u3=3-x3x3：0～3k=2容量44+3ukdk-xk4-x2

u2min{6,7-x2}

f2(x2)=min{8+2u2+2(x2+u2-4)+f3(x2+u2-4)}4-x2

u2min{B，d2+d3-x2}=min{6,7-x2}0

x2min{M，d2+d3}=min{4,7}=4u*2(0)=4x2=04-x2

u2min{6,7-x2}

x2=1u*2(1)=34-x2

u2min{6,7-x2}

x2=2u*2(2)=24-x2

u2min{6,7-x2}

x2=3u*2(3)=1x2=4u*2(4)=04-x2

u2min{6,7-x2}

結(jié)果見下表：k=1f2=302u16x2=x1+u1-d1=1+u1-3=u1-2u*1(1)=2x1=1f3=14最優(yōu)決策為{1，0，0，0}x2=u1-2=0x3=x2+u2-d2=0+4-4=0最優(yōu)路線為最優(yōu)目標(biāo)函數(shù)值為42。（狀態(tài)變量）u*1(1)=2，u*2(0)=4，u*3(0)=3

設(shè)備更新問題提法如下（以一臺機(jī)器為例）：

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

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

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

Ck(t)為第k年機(jī)器役齡為t年的一臺機(jī)器更新時(shí)所需的凈費(fèi)用（處理一臺役齡為t的舊設(shè)備，買進(jìn)一臺新設(shè)備的更新凈費(fèi)用）。

設(shè)備更新問題為折扣因子，表示一年以后的收入是上一年的單位。要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺新的，使n年內(nèi)總效益最大？建立動(dòng)態(tài)規(guī)劃模型如下：

階段k（k=1，2，…，n）表示計(jì)劃使用該設(shè)備的年限數(shù)。

狀態(tài)變量sk：第k年初，設(shè)備已使用過的年數(shù)，即役齡。

決策變量xk：是第k年初更新，還是保留使用舊設(shè)備，分別用R，K表示。

階段效益為：

狀態(tài)轉(zhuǎn)移方程為：

最優(yōu)指標(biāo)函數(shù)fk(sk)：表示第k年初，使用一臺已用了sk年的設(shè)備，到第n年末的最大收益。實(shí)際上例7：設(shè)某臺新設(shè)備的年效益及年均維修費(fèi)用、更新凈費(fèi)用如下表，試確定今后五年內(nèi)的更新策略，使總效益最大。（設(shè)=1）

動(dòng)態(tài)規(guī)劃的基本方程為解：n=5狀態(tài)變量s5可取1，2，3，4

役齡項(xiàng)目012345效益IK(t)54.543.7532.5運(yùn)行費(fèi)OK(t)0.511.522.53更新費(fèi)CK(t)0.51.52.22.533.5單位：萬元賣掉役齡2年的設(shè)備，買入新設(shè)備的更新費(fèi)用狀態(tài)變量s4可取1，2，3此時(shí)s3可取1或2由于狀態(tài)s2只能取1，所以有由于狀態(tài)s1只能取0，所以有尋找最優(yōu)解，上述過程遞推回去。當(dāng)x*1(0)=K，由狀態(tài)轉(zhuǎn)移方程

本例的最優(yōu)策略是{K，R，R，R，K}，即第一年初購買的設(shè)備到第二、三、四年初各更換一次，用到第五年年末，總效益為17萬元。s2=1，查f2(1)得x*2=Rs3=1，查f3(1)得x*3=Rs4=1，查f4(1)得x*4=Rs5=1，查f5(1)得x*5=K