灾情巡视路线寻优模型

本文讨论了灾情巡视路线的优化问题。并总结出一些在这类图中求最优回路的有效法则。文中首先将乡村公路示意图转化为赋权连通图,并通过最小生成树分解法将原权图分为若干子图,分析并给出在这些子图中寻找最佳回路的若干原则:扩环策略、增环策略、换枝策略。依据这些原则,求得不同条件下的巡视路线。 当巡视人员分为组时,在要求总路程最短且尽可能均衡的条件下各组巡视路程分别为:2O6.8km,219.5km 159.3km。当要求在24小时完成巡视,至少需分4组,巡视完成时间为:22.3小时。当巡视人员足够多时,完成巡视的最短时间为6.43小时,巡视人员需分成22组     

分块分层优化的旅游路线规划问题研究

针对旅游路线规划决定着自驾旅游者的旅游成败问题,利用分块分层优化的思想解决了旅游路线规划这一网络优化问题。用赋权图和近邻聚类的思想构建分块网络加权图,建立考虑旅游时间、行车时间和游览时间的改进旅行商优化模型,规划区块内景点的自驾旅游路线;然后将各区块视为节点、区块间旅游时间作为时间权值之一,建立改进的多旅行商优化模型,并用模拟退火算法规划出区块间的自驾旅游路线;其次,用类比一维装箱问题的思想,建立了求最少旅游年数的一维装箱模型,并用交叉装填算法求得其最小值;最后,应用提出的方法为西安市的自驾旅游爱好者规划出了满足多种约束的游遍全国201个5A级景区的最佳旅游路线。     

图论在离散事件动态系统中的应用

运用图论方法和极大代数方法,研究了非强连通图中的强连通分支的最大圈长平均值与该图的赋权邻接矩阵的特征值之间的关系,并进一步证明了其等价性.     

最优公交线路选择问题的数学模型及算法

公交线路选择问题是城市公共交通信息查询的重要内容，本文建立了满足不同公交线路查询者需求的最优线路选择模型并给出了相应的算法。首先通过引入各条公交线路直达最短距离矩阵构造了公交网络直达关系图（直达矩阵），在直达关系图（直达矩阵）上，利用修改了的最短路算法，即可求得最优换乘路线。根据出行者的不同需求，通过在直达关系图上定义不同的权系数，可以分别求得换乘次数最少的公交出行线路、经过站点最少的公交出行线路；通过修改最短路算法，可以求得出行耗时最少的线路及出行费用最低的线路，另外，本模型还可以综合考虑出行者的需求情况，求得出行者满意度最大的出行路线。     

关于非交换群上Cayley图的Hamilton分解的一点注记

一、引言图的Hamilton分解问题是图论中的一个引人注目的问题。称一个2k-正则的连通图Γ可以Hamilton分解,是指Γ可以分解为k个Hamilton圈。Alspach在[1]中给出了如下猜测:是否每个2k度连通Cayley图都可以Hamilton分解?文[4]对此问题给出了部分回答,即任意一个4度交换群上连通Cayley图可以分解为2个Hamilton     

图的k-单圈划分中的优化问题

图的划分问题曾引起图论界的广泛关注，在文献[4]中讨论了k-单圈划分，本文进一步研究基于k-单圈划分的优化问题，即在一个赋权图中求一个最小权可k-单圈划分的支撑子图，以及对一个不存在k-单圈划分支撑子图的图，如何添最少的边使得它有k-单圈划分的支撑子图。     

公务员招聘的数学模型

利用组合图论的方法将公务员招聘问题转化为求赋权平衡二部图的最大权完美匹配问题,再利用Kuhn-Munkras算法得到它的解,在此过程中利用迭加因子方法充分考虑了用人单位的希望要求及应聘人员的个人意愿,因而是一套最大限度地同时满足应聘者意愿和用人单位要求的解决方案.     

弦图扩张与最优排序

弦图是一类特殊的完美图,以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题,沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

连通图的谱半径上界

图谱理论是图论研究的重要的领域之一.设图G是n阶简单连通图,具有n顶点和m条边的连通图,p(G)为图G的邻接矩阵的谱半径.利用代数的方法得出两个ρ(G)的上界为:■与■和达到上界的图.     

最短时限缺省指派问题的一种解法

将周良泽在 1998年提出的最短时限缺省指派问题转化成赋权二分图的最小权 K-匹配问题。研究了其解的最优性充分及必要条件 ,并给出了适合在图上求解的生长树法及适合在表上直接求解的标号法 ,最后给出一个实例。该解法是一种较简便的算法。     

突发事件中对嫌疑犯有效封堵的模型与算法

基于CUMCM-2011 B题中关于嫌疑犯的封堵问题的研究.通过建立描述市区交通网络图的权矩阵,采用求最短路的Dijstra算法求出市区任意两节点的最短路径及路长,构作最佳路径阵和距离矩阵,以此为基点建立封堵路口的最优调度方案模型,再在此基础上建立封堵住嫌疑犯的最优模型,并设计了模型求解的算法.将算法应用于CUMCM-2011 B题中关于嫌疑犯的封堵问题,获得最优封堵方案.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

解一般TSP问题的并行算法

任何连通的带权图均有ＴＳＰ的解．本文用图的最短路径矩阵代替加权邻接矩阵，使所有带权图，ＨＰ模型都能够接受．由于采用并行算法，可以较快获得问题的最优解．     

Using matrices to link conflict evolution and resolution in a graph model

The graph model for conflict resolution provides a convenient and effective means to model and analyze a strategic conflict. Standard practice is to carry out a stability analysis of a graph model, and then to follow up with a post-stability analysis, an important component of which is status quo analysis. A graph model can be viewed as an edge-colored graph, but the fundamental problem of status quo analysis – to find a shortest colored path from the status quo node to a desired equilibrium – is different from the well-known network analysis problem of finding the shortest path between two nodes. The only matrix method that has been proposed cannot track all aspects of the evolution of a conflict from the status quo state. Our explicit algebraic approach is convenient for computer implementation and, as demonstrated with a real world case study, easy to use. It provides new insights into a graph model, not only identifying all equilibria reachable from the status quo, but also how to reach them. Moreover, this approach bridges the gap between stability analysis and status quo analysis in the graph model for conflict resolution.     

网络最短的最优解集结构

The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2-transformation graph (?) on the shortest-paths for G are presented heavily.     

选择最佳公交线路的数学模型

归纳影响乘客选择公交路线的诸多因素,以换乘次数少、时间短、费用低作为设计最佳路径的目标,利用数据结构和图论思想,建立了选择最佳公交线路的数学模型.     

最短时限运输问题及图上求解法

提出了最短时限运输问题,借助于赋权二分图研究了其解的最优性充要条件,并给出了在赋权二分图上求解的具体步骤,最后给出了一个实例。事实证明,该法是一个有效的算法     

An almost linear time algorithm for field splitting in radiation therapy

In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of a MLC may require to split a large intensity map into several overlapping sub-IMs with each being delivered separately. We develop a close-to-linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs, thus improving the treatment delivery efficiency. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, which expresses a special “layered” structure. The edge weights of the graph satisfy the Monge property, which enables us to solve this shortest path problem by examining only a small portion of the graph, yielding a close-to-linear time algorithm. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min–max slope path problem in a monotone polygon which is solvable in linear time. The min–max slope path problem may be of interest in its own right. Experimental results based on real medical data and computer generated IMs showed that our new algorithm runs fast and produces high quality field splitting results.     

基于时变需求的集成多级供应链生产订货策略研究

考虑一个时变需求环境下集成多级供应链问题,在有限的规划时间内销售商以固定周期订货,而生产商以不同的周期生产,目的是寻找销售商最优的订货周期和生产商最佳的生产策略,从而使供应链系统的总运营成本最少.建立了该问题的混合整数非线性规划模型,求解该模型分为两步：先求对应一个订货周期的最佳生产策略,再求最优的订货周期,第一步用到了图论里求最短路方法.给出了两个步骤的算法和程序,实验证明它们是有效的.通过算例对模型进行了分析,研究了各参数对最优解及最小费用的影响.