运筹学最短路径范文

导语：如何才能写好一篇运筹学最短路径，这就需要搜集整理更多的资料和文献，欢迎阅读由公务员之家整理的十篇范文，供你借鉴。

篇1

［关键词］动态规划；最优性原理；无记忆性；记忆性

在运筹学的分支体系中，动态规划因其应用的广泛性而占有十分重要的地位。但动态规划仅仅是解决某类特殊的多阶段决策问题的一种方法，不具有统一的数学模型和算法步骤[1]，而且概念多，因此学生普遍反应“动态规划真的有用但确实难学”。本文以最短路问题为案例，对动态规划相关概念、最优性原理、无记忆性等进行了阐释。

一、案例的选择

可用动态规划求解的问题很多，如最短路、资源分配、生产与存储等，而最短路问题因其空间特征明显，易于划分阶段、易于描述每阶段开始和结束时的状态，以及在每个状态之下做出的决策、每次决策产生的决策指标值等，因此，对初学者而言，最易接受和理解的例子还是最短路问题。本文以最短路问题作为引例，帮助学生们理解和掌握动态规划的相关概念及基本方程、最优性原理等。

二、相关概念的解释

动态规划相关概念繁多，从阶段、状态开始，到过程指标函数，刚接触时，不少学生感到一头雾水，十分茫然。而借助于最短路问题，将动态规划的相关概念与最短路问题中大家耳熟能详的名称相对应，则十分有助于学生对动态规划基本概念的把握。

三、最优性原理的解释教材[1]

对最优性原理作了如下表述：无论过去的决策和状态如何，对前面的决策所形成的当前状态而言，余下的决策序列必须构成最优策略，即最优策略的子策略总是最优的。

四、无记忆性与记忆性

在动态规划一章中，教师经常会提到“无记忆性”与“记忆性”两个看似完全矛盾的概念，不少学生也感到十分茫然。其实，这两个概念在动态规划中得到了完美的统一。“无记忆性”指的是可用动态规划方法求解的多阶段决策问题，在划分阶段时，状态必须满足的一个特性，也称为无后效性或马尔科夫性。其实质是：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。即“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。[1]“记性性”指的是用动态规划方法求解多阶段决策问题时（以逆序为例），为求得第K步最优子策略fk（Sk），必须先计算出从第K＋1阶段的各状态出发所对应的最优子策略fk＋1（Sk＋1），并由第K＋1步的最优子策略fk＋1（Sk＋1）去求取第K步最优子策略fk（Sk）。这些后续状态对应的最优子策略实际上构成了一张查找表（LookupTable）。[3]为更好地理解无记忆性与记忆性，仍以最短路问题为例进行说明。假设有一个可分为10个阶段的最短路问题，每阶段有10个状态可供选择。“无记忆性”指的是当游客在第k阶段处于状态Sk时，则该游客从Sk出发到终点的最短路径（K步最优子策略）只与Sk相关，而与Sk之前的状态、决策无任何关系。“记忆性”指的是当用动态规划方法求解最短路问题时，第K步最优子策略是由第K步的决策和第K＋1步的最优子策略共同决定的，而第K＋1步的最优子策略已在之前求出并存放于内存之中，这就是记忆性。动态规划的记忆性可节省大量的计算时间，但会占用较多的计算机内存，即常用的“空间换时间”策略。以上题为例，10个阶段每阶段10个状态的最短路问题，如果采用穷举法，则需要计算的路径条数（相当于动态规划中的全策略）为109条，每条路径需要进行10次加法运算；在109条路径中找出最短路径需要进行109－1次比较运算，则总的基本运算是11＊109－1次。而采用动态规划方法时，每阶段的每个状态需要进行10次加法运算和9次比较运算，则总的基本运算次数为1539次（其中加法运算810次，比较运算729次），和穷举法比较可节省大量的计算时间。从该例题的分析可知，一个多阶段决策问题之所以可采用有“记忆性”的动态规划方法求解，恰恰是因为该问题在划分阶段时，各阶段的自然特征（即状态）满足“无记忆性”。因此，我们说，“记忆性”与“无记忆性”在动态规划中得到了完美的统一。

五、结束语

经教学实践证明，在动态规划教学中以最短路为引例，有利于学生对动态规划相关概念的理解，尤其有利于学生掌握最优性原理和无记忆性、记忆性这些晦涩难懂的原理与性质，为学生学好、用好动态规划打下了良好基础。

［参考文献］

［1］胡运权.运筹学教程（第四版）［M］．北京：清华大学出版社，2012：191-232．

［2］［M］．普林斯顿大学出版社，1957：58-92．

［3］北京：人民邮电出版社，2008：744-754．

［4］《运筹学》教材编写组.运筹学（第三版）［M］．北京：清华大学出版社，2005：194-215．

篇2

关键词：最短路径，Dijkstra算法，优化

 

最短路径问题是指在一个非负权值图中找出两个指定节点间的一条权值和最小的路径，是一类受到普遍重视和研究的网络优化问题，广泛应用于计算机科学、交通工程、通信工程、运筹学等众多领域。实际生活中的许多问题都可归结为最短路径问题。邮政自动分拣机、计算机网络结点上的路由选择、人工智能游戏设计、交通咨询系统等都是最短路径问题的现实应用。由于带权图中权值所代表的意义不同，最短路径也不仅仅局限于地理意义上的距离最短，还可以引申为最少费用、最短时间、延时最短、吞吐量最大等[4]。

Dijkstra算法是典型的最短路径算法，用于计算一个结点到其他所有结点的最短路径。。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。Dijkstra算法的基本思想是以源点为圆心，按最短路径长度递增的顺序通过对路径长度迭代得到从源点到其他各目标结点的最短路径。

1 Dijkstra算法原理

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算非负权值图中一个结点到其他所有结点的最短路径，是一个非常经典的贪心算法例子。。基本思想是：把带权图中所有结点分成两组，第1组包括已确定最短路径的结点，第2组为未确定最短路径的结点。按最短路径长度递增的顺序逐个把第2组的结点加入第1组中，直到从源点出发可到达的所有结点都包含在第1组中[2]。

2 Dijkstra算法描述

根据Dijkstra算法的基本思想，引入如下状态变量：

1）辅助向量D，可用数组实现，其每一个分量D[i]用来存放源点到其他结点的最短路径长度；

2）集合V和S，其中V集合用来存放未确定最短路径的结点，S集合用来存放已确定最短路径的结点。S的初始状态为空集，V则包含带权图中的所有结点。

3）辅助变量path_matrix，可用二维数组实现，用来记录源点到其他各个结点的最短路径所经过的顶点。

由于Dijkstra算法是按照最短路径长度递增的顺序逐个确定源点到各个结点的最短路径的，所以源点到各结点的最短路径或者是源点到此结点的弧，或者是中间只经过已确定了最短路径的顶点（即S集合中的结点）而最终到达此结点的路径。

根据以上分析，得到如下的算法描述[1]：

1）初始化集合V、S，同时利用带权图的邻接矩阵arcs初始化数组D，即若源点到相应结点有弧，对应的分量取值为弧上的权值，否则对应的分量取值为∞；

2）选择D中最小的数组分量，假设为D[i]，则i就是已求得源点到其最短路径的终点，故将S=S∪{i},即将已确定最短路径的结点i加入S集合；

3）根据结点i修改更新数组D中源点到集合V-S中的结点k所对应的分量，即若D[i]+arcs[i][k]<D[k]，则D[k]=D[i]+arcs[i][k]；

4）重复2）、3）操作，直至所有的结点确定最短路径，即集合V为空。

对下图G施行Dijkstra算法，假设源点V1，求解V1到其他各个结点的最短路径。

图G

假设源点为v1，则第一个选择的顶点是v1，路径长是0，D[]={0，50，10，∞，16}；

Step1 S={v1}，V={v2，v3，v4，v5}，S点集扩充，v3为下一个最短路径顶点，路径长为10，D[]={0，50，10，25，16}；

Step2 S={v1，v3}，V={v2，v4，v5}，S点集扩充，v5为下一个最短路径顶点，路径长为16，D[]={0，50，10，21，16}；

Step3 S={v1，v3，v5}，V={v2，v4}，S点集扩充，v4为下一个最短路径顶点，路径长为21，D[]={0，41，10，21，16}；

Step4 S={v1，v3，v4，v5}，V={v2}，S点集扩充，v2为下一个最短路径顶点，路径长为41，D[]={0，41，10，21，16}；

Step5 S={v1，v2，v3，v4，v5}，V={}，V点集为空，结束算法。至此，得到从源点到其他各个结点的最短路径。

3 Dijkstra算法优化策略分析

Dijkstra算法是计算最短路径的经典算法,但在实际使用过程中，该算法耗费大量的计算时间和存储空间，在某些实际应用中产生冗余。所以需要进行优化。在评判一个算法优劣时，通常研究该算法的时间复杂度和空间复杂度。可见，可以从影响Dijkstra算法效率的关键“存储空间和时间效率”进行优化。

3.1 权值排序优化策略

问题：S集合中未确定最短路径的顶点无序存放在数组中，每一次选择权值最小的弧段必须将所有未选择顶点对应的数组元素完全扫描才能找到，在数据量较大的情况下，计算速度受到严重制约。

优化策略：将要扫描的结点按其对应弧的权值进行顺序排列，每循环一次即可得到符合条件的结点，大大提高了算法的执行效率[5]。

3.2 A*算法优化策略

问题：Dijkstra算法基于广度优先搜索策略，即从源点出发，通过权值迭代遍历所有其他结点后，最后得到从源点到其他各结点的最短路径。整个搜索好似一个圆形向外展开，直到到达目的地，这样的搜索方式是盲目的。很明显这样求解一定能找到最优解，但节点展开的数量和距离成级数增加，会导致大量无效点的搜索，大大的降低搜索的效率。

优化策略：采用改进的Dijkstra算法——A*算法。A*算法是人工智能运用在游戏中的一个重要实践,它主要是解决路径搜索问题。A*算法实际是一种启发式搜索。。所谓启发式搜索，就是利用一个估价函数judge（）评估每次决策的价值，决定先尝试哪一种方案。这样可以极大地优化普通的广度优先搜索。从Dijkstra算法到A*算法是判断准则的引入，如果这个判断条件不成立，同样地，只能采用Dijkstra算法。所以A*算法中的估价函数是至关重要[3]。

3.3 扇形优化策略

问题：Dijkstra算法的搜索过程好似以源点为圆心的一系列同心圆向外展开，搜索过程中没有考虑到终点所在方向或位置，搜索是盲目的。这样导致大量的无用临时结点被反复搜索，成为实际应用中的瓶颈。

优化策略：从尽量减少最短路径分析过程中搜索的临时结点数量，限制范围搜索和限定方向搜索考虑进行优化。那么这种有损算法是否可行呢？我们知道，现实生活中行进，不会向着目的地的相反方向行进，否则就是南辕北辙。所以，当所研究的网络可以抽象化为平面网络的条件下，也不必搜索全部结点，可以在以源点到终点所在直线为轴线的扇形区域内搜索最短路径。这样，搜索方向明显地趋向终点，提高了搜索速度，虽然抛弃了部分结点，但基本上不影响搜索的成功率[5]。

3.4 邻接点优化策略

问题：Dijkstra算法在提取最短路径结点时需要访问所有的未确定最短路径的结点，算法的时间复杂度为O（n2），如果只希望找到从源点到某一特定的终点的最短路径也不例外。结点数n越大，算法的计算效率和存储效率越低。

优化策略：只对最短路径上结点的邻接点作处理，不涉及其他结点。即（1）只从源点的邻接点集合中选择权值最小的结点作为转接点，将此转接点加入已确定最短路径的结点集合S中；（2）对此转接点的邻接点集合与S的差集中的结点的权值进行更新；（3）从S中所有结点的邻接点集合的并集与S的差集中选择权值最小的结点作为下一个转接点，并将此转接点加入S中。重复（2），（3）操作，直至所有的结点确定最短路径。优化算法在更新最短路径值与选择最短路径值最小的结点时，仅仅涉及相关结点的邻接点集合及S集合中所有结点的邻接点集合与S集合的差集，时间复杂度取决于转接点的邻接点的数量多少，减少了计算次数与比较次数[4]。

4 总结

在详细分析求解最短路径问题的经典算法Dijkstra算法的基础上，针对Dijkstra算法存在的问题介绍了几种优化策略。Dijkstra算法在不同的现实应用中，可以具体情况具体分析，从而得到算法的高效率实现。

参考文献：

[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，1997，186～190.

[2] 谢柏青，佘晓歌. 算法与数据结构[M]. 北京：高等教育出版社，2001，230～232.

[3] 陈益富，卢 潇，丁豪杰. 对Dijkstra算法的优化策略研究[J]. 计算机技术与发展，2006，16（9）：73～75.

[4] 章永龙. Dijkstra最短路径算法优化[J]. 南昌工程学院学报，2006，25（3）：30～33.

[5] 胡树玮，张修如，赵 洋.扇形优化Dijkstra算法[J]. 计算机技术与发展，2006，16（12）：49～51.

篇3

关键词： 智慧旅游； 导览； 线路规划； 个性化游览线路

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2016）20?0092?05

Abstract： Personalized tour route planning is one of cores of intelligent guiding to visitors， and the formalizing denotation of the information of scenic regions and view spots is the fundament of personalized automatic planning of touring routes. A method of generating the route automatically is given in this paper for automatic planning of touring route based on directed graph， H?RVT and users′ preference. On the basis of analyzing the related factors， a method of how to express the information of scenic regions and view spots is given in this paper. A expressive method of view spot information is proposed according to the table of maximum relative price. An automatic planning method of personalized tour route is offered， which considers the selection of start point， end point， view spots and visiting time control. The method of formal representation for scenic regions， view spots and routing generation provide a theory support for realization of route planning.

Keywords： wisdom tourism； guiding to visitor； rout planning； personalized tour route

0 引 言

智能导览是智慧旅游研究与建设的关键内容之一，也是物联网技术的重要应用[1?2]。参观游览路线是否科学合理在很大程度上影响到整个游览过程的用户体验。对游客而言，科学合理的游览路线能够使其在较短的时间、较小的路程代价下获得较好的游览体验，同时，对旅游服务提供者来说，高效的游览路线也能使得相同服务资源代价的情况下获得游客更高的服务评价，从而促进旅游及其服务业的健康持续发展和进步[3?4]。

实际情况下，游客的游览时间有限，不足以完整地游览当前景区中所有的景点。游客的真实需求是在有限的时间内个性化地对当前景区内景点进行游览。因此，如何安排游览路线，成为智能导览系统中急需解决的一大问题，生成的游览路线是否可行有效且满足游客的偏好，对用户体验至关重要。

游览路线的规划设计工作本质是依据游客当前的位置信息和待参观的景区景点信息，根据一定的策略筛选合适的路线和景点，并将之有序排列在具体游览行程路线的过程中。完整的游览路线应当包括起点、景点集合、景点间的路径集合以及终点。因此，对景区内最佳游览路线问题模型的建立以及路线生成策略的设计是决定游览路线优劣程度的关键所在。

面向智能导览的个性化线路自动规划本质上是解决在有限约束下的最短路径应用问题，它是运筹学、地理信息学以及计算机网络等学科中的研究热点，比如求单源且无负边权的“一对多”的Dijkstra算法[5]、用于求多源且无负权边的“一对一”最短路径的Floyd算法[6]、求多个备选优化路径的K最短路径算法[7]以及静态路网中较为有效的“直接搜索”A*算法[8]等。同时，随着经典图论和计算机数据结构的有效结合，使得各类最短路径算法不断涌现以解决不同特征的实际问题，它们在时间复杂度、空间复杂度、应用范围以及易实现等性能上各具特色[9?10]。国内有学者专门就最短路径算法的分类体系以及研究进展[11]方面进行过较为全面的总结与研究分析。文献[12]提出了一种利用线图以及顶点赋权图的最优完全子图的方案解决中国邮递员问题中如何生成最优邮递路线的问题。该方法与通常图的相关概念的区别在于其为图中的节点（也称顶点）赋加了权值，最终求出一条能访问到图中所有节点且具有最小权值的环游。文献[13]提出了一种解决图中受K顶点数限制的所有最短路径BCSP算法以及其改进的ICSP算法，运用图的广度遍历算法以及逆邻接表、指针等数据结构知识生成扩展最短路径树。

1 问题背景

在游览过程中，以有限的时间条件为前提，从游客需求的角度出发，有如下三点直观的要求：优先参观景区内游览价值大的景点；要求所步行的路程最少，即花费在步行过程中的时间短；在不超出限定时间的前提下，尽可能充分地利用限定的时间。

以现实中大量游客对景区的参观游览行为过程的总结为基础，描述游客游览某一景区的一般活动流程为：

Step1：根据当前的位置寻找到该景区最近的入口，从入口处进入景区。

Step2：若游览时间足够长，则从当前位置开始按距离的远近开始按序游览景区内景点，直至景区内所有景点都游览完毕，结束游览活动。若时间有限，不能完整游览整个景区内所有景点，则执行Step3。

Step3：以当前位置为参考，在限定时间内，选择相对游览价值最高的未被游览的景点（即该景点知名度高且对其进行游览花费时间少）。

Step4：步行到达待参观的景点并花费一定时间完成对该景点的参观。此时，检查剩余时间是否可继续游览活动。若剩余时间可继续游览活动，则返回Step3，若剩余时间无法满足继续游览要求，则执行Step5。

Step5：从当前景点位置行至距离最近的景区出口，离开景区结束对该景区内景点的游览，完成本次游览活动。

因此，解决最佳游览路线生成问题需要完成工作为：

（1） 寻找或设计最短路径算法，以无向图中任意某一节点为起点，根据其余节点的权值、价值以及该节点与其余各节点之间的最短路径，得到在当前位置状态下，满足时间限制条件的最佳下一个待游览节点。

（2） 当需要游览的节点集合选定之后，在无向图[G]中根据边信息以及边的权值数据确定最佳的游览路线，生成选定节点集合中节点的最终游览序列。

2 景区模型抽象与景点属性表示

2.1 建立无向图处理模型

旅游景区由多个出入口、内部景点集、公共服务点及内部相互之间的路径组成，游览路线的生成工作即根据约束条件按序选择合适的景点集合与路径集合。本文以无向图作为景区及景点的表示模型，将景区相关信息抽象成如图1所示附加节点值的带边权的无向图模型。

由图1可知，将某景区的平面示意图转换为无向图[G]，将景区中的景点以及出入口转换为无向图[G]中的顶点，景点之间的路径转换为无向图中的边。

定义1：无向图[G]由一个二元组[V，E]组成，其中集合[V]称为无向图[G]的节点集合，记为[V={v0，v1，v2，…，vn}，（n∈N*）]，[V]中每个元素对应代表实际景区中一个景点；集合[G]称为无向图[G]的边集，是由集合[V]中的元素组成的无序对[vi，vjvi∈V，vj∈V]组成，记为[E=ei，jei，j=vi，vj或ei，j=vj，vi，vi∈V，vj∈V，][E]中每个元素表示实际情况下景区景点之间的一条路径。

2.2 景点信息表示策略

2.2.1 节点相对价值

在无向图[G]中，以[vi]为起点，[vj]为终点的一条路径[px（vi，vj）]的定义，以及该路径的路径代价[Wpx（vi，vj）]的定义。一般情况下，从节点[vi]出发到节点[vj]的路径并不惟一，并且不同的路径代价一般各不相同。根据每条路径的路径代价大小，节点[vi]到节点[vj]的所有路径的集合[Pij]中必定存在一条路径代价最小的路径。

对表1的几点说明：

（1） 目标节点表示以节点[vi]为起点出发需要达到的节点。节点vi的相对价值表中目标节点中包含无向图[G]中除vi以外的所有节点。

（2） 路径时间代价表示vi与目标节点之间最短路径之中所有路径的权值之和，即从vi出发达到目标节点过程中经过的路径所用的路程时间。

（3） 节点时间代价表示目标节点的时间代价，即游览目标节点对应景点所需要的时间。

（4） 节点价值表示目标节点的价值，为目标节点对应景点的自身固有价值。

（5） 是否已加入路线标记目标节点，是否已经被加入到最佳路线中，1代表该目标节点已加入到最佳路线中，0代表未加入。

（6） 最大相对价值表示目标节点在以[vi]为起点的情况下的最大相对价值。在最佳路线的生成过程中，优先选择表[H-RVT（vi）]中相对价值高的目标节点加入到最佳路线中。

在表示景点和路径信息的无向图[G]中，所有节点都有其最大相对价值表，每一张表中都包含了以该节点为起点，到其他所有节点的最大相对价值。

3 条件约束与个性化路线生成

游览时间分为路程中花费的时间以及对景点进行参观游览花费的时间，游览价值取决于路线中所有景点的价值高低。从宏观上描述最佳游览路线的要求为“在限定的时间内，最高效地利用有限的时间，寻找游览价值最高游览路线”；从路线生成过程中描述最佳游览路线的要求为“保证每次加入到游览路线中的景点都是当前条件下最值得游览的景点”。

3.1 路线起点选择

3.3 路线终点选择

生成最佳路线的整个流程，首先生成最佳路线的起点，也就是选择进入景区的入口；第二步是生成最佳游览路线的主要内容，不断的在为图中未加入最佳路线的节点集合中按照加入之后的“效益”大小的顺序以及是否满足时间限制条件来选择下一个最值得加入路线；当图中未加入最佳路线的节点集合中没有满足时间限制条件的节点时，为最佳路线按照选择终点，即选择离开景区的出口，生成完整的最佳路线并输出结果。

4 结 论

本文针对在有限时间生成最佳游览路线的问题，从游客的实际需求分析着手，设计了使用无向图数学模型，总结出在时间限定条件下影响景点与路径选择的三个主要因素，并根据分析结果为每个节点生成各自H?RVT表，从而成功实现了生成最佳的游览路线。

参考文献

[1] OWAIED H H， FARHAN H A， AL?HAWAMDEH N， et al. A model for intelligent tourism guide system [J]. Journal of applied sciences， 2011， 11（2）： 342?347.

[2] GAVALAS Damianos， KENTERIS Michael. A web?based pervasive recommendation system for mobile tourist guide [J]. Personal and ubiquitous computing， 2011， 15（7）： 759?770.

[3] 廖川荣.校园最佳游览路线问题的数学模型分析[J].大学数学，2012，28（6）：78?82.

[4] 姜西瑞.基于GPS和GSM/GPRS的定位系统的设计与实现[D].北京：中国科学院计算机技术研究所，2006.

[5] 章永龙.Dijkstra最短路径算法优化[J].南昌工程学院学报，2006，25（3）：30?33.

[6] 赫自军，何尚录.最短路问题的Floyd算法的若干讨论[J].重庆工学院学报（自然科学版），2008，22（5）：156?159.

[7] 徐涛，丁晓璐，李建伏.K最短路径算法综述[J].计算机工程与设计，2013，34（11）：3900?3906.

[8] 刘浩，鲍远律.A*算法在矢量地图最优路径搜索中的应用[J].计算机仿真，2008，25（4）：253?257.

[9] ZHAN F B， NOON C E. Shortest paths algorithms： an evaluation using real road networks [J]. Transportation science， 1998， 32（1）： 65?73.

[10] CHERK ASSKY B V， GOLDBERG A V， DIZK T R A. Shortest paths algorithms： theory and experimental evaluation[J]. Mathematical programming， 1996， 73（2）： 129?174.

[11] LU Feng. Shortest path algorithms： taxonomy and advance in research [J]. ACAT geodaetica cartographica， 2001， 30（3）： 269?275.

篇4

关键词：管理；运筹学；教学改革

中图分类号：G642.3 文献标识码：A 文章编号：1002-4107（2013）08-0050-02

运筹学是一门集应用数学和形式科学为一体的跨领域学科，它利用统计学、数学模型和算法等优化方法，去寻找复杂问题中的最佳或近似最佳的结果。它也是管理类专业的一门重要专业基础课，其主要教学目的是使学生掌握各种模型及其求解方法，为今后解决实际决策优化问题打下扎实的基础。因此，做好运筹学的课堂教学对管理类专业的学生做好学习铺垫至关重要。

一、运筹学课堂教学现状

课堂教学是教育教学中普遍使用的一种手段，它是教师给学生传授知识和技能的全过程，也是教学的主要渠道。它主要包括教师讲解，学生问答，教学活动以及教学过程中使用的所有教具，而“教师讲解”环节占整个过程的比重最大。在现阶段运筹学课堂教学中，主要存在以下几个问题。

（一）学生主动意识薄弱

长期以来，在传统教育思想影响下，通常把教师当做教学的主体，把学生当做客体，过分强调教师的权威性，而在一定程度上忽视了学生作为学习主体的存在；过分强调了知识传授的灌输性，而忽视了师生之间的互动性，这样的形式削弱了学生主动参与学习的积极性，容易导致知识掌握不牢固的结果，影响教学的有效性。

（二）差等生难以融入课堂

现代的高等教育已经发展到大众教育阶段，同一个班级的学生的学习兴趣、学习欲望、学习成绩有很大的差别，学习不良、成绩落后的学习障碍学生人数比重大为增加，这会直接影响整个班级的学习氛围。运筹学对数学底子薄、注意力不集中的学生来讲，很容易脱离课堂教学节奏，最后放弃学习，站到“差等生”的队列。因此，控制差等生的比重或提高差等生的学习积极性对改善整体学习状况非常有利。

（三）学习效果评价手段单一

现阶段运筹学教学结果的评价一般采用传统的闭卷笔试的考试方式，其中尤以期终考试卷面成绩为主，占80%―100%。导致学生将学习重点放在对知识的死记硬背上，难以将其“活学活用”。

二、管理类运筹学课堂教学改革实践

（一）教学目标定位

联合国教科文组织提出，21世纪的教育支柱，即是学会求知，学会做事，学会共处，学会做人。在这些人类生存所必须具备的素质中，学会做人最重要。因此，教师在教学中不仅要让学生掌握课程中的知识点，还要注重对学生学习方法及学习兴趣的培养、创新能力的培养以及人格的教育。

（二）教学内容优化

运筹学是一门具有较多分支的学科，因课时限制，教师在教授课程中不可能做到面面俱到，对教学内容，应坚持适用性的原则适当调整：难度较大、应用性不强的内容，应少讲或不讲；对于纯理论的数学推导可以少讲，会运用其推导结论即可；应用性较强的内容应多讲、详讲。例如，对数据包络分析、非线性规划、动态规划等较复杂的内容可以不讲；对存贮论、对策论等让学生理解原理、能运用结论即可；物流管理专业的授课对运输问题、图与网络分析可详讲，并适当加深难度；工程管理专业的授课应增加网络计划的内容。

（三）教学模式改革

1.让学生成为课堂的主人。在教学实践中，多创造机会让学生参与教学，成为课堂的主人。教师在教学中可以通过与学生互换角色来调动其学习主动性、积极性，达到良好的学习效果。教师将教学内容分为简单的、复杂的两类，复杂的由教师自己讲授，简单的则分给愿意承担的学生，这样就把学生当作了教学的主体，学生在这种压力情况下会将课前预习的效果发挥到极致。鼓励学生之间的合作，进行团队学习，承担不同的角色，如PPT制作，黑板板书，卡片制作、上台讲析等，各自发挥长处，并且能够培养团队精神。如运筹学中图与网络分析、网络计划前面的基本知识部分就可以通过这种形式进行教学，在学生的教学活动结束时教师再做适当的补充。

课堂练习题等也可以作为学生参与教学的部分，可以让更多的学生参与其中，通过自己的尝试，体会讲课的过程才会更加理解教师的劳动成果，更加用心听课，形成良性循环；学生参与课堂练习的分析也会促进课后复习的效果。如在单纯形法、指派问题等章节中鼓励学生评讲课堂练习题或者课后习题；让学生参与期末课程总复习的指导。

2.全员参与式教学。成绩处于中上水平的学生比较配合教师的教学，能够紧跟课堂教学的节奏，而成绩靠后的学生则很难融入进来。在课堂教学中应该让差等生也能参与其中，改善班级整体学习氛围。在这种情况下，可以通过黑板板书、画图等比较简单的形式让成绩略差、缺乏学习热情的学生也能参与到课堂教学中，并对他们进行适当表扬，提高他们的学习兴趣，逐渐脱离“差等生”的队伍。

篇5

关键词：蚁群算法；物流配送；路径优化；数学模型

DOIDOI：10.11907/rjdk.161974

中图分类号：TP319

文献标识码：A 文章编号文章编号：16727800（2016）011014004

基金项目基金项目：

作者简介作者简介：袁文涛（1993-）男，安徽马鞍山人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为模式识别与智能系统；孙红（1964-）女，上海人，上海理工大学光电信息与计算机工程学院副教授、硕士生导师，研究方向为模式识别与智能系统、 控制理论与控制工程、企业信息化系统与工程。

0 引言

解决组合优化问题的最优化求解算法有多种现代人工智能算法方案，优化算法用来处理问题最优解的求解，该问题通常由多个变量共同决定。当前，求解最短路径问题是图论研究中的一个典型求解组合优化算法问题，旨在寻找图表（由节点和路径构成）中两节点或多节点之间的最短路径。常用的最优化路径求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蚁群算法。这些算法都有自身的优点和不足。在对不同算法作出比较后，可以得出蚁群算法在解决网络路由和城市交通系统的问题中是相对有利的。

就目前研究来看，随着实际组合问题的变化，基本的智能算法已经不能满足解决这类组合优化问题，同时其优势也在减弱[1]。本文采取改进后的组合优化蚁群算法以弥补传统蚁群算法易陷入局部最优解的不足，加快了求全局最优解的构造速率。

蚁群算法（Ant Colony Optimization， ACO），是一种模拟蚂蚁群体智能行为的进化仿生类优化算法，在求解性能上具有强鲁棒性、优良的分布式计算能力、便于与其它算法相结合等优点[2-3]。通常作为一种用来在多变量组合优化问题的多候选解中寻找最优化路径的机率型算法。它由Marco Dorigo于1992年在其博士论文《Ant system： optimization by a colony of cooperating agents》中首先提出，其灵感来源于通过对蚁群社会的长期跟踪观察后发现，虽然单个蚂蚁没有视力、智慧程度低、工作方式简单，但它们却有强大的执行能力和协同工作能力，依靠复杂群体的自组织协同能力发挥出超出单个个体累加的智能，是一种超个体（superorganism，又称超有机体）存在现象。蚁群是在这样的超个体案例中最有名的例子。虽然蚁群算法的严格理论基础和实际应用尚未成熟，国内外相关研究暂处于实验阶段，但这并不妨碍人们对蚁群算法的研究已经由当初单一的解决商旅问题（TSP）发展到解决调度问题、网络通信等多个方向的最优化求解应用。

目前，蚁群优化算法已广泛应用于多种求组合最优化问题，在面临路例如作业安排调度问题和路由车辆的二次分派问题上表现出了良好的性能，也经常被用来求旅行推销员问题的拟最优解。它在图表动态变化情况问题的求解上相比萤火虫算法和遗传算法具有绝对优势：蚁群算法的最大优点在于可以连续运行并适应实时变化；缺陷是在处理较大规模和复杂数据问题时，容易存在运算耗时长、收敛速度慢、得不到全局最优解等问题。

在求最优解的历次迭代中，单个蚂蚁会根据给定的规则和限定条件选择从一个城市（节点）转移到另一个城市（节点）：它必须对所有城市访问一次，而相对距离越远的城市被选中为下一个访问点的机会越少（能见度低）；相反，在两个城市（节点）边际的一边形成的信息素越浓烈，则该边际作为路径被选择的概率越大；在较短路程情况下，短时间内更多蚂蚁会在所有走过的路径上留下更多信息素，在每次迭代更新后，信息素轨迹浓度会按百分比挥发从而反馈给下一只途经的蚂蚁并影响它作出路径选择。

1 车辆路径问题

传统的车辆路径问题也叫VRP（Vehicle Routing Problem）问题，是关系到现代物联网发展过程中物流配送系统的一个关键问题，属于NP难题。一直以来，该问题也是管理科学和物流运输方面的重要课题[4]，受到国内外学者的广泛关注。

VRP问题描述如下：在一些由于经济或者地理限定的条件约束下，组织一个车队，从一个或者多个初始点出发，规定达到多个不同的地点，设计一个成本最小、路程最短的路线集，使得：① 每个城市只能被一辆车访问，只访问一次；②所有送货车辆必须从起始点出发再回到起始点；③某些特定的约束条件需要被满足。

VRP的数学模型表示如下：一共有k个客户，第i个客户的货物需求为gi，配送中心派出车辆承担运输任务，其载重为q。设gi

如果前提有约束条件用于车辆本身，即容量限制和总长限制，则称为有能力约束的车辆路径问题（Capacitated Vehicle Routing Problem）。此模型是车辆路径问题的基本模型，这类VRP问题叫作CVRP问题[5]。

设每个客户点只允许被访问一次，车辆所访问的客户点的需求总和不能超过车辆的负载能力，且总行驶的路程也不得超过其最大的行驶距离，达到用最少的车辆最短的路径完成既定任务。

。

2 可约束蚁群算法实现

2.1 算法实现方式

当前蚁群算法领域存在MPDACO局部更新和MPDACO全局更新两种方式。前者指当单个蚂蚁从一个节点到达下一个节点完成转移后就立刻更新蚂蚁通过路径时所留下的的信息素，后者是当蚂蚁遍历完所有给定节点后再更新整条路径上的信息素，不再是对所有的蚂蚁，而是仅对全局最优的蚂蚁得到的路径使用。从两种更新方式得到的结果作对比可以得出，全局信息素更新方法虽然可以加快收敛速率，但是存在着一定的缺陷和不足，易使路径更快地集中于单一解，易陷入局部最优，这些缺点限制了它的广泛传播及应用。

本文综合上述两种更新方法的优点和不足，列出了一种新的组合叠加更新方法：在路径搜索的前十次循环中，采用局部最优解更新，十次固定循环结束后，再采用全局最优解进行更新，这种更新方式可以有效避免蚁群搜索得到的路径沉入局部最优解中，有利于发现更多较优解。

2.2 算法实现步骤

根据改进的蚁群算法，将优化后的蚁群算法应用于CVRP问题的实现步骤如下：

（1）参数初始化。设迭代次数 Nc=0；每条路径上的信息素浓度Δτij（0）=c（c为常数），并且Δτij=0；随机将m个蚂蚁放置到初始点上。

（2）更新迭代（循环）次数，即Nc=Nc+1。

（3）初始化禁忌表，蚂蚁禁忌表的索引号k=1。

（4）更新蚂蚁数目k=k+1。

（5）判断路径是否在搜索热区内。按照式（a）～（f）计算出每只蚂蚁应当转移至下一个城市（节点）的概率并完成移动。

（6）当蚂蚁从i城市（节点）出发到达j城市（节点）时，对其所经过的路径上的信息素进行更新，并修改禁忌表，将禁忌表指针按照当前状况进行修改，即将新城市（节点）j置于禁忌表tabuk中。

（7）执行步骤（b）～（f），直到所有蚂蚁都找到了一条包含所有城市（节点）的可行路径解。

（8）在新生成的所有可行解中找到一条最短路径作为本次迭代中的最优路径解。

（9）判断循环次数是否小于十次，若小于十次，则对蚂蚁找到的最优路径按照本次迭代最优值进行信息素更新；若循环次数超过十次，则按照全局信息素进行更新。

（10）对所有蚂蚁经过的路径，按式（1）进行一次全局更新。

（11）循环执行（b）～（j），直到连续多次的迭代中得到的解已收敛或循环次数Nc的值已经达到给定的最大迭代次数的情况下选取当前输出值作为本次最优解。

3 实验仿真

设存在一个物流中心有4辆运输车， 单辆车最大载重为1 000kg， 现需要同时向7个随机分布的客户点派送货物， 蚁群算法的初始化参数为： 蚂蚁总数为20只， 算法的最大迭代数为100次， α和β分别为1，2， 信息素的挥发速度为0.75， 实验重复运行100次， 求得的平均结果为最终结果。同时初始时刻各边上的信息痕迹为1，残留信息的相对重要度为1，设置预见度为5。原始数据进行处理结果分析如图3所示。按本文提出的优化蚁群算法求解CVRP后的处理仿真结果如图4所示。

观测图3、图4的收敛曲线，可以知道蚁群算法优化后的结果相比之前的行车路径有大幅度优化[810]，如图5所示。针对每个收敛的点结合数据可以看出，传统蚁群算法的平均路径在迭代次数为45时可以得到最优解，而改进后的蚁群算法可以在第5次左右得到最优解，相当于收敛速度提高了近80%。

4 结语

在当今应用数学和理论计算机科学的领域中，组合优化（Combinatorial Optimization）是在一个有限的对象集中找出最优对象的一类重要课题，属于运筹学的一个重要分支。在很多组合优化问题中，穷举搜索/枚举法是不可行的。组合优化问题的特征为可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。解决组合优化问题一般采用智能算法，而这些算法都有自身的优点和缺点。组合优化的难处，主要是加进来拓扑分析，在不同的拓扑形态下，算法也需随着不同部分的约束关系作出相应调整。从目前研究来看，随着实际组合问题的变化，基本的智能算法已不能解决这类组合优化问题。

蚁群算法作为一种仿生类进化算法在求路径最优化解方面具有很好的效果。本文首先引出蚁群算法可以用于解决这一类问题，然后介绍了约束车辆路径问题，也即CVRP问题，说明了其约束模型；接着研究了基本的蚁群算法步骤，并对其中信息素更新和改进了启发因子，解析并改良了蚁群算法应用于CVRP问题的实现步骤和处理方法。

本文提出的组合叠加更新方法可有效克服传统蚁群算法收敛质量低、耗时长、易陷入局部最优解等缺陷，使蚁群算法的全局优化能力得到大幅度提高。对比实验前数据可以看出，蚁群算法找到最短路径的收敛速度比传统方法快了80%左右，确实是一种求解最短物流配送路径的有效算法。

参考文献：

[1] 陈昌敏.基于蚁群算法的物流配送路径优化研究与应用[D].成都：西华大学，2012（4）：1154.

[2] 宋留勇，王锐，周永旺，等.动态城市交通网络优化模型研究及算法设计[J].测绘科学，2011，36（1）：134136.

[3] 钟石泉，贺国光.有时间窗约束车辆调度优化的一种禁忌算法[J].系统工程理论方法应用，2005，14（6）：523527.

[4] CHAO YIMING.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：3351.

[5] 杨中秋，张延华.改进蚁群算法在交通系统最短路径问题的研究[J].科学计算与信息处理，2009，32（8）：7678.

[6] 李松，刘兴，李瑞彩.基于混合禁忌搜索算法的物流配送路径优化问题研究[J].铁道运输与经济， 2007， 29（3）：66 69.

[7] 陶波， 朱玉琴.改进的7动态规划法在车辆最短路径问题中的应用[J].重庆工学院学报， 2009，23（1）：2427.

[8] 李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社， 2001：101113.

[9] 张万旭，林健良，杨晓伟.改进的最大最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统，2005，11（4）：572576.

[10] 余h，胡宏智.基于改进遗传算法的物流配送路径求解[J].计算机技术与发展，2009，19（3）：5255.

[11] 朱庆保，蚁群优化算法的收敛性分析[J]. 控制与决策，2006，21（7）：3016.

[12] 郑松，侯迪波，周泽魁，动态调整选择策略的改进蚁群算法[J].控制与决策，2008，23（2）：13.

[13] 夏亚梅，程渤，陈俊亮，等.基于改进蚁群算法的服务组合优化[J].计算机学报，2012，35（2）：311.

篇6

Abstract: Through the analysis of path optimization of emergency logistics distribution, the article establishes its model, proposes the solving method on this basis. Finally, through an example application of path optimization of emergency logistics distribution, the solving process are described, and the results are further discussed.

关键词：物流；应急配送；路径优化

Key words: logistics；emergency distribution；path optimization

中图分类号：F253 文献标识码：A 文章编号：1006-4311（2011）28-0025-02

0 引言

随着市场经济的发展和竞争的加剧，市场呈现多品种、小批量产品多样化、消费多样化的趋势，物流配送就是为适应这种趋势而产生的一个重要环节，它是指对局域范围内的客户进行的多客户、多品种的按时联合送货活动。配送的“送”就是送货运输。从这个角度来看，物流配送中送货路线的选择，是影响物流成本的一项重要因素。从降低物流成本的途径来看，提高物流速度，可以减少资金占用和，缩短在物物流周期，降低储存费用，从而节省物流成本。所以，在应急物流配送过程中，要使得各物资需求点能在最短时间内得到物资补充，物流中心就需要选择最优的保障方式，将物资送达各个需求点。

1 影响物流中心选址的因素及物资需求问题描述

在整个物流系统中，配送中心地点的选择更是物流系统优化的一个具有战略意义的问题。传统意义上的物流配送中心（或分销中心）是商品从供应商（制造商）至零售商之间的中间储存点，具有集中和分散物资，促进商品迅速流转的功能。物流中心的位置的选择，根本目的应以费用低、服务好、社会效益高为目标，以物资运输合理、方便用户、投资少、有利于适应经济发展的需要为基本原则。物流中心的选址需要对多种因素综合考虑包括：自然资源的特点、客户的分布、运输服务条件、建设费用、城市建设的整体规划、外部环境因素等，此外对物流中心未来的发展应仔细研究，使决策具有前瞻性。它包括物流中心在此处有没有发展前途和大的作为，以及一定时期内城市经济发展的变化，以便使物流中心能适应未来发展的需要。

在满足物流中心开设地点要求和综合各物资需求点之间距离的前提下，物流中心与各物资需求点之间就不可避免地存在一定的距离。由于各物资需求点的周围客户量不同，物资的销售情况也必然不同，必然会导致物资需求产生的偶然性，而物资需求点相对分散。物流中心收到来自这些分散的位置的物资配送申请后，对这些物资需求点进行物资配送，模型就是要解决在物流中心现有运输力量前提下，以最优的方式将物资送达每一个需求点，由此产生了物资需求问题。

2 应急物流配送路径优化问题建模

2.1 物流中心与物资需求点的实际关系 由于物资需求点产生的偶然性，使得物流中心和物资需求点关系如图1所示。以五个物资需求点的情况为例，各点编号分别为1、2、3、4、5，物流中心编号为0。现实情况是这样的，各需求点之间以及需求点与物流中心之间，可能是可以不经过第三点直达的（如需求点1、需求点2及物流中心之间都是可直达），也可能是必须经过第三点才可以到达（如需求点5与物流中心之间）。若可以直达，则以连线表示两点之间的支路。无论怎样，需求点与物流中心之间总可以找到一条路，即是可达的。若某个需求点与物流中心之间没有路，则表明该点与物流中心不可达，则该点也就没有存在的必要。

2.2 现实情况的完全加权图表示 将图1所示的现实情况转化为完全加权图形式后得到如图2所示的关系形式。图2中0点为物流中心，其他为物资需求点，实线为实际支路，虚线表示虚拟支路。则物流中心应急物流配送问题可以描述为：找到从0点出发不重复的遍历所有节点的最短闭合回路。由此，可以看出物流中心物资输送问题实质上为一个TSP问题。

2.3 所求最优回路中的组成支路的权值的确定 解决该问题的目标是找到从0点出发不重复的经过所有节点的最短闭合回路。也就是使得这条闭合回路的组成支路的权值之和最小。所以，求得最优路径的问题依赖于各条组成支路的权值的确定。在现实情况下，各路径的权值是综合考虑物流中心到各需求点间的距离、道路状况以及各道路安全性等因素得出的结果，因此在对实际支路赋权的过程中，会出现违背三角不等式的情况，在此对具体的赋权规则不做研究，而假设各实际支路的权值已得出。在对实际支路赋权完毕后，进行虚拟支路的赋权，各虚拟支路的权值均为实际支路权值之和的m倍，m为无穷大的自然数，即虚拟支路不可通行。

2.4 设计求解最优路径问题的流程 物流中心应急物流配送问题抽象后实质为一个N个节点的TSP问题。因此，总能找到一条最优路径。现在假设找到了此问题的一条最优路径L。L若不包含虚拟支路，则表示从物流中心出发，确实存在一条最优的配送路径，从距离、路况及安全性角度综合分析是最优的配送路径；若L中包括至少一条虚拟路径，则表示在现有路径下不存在符合条件的最优路径。即现有条件下的最短路径中某些节点至少需要经过两次。因此，为求得较优路径对图作如下处理。

假设L中某一虚拟路径为（a，b），则总可以从点a到点b找到（a，K1，K2，…，Kn，b）这样一条最短路，其中ki为最初的N个节点之一，且路（a，K1，K2，…，Kn，b）必不含虚拟路径路，称路（a，K1，K2，…， Kn，b）为虚拟路径（a，b）的最短代替路径。在已有节点之外新增加k个节点（A1，A2，…，Ak），新增节点的规则是节点Ak与Ki具有完全相同的属性，即Ak到任何节点的权值与Ki到任何节点权值相同，特别的Ak到与Ki具有相同属性的节点的权值为0。对L中每条虚拟路径都按照（a, b）的方式处理。

完毕后则全部节点数目增加到N+A，其中N个是最初的实际节点，A个为新增节点。此时，对于N+A个节点来说已经找到了一条回路L*，L*只包括这N+A个节点，且这N+A个节点在L*上出现且仅出现一次，同时L*上不含虚拟路径。说明这N+A个节点的TSP问题存在最优解。

根据以上分析，对物流中心应急物流配送问题设计的求解流程如图3。

3 模型的实例应用

3.1 实例分析 以四个需求点为例进行实例说明。假设需求点与物流中心的完全加权图表示如图4所示，各支路权值已给出。

①求这四个点的TSP问题，最优解为（0，2，1，4，3，0），路的长L=12+M，其中包含虚拟路径（2，3）。

②寻找（1，4）的最短代替路径为（1，2，0，3，4）。

③增加点A，B，C，则原图变为图5。

④求这八个点的TSP问题，最优解为（0，2，1，C，B，3，4，A，0）。

3.2 关于求得的解的讨论和实际意义解释 以上通过增加虚拟点的方法建立的求解模型，最终求得的最优路径L可以分为两种情况。情况一：最优路径L中除起点和终点外，不包含其它与起点具有相同属性的点，说明在实施应急物流配送过程中，运输车队从物流中心出发后经过路径L所示的各个需求点，物资送达完毕返回物流中心，各个需求点都得到供应。选择该运输路径，可以减少运输车队的使用，只组织一支物资运输车队，就可以达到完成运输任务的目的，有效地节约了运输资源。情况二：最优路径L中除起点和终点外还包含其它与起点具有相同属性的点。这说明在实施应急物流配送过程中，运输车队从物流中心出发后，中途要返回物流中心，再到其他未配送的需求点，最后遍历所有需求点后回到物流中心。解决此种情况的办法的，根据中途回到物流中心的次数n，在可行的情况下，将整体运输力量分成n+1支配送小分队，各小分队对相应的若干需求点进行物流配送，完毕后返回物流中心。这样，在总路径不增加的前提下，对所有物资需求点展开了并行的物流配送，使得对所有需求点的最长物流配送时间减少，配送的效率更高。

4 结束语

物流中心是物资供应体系中的一个重要的环节。研究应急物流配送路径优化问题，对提高物流中心配送效率具有重要意义。文章对物流中心应急物流配送路径问题进行了分析研究，建立了应急物流配送路径优化问题的模型，设计了模型的求解流程，最后通过实例对应急物流配送路径优化问题求解过程进行了详细说明。并结合现实情况，对求得的解进行了进一步分析讨论，提出了物流中心应急物流配送策略可能的改进意见，供物流中心决策参考。

参考文献：

[1]殷剑宏，吴开亚．图论及其算法[M]．北京：中国科技大学出版社，2003．

篇7

关键词：TSP模型；循环取货；德邦物流

中图分类号：F224 文献标识码：A 文章编号：1009-2374（2014）02-0021-03

第三方物流的迅速发展，为零担运输企业提供了更多的市场机会，但同时也使市场竞争更加激烈。由于行业进入的壁垒较低，许多小企业或个人进入零担运输市场，使得价格竞争非常激烈，对规范的市场竞争不利。第三方物流企业大打“价格战”，各企业利润空间狭小、生存压力大，如何降低企业成本是企业经营者长期思考的问题。

1 TSP模型及求解

1.1 TSP简介

旅行商问题（TSP），也称为货郎担问题、巡回销售问题。该问题是一个典型的组合优化问题，可以简单地描述为：设有N个城市以及设定城市之间的旅行费用，找一条走遍所有城市且费用最低的旅行路线。旅行商问题是单回路运输问题中最为典型的一个问题。

配送路径优化问题可以说是对旅行商问题加以一定限制而形成的，这些限制包括：客户有一定的货物需求（货供应）数量且要求货物在一定的时间范围内送达（或取走）、配送车辆的装载量限制及一次配送的最大行驶距离限制等，即车辆路径优化问题是一个多约束的旅行商问题。

单回路运输问题是指在运输路线优化时，在一个节点集合中，选择一条合适的路径遍历所有的节点，并且要求闭合。单回路运输模型在运输模型中，主要用于单一车辆的路径安排，目标是在该车辆遍历所有用户的同时，达到所行驶距离最短，这类问题的两个显著特点：（1）单一性，只有一个回路；（2）遍历性，经过全部用户，不可遗漏。

1.2 TSP数学模型

TSP问题的模型可以描述为：在给出的一个有n个定点网络（有向或者无向）要求找出一个包含n个定点的具有最小消耗的环路。任何一个包含网络中所有n个定点的环路被称为回路。在旅行商问题中，要设法找到一条最小耗费的回路。既然回路是包含所有定点的一个循环，故可以把任意一个点作为起点（也是重点），这也是TSP模型的一个特点。

TSP模型的数学描述为：

假设连通图H，起定点集A。

定点间的距离为：

满足：

决策变量：

求解TSP模型时，如果要得到精确的最优解，最简单的方法是枚举法。对于小型问题，这也是一种十分有效的方法。但是对于大型问题，由于枚举法的列举次数为（n-1）次，若用枚举法将是无法想象的。

另外，运筹学领域的证书规划的方法也可以用于结局部分TSP模型，其中分支定界法是一种比较实用的算法，但是该算法也是只能对一部分中小规模问题的TSP模型进行求解，对于大多数问题的求解都存在一定的难度。由于此次研究是针对德邦某门店的循环取货实证研究，主要采用Lingo软件求解。该门店的特点如下：（1）需要规划的取货点少，规模不大；（2）取货方式满足旅行商问题的条件；（3）Lingo软件能够对小规模旅行商问题求解。

2 Lingo软件程序及建模

2.1 Lingo程序简介

Lingo全称是Linear Interactive and General Optimizer的缩写―交互式的线性和通用优化求

解器。

Lingo是使建立和求解线性、非线性和整数最佳化模型更快、更简单、更有效率的综合工具。而且Lingo能够提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。

2.2 Lingo建模

简单的模型表示：

model：

sets：

cities/1..7/：level；！level（！）=the level of city；

link（cities，cities）：

distan

ce，

x；！x（i，j）=1 if we use link i，j；

endsets

data：

distance=

enddata

n=@size（cities）；！the model size；

min=@sum（link（i，j）|i #ne# j：distance（i，j）* x（i，j））；

@FOR（cities（i）：

@sum（cities（j）|j #ne# i：x（j，i））=1；

@sum（cities（j）|j #ne# i：x（i，j））=1；

@for（cities（j）|j #gt# 1#and# j #ne# i：

level（j）>=level（i）+x（i，j）-（n-2）*（1-x（i，j））+（n-3）*x（j，i）；

）；

）；

@for（link：@bin（x））

@for（cities（i）|i#gt#1：

level（i）

3 实证研究

3.1 德邦物流简介

德邦是国家“AAAAA”级物流企业，主营国内公路运输业务。截至2013年10月末，公司已开设直营网点4200多家，服务网络遍及全国，自有营运车辆7200余台，全国转运中心总面积超过88万平方米。

德邦物流始终以客户为中心随时候命、持续创新，始终坚持自建营业网点、自购进口车辆、搭建最优线路，优化运力成本，为客户提供快速高效、便捷及时、安全可靠的服务体验，助力客户创造最大的价值。

3.2 德邦物流某网点现状

本文将以德邦物流某网点的上门取货路径做实证

研究。

该网点目前有一名门店经理、三名营业员以及一名驾驶员。门店订单来源主要来源于客户上门订单、电话订单和网络订单。对于需要上门取货的客户，门店经理根据排班表由一名营业员陪同司机驾车外出取货。而为了达到较高的客户满意度，门店都是在客户有需求的时候上门，一次出门提取的商家只有2～3家，并且出门时间不确定，完全根据客户的需求。这样的做法导致的结果是多次上门取货汽车行驶距离长，燃油成本高，并且驾驶员需要全天处于待岗状态，休息时间不确定，行车安全存在隐患。

3.3 路径优化实证

通过与服务商家协商制定配送时间表，保证取货及时以及减少燃油成本，同时驾驶员也能有足够的休息时间，确保行车安全。

本文选取了门店的几个长期服务商家进行实证研究，其中①点为门店所在位置，③点为工业园区，其中包含十余家企业，因距离近合并为一点。

各个节点之间的距离如表1所示。

各个节点之间的行车时间如表2所示。

将表1和表2中的数据输入模型，应用Lingo软件建模运行求解得到该问题的最短路径为①②③⑤⑥⑧⑦④①，最短距离为56.6公里。

通过与相关商家协商，安排了如表3所示的行车时间表：

表3

节点 停留时间

① 14∶00（出发时间）

② 14∶04～14∶09

③ 14∶13～14∶53

⑤ 14∶09～15∶14

⑥ 15∶35～15∶40

⑧ 15∶46～15∶51

⑦ 15∶54～15∶59

④ 16∶26～16∶31

① 16∶45（回程时间）

注：根据对每次取货流程耗费时间的记录，一般耗时4分钟，我们选取五分钟作为一个节点的标准时间；由于节点③处于工业区，周边有十余家服务商家，停留时间为40

分钟。

通过实证研究，循环取货路径得以优化，行车距离减少，企业燃油成本能够大幅减少，并且通过与商家协商，加强了伙伴关系，也提高了服务质量。

参考文献

[1] 赵春英，张铃.求解货郎担问题（TSP）的佳点

集遗传算法[J].计算机工程与应用，2001，37

（3）：83-84.

[2] 蒋长兵，吴承建，彭扬.运输与配送管理建模与仿

真[M].北京：中国物资出版社，2011.

[3] 谢金星，薛毅.优化建模与LINDO/LINGO软件

篇8

[关键词] 矿井 高压供电网络 区域选择性联锁 短路保护 保护配置策略

中图分类号：TD611 文献标识码：A 文章编号：

1 煤矿井下高压供电网络中存在的问题

在我国煤矿企业安全生产事故中，由矿井供电直接或者间接引发的安全事故不断呈现上升趋势[1]。据相关资料显示，煤尘爆炸与瓦斯等严重危害煤矿的安全事故中，有2/3以上与矿井供电系统问题有关[2]。

煤矿企业安全生产对煤矿井下供电工作提出了较高要求，要求100%安全生产和安全生产零事故[3，4]。当前，多数煤矿企业建矿较早，且多次更新井下采煤设备，由于采矿工作面过度延伸，造成了高压供电网络过多分级，导致了矿井下高压供电系统多发短路现象，继电保护出现越过多级、拒动或者误动跳闸，致使停电事故频繁发生，严重时会威胁到矿井安全生产。通过考察研究我矿井生产的实际情况，发现我矿供电系统的实际结构与煤矿井下巷道的走向和分布有一定关系，在很大程度上影响了煤矿供电系统构建[5]。本文结合图论，统一规划了矿井下的高压供电网络，通过使用网络通讯技术实现煤矿矿井高压供电网络继电保护信息的一致共享，通过开关智能控制器的统一控制及综合判断，实现了煤矿井下供电线路继电之间的保护闭锁，从本质上解决煤矿井下高压供电系统中存在的越级跳闸问题。

2 图论在矿井供电网络中的应用

图论是一种运筹学分支，近年来得到了广泛应用，可以使用图论方法解决电力系统的状态估计、可靠性分析及规划等问题。通常情况下，图论研究抽象图形可以用施工流程、运输系统或者电气图形等形式表示。当前，电力系统设计规划中较多应用的是最小费用流问题、最大流问题、最短路径问题等[6]。

本文结合图论，针对煤矿井井下高压供电网络系统提出了安全可行的网络化供电系统保护策略。主要介绍如下：

⑴在煤矿井下供电系统中使用网络优化技术，实现了多级继电保护装置间的联锁保护；⑵采用矿井供电网络优化与保护配置相互结合的供电线路级数设计策略，尽量将煤矿井下供电线路级数减少到最低；⑶减小供电系统回路中出现的低压误动：通过改变欠电压释保护放回路的低压动作值来实现；⑷以保障选择性为前提，尽可能缩短各保护间的时间级差，即改变过负荷保护、无时限电流速断和限时电流速断间的时间级差，将0. 5s改成100～300ms[7]。

3 智能控制模块的工作原理及构成

本文中所述智能控制模块由光纤耦合器、光纤通信元件及单片机等主要元件构成。其中，单片机成功输入、输出各种信号，通过分析各种信号，发出跳闸或者自锁信号。信号转换工作由光纤耦合器和光纤通信元件共同完成，且网络通信在上、下级之间进行。跳闸信号或系统故障信号的开合都可以由单片机系统的控制开关（I/O）装置的分励线圈回路控制，借此实现跳闸操作。

4 煤矿井下高压供电网络区域的选择性联锁保护

煤矿井下高压供电网络的三级区域选择性保护联锁的基本结构如图2所示，即将一个智能控制模块安装在原有开关装置上，使之配合原有继电保护装置当中的电流速断保护工作，以顺利实现区域选择性的联锁保护。原有电流速断保护的信号回路中串联有该智能控制模块，所以不会改变原有的继电保护装置功能。

图2中所示的各级继电保护装置中动作闭锁功能的原理如下：在各级继电保护装置中的电流速断保护中使用智能控制模块，并对其进行延时闭锁，在各级保护间进行可行的信息传递和通信联络，也就是在发生故障后，智能控制模块能及时接到速断保护信号，在有效延时时间内行联络闭锁通信，将各级保护间的操作时间安排好。如果故障线路上安装的保护装置未能在在规定的延时时间内接到由下级继电保护装置中智能控制模块发过来的闭锁信号，则需要将本保护装置发来的闭锁信号解除，接着由本级保护装置发出的速断保护动作来执行。而系统末端开关装置中所安装的智能控制模块无需延时闭锁。

区域选择性联锁保护优化方案发挥作用的关键是要完成煤矿井下各种智能控制模块的成功通信，对各种智能控制模块控制程序的综合性判断要依据控制模块自身及各级模块传来的信号进行，并发出跳闸或者自锁的控制信号，然后结合硬件和软件，以顺利实现煤矿井下高压供电网络区域的选择性保护联锁功能，依此来解决供电系统中存在的越级跳闸问题[8]。

由以上内容可以看出，当出现线路故障时，可以借助上下级通信信号，安排各级保护装置所具有的速断保护动作，实现保护装置的保护联锁，避免越级跳闸现象的出现以及事故扩大；三级线路可以承受的最大短路能量冲击时间是0.2s，既降低了三级线路所承受的内部应力及较重电动力，又减少了故障电流带来的冲击，因此达到了较好的保护效果[2，5]。

5 结语

综上所述，区域选择性联锁保护方案指将一个智能控制模块安装到原有的矿用开关上，从而与原有速断保护装置配合工作，借此实现

煤矿井下高压供电线路的闭锁保护。该智能控制模块在仅串联在速断保护脱扣信号回路中，不改变保护装置的传统功能。该方案既能降低短路电流对供电网络系统的影响，又能实现工作配合的完全选择性，值得将其应用于煤矿井下高压供电网络中。

参考文献

[1]刘士光. 煤矿井下高压供电系统过电压的分析与预防[J]. 科技创新导报，2013，19：23.

[2]余存泰. 一种区域选择性联锁保护装置的设计[J]. 低压电器，2011，03：18-21.

[3]王光超，史世杰，张根现，邹有明. 煤矿井下高压供电网络优化[J]. 中州煤炭，2011，06：80-81.

[4]高锋. 煤矿井下3.3 kV供电网络漏电故障保护研究[J]. 科学技术与工程，2012，29：7525-7531.

[5]卫小兵. 煤矿井下高压供电系统继电保护配置分析[J]. 科技与企业，2013，13：150.

[6]任宪友. 煤矿井上、下高压供电方式的改造[J]. 电子世界，2013，11：57.

篇9

关键词：复杂网络；关联性风险；无标度网络；小世界网络

中图分类号：F83

文献标识码：A

doi：10.19311/ki.16723198.2016.30.051

1引言

伴随金融自由化、复杂化趋势的发展，金融机构之间更紧密地相互联系在一起，这种相互联系增加了金融危机迅速蔓延的可能性，由次贷危机所引发的全球金融危机显示了金融传染的危害性。研究表明，金融系统的微观特征以及展现的宏观结构对于系统内部风险传染的程度具有重要影响。近年来，统计物理学领域在复杂网络的形成及特征等方面获得显著进展，在诸多领域中，基于复杂网络结构理论分析个体间结构及关联性卓有成效，这为本文的研究提供了坚实的理论基础和有益的借鉴。

作为货币市场的核心以及银行间业务的重要组成部分，同业拆借市场平稳运行具有重要意义。同业拆借市场的平稳运行对于调节机构之间的流动性以及货币政策的实施至关重要。同业拆借市场因其市场化的运作以及高效率的机制使得同业拆借利率及时、灵敏地反映了市场资金的供求。因此在货币政策执行中，中央银行将同业拆借利率作为反映金融系统中资金供求状况重要指标，同业拆借利率成为货币市场上的基准利率之一。同时，银行同业拆借市场也是商业银行之间进行短期资金借贷的场所，是一国金融体系的重要组成部分。银行主要依靠同业拆借市场进行流动性管理，银行间市场的发展为银行间资金调剂提供了顺畅渠道.作为货币市场的核心部分，中国同业拆借市场进入了稳定发展阶段，市场规模逐步扩大，2013年同业拆借市场总规模超过45万亿元，其中银行与银行之间拆借交易成交量占整个市场成交量的80%以上。然而，同业间风险暴露也使得银行间的关联性风险增大。因此，基于同业拆借产生的银行间的关联性风险是危机传染的重要渠道之一。

为了提高分析结果的稳健性，在基于同业拆借市场分析的基础之上，利用上市银行股票收益的格兰杰因果检验进一步分析银行体系网络结构特征。

2文献综述及理论分析

由于银行之间存在复杂的债权债务关系，导致银行之间形成紧密的内在关联性，一旦某个银行倒闭，银行间的信贷关系使得破产危机在银行之间传染。要实现对系统性风险有效监管，对关联性风险进行有效评估至关重要。国际货币基金组织在《全球金融稳定报告》（2009）介绍了评估系统性关联风险的四种方法：网络传导分析法、共同风险模型法、困境依赖矩阵法以及违约强度模型法。金融系统是由多子系统、多种性质参与主体以及复杂交互作用关系构成的复杂网络系统，这使得基于单个机构的分析无法有效评估整个金融系统所面临的风险。复杂网络金融理论认为，金融体系的内部结构必然与其功能以及运行状态有紧密的关联性。复杂网络的拓扑结构通常可以描述金融系统的共同特征，复杂网络理论通过研究金融系统结构的拓扑特征，从而对金融系统运行规律进行有效的揭示并达到控制风险的目的。该理论将金融网络用抽象图来替代，就是用抽象的节点来表示金融网络中的个体，并用两个节点间的连线表示个体之间的某种关联性，金融系统中个体之间的关联性通常是基于债权债务关系而产生。通过分析反映金融网络结构特征一些参数指标，可以揭示金融系统的结构与特征。伴随复杂网络结构理论的发展，将复杂网络的研究方法运用到金融领域问题的研究得到了极大的发展，尤其是针对系统性风险问题，复杂网络金融理论基于系统论视角分析金融体系内部关联性风险，二者之间在逻辑关系上存在一致性。

利用网络结构理论研究关联性风险主要包括微观路径和宏观路径两种方法。在微观路径研究中，主要是运用风险管理、复杂网络等领域的知识，并结合金融风险的发生机制研究稳定性较高的金融网络所需具备的微观特征。该领域的早期研究关注银行间的连接方式及连接的紧密程度，Allen和Gale（2000）假设流动性冲击来自于存款者取款时间的不确定性，当网络处于完全连接状态，网络系统具有较高的稳定性，而当网络处于不完全连接状态时，系统会变得较为脆弱。Gai（2010）借鉴其他学者研究复杂网络的数学方法，通过模拟金融网络的形成过程分析稳健性的金融网络应具备的特征，得出的结论是最短路径长度应适当偏长。部分学者尝试利用运筹法判断最优微观结构，Leitner（2005）运用运筹学理论，得出最优金融网络的规模特征即每个小群体内最优节点数量为5。在宏观路径研究中，主要基于节点度、聚类系数、最短路径长度等微观指标研究金融网络所呈现的宏观结构。Hajime Inaoka等（2004）利用银行交易结算数据分析了银行网络结构特征，研究表明银行网络具有自相似以及无标度特征。此外，并从理论上分析了不同网络结构特征下的稳定性。该文将冲击分为随机性冲击与选择性冲击两种类别。对于随机网络，随机性冲击与选择性冲击的效应趋于一致，而对于无标度网络，选择性冲击的效应远远大于随机性冲击。Michael Boss、Helmut Elsinger等（2004）基于同业拆借数据，并利用最小交互熵方法对奥地利银行间市场网络结构特征进行了分析，研究表明少数银行具有大量关联性，而多数银行具有较少的连接。此外，奥地利银行网络呈现出群体结构特征，群体内部关联性紧密，而群体之间的连接较为稀疏。Giulia Iori等（2008）利用隔夜拆借数据分析了意大利银行间网络结构特征及其演化特征。研究表明银行间网络具有随机网络的特征，并且呈现出度增加而强度减弱的状态，研究还发现不同规模主体行为具备差异性。Nier（2007）研究表明银行网络集中度对关联性风险产生的影响并不是单调的，在一定的阈值范围内，集中度增加⒌贾鹿亓性风险增大，但当集中度超过一定的阈值范围后，集中度增加反而会降低关联性风险。Simone Lenzu（2012）基于市场主体的行为探讨了银行网络形成的内生机制，并基于模拟分析风险传染的特征。该文基于关联形成的内生机制形成了随机网络与无标度网络，为了研究不同网络的稳健性，对网络进行随机性冲击模拟，结果发现无标度网络比随机网络具有更高的脆弱性。李守伟等（2010）通过构建有向网络模型，通过分析随机性攻击与选择性攻击对网络成分的影响研究银行间网络的稳定性。研究结果表明，银行间网络对于选择性攻击具有较低的稳定性，而对于随机性攻击具有较高的稳定性。

上述研究表明，金融网络的微观特征以及展现的宏观结构对于分析金融系统的关联性风险具有重要意义。本文以复杂网络结构理论为基础，基于银行间市场同业拆借关系以及上市银行股票收益的格兰杰因果检验分析了银行体系网络结构特征及关联性风险。具体结构安排如下：第三部分主要介绍矩阵法网络模型及因果网络模型；第四部分对银行网络结构特征进行实证分析；最后一部分内容对于本文的主要观点与结论进行总结，并阐述了相关的政策启示。

3研究设计

3.1基于矩阵法构建银行网络模型

首先基于最大熵的方法估计银行间同业拆借矩阵，并利用RAS算法进行优化，该方法意味着各银行尽量可能均匀分布资产；然后利用阈值法构建银行网络模型，由于在实际拆借行为中不可能任意两个银行间都存在双向信用拆借关系，因此假设只有两个银行之间拆借规模超过一定阈值水平才认为两个银行之间存在拆借关系；最后计算度、聚类系数以及平均路径长度等相关指标进而揭示银行间同业市场网络结构特征及关联性风险。

由于只能获取各个银行同业拆借的总资产和总负债数据，无法获得各个银行相互之间交易的具体数据，因此需要基于总资产和总负债数据利用熵最优化法测算银行同业拆借矩阵。银行间市场同业拆借关系可以用矩阵X=（xi，j）N×N表示。其中，xi，j表示银行i对银行j的同业资产头寸，N表示银行数量。设ai表示银行i对其他银行的资产总额，ai=∑Nj=1xi，j，lj表示银行对其他银行的负债总额，lj=∑Nj=1xi，j。在一个具有N家银行的系统中，X包含N2个元素，xi，j的具体值是未知的，但是ai和lj是已知的，在缺少其他约束l件下可以选择最大化双边交易不确定性分布（信息熵最大化）。通过标准化，X视为联合分布函数f（a，l）的实现值，而a和l可视为边际分布函数f（a）和f（b）的实现值。如果f（a）和f（b）相互独立，通过最大熵的方法可以得出xi，j=ai×lj。这种方法意味着i银行对j银行的资产额度取决于i银行对其他银行的资产总额以及j银行对其他银行的负债总额。通过上述方法可以计算出矩阵X，但是银行不能与自身发生借贷关系，也就意味着xi，i=0，因此需要对矩阵X进行修正，修正后的矩阵为X*。求解X*等同于如下问题求解：

min∑Ni=1∑Nj=1x*i，jln（x*i，j/xi，j）

s.t.ai=∑Nj=1x*i，j，lj=∑Nj=1x*i，jx*i，j≥0

上述最优化的解可以利用RAS法计算获得，从而得到银行间同业拆借矩阵。在银行间同业拆借矩阵的基础上，本文采用阈值法构建银行网络特征。由于大部分银行的银行间资产、负债占所有银行间资产、负债的比例在区间（0，0.01）之间，因此，我们将阈值c界定在（0.00001，0.0001）之间。如果当两银行之间同业拆借比例大于阈值c，则认为两银行之间存在拆借关系，在复杂网络理论中意味着两节点之间存在边进行连接。本方法利用各个银行的合并报表的拆借数据进行实证分析。我们使用两组数据进行分析，一组是73家银行2015年的同业拆借数据，另外一组是16家上市银行2008-2015年间的同业拆借数据。

3.2因果网络模型

在一个由n个金融机构构成的金融体系中，Ri表示金融机构i的股票收益率，Rm表示市场回报率，Rf表示无风险利率，则资本资产定价模型可以表示如下：

Ri―Rf=βi（Rm―Rf）+εii=1，2，……，n

则余项εi反映公司i特定风险溢价，本文定义Li=εi反映金融机构i所承担的公司风险。由于金融时间序列数据通常具有波动集聚现象，本文利用GARCH（1，1）模型来描述公司风险的动态相关性。

Li，t=μi+σi，tZi，t

σ2i，t=wi+αiu2i，t-1+βiσ2i，t―1

其中，μi表示条件均值，σi，t表示条件标准误，Zi，t表示白噪声过程，ui，t=σi，tZi，t。

如果时间序列Zi，t包含时间序列Zj，t的有效信息，有助于提高Zj，t预测精度，则认为Zi，t是Zj，t的格兰杰原因。

Zj，t+1=ajZj，t+bjiZi，t+ej，t+1

Zi，t+1=aiZi，t+bijZj，t+ei，t+1

如果bji显著不为0，则Zi，t是Zj，t的格兰杰原因。类似，如果bij显著不为0，则Zj，t是Zi，t的格兰杰原因。基于因果关系检验结果界定金融机构之间的网络关系，如果存在因果关系，则表明代表金融机构的节点之间存在有向边所连接。本方法利用16家上市银行2015年股票收益数据分析银行体系的因果网络结构。

4实证分析

4.1银行网络节点度分布

为了分析银行间市场网络节点度分布情况，将阈值设定为0.00001、0.00003、0.00005、0.00007四种状态，分别计算每一对应阈值状态下各个节点的度，为了能够更清晰地反映度的分布特征，我们将各节点度划分到若干等距区间，即[0，9][10-19][20-29][30-39][40-49]，然后分别计算每一区间的概率，利用各个区间的概率分布来描述节点度分布状况。图1揭示了不同阈值水平下节点度分布状况，我们发现节点度分布具备幂律分布的基本形态。

上述结论是建立在一定假设前提的基础之上得出的，为了验证该方法的有效性，我们可以从另外一个角度分析银行市场的无标度网络特征。我们分析了16家上市银行2008年―2015年的同业拆借的总量，实际数据表明16家银行借入资金总量与借出资金总量呈现出稳步上升趋势，如图2所示。而且根据2015年的完整数据，16家银行同业拆借的总量占样本73家银行同业拆借的总量的比例达到38%。通过以上分析，进一步说明银行间市场网络存在一些中心银行，银行间同业拆借业务主要发生在这些银行之间以及这些银行与其他银行之间。这些处于中心的银行一旦出现危机，很容易通过他们的高连接状态而影响整个银行体系。H.A.Degryse（2004）将银行间市场的这种结构称作货币中心结构，从风险传染的角度来看，决定整个银行体系稳定性的是处于核心地位的银行，而其他规模较小的银行影响有限。根据H.A.Degryse（2004）研究表明，当处于货币中心地位的银行倒闭时，货币中心型的市场结构比完备型的市场结构具备更强的传染性，而当处于中心地位的银行平稳运营时，货币中心型的市场结构更具稳健性。

因此，我们可以得出结论，银行间市场网络具有无标度网络特征，即少数银行具有较大的度，绝大多数银行具有较小的度。无标度网络特征意味着银行间市场对于随机性冲击具有较强的稳健性，而对于选择性冲击具有脆弱性。因为绝大多数银行具有较小的度，因此无标度网络在遭受随机冲击时，这些具有较小度的银行最容易遭到破坏，但这些银行又只有较少的连接，所以这些银行的危机对整个银行体系的影响有限。但当银行系统中具有较大度的银行面临危机时，局部危机会迅速扩散到整个银行体系进而产生系统性危机。

4.2银行网络聚类系数及平均路径长度分析

理论分析表明，如果一个网络同时具有较大的集聚系数和较小的平均路径长度，那么这样的网络称为小世界网络。在上文分析的基础上，利用同业拆借矩阵计算不同阈值水平下的平均路径长度与聚类系数。为了获得因果网络结构，需要对16家上市银行股票收益数据两两之间进行格兰杰因果关系检验。首先，基于资本资产定价模型计算β系数；其次，利用残差数据，基于GARCH（1，1）模型进行参数估计；最后，在显著水平为10%的条件下进行格兰杰因果关系检验。表1为两种不同方法所计算出来的平均路径长度和聚类系数。

从上述数据可以看出，银行间市场网络具有较大的聚类系数和较小的平均路径长度，这说明银行间市场具有典型的小世界网络特征。小世界网络特征意味着一旦一个银行出现严重危机，就会迅速传导给并无直接关联的其他银行，从而导致整个银行体系陷入危机状态。因此，银行间市场小世界网络特征是导致关联性系统性风险的重要原因。需要说明的是，在两种不同的分析方法下，平均路径长度趋于一致，但是聚类系数相差较大，这是由于相关指标值受阈值水平的影响较大。但根据网络结构理论表明，即使是0.21的聚类系数水平仍然可以显示网络结构的无标度特征。

5结论及政策启示

5.1银行同业市场网络结构特征及系统性风险分析

本文由复杂网络金融理论与系统性风险管理之间的内在联系出发，探讨网络结构对银行间关联性风险产生的重要影响，基与银行间资产负债数据，通过理论与实证相结合的分析方法得出以下几点结论：

（1）基于系统论的视角，进一步明确了系统性风险的内涵。系统性风险主要表现在两个方面：一是金融系统作为整体与实体经济相互作用过程中，导致系统性风险积聚；二是金融体系内部的关联性风险，尤其表现为金融机构之间的风险溢出效应。

（2）各个银行的同业拆借规模存在很大差异性，以中、农、工、建为代表的16家上市银行形成了同业拆借网络的中心，其他银行之间虽然也存在业务往来，但规模较小，对银行间市场的影响有限。

（3）实证上，通过阈值法对度、平均路径长度以及聚类系数等相关指标进行分析，研究结果表明银行间网络具备小网络特征以及无标度特征。这意味着银行间市场对于随机性冲击具有较强的稳健性，而对选择性冲击具有较大的脆弱性。

5.2本文结论对金融监管的有效启示

银行间同业市场处于核心地位的银行数量虽然较少，但与大多数银行之间存在信贷关联，一旦这些银行出现危机，会迅速传播到整个网络，威胁银行同业拆借市场的稳定。因此，加强对银行间市场具有系统重要性银行的监管有助于维护银行间市场的稳定，确保银行系统平稳运行。系统重要性银行监管的首要问题是系统重要性机构的界定，需要根据我们国家的实际情况确定有效的指标体系，并选择合理的方法进行量化以及相关指标的合成，减少执行操作的难度。

相关研究表明（马君潞，2007），单一系统重要银行产生的影响较为有限，如果处于网络中心的众多银行同时出现危机，则会对金融体系产生重大冲击。由于经济波动的周期性以及其他共同风险暴露因素可能会导致多家银行同时倒闭，从而引发更为严重的传染。现阶段我国经济形势较为复杂，在全球经济复苏进程缓慢的背景下，我们正处在产业结构调整的关键时期，经济增长下行压力较大。从金融体系改革与监管的层面来看，需要处理好以下几方面的问题：

（1）实现金融和实体经济的有效结合。次贷危机表明，只有正确处理金融发展与实体经济的关系，才能有效预防危机发生。中国在金融体系快速发展过程中，出现了金融脱离实体经济的状态，尤其是表现为房地产价格泡沫。针对金融发展过程中脱离实体经济的苗头，需要有效的预警机制，并通过相应的措施化解潜在的金融失衡风险。

（2）构建危机预警指标。陈雨露（2011）提出“金融失衡指数”这一指标对金融体系的失衡进行描述，用以构建“金融失衡指数”的基本指标包括：社会融资总量、投资、企业杠杆、利差水平、房地产价格和股票价格。该方法为构建危机预警指标提供有益引导，但关于预警指标的选择与测度方法需要进一步深入研究。

（3）稳步推进金融混业经营。面对全球范围内金融业混业经营大趋势，为了提高中国金融体系的稳定性与效率，推进金融混业经营势在必行。但在现阶段金融监管滞后、内外约束机制尚不健全的状况下，混业经营的推进要保持效率与稳定之间的动态平衡。

参考文献

[1]IMF.Global Financial Stability Report：Responding to the Financial Crisis and Measuring Systemic Risk[R].working paper，April，2009.

[2]Allen F，Gale D.Financial contagion[J].The Journal of Political Economy，2000，（108）：133.

[3]Gai，P.，Kapadia， S. Contagion in Financial Networks[J].Proceedings of the Royal Society A，2010，466（2120）：24012433.

[4]Leitner，Y.Financial Networks： Contagion，Commitment，and Social Coordination[J].The Journal of Finance，2005，60（6）：29252953.

[5]Hajime Inaoka， Hideki Takayasu.Self-similarity of banking network[J].Physica A，2004，（339）：621634.

[6]Boss，M.，Elsinger，H.，Summer，M. Network Topology of the interbank Market[J].Quantitative Finance，2004，4（6）：677684.

[7]Giulia Iori，Giulia De Masi.A network analysis of the Italian overnight money market[J].Journal of Economic Dynamics & Control，2008，（32）：259278.

[8]Nier，E.，Yang，work Models and Financial Stability[J].Journal of Economic Dynamics & Control，2007，31（6）：20332060.

篇10

关键词：离散数学；辐射作用；辐射体系；编译原理；数据库

中图分类号：TP3-4

离散数学是现代数学的一个重要分支，也是计算机科学与技术的理论基础，所以又称为计算机数学[1]。离散数学研究离散量的结构及其相互关系，通过离散数学的学习，不但可以掌握离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和逻辑推理能力，为将来参与创新性的研究与开发工作打下坚实的基础。

离散数学课程所传授的思想、方法与工具，广泛地体现在计算机相关专业的诸领域，从科学计算到数据处理，从计算机科学理论基础到计算机应用技术，从计算机软件与理论到计算机硬件及体系结构，从人工智能到知识系统与工程，无不与离散数学密切相关。由于计算机本身是一个离散结构，它只能处理离散的或离散化了的对象及对象关系，因此，无论计算机科学理论本身，还是与计算机应用密切相关的现代科学的其它研究领域，都面临着如何对离散结构进行数学建模的问题；当然，也需要考虑如何将已建立的离散数学模型进行计算机应用的问题。

随着计算机专业研究生入学考试中专业课程统考的实行，很多高校的计算机专业对离散数学的教学投入开始缩减，减少课时，降低难度，避重就轻；学生也无法认识与理解离散数学在整个计算机专业课程体系中的重要性，致使离散数学的教学与学习在计算机专业越来越边缘化。实际上，离散数学在各学科领域，特别在计算机相关专业领域有着广泛的应用；离散数学是计算机专业许多专业基础课程，如数据结构、操作系统、编译原理、人工智能、数据库系统原理、算法设计与分析、理论计算机科学基础、软件工程等必不可少的先行课程[2]。

作为计算机相关专业数学基础的离散数学，对其它计算机专业基础课程有很强的知识辐射作用。本文致力于从一些计算机专业基础课内容中还原离散数学知识，从而体现离散数学核心内容在计算机专业系统知识中的辐射作用。通过对离散数学辐射作用的介绍，让计算机相关专业的本科生重新认识到离散数学对计算机专业系统知识学习的重要性，从而提高本科生学习离散数学的兴趣，重视自己数学理论基础的巩固和形式思维能力的培养。

1 离散数学辐射体系

离散数学是计算机及相关专业的一门核心课程，它不是一门纯数学课程，而是计算机学科的专业基础课程。离散数学是应计算机科学的发展而形成的一门交叉课程，主要内容涵盖了计算机相关专业对数学的一些基本要求。广义的离散数学主题包括集合论、数理逻辑、关系理论、图论、代数结构、数论、信息论、组合数学等，甚至包含拓扑学、运筹学的内容。有些高校将除拓扑学、运筹学等内容外的主题分为三门课程，即集合论与图论、代数结构与组合数学、数理逻辑。本文谈到的离散数学内容只涉及到数理逻辑、关系理论、集合论、图论以及代数结构。

离散数学课程与后续的计算机相关专业基础课程有着千丝万缕的联系，对其它专业基础课程的影响极其深远，在很多计算机专业课程内容中都会涉及到离散数学知识。无论计算机软件系列专业基础课程，还是计算机硬件相关基础课程，例如编译原理、数据结构、数据库、操作系统、软件工程和计算机组成原理。本文选择这六门计算机相关专业基础课程来阐述离散数学在专业系统知识中的辐射作用，如图1所示的离散数学辐射体系。

在图1中，编译原理的课程内容中就可以还原出全部的离散数学知识结构；数据库的课程内容则可还原出离散数学内容中的关系理论、代数结构、集合论与图论等内容；操作系统、软件工程、数据结构和计算机组成原路中都有离散数学知识辐射的印迹。

2 离散数学辐射作用

2.1 编译原理中的离散数学

编译原理是计算机相关专业的一门重要专业基础课[3]，旨在介绍编译器构造的一般原理和基本方法，课程内容除了形式文法、有穷自动机等编译原理所涉及的基础知识外，其它内容基本上围绕处理程序设计语言的编译器应该具有的各功能模块展开，包括词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。

离散数学的数理逻辑中最重要的内容就是逻辑推理，由前提事实出发，采用相应的逻辑恒等式、永真蕴涵式、推理规则、推理方法等进行不停的推导演绎，最终得到想要的结论，这是一个严格的演绎分析过程。在编译原理中，与这一演绎分析过程相对应的则是语法自上而下分析方法，即从形式文法的开始符号（前提）出发，利用文法规则产生式（永真蕴涵式），采用相应的推理方法（最左或最右推导），最终得到想要的句型或句子（结论）。在推理证明中还有一种常用的证明方法，那就是从要求证的最终结论出发，依次为其找到相应的逻辑恒等式、永真蕴涵式、推理规则等作为最终结论或中间结论的依据，即从结论出发追本溯源到前提事实，这是一种典型的归纳逻辑。在编译原理的语法分析中，自底向上的语法分析方法则是归纳过程的代表，即从要得到的句型或句子出发，利用文法产生式规则和推理方法，进行不停的归约，一直到开始符号或失败至，这是一直明显的归纳逻辑推理过程，对应最右推导。

在离散数学的关系理论中，等价关系尤为重要。而在编译原理中，处处有等价原理辐射的痕迹，例如形式文法等价、有穷自动机等价、中间代码表示形式等价等。在编译原理的内容中，有关等价的部分还包括正规文法与正则表达式的等价性、正则表达式与有穷自动机的等价性、正规文法与有穷自动机的等价性。实际上，有穷自动机等价是进行非确定有穷自动机确定化、确定有穷自动机化简的理论基础。

编译原理的很多内容中都使用了形式化技术，最典型的就是状态图刻画有穷自动机、语法树表示语法分析过程，当然在LL（1）文法FIRST集与FOLLOW集计算、算符优先文法的优先函数关系图以及基本块有向图中都体现了离散数学的集合论与图论。在编译原理全部内容中都贯穿了符号串运算，符号串与其上的运算则构成了一个完整的代数系统。

2.2 数据库中的离散数学

数据库技术和系统已经成为信息基础设施的核心技术和重要基础，数据库技术作为数据管理的最有效的手段，极大的促进了计算机应用的发展[4]。数据库的数据模型中的关系模型就经典地体现了离散数学中的关系理论，尤其是关系模型中的参照完整性。数据库概念模型描述中使用的实体-联系模型（图）更是生动地呈现了实体型之间的关系。在离散数学中，函数是一类特殊关系，而关系数据理论中的函数依赖则描述了关系模式属性（集）之间的语义关联。数据库中的查询处理与优化的理论基础则是离散数学中等价原理，查询被处理或优化前后在功能和语义上必须满足等价关系。

与关系模型紧密相连的则是关系代数，这是一类典型的代数系统。关系数据结构是其运算对象，关系操作则是定义在关系上的具体运算，如选择、投影、连接、除等，这些运算都满足封闭性，关系操作的输入与输出则都是表示关系数据的集合，因此集合运算中的并、交、差、笛卡尔积等也是关系操作的一部分。关系数据模型中常用的SQL语言则是关系代数的一种具体实现，即一种具体的代数系统。

数据库理论中被集合论与图论辐射到的内容包括：（1）一个关系数据库是关系模式（二维表）的集合；（2）一个关系模式（二维表）就是一个实体集，表中每一个就是一个具体的实体元素；（3）在概念世界中描述实体型以及实体型间关系的实体-联系图；（4）关系查询处理与优化中的查询树。

2.3 其它课程中的离散数学

数据结构是计算机程序设计的重要理论技术基础[5]，也是计算机存储与组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，因而，数据结构课程中很多具体的数据结构都是集合，如队列、栈、线性表等。数据结构除描述集合中数据元素的特性外，还要刻画集合中数据元素之间的关系，因此，一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构。数据结构课程内容中的树、二叉树以及图等结构则是离散数学图论内容的延续，基于图结构的各种算法，如最短路径、最小生成树、关键路径等，在离散数学和数据结构中都有不同深度的描述。

操作系统课程中的进程状态图为典型的图论内容；操作系统在对进程等对象进行管理时，很多内容涉及到对象间关系，如死锁中进程间时序上的先后关系；操作系统中很多算法都使用到了集合概念，如死锁的解锁算法等。离散数学的核心内容辐射到了操作系统的管理与控制中。

软件工程最终的产物是软件系统，既然是软件系统，在进行软件系统分析与设计时，不可避免要研究系统各部分之间的关系。在结构化分析方法中，有自顶而下和自底而上两类分析方法，自顶而下对应数理逻辑中的演绎逻辑，而自底而上则表示数理逻辑中的归纳逻辑。软件工程内容中同图论有关的包括软件开发模型、软件模块间关系表示、软件测试等。

计算机组成原理作为计算机专业硬件方面的基础课，在学生对计算机的认知方面有着举足轻重的作用。计算机硬件的基础组成单元“逻辑门”等以离散数学中的命题逻辑为基础；计算机处理器的结构形式化等都离不开集合论与图论的参与。实际上，在让学生认知软件与硬件的功能等价性时，则充分体现了软硬件的逻辑等价原理。

3 结论

针对离散数学课程在计算机专业课程体系中越来越边缘化的问题，本文以编译原理、数据库、数据结构、操作系统、软件工程和计算机组成原理计算机专业基础课为例，论述了离散数学在计算机专业综合知识体系中的辐射作用，从而体现离散数学在计算机专业教育中的重要性和必要性。

参考文献：

[1]傅彦，顾小丰，王庆先等.离散数学及其应用[M].北京：高等教育出版社，2007.

[2]耿素云，屈婉玲，王捍贫.离散数学教程[M].北京：北京大学出版社，2002.

[3]张素琴，吕映芝，蒋维杜等.编译原理（第二版）[M].北京：清华大学出版社，2005.

[4]王珊，萨师煊.数据库系统概论（第4版）[M].北京：高等教育出版社，2006.

[5]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2011.

作者简介：胡慧君（1976-），女，讲师，研究方向：智能信息处理；刘茂福（1977-），男，教授，研究方向：自然语言处理。