数学建模在计算机专业的应用.docx
《数学建模在计算机专业的应用.docx》由会员分享，可在线阅读，更多相关《数学建模在计算机专业的应用.docx（9页珍藏版）》请在冰点文库上搜索。
数学建模在计算机专业的应用
应用一图论算法
图论在计算机处理问题中占有重要地位，现实中的很多问题最终都可以转化成图论问题，或者要借助图构造来存储和处理。
但是怎么把一图存入计算机就要涉及到数学建模的知识。
比方下面一图：
如果要求出从节点v1到节点v5的所有路径，就可以借助计算机来很轻松的解决。
但前提条件是，必须要把图以一种计算机可以理解的形式存进去，即要把它抽象为数学问题。
在此，我们需要定义一些关于图的概念，以便更好的描述问题。
边与顶点的关系有如下几种典型情况：
简单图：
无自回环，无重边的图。
无向图：
边没有指向，
此时称边
与顶点
关联，称顶点
与顶点
邻接。
有向图:
边有指向，
下面是具体涉及到图如何存储的问题：
1.图G（V,E）的关联矩阵
，假设G（V,E）为无向图，
假设G（V,E）为有向图，
因此该图可以用关联矩阵表示出来，如下所示
这样，我们就可以以矩阵的形式将图存入计算机
2.邻接矩阵
图G（V,E）的邻接矩阵
假设G（V,E）为无向图，
=从
到的
边数，假设不邻接，取0；假设G（V,E）为有向图，
=从
到
的有向边数，假设无，取0.
应用二动态规划问题
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
也是信息学竞赛中选手必须熟练掌握的一种算法。
多阶段决策过程的最优化问题。
含有递推的思想以及各种数学原理〔加法原理，乘法原理等等〕。
动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例
线性动规：
拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：
石子合并，加分二叉树，统计单词个数，炮兵布阵等；
树形动规：
贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：
01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶。
多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型中数学建模知识的运用。
最短路线问题：
某工厂需要把一批货物从城市A运到城市E，中间可经过B1、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下列图所示，问应该选择一条什么路线，使得从A到E的距离最短？
6
3
845
564
98
72
63
671
83
7
下面引进几个动态规划的根本概念和相关符号。
（1）阶段（Stage）
把所给问题的过程，按时间和空间特征划分成假设干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。
如例中（最短路线问题）可看作是n=4阶段的动态规划问题，k=2表示处于第二阶段。
（2）状态（State）
状态表示每个阶段开场时系统所处的自然状况或客观条件，它描述了研究问题过程状况。
描述各阶段状态的变量称为状态变量，常用字母sk表示第k阶段的状态变量，状态变量的取值围称为状态集，用Sk表示。
如例l中，第一阶段的状态为A〔即出发位置〕。
第二阶段有三个状态：
B1、B2、B3，状态变量s2=B2表示第2阶段系统所处的位置是B2。
第2阶段的状态集S2={B1、B2、B3}。
动态规划中的状态变量应具有如下性质：
当某阶段状态给定以后，在这个阶段以后过程的开展不受这个阶段以前各个阶段状态的影响。
也就是说，未来系统所处的状态只与系统当前所处的状态有关，而与系统过去所处的状态无关，即过去历史只能通过当前的状态去影响它未来的开展，这种特点称为无后效性〔又称马尔可夫性〕。
如果所选定的状态变量不具备无后效性，就不能作为状态变量来构造动态规划模型。
如例1中，当某阶段的初始状态即所在的城市选定以后，从这个状态以后的运货路线只与这个城市有关，不受以前的运货路线影响，所以是满足状态的无后效性的。
〔3〕决策（Decision）
当系统在某阶段处于某种状态，可以采取的行动〔或决定、选择〕，从而确定下一阶段系统将到达的状态，称这种行动为决策。
描述决策的变量，称为决策变量。
常用字母uk（sk）表示第k阶段系统处于状态sk时的决策变量。
决策变量的取值围称为决策集，用Dk（sk）表示。
在例l的第二阶段中，假设从状态B2出发，可以做出三种不同的决策，其允许的决策集为D2（B2）={C1、C2、C3}，决策u2（B2）=C2表示第二阶段处于状态B2，选择确实行动下一阶段是走到C2。
〔4〕策略（Policy）
系统从第k阶段的状态sk开场由每阶段的决策按顺序组成的决策序列{uk（sk），uk+1（sk+1），…，un（sn）}称为一个策略〔k=1,2,…，n〕,记作
。
在例l中，p2,4（B2）={u2（B2）=C2，u3（C2）=D1，u4（D1）=E}是一个策略，表示第二阶段从状态B2出发，沿着B2→C2→D1→E的方向走到终点。
注意策略必须是一串实际可行的序列行动。
〔5〕状态转移方程
系统由这一阶段的—个状态进展决策后转变到下—阶段的另—个状态称为状态转移，状态转移既与状态有关，又与决策有关，描述状态转移关系的方程称为状态转移方程，记为：
sk+1=Tk（sk，uk）
它的实际意义是当系统第k阶段处于状态sk做决策uk时，第k+1阶段系统转移到状态sk+1。
状态转移方程在不同的问题中有不同的具体表现形式，在例l中，状态转移方程表示为：
sk+1=uk（sk）。
〔6〕阶段指标
阶段效益是衡量系统阶段决策结果的一种数量指标，记为：
表示系统在第k阶段处于状态sk做出决策uk时所获得的阶段效益。
这里的阶段效益在不同的实际问题中有不同的意义。
在例l中它表示两个中转站的距离，如
表示从中转站B2走到中转站C2之间的距离为7。
更一般地有
。
〔7〕指标函数
指标函数是用来街量所实现过程的优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上确实定的数量函数，记为：
它应具有可别离性，并满足递推关系式：
常见的指标函数的形式是：
1〕过程和任一子过程的指标是它所包含的各阶段指标的和。
既
2〕过程和任一子过程的指标是它所包含的各阶段指标的积。
既
〔8〕最优值函数
指标函数的最优值，称为最优值函数，记为
。
它表示系统在第k阶段处于状态sk时按最优策略行动所获得总的效益。
既
其中opt是最优化〔optimization〕的缩写，根据实际问题可取max（最大值）和min（最小值）,
表示对所有允许策略
使后面算式取最优。
下面利用动态规划的逆推归纳法，将例1从最后一个城市E逐步推算到第一个城市A，在此
表示第k阶段从城市sk到城市E最短路。
1）当k=4时：
要求
，由于第4阶段只有两个城市D1、D2〔即s4的取值为D1、D2〕，从D1到E只有一条路，故
，同理
。
2）当k=3时：
s3的取值为C1、C2、C3，从C1出发到E有两条路，一条是经过D1到E，另一条是经过D2到E，显然：
即从C1出发到E的最短路为7，相应决策为
，最短路线是C1→D1→E。
同理
2）当k=2时：
s2的取值为B1、B2、B3，从B1出发到E有三条路，分别是经过C1、C2、C3到E，那么有：
同理
2）当k=1时：
s1的只有一个取值为A.从A出发到E有三条路，分别是经过B1、B2、B3到E，那么有：
于是得到从A到E的最短距离17，为了找出最短路线，按计算的顺序逆推回去，可得到最优策略为：
，最短路线是A→B1→C2→D2→E。
升级会员 