耦合动力系统的Conley指标

从Hessian矩阵入手,研究了几种有限网络上动力系统的两种孤立不变集的Conley指标.对于网络节点仅具有单个状态参量时,分析了在线性耦合关系和非线性耦合关系下的全连接网络(全耦合网络)、最近邻网络和任意连接网络上流的孤立不动点的Conley指标与单个节点状态流的孤立不动点的Conley指标的关系;对于节点具有双状态参量和孤立节点不变集为极限环时,给出了在一定耦合条件下,文中所定义的映射F(s)的C0nley指标与节点状态积流的Conley指标的关系.     

(m,n,k)指派问题的最小费用流模型及其算法

构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行.     

非牛顿流体偏心环空螺旋流的解析解

石油和化工中许多问题需要求解非牛顿流体偏心环空螺旋流。本文全面地研究了幂律流体和宾汉流体在偏心环空中层流螺旋流的流动规律与流动状态的判别。在理论上,根据流体力学原理,运用数学方法,在作者同心环空螺旋流的理论基础上,通过对偏心环空螺旋流流场的无限细分法,给出了该流场的视粘度分布、速度分布、流量和压降方程,进而建立了判别流态的稳定性参数。     

含有不可靠节点的无圈序贯网络可靠性分析

首次对含有不可靠节点的无圈序贯网络(Acyclic consecutively connected networks,ACCN)的可靠性进行分析.并首次提出n中取[k_1,k_2]节点的概念:当节点接收到的信号数量不小于k_1且不大于k_2时节点正常,否则失效.针对含有不可靠节点的.ACCN的性质对一般生成函数进行改进,建立节点的改进一般生成函数.随后根据改进一般生成函数的特点对递归过程进行简化.最后给出一个含有不完全可靠节点的网络的算例,利用改进一般生成函数和简化的递归过程对网络的可靠性进行评价,证明改进后的方法解决了含有不可靠节点的ACCN可靠性评价问题并有效的简化了计算过程.     

三种单节点摄动对混合值逻辑网络极限集的影响

研究了三种单节点摄动对混合值逻辑网络不动点和极限环的影响.受布尔网络单节点摄动的启发,文章首先在结构矩阵的基础上提出了混合值逻辑网络中单节点摄动的定义,并利用矩阵半张量积的方法得到了单节点摄动下混合值逻辑网络的代数形式.然后,研究了结构矩阵与状态转移矩阵间的关系,并提出了三种特殊类型的单节点摄动.最后,得到了三种单节点摄动对混合值逻辑网络的不动点及极限环影响的充分必要条件.     

网络最大流算法的性能分析

对网络最大流问题的求解算法进行性能分析和比较.结果表明,与经典的增载轨算法相比,基于动态规划思想的算法将最大流的求解过程看作一个动态调整过程,通过判断在各个动态阶段各节点允许通过的最大流量,从而能更快的得到网络的最大流值.同时文中的算法分析进一步为这一算法建立了严格的理论基础.     

考虑路损的最大流问题及其基本特征

本文给出了考虑流量损耗的最大流问题的数学模型,并阐明了该问题的几个基本特征.     

钢管的订购和运输解答模型

首先通过最短路算法简化了供需距离网络 ,去掉了铁路、公路等边的性质 ,使供需距离网络简化为一个供需运输价格表 .在此基础上构造了三个模型 :线性费用的网络流模型、改进的线性费用的网络流模型和具有非线性费用的网络流模型 .通过改进传统的最小费用最大流算法 ,解决了本题的非线性费用网络流模型 ,并给出了算法的正确性证明与复杂度分析     

复杂金融网络收益率加权和的不变性研究

对包含两个子网络的复杂金融网络进行了分析,研究了网络中各节点收益率与资金流通量之间的关系.通过建立数学模型,证明了网络中各节点收益率加权和的不变性.     

输送网络新模型——改进的K-H模型

引入了网络流中最小流函数的概念并对此进行了深入研究,给出了最小流函数s(λ_1,λ_2,…,λ_r)的分析表达式,建立了输送网络"发"收"叠加的新数学模型,该模型克服了传统的K-H模型中将输送源排除在网络系统之外的弊端,在输送网络的优化问题上具有极强的可操作性.     

Operating Points in Infinite Nonlinear Networks Approximated by Finite Networks

Given a nonlinear infinite resistive network, an operating point can be determined by approximating the network by finite networks obtained by shorting together various infinite sets of nodes, and then taking a limit of the nodal potential functions of the finite networks. Initially, by taking a completion of the node set of the infinite network under a metric given by the resistances, limit points are obtained that represent generalized ends, which we call ``terminals,' of the infinite network. These terminals can be shorted together to obtain a generalized kind of node, a special case of a 1-node. An operating point will involve Kirchhoff's current law holding at 1-nodes, and so the flow of current into these terminals is studied. We give existence and bounds for an operating point that also has a nodal potential function, which is continuous at the 1-nodes. The existence is derived from the said approximations.

     

Dual track and segmented single track bidirectional loop guidepath layout for AGV systems

In this study, we develop integer programming models for simultaneous design of the guidepath track and location of the pickup and dropoff stations for automated guided vehicle systems. Two alternative bidirectional topologies are compared: a dual track loop, and a single track loop partitioned into non-overlapping segments, each served by a single vehicle. We show that the empty vehicle trips have a significant impact on the quality of design in both topologies. More importantly, we identify the difference between empty flow node balancing for a dual track loop with the empty flow edge balancing on a single track loop subject to segmentation. Our work presents an economic decision making model for the trade-off analysis between the costs associated with the additional shop floor space of a dual track loop and the increased vehicle fleet size of a segmented single track loop.     

Using mathematical programming heuristics in a multicriteria network flow context

In this paper, we propose a local search procedure to test the robustness of a specific ‘satisfying point’ neighbourhood. It consists of the following steps: (1) build an indifference area around the satisfying point in the criteria space by using thresholds (this takes into account the possible uncertainty, vagueness and/or inaccuracy of data); (2) find some points in the satisfying point neighbourhood and the corresponding solutions in the decision variables space; (3) test the quality of these solutions from the point of view of user preference. The indifference area is defined by adding constraints to the network model. This approach, which allows us to verify the adequacy of the model, has been applied to a set of multicriteria network flow problems. A heuristic method, based on Lagrangian duality and subgradient techniques, exploits the combinatorial structure of network flow problems in order to find certain feasible points.     

基于正交试验的乘用车运输网络优化方法

在交通部治理公路超限运输的背景下,本文研究了乘用车物流企业多式联运模式下的网络优化问题,以运输网络总成本最小为目标,考虑物流时效、枢纽节点容量及规模经济效应等因素,构建了基于轴辐式理论的运输网络优化模型,提出了混合智能优化算法。针对多参数多水平的寻优问题,对模型的三个关键输入参数,即枢纽节点数量、枢纽节点容量和规模效应折扣系数,引入正交试验方法,降低求解多参数多水平寻优问题的工作量,为确定各参数合理取值提供了新的途径。研究结果表明:枢纽节点容量、折扣系数与枢纽数量三个输入参数对优化结果的影响具有主次顺序,影响程度依次减弱,而且只有枢纽节点容量与折扣系数对乘用车运输网络总效益的影响起显著作用。采用混合轴辐式的网络结构与多式联运的运输组织模式进行优化后的运输网络,相对于原有“点对点”公路运输网络总成本减少10%,从运营管理与成本控制两方面均可有效应对公路治超带来的风险。     

An Efficient Approach to Real-Time Traffic Routeing for Telephone Network Management

When contingencies occur in the telephone network the proper traffic control actions for rearranging the traffic flow must be promptly taken in a short period of time, otherwise, the congestion will soon spread to other parts of the network. In this paper, a multicommodity maximal flow model is proposed to formulate the problem, and an efficient approach is proposed to find the solution within a short time period. The node pairs are first sorted by the traffic demand into decreasing order and the capacity of links is allocated to the node pair with largest demand. The traffic allocation is then iteratively reallocated on those routes which share the same links to find a better solution, until that solution is obtained. The advantages of this approach are: (1) a feasible solution can be obtained within a short time period; (2) the affected traffic can be rerouted on paths with more than two links; (3) an acceptable solution can be found once the period has expired.     

On the enrouting protocol problem under uncertainty

In this paper we present a two-stage stochastic mixed 0–1 dynamic multicommodity model and algorithm for determining the enrouting protocol in the telecommunications network under uncertainty. Given the network connectivity, node processing and buffer and arc flow capacity, the aim is to determine the outgoing arc for the information flow reaching a given node for each destination terminal node (i.e., obtaining the route to be followed by the information flow from each origin terminal node to each destination terminal node). The origin–destination (O–D) flow matrix is given by the number of information packets to be sent from the origin terminal nodes to the destination terminal nodes along a given time horizon, i.e., a call scale. The uncertainty in the O–D flow matrix is treated via a scenario tree approach. The main goal is to minimize a composite function of the expected lost information, a penalization of the deviation from the FIFO strategy on the information flow entering the network, and the expected number of nodes visited by the information packets. A mixture of an enrouting arc generation scheme and a genetic algorithm for obtaining the enrouting protocols over the scenarios is presented. The tool presented in this paper could be used for simulating the enrouting protocols to analyze the saturation of the network, but it has a time constraint for real time operation. Faster algorithms are needed to define the routing tables during the operation stage. Computational experience is reported.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

会计数据的网络流分析

学者已证明一个会计主体如一家企业、其复式簿记中一级账户记录的数据组成一个矩阵;继而提出了会计回路概念,并认识到会计回路符合网络的某些规律.提出复式簿记系统的矩阵对应于1个网络,该网络存在着网络流.图论中的最大流最小割定理在该网络中同样有效,可以对之求解最大流最小割.最小割的集合是网络中的"瓶颈",直接影响着总的通过流量.计算出最小割的值,找出它由哪些会计分录组成、关联到哪些会计科目、流量是多少,这正是该会计主体运营中的薄弱环节.这是会计史上第一种整体地、定量地分析会计主体运营状况的数学方法.     

The multi-terminal maximum-flow network-interdiction problem

This paper defines and studies the multi-terminal maximum-flow network-interdiction problem (MTNIP) in which a network user attempts to maximize flow in a network among K ? 3 pre-specified node groups while an interdictor uses limited resources to interdict network arcs to minimize this maximum flow. The paper proposes an exact (MTNIP-E) and an approximating model (MPNIM) to solve this NP-hard problem and presents computational results to compare the models. MTNIP-E is obtained by first formulating MTNIP as bi-level min-max program and then converting it into a mixed integer program where the flow is explicitly minimized. MPNIM is binary-integer program that does not minimize the flow directly. It partitions the node set into disjoint subsets such that each node group is in a different subset and minimizes the sum of the arc capacities crossing between different subsets. Computational results show that MPNIM can solve all instances in a few seconds while MTNIP-E cannot solve about one third of the problems in 24 hour. The optimal objective function values of both models are equal to each other for some problems while they differ from each other as much as 46.2% in the worst case. However, when the post-interdiction flow capacity incurred by the solution of MPNIM is computed and compared to the objective value of MTNIP-E, the largest difference is only 7.90% implying that MPNIM may be a very good approximation to MTNIP-E.     

Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout

The shortest loop covering at least one edge of each workcenter in a manufacturing facility layout is an instance of the generalized traveling salesman problem. The optimal solution to this problem is a promising design for non-vehicle-based material handling, typical of most types of conveyors and power-and-free systems, where the length of the path is the main driver of the total investment costs. The loop formulation is usually embedded within a larger problem of the concurrent design of the loop and the input/output stations for vehicle-based material handling typical of automatically guided vehicles and autonomous delivery robots. In these systems, it is not the length, but the total flow of the loaded and empty vehicles that drives the objective function. It has been shown that the shortest loop provides an effective heuristic scheme to achieve prosperous and robust solutions for the concurrent design of the loop and input/output stations. We review and compare covering constraints formulations, provide new insight into connectivity constraints, improve the model formulation and its solution procedure, and report computational results.