数学建模作业

数学建模首次作业。

题目：动态规划最短距离。

数学建模。问题：最短路线，下图为路线网络，边上数字为两点间的距离，现求从a到e的最短路线。

问题的分析：

a到e有18条不同的路，如果阶段数增加，则路的条数也增加，用穷举法显然不可取，而用动态规划只需计算其中一部分便可求出a到e的最短路线。

阶段：根据时间和空间将问题划分为若干个有关联的阶段，用k表示阶段变量，n表示总的阶段数。如图根据空间划分成四个阶段。

状态：从某阶段出发的位置。它既是该段支路的起点，又是前一段某支路的终点，通常一个阶段包含了若干个状态，如题中四个阶段的状态集合分别为，，。

描述状态的变量称为状态变量，极为sk。题中四个阶段的状态集合就是相应的四个状态变量sk（k=1,2,3,4）的取值集合。

决策：当阶段和状态给定后，从该阶段到下一阶段某的状态的选择。描述和决策的变量称为决策变量，记为xk或xk（sk），它表示第k阶段处于状态sk是的采取的决策，是状态sk的函数。

决策变量的取值范围称为允许决策集合，记为xk行货xk（sk）,即xk∈xk。如题中从b1出发有三种选择，若选择下一步到c1，有x2(b2)=c1;若选择到c2，则有x2（b1）到c3。即有x2（b1）∈x2（b2）=。

状态转移方程：描述状态转移规律的函数关系sk+1=t（sk,xk）.

当sk和 xk取定后，sk+1的取值就随之确定。

策略：各阶段所确定的策略构成的决策序列，即。目的是从众多的策略中选出最优策略，记为。

从第k个阶段开始到终点的决策序列称为k子策略。题中为一策略。

报酬函数：当构成处于状态sk时，采取策略sk时所得到的报酬（或费用），通常记为vk（sk，xk）.如题中的vk为第k阶段到第k+1阶段两点间的路程。

目标函数：衡量策略好坏的函数。从第k阶段的sk出发到终点的目标函数记为。

vkn=vkn（sk，xk，…，xn），最优目标函数值记为。

fk*（sk）=opt vkn（sk，xk，…，xn），k=1,2, …n。

最优化原理：从题中可以看出，a→b2→c1→d1→e是a到e的最短路线，则b2→c1→d1→e是从b2出发到e的最短路线，c1→d1→e是从c1出发到e的最短路线。即作为整个过程的最优策略具有如下的性质：

无论过去的状态和策略如何，对前面策略所形成的某确定状态而言，余下的策略必须构成最优子策略。这就是动态规划的最优化原理。利用此原理，可以把多阶段决策问题的求解过程看成一个连续的递推过程，由后向前逐步推算。

这相当于把原问题化成许多互相有连续的比原问题简单的子问题，在求解每个子问题时，均利用它的后部子问题的最优化结果，依次向前推进，最后一个子问题的最优化解就是原问题的最优解。

数学模型：先利用最优化原理求题中的最短路线，再归纳出数学模型。

第4阶段：

f4*（d1）=v4（d1，e）=3

得最优决策x4*（d1）：d1→ e。

f4*（d2）=v4（d2，e）=4

得最优决策x4*（d2）：d2→ e。

第3阶段：

f3*（c1）=min

minmin=4

得最优决策x3*（c1）：c1→ d1；

f3*（c2）=min

minmin=7

得最优决策x3*（c2）：c2→ d2；

f3*（c1）=min

minmin=6

得最优决策x3*（c3）：c3→ d1；

同理，可推得第2阶段和第1阶段的最优决策。

第2阶段：f2*（b1）=min=11，x2*（b1）：b1→ c1或b1→ c2；

f2*（b2）=min=7，x2*（b2）：b2→ c1或b2→ c2；

第1阶段：f1*（a）=min=11，x1*（a）：a→ b2或a→ b3。

最后，由第1阶段到第4阶段的最优决策，可得到最短路线三条：

1 a→b2→c1→d1→e

2 a→b3→c1→d1→e

3 a→b3→c2→d2→e

最短路程：f1*（a）=11.

数学建模作业

数学建模作业

数学建模作业

数学建模作业

其他用户还读了