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

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS: Vol. 45, No. I，JANUARY 1985TECHNICAL NOTEA Mixed Forward-Backward Dynamic ProgrammingMethod Using Parallel Computation 此项研宂由国家科学基金会赞助(项R号INT-78-09263)，时值作者在加利 福尼亚州伯克利的加利福尼亚大学访学期间 高级研究员，就职于 Laboratoire d’ Automatique et d’ Analyse des Sustmes du CNRS,法国图卢兹J. B. Lasserre7Communicated by S. E. Dreyfus技术札记平行计算的前后动态混合规划方法J. B. LASSERRE 2与 S. E. Dreyfus 合议摘要：我们考虑使用前后动态混合规划解决最优化问题，并提出一种通过两个处 理器执行平行计算来减少计算时间的方法关键词：动力学设计，平行线计算1. 介绍我们关注一种分散时间最理想的控制难题，而在这个难题中，动态可能采 用常规方式描述xt=/t (xt~l, ut)或者用动态规划的向后处理法 xt~l= f t (xt, ut)例如，在生产计划或库存计划中，库存水平方程式就属于这种形式： xt=AtXt-l+Btut所以，如果At是一个可逆矩阵(从参考文献1查看这些模型)也可以写做: xt—l=At lxt+At *Btut因此，这个问题能使用标准的向后或向前动态规划处理法解决。

假设两个处理器能平行计算，我们提山一种前后动态混合规划方法一个处 理器使用向前动态规划运算法则来解决T/2周期问题(假设原始问题冇T周期) 同时，第二个处理器则使用向后动态规划运算法则來解决另T/2周期问题一旦 成功，小小额外工作就是寻找一种原始问题的最佳解决方案计算的整个数量与 标准向后动态规划运算法则和同(如果我们假设向前或向后动态规划运算需要同 样的计算)这样，计算时间基木上可分成两部分，就一个庞大的运算周期来说, 这个小小的额外工作可以忽略不计(在两个处理器都解决了各自的问题之后)2. 注释与定义让我们思考以下问题[问题(P)]:取最大值 TZ [/t(xt)+gt(ut)], t=ls. t. xt=ht (xt-1, ut), xtEXt, utEUt,已知xO,这里的xt是一个维矢量，ut是一个多元向量假设 存在一个明确的函数h’，就有：xt=ht(xt-1, ut) xt~l=ht7 (xt, ut).让我们把Vt (x,)叫做从X开€>Xt结束的最优策略的最优成本通过使用向前的动态规划定理，我们得到：*V1 (x) = /l (x)+gl (u),对于 xEXl (la)其中，u=argmax gl(ul)(lb)s. t.hl (xo, ul)=x,(lc)166uieUl(Id)和Vt(x)=ft(x)+max[gt (ut)+vt-l (xt~l)], (2a)s. t xt-l=h’ t (x, ut), (2b)xt~l GXt-1, utEUt (2c)让我们把％&)称作最优策略的最佳成本，用x来表示起始时间t,用T来 表示完成时间。

通过动态规划方程定理，我们可以得知：WT-1(X)=max[gt(uT)+fT(Xt)], (3a)s. t xT=hT (x, uT), (3b)xTEXT, uTGUT , (3c)和Wt(x)=max[ft+l(xt+1)+gt+l(ut+1)+Wt+1(xt+1)], (4a)s. t. xt+l=ht+l (x, ut+1), (4b)xt+1 E Xt+1, ut+lGUt+1 (4b)用向后动态规划运算法则计算时，可以把最佳成本设为WcXXj在下一部分， 我们将明白向前动态规划和向后动态规划如何结合以更快地得到最优解3. 前后动态混合规划方程求解过程把问题(P)的最佳成本设为C*接着，通过最优定理，我们可知：任何t, 其 O=max [Vt (x) +\Vt (x) ]， (5a)s. t. xEXt (5b)现在，假设我们可以平行使用两台处理器计算接着，运用(1)和(2)，Vt (x)可以在处理器1中进行运算，同吋将\H(x)输入处理器2用(3)和(4)进行 运算这样，一旦开始计算V’ t(.)和Wt(.)，我们只需要使用(5)來检测x 赋予C*的值我们需要用标准的向后动态规划计算WO(xO)。

如果T=2p，那么选择t二a 167Vp和Wp基本上要求等量的计算如果T=2/zH，那么选择f - p, Wp会比计算 Vp稍多花一点时间，因为(4)会有比(2)有更多的重复计算所以，计算时 间几乎要除以2,因为用(5)去计算C*的工作量相对更大的T来说是微不足道 的在下一部分，我们会举例说明在一个典型的资源分配问题中应用的结果4. 资源分配问题中的计算量让我们思考一个典型的资源分配问题(看参考文献2,第33页)需要用 (T-2)(X+l)(X+2)/2 加法和(p-l)X(X+l)/2 对照来计算 WT-2(x),. • .,Wp(x)o Wo(Xo)需要X+l加法和X对照WT-1 (x)只需要估算让我们现在来思考一下这个新方程例题Case(i).T=2p. —台处理器运算，WT-1，WT-2,…，Wp，’同时另一台处 理器计算VI, V2,. . .，VP.最后，全部的计算量是：(p-1) (x+l) (x+2)/2加 法和(p-l)X(X+l)/2对照在•一台处理器上计算WT-2(x)，. . .，Wp(x)同吋另一台 处理器计算V,(x),…,Vp(x)我们也需要X+1和X对照去计算C*。

因此，在计 算过程中需要去演算(p-1) (X+l) (X+2)/2+X+l加法和(p- 1)X(X+ D/2+X对照， 而不是(P- 1) (X+ l)(X+2)+X+ 1 加法和(p - 1)X(X + 1) + X 对照对于大 P，实际上计算时间将会除以2.例题Case(ii).T=2p+l..为了计算 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*同样地，对于大八实际计算 时间要除以2参考文献：1. JOHNSON, L. A., and MONTGOMERY, P. C., Operations Research in Production Planning, Scheduling, and Inventory Control, Wiley, New York, New York, 1974. 2. DREYFUS, S. E., and LAW, A. M., The Art and Theory of Dynamic Programming, Academic Press, New York, New York, 1977.。