用动态规划方法手工求解下面的问题

一、用动态规划方法手工求解下面的问题：某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。时期（月）需要量（产品单位）12233244已知：对每个月来讲，生产一批产品的固定成本费为3(千元)，若不生产，则为零。每生产单位产品的成本费为1(千元)。同时，在任何一个月内，生产能力所允许的最大生产批量为不超过6个单位。又知每单位产品的库存费用为每月0.5(千元)，同时要求在第一个月开始之初，及在第四个月末，均无产品库存。问：在满足上述条件下，该厂应如何安排各个时期的生产与库存，使所花的总成本费用最低？解：这是一个多阶段问题，我们按照计划时间自然划分阶段。状态变量定义为第k月月初时的存储量，决策变量定义为第k月的产量，记每个月需求量为，则状态转移方程为：第k月允许决策集合阶段指标为阶段的生产成本费用和存储费用之和，即：指标函数为表示由第k月出发采用最优方案到第4月月底4个月时间内总成本由条件可得到递推式：k=4,3,2,1(0)=7 =4(1)=6.5 =3(2)=6 =2(3)=5.5 =1(4)=2 =0(0)=min{12,12.5,13,13.5,11}=11 =6(1)=min{11.5,12,12.5,13,10.5}=10.5 =6(2)=min{8,11.5,12,12.5,10}=8 =0(3)=min{8,11.5,12,9.5}=8 =0(4)=min{8,11.5,9}=8 =0(5)=min{8,8.5}=8 =0(6)=min{5}=5 =0(0)=min{17,17.5,16,17}=16 =5(1)=min{16.5,17,15.5,16.5,17.5}=15.5 =4(2)=min{16,16.5,15,16,17,18}=15 =3(3)=min{12.5,14,14.5,15.5,16.5,17.5,15.5}=12.5 =0(4)=min{12.5,14,15,16,17,15}=12.5 =0(5)=min{10.5,14.5,15.5,16.5,14.5}=10.5 =0(6)=min{11,15,16,14}=11 =0(0)=min{21,21.5,22,20.5,21.5}=20.5 =5逆推可得u={5,0,6,0}x={0,3,0,4}即第1个月生产5单位产品，第4个月生产6单位产品，第2、3月不生产。第2、3、4月的库存量分别为3、0、4。采取这个方案可以使总成本降至最低20.5（千元）。二、用动态规划方法编程求解下面的问题：某推销员要从城市v1出发，访问其它城市v2，v3，…，v6各一次且仅一次，最后返回v1。D为各城市间的距离矩阵。问：该推销员应如何选择路线，才能使总的行程最短？要求：写出递推关系式、伪代码和程序相关说明，并分析时间复杂性。（请遵守第一节课提出的有关assignment的要求）解：问题的动态规划模型构造如下：阶段k：已经历过的城市个数，包括当前所在的城市。k=1,2,3,4,5,6；k=1表示出发时位于起点，k=7表示结束时回到终点。状态变量：，其中i表示当前所在的城市，表示尚未访问过的城市的集合。S1={2,3,4,5,6},S6=S7=x6=(i,)i=2,3,4,5,6；x7=(1,)决策变量：，其中i为当前所在的城市，j为下一站将要到达的城市。状态转移方程：阶段指标：最优指标函数表示从城市i出发，经过中每个城市一次且仅一次，最后返回城市1的最短距离。可得递推式也即k=6,5,4,3,2,1伪代码：ProcedureTSP_DP(i,)//D为全局数组，这是一个递归函数//输入：城市i,以及一个城市集合//输出：从城市i出发，经过中每个城市一次且仅一次最后返回城市i的最短距离minDist// 以及该最短路径pathBegin1 Ifthenreturn（，1）2 对所有 T1←找到使最小的j，记为n3 T←Dist←Path←4 Return(Dist,Path)End初始化S1←{2,3,4,5,6}调用T=TSP_DP(1,)即可得到结果时间复杂性分析：该算法只需考虑加法和比较运算次数，由于加法和比较运算次数为同一数量级，而且加法运算要多于比较运算次数，故单考虑加法运算次数即可。令m=n-1k=1时,需要做