动态规划模型举例

《动态规划模型举例》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§6动态规划模型举例10/16/20211以上讨论的优化问题大多数属于静态的，即不必考虑时间的变化，建立的模型——线性规划、非线性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以时间或空间为标志）要根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。例如：（1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出为后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。（2）发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标运动的情况，不断地决定导弹飞行的方向和速度，使

2、之最快地命中目标。10/16/20212（3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外，每次更新都要付出更新费用。因此，应当如何决定它的使用年限，使总的效益最佳。动态规划模型是解决这类问题的有力工具。下面结合具体例子阐述建立动态规划模型的思路。例13最短路问题。图2是一个线路网，连线上的数字表示两点之间的距离（或费用），寻找一条由A到G的路线，使距离最短（或费用最省）。10/16/20213解：用穷举法当然可以解决这个问题。不难算出，一共有48条从A到G的路线，用加法

3、得到每条路线的长度后，再作比较即可找出最短路线。显然当路段很多时，计算工作量将是很大的。AB1B2C1C2C3C4D3D2D1E1E2E3F1F2G531368768433538622123366255343图２10/16/20214用动态规划解决问题的思路，来源于生活中这样一个基本常识：如果已经找到由A到G的最短路线是A—B1—C2—D1—E2—F2—G（图中粗线，记作L），那么当寻求L中的任何一点（如D1）到G的最短路时，它必然是L中的子路D1—E2—F2—G（记作L1）。因为否则，若D1到G的最短路是另一条路线L2，则把A—B1—C2—D1与L2连接起来，就会得到一条不同于L的从A

4、到G的最短路。根据最短路的这一特性，我们可以从最后一段开始，用逐步向前递推的方法，依次求出路段上各点到G的最短路，最后得到A到G的最短路。10/16/20215具体实施如下：从A到G要走6个路段，是一个6阶段决策问题，记k=1，2，…，6。用dk（xk，xk+1）表示第k段的点xk与第k+1段的点xk+1之间的（已知）距离（视k的不同，x分别代表A，B，…，F），用uk（xk）表示在xk的决策，即从xk向哪一点走，则xk+1可以记作xk+1=uk（xk）。设xk到终点G的最短距离为fk（xk），则k=6时，f(F1)=4,f(F2)=3,显然u(F1)=G,u(F2)=G,k=5时，f5

5、(E1)=min=min=7表明E1到G的最短路是E1—F1—G，即E1的最优决策为u(E1)=。10/16/20216表明E2到G的最短路是E2－F2－G，即E2的最优决策为u5（E2）=F2。同法计算出f5(E3)=9，u5（E3）=F2，10/16/20217k=3时，k=2时,f2(B1)=13,u2(B1)=C2f2(B2)=16,u2(B2)=C3k=1时,f1(A)=18,u1(A)=B1,于是从A到G的最短距离为f1(A)=18，而最短路线则由A开始顺次找出最优决策来确定，即u1(A)=B1，u2(B1)=C2,u3(C2)=D1，u4(D1)=E2，u5(E2)=F2，

6、u6(F2)=G，最短路线为A——B1——C2——D1——E2——F2——G。10/16/20218不难看出，上述计算过程可以表示为如下的一般形式：(1)其中D（x）表示在x的允许决策集合，如D2（B1）=（C1，C2，C3)，X表示第k段的允许状态集合，如X2=(B1，B2）。当按（1）式由k=6逆推至k=1时，就得到了最短距离，而最短路线由顺推的最优决策确定。在动态规划中f（x）称最优值函数，（1）式称最优方程。10/16/20219需要指出，上例只是最短路问题的一种形式，实际问题中可以有多种形式，如：1）路线数目不定，如图3，求任一点（如B）到E的最短路线（不论它由几段组成）；2）

7、有向路网，如图4，求V1到V6的有向最短路；3）旅行商问题，如图3，求从A点出发，经每点一次又回到A点的最短路。EDABCV4V5V6V3V1V22535267510.528723116310图３　　　　　　　　　　　　图４10/16/202110下面介绍动态规划相关的基本概念及其数学描述（1）阶段整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为阶段变量，记为。（2）状态状态表示每个阶段