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

1、=J最利用动态规划法求解运输问题的最短路径分析：针对最短路径问题，最容易想到的方法是穷举法，即列出所有 可能发生的方案和结果，针对要求进行比较求出最优方案，对于简单 变量少的问题还是可行的，但是对于复杂变量多的问题计算工作量就 比较大。最短路径的最优性原理启发我们从最后一步逐步向前推的方 法来求解，也就引入了动态规划方法，实践证明许多问题用动态规划 求解比用线性规划或非线性规划更加有效，特别是对离散性问题，运 用解析数学无法解决，而动态规划就成为得力的工具。动态规划方法 把一个比较复杂的问题分解为一系列同一类型的更容易求解的子问 题，计算过程单一化便于应用于计算机。先按照整体最优思想逆序求 出

2、各个可能状态的最优策略，然后顺序求出整个问题的最优策略和最 优路径。由于把最优化应用到每个子问题上，就系统的删减去了所有 中间非最优方案使得计算量比穷举法大大减少。将动态规划思想应用 到求解运输问题的最短路径中，方法简便，理论可靠，求解结果清晰 明了，在实际运用中取得了良好的效果。建模（1）将实际问题的过程划分成恰当阶段，确定阶段变量。根据多阶段决策问题的实际过程，将其划分为若干个相互独立又 相互联系的部分每一个部分为一个阶段，划分出的每一个阶段通常就 是需要做出一个决策的子问题。阶段通常是按决策进行的时间或空间 上的先后顺序划分的，阶段变量用表示。（2）确定状态，正确选择状态变量。在多阶段决

3、策过程中，状态是描述每个阶段所必须的信息，表示 每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态， 用一个或一组变量来描述，状态变量必须既能描述过程的演变，又要 满足无后效性。用n表示第n个阶段的状态变量。（3）确定决策变量及允许的决策集合。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对 下一阶段状态做出的选择。决策变量用xk表示；允许的决策集合是决 策变量的取值范围用Dk （sk）表示。（4）写出状态转移方程。状态转移方程sk+1 =Tk（sk，xk），这里的函数关系Tk因问题 的不同而不同，如果给定第k个阶段的状态变量sk，则该阶段的决策 变量xk 一经确定，第k+1

4、阶段的状态变量的值也就可以确定。（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表示终到点，其余节点为运输过程中可经由点，边线表示可能路径，边线上数值表示 其间运输成本。利用动态规划模型并求解运输过程中的最短路径。n4首先根据网络图以及上节提到的建模方法我们可以将运输过程划分成四个阶段，阶段变 量用k表示；状态变量林表示k阶段初可能的位置；决策匕

5、表示k阶段初可能选择的路线；状 态转移方程sk+1=sk-xk；阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数 vkn=富表示k至4阶段的总路长；fk表示第k阶段点sk到终点E的运输成本；递推公式 fk=minvk+fk+1，k=4, 3, 2, 1； xk*表示最优决策；边界条件k=5时，f5=0。将动态规 划的计算结果列表表示，如表1所示。计算结果列表KS(k)X(k)V(k)V=V0+F(_K+1)F(k)X(k)4D1D2E33+04+03E3C1C2C3D1D2D1D2D1D241+34+46+33+43+33+44D1D2D12B1B2B3C1C2C3C1C2C3C1C2C374+7 7+4 6+63+42+74+64+4 1+7 5+611C1,C2C1C1,C21AB1B222+1