紧急网络中的最小饱和流问题

网络N中的一个流,如果沿前向已无法再增流,则称为饱和流,在交通拥挤或紧急疏散时,网络往往被一饱和流所堵塞。显然,这饱和流的值越小,网络的性能就越差。于是从网络分析的观点就提出最小饱和流问题。本文首先证明此问题NP－困难的。然后给出关于最小饱和流与最大流的关系及算法方面的结果。     

运输网络中最小饱和流的求解

运输网络中常常由于流量的不可控易发生堵塞现象.网络发生堵塞时的饱和流值达不到最大流值.最小饱和流是运输网络,尤其是紧急疏散网络设计中很重要的一个参数.通过建立网络的割集矩阵来确定网络的堵塞截面,基于此提出了求解最小饱和流的线性规划模型及算法.举例分析表明,利用该算法计算网络最小饱和流更加简便、更加实用.     

有上下界网络最大流与最小截问题

为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统，本文给出一个求有上下界网络最大流与最小截的数值算法，证明了算法的理论依据，并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解，在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率，可用于求解最小饱和流问题。     

分配网络的一个最小费用流算法

分配网络流广泛应用于解决水源、电力的调度及工厂的产品运输、分配、合成等问题.本文提出一个分配网络流的最小费用流算法.     

无容量限制的最小费用流问题

本文研究了无容量限制的带固定费用和可变费用的单物资和二物资的最小费用流问题,并分别给出了多项式算法.最后应用该算法,计算了一个二物资的最小费用流问题的实例.     

一个综合植被地表径流与饱和地下水流之间相互作用的数值模型

构建一个综合的数值模型,用来处理植被地表径流与饱和地下水流之间的相互作用问题.综合了早先提出的准三维植被地表径流模型,与二维饱和地下水流模型建立起该数值模型.植被地表水流模型被构建为,二维浅水方程(SWE)显式的有限体积解,耦合了Navier-Stokes方程(NSE)隐式的有限差分解,得到了竖向速度的分布.地下水流模型是以二维饱和地下水流方程(SGE)显式的有限体积解为基础构建.通过在连续方程中引入源-汇项,达到植被地表径流和地下水流之间的相互作用.单一的规则将2个解紧密地耦合在一起.最后,应用4个案例来验证本综合模型,结果是令人满意的.     

会计数据的网络流分析

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

最大利润流问题及算法

最大利润流是以运输利润最大为目标的网络优化问题 .一个利润可行流可分解为若干个路流和圈流 ,相应地该可行流的利润也等于这些路流和圈流的利润之和 .本文证明了一个可行流为最大利润流的充要条件是不存在利润增广路 ,并据此提出了求解算法 .文章最后给出了一个计算实例 .     

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

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

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

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

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0,1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C₂,C₃,C₄,…. It is known that C₂ can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing require solving a linear program. In this paper we prove that C₃ can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0,1}ⁿ, this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network.     

On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks

In this paper, a pseudopolynomial time algorithm is presented for solving the integral time-dependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the time-dependent evacuation and quickest transshipment problems. A more widely known, though less general version, is the quickest flow problem (QFP). The QFP has historically been defined on a dynamic network, where time is divided into discrete units, flow moves through the network over time, travel times determine how long each unit of flow spends traversing an arc, and capacities restrict the rate of flow on an arc. The goal of the QFP is to determine the paths along which to send a given supply from a single source to a single sink such that the last unit of flow arrives at the sink in the minimum time. The main contribution of this paper is the time-dependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a time-dependent dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the time-dependent minimum time dynamic flow problem, whose objective is to determine the paths that lead to the minimum total time spent completing all shipments from source to sink. An optimal solution to the latter problem is guaranteed to be optimal for the TDQFP. By adding a small number of nodes and arcs to the existing network, we show how the algorithm can be used to solve both the time-dependent evacuation and the time-dependent quickest transshipment problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

Note on “Inverse minimum cost flow problems under the weighted Hamming distance”

Jiang et al. proposed an algorithm to solve the inverse minimum cost flow problems under the bottleneck-type weighted Hamming distance [Y. Jiang, L. Liu, B. Wuc, E. Yao, Inverse minimum cost flow problems under the weighted Hamming distance, European Journal of Operational Research 207 (2010) 50–54]. In this note, it is shown that their proposed algorithm does not solve correctly the inverse problem in the general case due to some incorrect results in that article. Then, a new algorithm is proposed to solve the inverse problem in strongly polynomial time. The algorithm uses the linear search technique and solves a shortest path problem in each iteration.     

A note on the minimum interval cost flow problem

We reduce the problem of minimum interval cost flow problem (MICFP) introduced by Hashemi et al. (2006) to the well-known minimum cost flow problem (MCFP).     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

A network flow model for the optimal allocation of both foldable and standard containers

This paper considers a multi-port and multi-period container planning problem of shipping companies that use both standard and foldable containers. A company must decide which number of empty containers of each type to purchase and reposition at each port within a defined period to minimize the total purchasing, repositioning, and storage costs.We develop a model to optimally allocate both foldable and standard containers. We show that a single commodity minimum cost network flow algorithm solves the problem by proving that a two commodity flow problem can be modeled as a single commodity flow problem.