北航计算机研究生课程 算法设计与分析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≠0min{0.5*(Xk - Nk) + Fk+1(Xk -Nk) }Uk=0F5(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.5413F3(0)1104711215.5611.5327512438.5412F3(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≤min{6，11}X1U1X2V1F2(X2)V1 + F2(X2)02051621316.51521.54281422539.51120.5=F1(0)641110.521.5由以上计算可得，4个月的总最优成本为F1(0) = 20.5(千元)从k=1回溯，可得最优结果中各阶段的状态变量Xk和决策变量Uk如下表：月份k产量Uk月初库存量Xk需求量Nk每月成本Vk15029.52033036021140440解：1、变量设定阶段k：已遍历过k个结点，k=1,2…6,7。K=1表示刚从V1出发，k=7表示已回到起点V1状态变量Xk=(i，Sk)：已遍历k个结点，当前位于i结点，还未遍历的结点集合为Sk。则X1=(1，{2,3,4,5,6})，X6=(i，Φ)，X7=(1，Φ)决策变量Uk=(i，j)：已遍历k个结点，当前位于i结点，下一个结点选择j。状态转移方程：Xk+1 = T(Xk，Uk) = (j，Sk-{j})第k阶段的指标函数Vk = D[i,j]。最优指标函数Fk(Xk) = Fk(i，Sk)：已遍历k个结点，当前从i结点出发，访问Sk中的结点一次且仅一次，最后返回起点V1的最短距离。则Fk(i，Sk) = min{ D[i,j] + Fk+1(j，Sk-{j}) } 1≤k≤6F7(X7) = F7(1，Φ) = 02、分析：（1）k=6时，F6