文档介绍：《动态规划MATLab》
A
B1
B2
B3
C1
C2
C3
D1
D2
E
1 动态规划的基本概念
一、 阶段
对于一个多阶段决策过程，
可以根据问题的特
点，
把整个过程划分为几个相互联系的线。
如果不是这样，
则从B1点到 D点有另一条距离更短的
路线存在，
把它和原来的最短路线有A点到B1点的那
部分连接起来，
就会得到一条从A点到D点的新路线，
且比原来的那条最短路线的距离还要短些，这就与
假设矛盾。
基于最短路线的这一特性，
我们考虑寻找
最短路线的方法，
就是从最后一段开始，
用由后向前
逆向递推的方法，
逐步求出各点到终点的最短路线，
最后求得由起点到终点的最短路线。
以本案例为例，我们按上述思想寻找从A到E的最
短路线。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第一步，
从k=4出发，
状态变量
可取状态
它们到E点的路长分别为
第二步，k=3，
状态变量
可取三个值
这是经过一个中途点到达终点E的两级决策变量。
从
到E有两条路线，
需加以比较取其中最短的，
即
这说明由
到E的最短距离为7，
其路径为
相应的决策为
同理
即
到终点E的最短距离为6，
其路径为
相应的决策为
即
到终点E的最短距离为10 。
其路径为
相应的决策为
类似地，
k=2时
k=1时，
出发点只有一个A点，
则
即从起点A到终点 E的最短距离为15。
反推可得最优决策序列
再按计算顺序
即
所以得最短路线为
注1：
从本案例的计算过程可以看出，在各阶段，都
利用了第k阶段和第 k+1阶段的如下关系：
这种递推关系称为动态规划的基本方程，
称为边界条件。
上述最短路线的计算过程也可用图直观表示出
来，如图：
A
B1
B2
B3
C1
C2
C3
D1
D2
E
这里，每个节点上方的括号内的数字，
表示该点到
E点的最短距离，
连接各点到E点的线表示最短路径。
这种在图上直接计算的方法称为标号法。
动态规划方法相对于穷举法来说有以下优点：
（1）减少了计算量；
（2）丰富了计算结果。
动态规划方法存在的不足之处：
（1）静态规划模型转化为动态规划模型十分困难；
（2）状态变量的“无后效性”条件难以满足。
动态规划的基本思想总结：
先将多阶段决策的过程划分成几个相互联系
的阶段，
恰当地选取状态变量、决策变量，
定义最
优指标函数，
从而把问题化成一族同类型的子问题，
然后逐个求解。
求解时从边界条件开始，
逆方向逐
段递推寻优。
在每一个子问题求解时，
都要使用它
前面已求出的子问题的最优结果，
最后一个子问题
的最优解，
就是整个问题的最优解。
动态规划的基本方程是递推逐段求解的根据。
动态规划基本方程可表述为：
式中opt可根据实际问题选取min或max，
表示状态为
决策为
时对应的第k阶段的指标
函数值。
3 应用LINGO软件求解动态规划
解：
LINGO程序如下：
Model:
Sets:
Nodes/a,b1,b2,b3,c1,c2,c3,d1,d2,e/:d;
Arcs(nodes,nodes)/a,b1 a,b2 a,b3 b1,c1 b1,c2 b2,c1 b2,c2 b2,c3 b3,c2 b3,c3 c1,d1 c1,d2 c2,d1 c2,d2 c3,d1 c3,d2 d1,e d2,e/:w,p;
Endsets
n=***@size(nodes);
d(n)=0;
***@for(nodes(i)|i#LT#n:d(i)=***@min(arcs(i,j):w(i,j)+d(j)));
***@for(arcs(i,j):
p(i,j)=***@if(d(i)#eq#w(i,j)+d(j),1,0));
Data:
W=3 5 7 7 6 9 5 2 3 8 3 5 4 3 6 9 4 3;
Enddata
End
迭代后有如下结果：
Feasible solution found at iteration: 0
Variable Value
N
D( A)
D( B1)
D( B2)
D( B3)
D( C1)
D( C2)
D( C3