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

一、用动态规划方法手工求解下面的问题： 某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。 时期（月） 需要量（产品单位）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 伪代码： Procedure TSP_DP (i, ) //D为全局数组，这是一个递归函数 //输入：城市i, 以及一个城市集合 //输出：从城市i出发，经过中每个城市一次且仅一次最后返回城市i的最短距离minDist // 以及该最短路径path Begin 1 If then return （，1） 2 对所有 T1 ← 找到使最小的 j，记为 n 3 T← Dist ← Path ← 4 Return (Dist, Path) End 初始