最短路径问题的实际应用

子任务4.1　最短路径问题的实际应用

4.1.1　任务引入

【任务4-1】　某汽车物流公司要承担从A市到E市的大批汽车运输，从A市到E市之间要经过B，C，D3个地区，B地区有3个城市，C地区有3个城市，D地区有两个城市，问如何选择由A市到E市的运输路线，根据各点间的运输成本，求运费最低廉的运输路线。

图4-1　运输路线图

我们将上述问题可分为4个阶段，第一阶段：从A到B₁，B₂或B₃；第二阶段：从B₁到C₁，C₂或C₃，或从B₂到C₁，C₂或C₃，或从B₃到C₁，C₂或C₃；第三阶段：从C₁到D₁，D₂，或从C₂到D₁，D₂，或从C₃到D₁、D₂；第四阶段：从D₁或D₂到E。每个阶段都要做出一个决策，决定向哪个点前进。各阶段的决策有机地联系着，本阶段的决策影响着下一阶段的决策，以至于影响整体效果，决策者在做决策时，不应仅考虑本阶段最优，还应考虑对最终目标的影响。各阶段的决策形成一个决策序列，序列不同，其效果也不同。该问题就是在允许的策略中，求出A到E的距离最短的策略。

4.1.2　任务分析

动态规划英文名称为“DynamicProgramming”，简称DP，它是规划论的重要内容，同时也是运筹学的一个重要分支。其主要是解决多阶段决策过程最优化问题的一种理论和方法。目前已广泛应用于工程技术、经济管理、工业生产及军事等部门，特别是在动态系统的最优控制方面获得了显著的效果。

规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的。然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。

所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优策略，以便得到最佳效果。动态规划与前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，其必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。

动态规划的主要创始人是美国数学家贝尔曼。20世纪40年代末50年代初，当时在兰德公司从事研究工作的贝尔曼首先提出了动态规划的概念。1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法。1957年贝尔曼出版了他的第一部著作《动态规划》，标志着运筹学这一重要分支的诞生。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展作出了重大的贡献，其中最值得一提的是爱尔思和梅特顿。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔、威尔德一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质作出了巨大的贡献。

动态规划从创立到现在50多年来，无论在工程技术、企业管理还是在工农业生产及军事等部门都有广泛的应用，并获得了显著的效果。在管理方面，动态规划可用于资源分配问题、最短路径问题、库存问题、背包问题、设备更新问题、最优控制问题，等等。所以动态规划是现代管理学中进行科学决策不可或缺的工具。

动态规划的优点在于，它把一个多维决策问题转化为若干个一维最优化问题，而对一维最优化问题一个一个地去求解，这种方法是许多求极值方法所做不到的，它几乎优于所有现存的优化方法。除此之外，动态规划能求出全局极大或极小，这一点也优于其他优化方法。需要指出的是，动态规划是求解最优化问题的一种方法，是解决问题的一种途径，而不是一种新的算法。在前面我们学习了用单纯形求解线性规划问题，凡是具有线性规划问题那样统一的数学模型都可以用单纯形法去求解，而动态规划问题的求解却没有统一的方法（类似于单纯形法）。因此在用动态规划求解最优化问题中，必须对具体问题具体分析，针对不同的问题，使用动态规划的最优化原理和方法，建立起与其相对应的数学模型，然后再用动态规划的方法去求解。根据动态规划这些特点，要求我们在学好动态规划的基本原理和方法的同时，还应具有丰富的想象力，只有这样才能建好模型求出问题的最优解。

4.1.3　知识构建

1）动态规划基本思想

动态规划是解决多阶段决策问题的一种方法。它可按时间或空间把问题分为若干个相互联系的阶段。在每一阶段都要做出选择（决策），这个决策不仅仅决定着这一阶段的效益，而且决定着下一阶段的初始状态，从而决定整个过程的走向（从而称为动态规划）。每当一阶段的决策确定之后，就得到一个决策序列，即策略。所谓多阶段决策问题就是求一个策略，使各个阶段的效益总和达到最优。

为了具体阐述动态规划的基本思想和它的基本特点，并引进动态规划的术语，我们首先来看一个关于动态规划的经典案例。

【案例】

驿站马车问题

驿站马车问题是为说明动态规划而特地提出的一个问题，其大意是：一个神秘的美国推销员在一百多年前乘着驿站马车经过印第安地区向西旅行。虽然推销员旅程的起点和目的地是固定的，但在途中要经过哪些州，他却有相当大的选择余地。

此推销员是一个谨慎的人，十分关心他在这次旅程中的安全。在经过一番思考后他想到了一个相当巧妙的办法来确定他的最安全途径。人身保险当时是欢迎驿站马车乘客投保的。因为每张保险单的收费是在审核估量该行程的安全程度后订出，所以最安全的途径应当是人身保险单最低廉的途径。

于是他找来了各相邻州之间乘驿站马车旅行的人身保险价格表，虽然两州间的最小保险费用一目了然，但如何安排路线才能使从起点至终点的保险总费用达到最小？

驿站马车问题的提出，为动态规划问题的抽象结构提供了一种按字义的物理解释。所以，要判明其系统可否作为一个动态规划问题来构成，一个办法就是注意该系统在基本结构上与驿站马车问题是否相类似。

显然任务4-1是一个标准的动态规划问题，我们赋予其两点间的运输成本（图4-2），然后讨论一下如何选择路线，以使运输总费用最低？（也可直接称为最短路问题）

如何解决这个问题呢？如果用穷举法，则从A到E一共有3×3×2=18条不同的路径，逐个计算每条路径的长度，总共需要进行4×18=72次加法计算；对18条路径的成本做两两比较，找出其中最短的一条，总共要进行18-1=17次比较。

图4-2　A市运到E市运输路线图

以上求从A到E的最短路径问题，可以转化为3个性质完全相同，但规模较小的子问题，即分别从B₁，B₂，B₃到E的最短路径问题。

记从B_i（i=1，2，3）到E的最短路径为S（B_i），则从A到E的最短距离S（A）可以表示为：

同样，计算S（B₁）又可以归结为性质完全相同，但规模更小的问题，即分别求C₁，C₂，C₃到E的最短路径问题S（C_i）（i=1，2，3）；而求S（C_i）又可以归结为求S（D₁）和S（D₂）这两个子问题。从图4-2可以看出，在这个问题中，S（D₁）和S（D₂）是已知的，它们分别是：

S（D₁）=5，S（D₂）=2

因而，可以从这两个值开始，逆向递归计算S（A）的值。计算过程如下：

即　S（C₁）=8　　 　　且如果到达C₁，则下一站应到达D₁；

　　S（C₂）=7　　　 　且如果到达C₂，则下一站应到达D₂；

　　S（C₃）=12　　　　且如果到达C₃，则下一站应到达D₂。由此，可以计算S（B_i）：

即　S（B₁）=20　　　　且如果到达B₁，则下一站应到达C₁；

　　S（B₂）=14　　　　且如果到达B₂，则下一站应到达C₁；

　　S（B₃）=19　　　　且如果到达B₃，则下一站应到达C₂。由此，可以计算S（A）：

最后，可以得到：从A到E的最短路径为A→B₂→C₁→D₁→E。即按此路线，运输成本最低。计算过程及结果，可用图4-3表示。由图4-3可知，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。

图4-3　A市运到E市运输路线计算图

以上过程，仅用了18次加法，11次比较，计算效率明显高于穷举法。

2）动态规划的基本概念

（1）阶段与阶段变量

阶段是指问题需要做出决策的步数，也就是把所给问题的整个过程，恰当地分为若干个既相互联系又相互区别的子过程，以便能够按照一定的次序去求解。阶段总数常记为n，相应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变量，k=1，2，…，n。k既可以是顺序编号，也可以是逆序编号，通常采用顺序编号。任务4-1中把问题从中间站B，C，D，用空间位置分成4个阶段，阶段用阶段变量k来描述，k=1，表示第一阶段，k=2，表示第二阶段，依次类推。

（2）状态与状态变量

每一阶段的左端点（初始条件）集合称为本阶段的状态（即开始的客观条件，或称阶段初态，比如资源量、地理位置等）。它描述所研究问题过程的状况，是不可控因素。在任务4-1中，状态就是某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某支路的终点。通常一个阶段有若干状态，状态变量取值的集合称为状态集合，用S_k表示。第一阶段只有一个状态就是点A，表示为S₁=｛A｝，第二个阶段有3个状态，表示为S₂=｛B₁，B₂，B₃｝，第三阶段有3个状态，表示为S₃=｛C₁，C₂，C₃｝，第四阶段有两个状态，表示为S₄=｛D₁，D₂｝。

描述过程状态的变量称为状态变量，它可以用一个数、一组数或者一个向量（多维情形）来描述。常用小写s₁，s₂，s₃，……表示第一，第二，第三……阶段的状态变量。当处在状态C₂时，我们可记s₃=C₂，第k阶段的状态常用状态变量s_k表示。

动态规划中的状态具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。即过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。

（3）决策与决策变量

当过程处于某一阶段的某个状态时，可以作出不同的决定（或者选择），从而决定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，它可以用一个数、一组数或者一个向量（多维情形）来描述。

常用u_k（s_k）表示第k阶段当状态处于s_k时的决策变量，它是状态变量的函数。在实际问题中，决策变量的取值往往被限制在某一范围，此范围被称为允许决策集合。一般来说，用D_k（s_k）表示第k阶段从状态s_k出发的允许决策集合，显然有u_k（s_k）∈D_k（s_k），它相当于线性规划中的约束条件，决策变量的取值可以是离散的，也可以是连续的。

任务4-1中当处于C₂状态时，下一步怎么走？如何选择路线？即如何决策？是走向D₁，还是走向D₂？其允许决策集合D₃（C₂）=｛D₁，D₂｝，当过程处于某一阶段的某一状态时，可以做出不同的决策（或选择），从而确定下一阶段的状态，这种决定（或选择）称为决策。如果选择D₂，记u₃（C₂）=D₂，也就是说，当处于C₂状态时，下一步的决策为D₂。或者说D₂是在决策u₃（C₂）=D₂作用下的一个新的状态。

（4）策略与最优策略

策略就是决策者按阶段依次所做的决策序列。通常把从第k阶段s_k状态开始到终止状态的决策序列，称为k后部子策略，简称为k子策略，记做p_kn（s_k），即

p_kn（s_k）=｛u_k（s_k），u_k+1（s_k+1），…，u_n（s_n）｝

把从第一阶段即s₁阶段状态开始的子策略称为全策略，简称为策略，记做p_1n（s₁），有

p_1n（s₁）=｛u₁（s₁），u₂（s₂），…，u_n（s_n）｝

如任务4-1中每一阶段产生一个决策，4个阶段的决策就构成一个决策序列：u₁（s₁），u₂（s₂），u₃（s₃），u₄（s₄）称为一策略。这里的最短路径即为最优策略，动态规划就是在允许策略集中选最优策略。

（5）状态转移方程

状态转移方程是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，是描述由第k阶段到第k+1阶段状态转移规律的关系式。动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k段的状态s_k，本阶段决策为u_k（s_k），则第k+1阶段的状态S_k+1由公式

确定，称为状态转移方程，T_k称为状态转移函数。

（6）指标函数与最优指标函数

用于衡量所选定策略优劣的数量指标称为指标函数，相当于动态的目标函数。最后一个阶段的目标函数就是总的目标函数，它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态s_k出发，采用决策u_k时的效益，用d_k（s_k，u_k）表示。

从第k阶段到第n段的决策过程称为原过程的一个后部子过程。V_kn（s_k，u_k，u_k+1，…，u_n）k=1，2，…，n表示从第k阶段的状态s_k出发，选择决策u_k，u_k+1，…，u_n所产生的原过程的指标函数值。动态规划要求过程指标具有可分离性，即

V_kn（s_k，u_k，u_k+1，…，u_n）=d_k（s_k，u_k）+V_k+1（s_k+1，u_k+1，…，u_n）

称指标具有可加性，或

V_kn（s_k，u_k，u_k+1，…，u_n）=d_k（s_k，u_k）×V_k+1（s_k+1，u_k+1，…，u_n）

称指标具有可乘性。

过程指标函数也可表示为从第k阶段的某状态出发，采取子策略p_kn=｛u_k，u_k+1，…，u_n｝时所得到的阶段效益之和：

最优指标函数是指从第k阶段状态s_k采用最优策略到过程终止时的最佳效益值，用f_k（s_k）表示。即

其中opt可根据具体情况取max或min。

在不同问题中指标函数的含义是不同的，可能是距离、利润、成本、产品或资源的消耗等。在任务4-1中，指标函数V_k，n表示在第k阶段，从状态s_k出发至终点E的距离。用d（s_k，u_k）表示在第k阶段由点s_k到点s_k+1的距离。例如：d（C₂，D₁）是指由C₂出发，下一阶段的决策是D₁的两点间的距离。即d（C₂，D₁）=6。f₂（B₁）表示从B₁到E的最短距离。整个问题即为f₁（A）值为多少。

3）动态规划的基本模型

在任务4-1求最短路的问题中我们知道，从某一状态出发寻求最优选择时，它是从下述所有可能的组合中进行优化选取的：将本阶段决策的指标效益值加上从下阶段开始采取最优策略时的指标效益值。这是一种递推关系式，在这种递推关系中包含了动态规划的最优化原理。即“作为整个过程的最优策略应具有这样的性质，无论过去的状态和决策如何，对于前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”，也就是说最优策略的任一子策略都是最优的。

根据这个原理写出的计算动态规划问题的递推关系式称为动态规划的基本方程。

上述方程中f_n+1（s_n+1）=0为边界条件，或称终端条件。即问题从最后一个阶段向前逆推时需要确定的条件。边界条件的值要根据问题的条件来决定。对于可加性指标函数，其值一般为0，对于可乘性指标函数，其值一般为1。即f_n+1（s_n+1）=1。

上述方程即为动态规划的基本模型。给一个实际问题建立动态规划模型时，必须做到：

①将问题的过程划分成恰当的阶段；

②正确选择状态变量s_k，使它既能描述过程的演变，又要满足无后效性；

③确定决策变量u_k（s_k）及每阶段的允许决策集合D_k（s_k）；

④正确写出状态转移方程；

⑤正确写出指标函数V_kn的关系。

这5点是构造动态规划模型的基础。一个问题的动态规划模型是否正确给出，它集中反映在恰当的定义最优值函数和正确地写出递推关系式及边界条件上。

动态规划方法有逆序和顺序解法之分，其基本方程这里我们就不详细说明，在后面将通过例题予以介绍。

4）动态规划模型的分类

根据时间变量是离散的还是连续的，把动态规划问题的模型分为离散决策模型和连续决策模型；根据决策过程的演变是确定性的还是随机性的，动态规划问题的模型又可分为确定性决策模型和随机性决策模型。因此有离散确定性的动态规划模型、连续确定性的动态规划模型、离散随机性的动态规划模型和连续随机性的动态规划模型四大类。

此外有些决策过程的阶段数是固定的，称为定期的决策过程；有些决策过程的阶段数是不固定的或可以有无限多阶段数，分别称为不定期或无期的决策过程。

本教材介绍的主要是离散确定性的动态规划模型。

4.1.4　任务实施

在图4-2中，线路的起点A与终点E是固定不变的，从A点到E点的路线有多条，但最短路线只有一条。其寻找最短路径的方法是从最后一段开始，用从后向前逐步递推的方法，求出各点到E点的最短路线，最后求得由A点到E点的最短路线。即从终点逐段向始点方向寻找最短的路线。如果规定从起点到终点为顺行方向，则从终点至起点为逆行方向，那么这种由终点开始从后向前的计算方法我们称为逆序解法。

根据上述基本概念，我们对任务4-1运用逆序解法进行问题的实施。

步骤一　分阶段建立模型

将问题分成4个阶段，第k阶段到达的具体地点用状态变量s_k表示，例如：s₂=B₃，表示第二阶段到达位置B₃，等等，这里状态变量取字符值而不是数值。

将决策定义为到达下一站所选择的路径，例如目前的状态是s₂=B₃，这时决策允许集合包含3个决策，它们是

D₂（s₂）=D₂（B₃）=｛B₃→C₁，B₃→C₂，B₃→C₃｝

最优指标函数f_k（s_k）表示从目前状态s_k到E的最短路径。终端条件为

f₅（s₅）=f₅（E）=0

其含义是E点就是最终的端点。

在求解的各个阶段要利用第k段和第k+ 1段的如下递推关系：

步骤二　递推过程

第四阶段的递推方程为：

从f₅（x₅）到f₄（x₄）的递推过程用表4-1表示：

表4-1

其中标有“*”表示最优值，在上表中，由于决策允许集合D₄（x₄）中的决策是唯一的，因此这个值就是最优值。

由此得到f₄（s₄）的表达式。由于这是一个离散的函数，取值用列表4-2表示。

表4-2

第三阶段的递推方程为：

从f₄（s₄）到f₃（s₃）的递推过程见表4-3。

表4-3

由此得到f₃（s₃）的表达式见表4-4。

表4-4

第二阶段的递推方程为：

从f₃（s₃）到f₂（s₂）的递推过程见表4-5。

表4-5

由此得到f₂（s₂）的表达式见表4-6。

表4-6

第一阶段的递推方程为：

从f₂（s₂）到f₁（s₁）的递推过程见表4-7。

表4-7

由此得到f₁（s₁）的表达式见表4-8：

表4-8

步骤三　结论

从表达式f₁（s₁）可以看出，从A到E的最短路径长度为19。由f₁（s₁）向f₄（s₄）回溯，得到最短路径为：

A→B₂→C₁→D₁→E