数学建模在计算机专业的应用

1、.应用一图论算法图论在计算机处理问题中占有重要地位， 现实中的很多问题最终都可以转化成图论问题， 或者要借助图结构来存储和处理。 但是怎么把一图存入计算机就要涉及到数学建模的知识。比如下面一图：如果要求出从节点 v1 到节点 v5 的所有路径，就可以借助计算机来很轻松的解决。 但前提条件是， 必须要把图以一种计算机可以理解的形式存进去，即要把它抽象为数学问题。在此，我们需要定义一些关于图的概念，以便更好的描述问题。边与顶点的关系有如下几种典型情况：简单图 ：无自回环，无重边的图。页脚.无向图 ：边没有指向，（ e） =vi,vi=vivi. 此时称边 e与顶点 vi,vi关联，称i212i21

2、1顶点 v i1 与顶点 vi 2 邻接。uuuuur有向图 :边有指向，（ei ）=（vi 1 ,v i2）=vi1 vi 2 .下面是具体涉及到图如何存储的问题：1. 图 G(V,E)的关联矩阵 R=(r ij )nx m ，若 G(V,E)为无向图，0v与e不关联ijr1v与 e关联 , e为非自回环ijijj2vi与 ej 关联 , ej 为自回环0v 与e不关联ijrij1vi 是ej的起点若 G(V,E)为有向图，v是e2的终点ij因此该图可以用关联矩阵表示出来，如下所示11000001010100R0101001这样，我们就可以以矩阵的形式将图存入计00110100000111算

3、机页脚.2. 邻接矩阵图 G(V,E)的邻接矩阵 A=(a ij ) n xn ,若 G(V,E)为无向图， aij = 从vi 到的 vj 边数，若不邻接，取 0；若 G(V,E)为有向图， aij = 从 vi 到 vj 的有向边数，若无，取 0.0110010011A100110110101110应用二动态规划问题动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。 20 世纪 50 年代初美国数学家等人在研究多阶段决策过程的优化问题时， 提出了著名的最优化原理， 把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法动态规划。也是

4、信息学竞赛中选页脚.手必须熟练掌握的一种算法。 多阶段决策过程的最优化问题。 含有递推的思想以及各种数学原理（加法原理，乘法原理等等） 。动态规划一般可分为线性动规， 区域动规，树形动规，背包动规四类。举例线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；树形动规：贪吃的九头龙， 二分查找树，聚会的欢乐，数字三角形等；背包问题： 01 背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶。多阶段决策的实际问题很多， 下面通过具体例子， 说明什么是动态规划模型中数学建模知识的运用。最短路线问题：某工厂需要把一批货物从

5、城市 A 运到城市 E，中间可经过 B1 、 B2 、B3 、C1、C2、 C3、D1、D2 等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A 到 E 的距离最短？页脚.B6C113845D1564A89B27C22E661D3738C33B37下面引进几个动态规划的基本概念和相关符号。(1)阶段 (Stage)把所给问题的过程， 按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解， 阶段总数一般用字母n 表示，用字母 k 表示阶段变量。如例中(最短路线问题 )可看作是 n=4 阶段的动态规划问题， k=2 表示处于第二阶段。(2)状态 (Sta

6、te)状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量，常用字母 sk 表示第 k 阶段的状态变量，状态变量的取值围称为状态集，用Sk 表示。如例 l 中，第一阶段的状态为A（即出发位置）。第二阶段有三个状态：B1 、B2、 B3 ，状态变量 s2 =B2 表示第 2 阶段系统所处的位置是B2 。第 2 阶段的状态集S2= B 1 、B2、B3。动态规划中的状态变量应具有如下性质：当某阶段状态给定以后， 在这个阶段以后过程的发展不受这个阶段以前各个阶段状态的影响。也就是说，未来系统页脚.所处的状态只与系统当前所处的状态有关，而与系统

7、过去所处的状态无关，即过去历史只能通过当前的状态去影响它未来的发展，这种特点称为无后效性 （又称马尔可夫性）。如果所选定的状态变量不具备无后效性，就不能作为状态变量来构造动态规划模型。 如例 1 中，当某阶段的初始状态即所在的城市选定以后，从这个状态以后的运货路线只与这个城市有关，不受以前的运货路线影响， 所以是满足状态的无后效性的。（3）决策 (Decision)当系统在某阶段处于某种状态，可以采取的行动（或决定、选择），从而确定下一阶段系统将到达的状态，称这种行动为决策。 描述决策的变量， 称为决策变量。常用字母u k(sk)表示第 k 阶段系统处于状态sk 时的决策变量。决策变量的取值围

8、称为决策集，用Dk(sk)表示。在例 l 的第二阶段中，若从状态B2 出发，可以做出三种不同的决策，其允许的决策集为 D2(B2)= C 1、 C2、C3，决策 u 2(B2)= C 2 表示第二阶段处于状态B2，选择的确行动下一阶段是走到C2 。（4）策略 (Policy)系统从第k 阶段的状态sk 开始由每阶段的决策按顺序组成的决策序列 uk(sk )，u k+1(sk+1 )， ，u n(sn )称为一个策略（ k=1,2, ，n）,记作 pk,n (sk ) 。在例 l 中， p2,4(B2)= u 2(B2 )= C2， u3 (C2)= D 1，u 4(D1)=E是一个策略，表示第

9、二阶段从状态 B2 出发，沿着 B2 C2 D1 E 的方向走到终点。注意策略必须是一串实际可行的序列行动。页脚.（5）状态转移方程系统由这一阶段的 个状态进行决策后转变到下 阶段的另 个状态称为状态转移，状态转移既与状态有关， 又与决策有关， 描述状态转移关系的方程称为状态转移方程，记为：sk+1 =T k(sk， uk)它的实际意义是当系统第k 阶段处于状态 sk 做决策 uk 时，第 k+1 阶段系统转移到状态 sk+1 。状态转移方程在不同的问题中有不同的具体表现形式，在例l 中，状态转移方程表示为： sk+1 =u k(sk)。（6）阶段指标阶段效益是衡量系统阶段决策结果的一种数量指

10、标，记为：vk (sk , uk )表示系统在第k 阶段处于状态sk 做出决策 uk 时所获得的阶段效益。这里的阶段效益在不同的实际问题中有不同的意义。在例 l 中它表示两个中转站的距离，如 v2 (B2 ,u2 (B2 ) C2 ) d (B2, C2 ) 7 表示从中转站 B2 走到中转站 C2 之间的距离为7。更一般地有 vk (sk ,uk ( sk )d (sk , uk ( sk ) 。（7）指标函数指标函数是用来街量所实现过程的优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的确定的数量函数，记为：Vk ,n (sk ,uk , sk 1 ,uk 1 ,L , sk ,

11、 uk )k1,2,L ,n页脚.它应具有可分离性，并满足递推关系式：Vk ,n (sk , uk , sk 1 , uk 1 ,L , sk ,uk )sk , uk ,Vk 1,n (sk 1, uk 1 ,L , sk ,uk )常见的指标函数的形式是：1）过程和任一子过程的指标是它所包含的各阶段指标的和。既nLv j ( sj ,u j ) vk (sk , uk ) Vk 1,n (sk 1 ,uk 1 ,L, sk , uk )Vk,n (sk ,uk , sk 1, uk 1 , , sk , uk )j 12）过程和任一子过程的指标是它所包含的各阶段指标的积。既nVk,n (s

12、k , uk , sk 1, uk 1 ,L , sk ,uk )v j ( sj , u j )vk ( sk ,uk ) Vk 1,n (sk 1, uk 1 ,L , sk ,uk )j 1（8）最优值函数指标函数的最优值，称为最优值函数，记为f k (sk ) 。它表示系统在第 k 阶段处于状态 sk 时按最优策略行动所获得总的效益。既fk ( sk )opt Vk ,n ( sk ,uk , sk 1 ,uk 1,L , sk , uk )pk , n ( sk )其中 opt 是最优化（ optimization ）的缩写，根据实际问题可取 max(最大值 ) 和 min(最小值

13、), opt 表示对所有允许策略 pk , n ( sk ) 使后面算式取最优。p k ,n (sk )下面利用动态规划的逆推归纳法， 将例 1 从最后一个城市E 逐步推算到第一个城市 A，在此 fk (sk ) 表示第 k 阶段从城市 sk 到城市 E 最短路。1)当 k=4 时：要求 f 4 (s4 ) ，由于第 4 阶段只有两个城市D1、 D2（即 s4 的取值为 D1 、D2），从 D1 到 E 只有一条路，故 f 4 ( D1 )d (D1 , E)4, u4 * ( D1 )E ，同理f4 (D2 )d ( D2 , E)3, u4* (D2 )E 。页脚.2)当 k=3时： s的

14、取值为 C 、C、C ，从 C 出发到 E 有两条路，一条是经31231过 D1到 E，另一条是经过 D2到 E ，显然：f(C )d (C1 , D1 ) f 4 (D1 )min3 4*(C )Dmin7, u31d (C1 , D2 ) f 4 (D2 )5 3311即从 C1 出发到 E 的最短路为7，相应决策为 u3* (C1)D1 ，最短路线是 C1D1E。同理f3 (C2 )d (C2 , D1 ) f 4 ( D1)6 45,u3* (C2 ) D2d (C2 , D2 ) f4 (D2 )2 3f3 (C3 )d (C3 , D1) f 4 ( D1 )1 45,u3* (C

15、3 ) D1d (C3 , D2 ) f4 ( D2 )3 32)当 k=2时： s2 的取值为 B1、B2 、B3，从 B1 出发到 E 有三条路，分别是经过 C、C、C到 E，则有：123d (B1, C1) f3 (C1 )6 7f2 (B1 )d (B1, C2 ) f3 (C2 )4 59,u2* (B1 ) C2d (B1, C3 ) f3 (C3 )5 5d( B2 , C1 ) f3 (C1)8 7同理f 2 ( B2 )d( B2 , C2 )f3 (C2 )7511,u2*(B2)C3d( B2 , C3 ) f3 (C3 )6 5d(B3 ,C1) f 3 (C1 )7 7f2 (B3 )d(B3 ,C2 )f 3 (C2 )8512,u2* (B3)C3d(B3, C3 )f 3 (C3 )752)当 k=1 时：s1 的只有一个取值为A. 从 A 出发到 E 有三条路，分别是经过B 、B