并行计算的前后动态混合规划方法(原版译文)

1、技术札记平行计算的前后动态混合规划方法J. B. LASSERRE 2与 S. E. Dreyfus合议摘要：我们考虑使用前后动态混合规划解决最优化问题，并提出一种通过两个处理器执行平行计算来减少计算时间的方法。关键词：动力学设计，平行线计算1.介绍我们关注一种分散时间最理想的控制难题，而在这个难题中， 动态可能采用常规方式描述 xt=ft(xt-1,ut)或者用动态规划的向后处理法xt-1= ft(xt,ut)例如，在生产计划或库存计划中，库存水平方程式就属于这种形式：xt=AtXt-1+Btut所以，如果At是一个可逆矩阵（从参考文献1查看这些模型）也可以写做：xt-1=At-1xt+At

2、-1Btut因此，这个问题能使用标准的向后或向前动态规划处理法解决。1. 此项研究由国家科学基金会赞助（项目号INT-78-09263），时值作者在加利福尼亚州伯克利的加利福尼亚大学访学期间。2. 高级研究员，就职于Laboratoire dAutomatique et dAnalyse des Sustmes du CNRS，法国图卢兹。 165假设两个处理器能平行计算，我们提出一种前后动态混合规划方法。一个处理器使用向前动态规划运算法则来解决T/2周期问题（假设原始问题有T周期）。同时，第二个处理器则使用向后动态规划运算法则来解决另T/2周期问题。一旦成功，小小额外工作就是寻找一种原始问题

3、的最佳解决方案。计算的整个数量与标准向后动态规划运算法则相同（如果我们假设向前或向后动态规划运算需要同样的计算）。这样，计算时间基本上可分成两部分，就一个庞大的运算周期来说，这个小小的额外工作可以忽略不计（在两个处理器都解决了各自的问题之后）2. 注释与定义让我们思考以下问题问题（P）：取最大值 T ft(xt)+gt(ut), t=1s.t. xt=ht(xt-1,ut), xtXt,utUt,已知x0，这里的xt是一个维矢量，ut是一个多元向量。假设 存在一个明确的函数h，就有：xt=ht(xt-1,ut) xt-1=ht(xt,ut).让我们把Vt(xt)叫做从X0开始、Xt结束的最优策

4、略的最优成本。通过使用向前的动态规划定理，我们得到：*V1(x)= f1(x)+g1(u), 对于xX1 (1a)其中，u=argmax g1(u1) (1b) s.t. h1(xo,u1)=x, (1c) u1U1 (1d)166和Vt(x)=ft(x)+maxgt(ut)+vt-1(xt-1), (2a)s.t xt-1=ht(x,ut), (2b) xt-1Xt-1, utUt (2c)让我们把Wt(x)称作最优策略的最佳成本，用x来表示起始时间t，用T来表示完成时间。通过动态规划方程定理，我们可以得知：WT-1(X)=maxgt(uT)+fT(Xt), (3a)s.t xT=hT(x,

5、uT), (3b) xTXT, uTUT , (3c)和Wt(x)=maxft+1(xt+1)+gt+1(ut+1)+Wt+1(xt+1), (4a) s.t. xt+1=ht+1(x,ut+1), (4b) xt+1Xt+1, ut+1Ut+1 (4b)用向后动态规划运算法则计算时，可以把最佳成本设为W0(X0)。在下一部分，我们将明白向前动态规划和向后动态规划如何结合以更快地得到最优解。3. 前后动态混合规划方程求解过程 把问题(P)的最佳成本设为C*。接着，通过最优定理，我们可知：任何t，其C*=maxVt(x)+Wt(x), (5a) s.t. xXt (5b)现在，假设我们可以平行使

6、用两台处理器计算。接着，运用（1）和(2)， Vt(x)可以在处理器1中进行运算，同时将 Wt(x)输入处理器2用（3）和（4）进行运算。这样，一旦开始计算 Vt(.)和 Wt(.)，我们只需要使用（5）来检测x赋予C*的值。我们需要用标准的向后动态规划计算 W0(x0)。如果T=2p，那么选择t = p，167Vp和Wp基本上要求等量的计算。如果T=2p+1，那么选择t = p，Wp会比计算Vp稍多花一点时间，因为（4）会有比（2）有更多的重复计算。所以，计算时间几乎要除以2，因为用（5）去计算C*的工作量相对更大的T来说是微不足道的。在下一部分，我们会举例说明在一个典型的资源分配问题中应用

7、的结果。4. 资源分配问题中的计算量让我们思考一个典型的资源分配问题（看参考文献2，第33页）。需要用(T-2)(X+1)(X+2)/2加法和(p-1)X(X+1)/2对照来计算 WT-2(x),. . .,Wp(x)。W0(X0)需要X+1加法和X对照。 WT-1(x)只需要估算。让我们现在来思考一下这个新方程。例题Case(i).T=2p. 一台处理器运算, WT-1,WT-2,Wp, 同时另一台处理器计算 V1, V2,. . .,VP.。最后，全部的计算量是：(p-1)(x+1)(x+2)/2加法和(p-1)X(X+1)/2对照在一台处理器上计算WT-2(x),. . . ,Wp(x)

8、同时另一台处理器计算V1(x),Vp(x)。我们也需要 X+1和X对照去计算C*。因此，在计算过程中需要去演算(p-1)(X+I)(X+2)/2+X+I加法和(p- 1)X(X+ I)/2+X对照，而不是(p- 1)(X+ 1)(X+2)+X+ 1加法和(p - 1)X(X + 1) + X对照。对于大P，实际上计算时间将会除以2.例题Case(ii).T=2p+1.为了计算 Wp，我们需要p(X+l)(X+2)/2附加和pX(X+ 1)/2比较，然而对Vp我们需要(p-1) (X+ 1)(X +2)/2加法和(p- 1)X(X+ 1)/2对照。在此之前，用X + 1加法和X对照计算C*。同样地，对于大P，实际计算时间要除以2。参考文献：1. JOHNSON, L. A., and MONTGOMERY, P. C., Operations Research in Production Planning, Scheduling, and Inventory Control, Wiley, New York, New