北航计算机研究生课程 算法设计与分析Assignment_1.docx

解： 设第k月的需求量为Nk(k=1,2,3,4) 状态变量Xk：第k月初的库存量，X1=X5=0，0≤Xk≤Nk+…+N4 决策变量Uk：第k月的生产量，max{0，Nk-Xk}≤Uk≤min{6，Nk+…+N4 - Xk} 状态转移方程：Xk+1 = Uk + Xk – Nk 第k月的成本Vk = 0.5*(Xk - Nk) Uk=0 3 + Uk + 0.5*(Uk + Xk - Nk) Uk≠0 设Fk(Xk)是由第k月初的库存量Xk开始到第4月份结束这段时间的最优成本 则Fk(Xk) = min{Vk + Fk+1(X k+1)} 1≤k≤4 = min{ 3 + Uk + 0.5*(Uk + Xk - Nk) + Fk+1(Uk + Xk - Nk) } Uk≠0 min{ 0.5*(Xk - Nk) + Fk+1(Xk - Nk) } Uk=0 F5(X5)=0 四个月内的最优成本为F1(X1)=F1(0) 详细计算步骤如下： （1）k=4时 0≤X4≤4，max{0，4 - X4}≤U4≤min{6，4-X4} X4U4X5V4F5(X5)V4 + F5(X5)040707=F4(0)130606=F4(1)220505=F4(2)310404=F4(3)400000=F4(4)即对于状态X4的每个取值，都有唯一确定的决策变量U4使得F4(X4)最优 （2）k=3时 0≤X3≤6，max{0，2 - X3}≤U3≤min{6，6-X3} X3U3X4V3F4(X4)V3 + F4(X4)0205712316.5612.5428513539.5413.56411011=F3(0)1104711215.5611.5327512438.5412.55410010=F3(1)200077=F3(2)114.5610.5226511337.5411.5449093010.566.5=F3(3)125510236.5410.534808402156=F3(4)135.549.5247075031.545.5=F3(5)14606604302=F3(6) （3）k=2时 0≤X2≤9，max{0，3 - X2}≤U2≤min{6，9-X2} X2U2X3V2F3(X3)V2 + F3(X3)03061117417.51017.5529716=F2(0)6310.56.51712051116316.51016.5428715=F2(1)539.56.516641161721041115215.51015.5327714=F2(2)438.56.51554106166511.55.51730001111=F2(3)114.51014.5226713337.56.5144496155510.55.51666122144010.51010.5=F2(4)125713236.56.513348614459.55.5155611213502178=F2(5)135.56.512247613358.55.51446102126031.56.58=F2(6)146612257.55.513369211704268=F2(7)156.55.5122682108052.55.58=F2(8)16729906325=F2(9) （4）k=1时 X1=0，max{0，2}≤U1