文档介绍：案例：最短路问题
假设要从A城市到 E城市铺设一条输油管道，
中间需要经过三个地区，
每个地区都有若干个转运
站，
构成了许多不同的输油路线，
转运站间的数字
表示站间的运输路径的长度，
由于地理条件等原因，
某些地区之间我们结合案例的最短路问题来介绍动态
规划的基本思想与基本原理。
穷举法的计算量将非常大，显然不适合。
考虑最短路线的一个重要特征：
若从起点A经过
B点和C点而达到终点 D是一条最短路线，
则由B点出
发经过C点到达终点D点的这条子路线，对于从 B点
出发达到终点D点的所有可能选择的不同路线来说，
必定也是最短路线。
精选ppt
在本例中，
若找到了
是由
A到D的最短路线，
则
也应是从B1 出
发到D点的所有可能选择的不同路线中的最短路线。
如果不是这样，
则从B1点到 D点有另一条距离更短的
路线存在，
把它和原来的最短路线有A点到B1点的那
部分连接起来，
就会得到一条从A点到D点的新路线，
且比原来的那条最短路线的距离还要短些，这就与
假设矛盾。
基于最短路线的这一特性，
我们考虑寻找
最短路线的方法，
就是从最后一段开始，
用由后向前
逆向递推的方法，
逐步求出各点到终点的最短路线，
最后求得由起点到终点的最短路线。
精选ppt
以本案例为例，我们按上述思想寻找从A到E的最
短路线。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
精选ppt
第一步，
从k=4出发，
状态变量
可取状态
它们到E点的路长分别为
第二步，k=3，
状态变量
可取三个值
这是经过一个中途点到达终点E的两级决策变量。
从
到E有两条路线，
需加以比较取其中最短的，
即
精选ppt
这说明由
到E的最短距离为7，
其路径为
相应的决策为
同理
即
到终点E的最短距离为6，
其路径为
相应的决策为
精选ppt
即
到终点E的最短距离为10 。
其路径为
相应的决策为
类似地，
k=2时
k=1时，
出发点只有一个A点，
则
精选ppt
即从起点A到终点 E的最短距离为15。
反推可得最优决策序列
再按计算顺序
即
所以得最短路线为
注1：
从本案例的计算过程可以看出，在各阶段，都
利用了第k阶段和第 k+1阶段的如下关系：
精选ppt
这种递推关系称为动态规划的基本方程，
称为边界条件。
上述最短路线的计算过程也可用图直观表示出
来，如图：
A
B1
B2
B3
C1
C2
C3
D1
D2
E
精选ppt
这里，每个节点上方的括号内的数字，
表示该点到
E点的最短距离，
连接各点到E点的线表示最短路径。
这种在图上直接计算的方法称为标号法。
动态规划方法相对于穷举法来说有以下优点：
（1）减少了计算量；
（2）丰富了计算结果。
动态规划方法存在的不足之处：
（1）静态规划模型转化为动态规划模型十分困难；
（2）状态变量的“无后效性”条件难以满足。
精选ppt
动态规划的基本思想总结：
先将多阶段决策的过程划分成几个相互联系
的阶段，
恰当地选取状态变量、决策变量，
定义最
优指标函数，
从而把问题化成一族同类型的子问题，
然后逐个求解。
求解时从边界条件开始，
逆方向逐
段递推寻优。
在每一个子问题求解时，
都要使用它
前面已求出的子问题的最优结果，
最后一个子问题
的最优解，
就是整个问题的最优解。
精选ppt
动态规划的基本方程是递推逐段求解的根据。
动态规划基本方程可表述为：
式中opt可根据实际问题选取min或max，
表示状态为
决策为
时对应的第k阶段的指标
函数值。
精选ppt
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
精选ppt
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));
Dat