利用动态规划法求解运输问题的最短路径.doc

利用动态规划法求解运输问题的最短路径

分析：针对最短路径问题，最容易想到的方法是穷举法，即列出所有可能发生的方案和结果，针对要求进行比较求出最优方案，对于简单变量少的问题还是可行的，但是对于复杂变量多的问题计算工作量就比较大。最短路径的最优性原理启发我们从最后一步逐步向前推的方法来求解，也就引入了动态规划方法，实践证明许多问题用动态规划求解比用线性规划或非线性规划更加有效，特别是对离散性问题，运用解析数学无法解决，而动态规划就成为得力的工具。动态规划方法把一个比较复杂的问题分解为一系列同一类型的更容易求解的子问题，计算过程单一化便于应用于计算机。先按照整体最优思想逆序求出各个可能状态的最优策略，然后顺序求出整个问题的最优策略和最优路径。由于把最优化应用到每个子问题上，就系统的删减去了所有中间非最优方案使得计算量比穷举法大大减少。将动态规划思想应用到求解运输问题的最短路径中，方法简便，理论可靠，求解结果清晰明了，在实际运用中取得了良好的效果。
建模
（1）将实际问题的过程划分成恰当阶段，确定阶段变量。
根据多阶段决策问题的实际过程，将其划分为若干个相互独立又相互联系的部分每一个部分为一个阶段，划分出的每一个阶段通常就是需要做出一个决策的子问题。阶段通常是按决策进行的时间或空间上的先后顺序划分的，阶段变量用表示。
（2）确定状态，正确选择状态变量。
在多阶段决策过程中，状态是描述每个阶段所必须的信息，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态，用一个或一组变量来描述，状态变量必须既能描述过程的演变，又要满足无后效性。用n表示第n个阶段的状态变量。
（3）确定决策变量及允许的决策集合。
决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态做出的选择。决策变量用xk表示；允许的决策集合是决策变量的取值范围用Dk(sk）表示。
（4）写出状态转移方程。
状态转移方程sk+1=TK（sk，xk），这里的函数关系TK 因问题的不同而不同，如果给定第k个阶段的状态变量sk，则该阶段的决策变量xk一经确定，第k+1 阶段的状态变量的值也就可以确定。
（5）列出指标函数。
指标函数vkn的关系，并要求具有可分离性及递推性；
（6）写出动态规划函数基本方程，用fk(sn+1）表示k-n 阶段的最优策略函数：
fn+1 (xn+1）=0（边界条件）fk(sk)=opt｛vk+fk+1｝， k=n， n-1，…，1。
解：如图1 所示，节点A 表示发送点，节点E 表示终到点，其余节点为运输过程中可经由点，边线表示可能路径，边线上数值表示其间运输成本。利用动态规划模型并求解运输过程中的最短路径。

首先根据网络图以及上节提到的建模方法我们可以将运输过程划分成四个阶段，阶段变量用k 表示；状态变量sk表示k阶段初可能的位置；决策xk表示k阶段初可能选择的路线；状态转移方程sk+1=sk-xk； 阶段指标vk表示k阶段与所选择的路段相应的路长； 指标函数vkn=i=kkvi表示k 至4 阶段的总路长；fk表示第k 阶段点sk到终点E 的运输成本；递推公式fk=min｛vk+fk+1｝，k=4，3，2，1；xk* 表示最优决策；边界条件k=5时，f5=0。将动态规划的计算结果列表表示，如表1所示。
计算结果列表
K
S(k)
X(k)
V(k)
V=V0+F(_K+1)
F(k)
X(k)
4
D1
D2
E
E
3
4
3+0
4+0
3
4
E
E
3
C1
C2
C3
D1
D2
D1
D2
D1
D2
1
4
6
3
3
3
1+3
4+4
6+3
3+4
3+3
3+4
4
7
0
D1
D2
D1
2
B1
B2
B3
C1
C2
C3
C1
C2
C3
C1
C2
C3
7
4
6
3
2
4
4
1
5
4+7
7+4
6+6
3+4
2+7
4+6
4+4
1+7
5+6
11
7
8
C1,C2
C1
C1,C2
1
A
B1
B2
B3
2
4
3
2+11
4+7
3+8
11
B2,B3

由表1 中我们可以清晰地看出，距离最低的路线为A B2 C1D1 E 或A B3C1 D1`E 或A B3C2 D2 E ，最短距离为11。