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

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

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

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

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

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

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

带有模糊容量限制的网络中的最佳最小费用量大流

本文主要讨论当网络中弧容量限制和最大流目标要求带有模糊性时的最小费最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。     

带有模糊容量限制的网络中的最佳最小费用最大流

本文主要讨论当网络中的弧容量限制和最大流目标要求带有模糊性时的最小费用最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。     

会计数据的网络流分析

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

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

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

网络流在清理三角债问题中的应用

本文把清理三角债中两种优化数学模型问题，化成求解相应网络上最小费用流的问题，从而得到（强）多项式算法，并把另外的一种优化数学模型问题。化成线性规划问题.于是解答了文[3]中提出的清理三角债的三个基本问题．     

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

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

Maximum-throughput dynamic network flows

This paper presents and solves the maximum throughput dynamic network flow problem, an infinite horizon integer programming problem which involves network flows evolving over time. The model is a finite network in which the flow on each arc not only has an associated upper and lower bound but also an associated transit time. Flow is to be sent through the network in each period so as to satisfy the upper and lower bounds and conservation of flow at each node from some fixed period on. The objective is to maximize the throughput, the net flow circulating in the network in a given period, and this throughput is shown to be the same in each period. We demonstrate that among those flows with maximum throughput there is a flow which repeats every period. Moreover, a duality result shows the maximum throughput equals the minimum capacity of an appropriately defined cut. A special case of the maximum dynamic network flow problem is the problem of minimizing the number of vehicles to meet a fixed periodic schedule. Moreover, the elegantsolution derived by Ford and Fulkerson for the finite horizon maximum dynamic flow problem may be viewed as a special case of the infinite horizon maximum dynamic flow problem and the optimality of solutions which repeat every period.     

Maximum flow problem on dynamic generative network flows with time-varying bounds

This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem.     

A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks

Genetic algorithms and other evolutionary algorithms have been successfully applied to solve constrained minimum spanning tree problems in a variety of communication network design problems. In this paper, we enlarge the application of these types of algorithms by presenting a multi-population hybrid genetic algorithm to another communication design problem. This new problem is modeled through a hop-constrained minimum spanning tree also exhibiting the characteristic of flows. All nodes, except for the root node, have a nonnegative flow requirement. In addition to the fixed charge costs, nonlinear flow dependent costs are also considered. This problem is an extension of the well know NP-hard hop-constrained Minimum Spanning Tree problem and we have termed it hop-constrained minimum cost flow spanning tree problem. The efficiency and effectiveness of the proposed method can be seen from the computational results reported.     

A network simplex based algorithm for the minimum cost proportional flow problem with disconnected subnetworks

In this study, we present a variant of the minimum cost network flow problem where the associated graph contains several disconnected subgraphs and it is required that the flows on arcs belonging to same arc subsets to be proportional. This type of network is mostly observed in large supply chains of assemble-to-order products. It is shown that any feasible solution of a reformulation of this problem has a special characteristic. By taking into account this fact, a network simplex based primal simplex algorithm is developed and its details are provided.     

Minimum Maximal Flow Problem: An Optimization over the Efficient Set

The network flow theory and algorithms have been developed on the assumption that each arc flow is controllable and we freely raise and reduce it. We however consider in this paper the situation where we are not able or allowed to reduce the given arc flow. Then we may end up with a maximal flow depending on the initial flow as well as the way of augmentation. Therefore the minimum of the flow values that are attained by maximal flows will play an important role to see how inefficiently the network can be utilized. We formulate this problem as an optimization over the efficient set of a multicriteria program, propose an algorithm, prove its finite convergence, and report on some computational experiments.     

An introduction to dynamic generative networks: Minimum cost flow

What we are dealing with is a class of networks called dynamic generative network flows in which the flow commodity is dynamically generated at source nodes and dynamically consumed at sink nodes. As a basic assumption, the source nodes produce the flow according to time generative functions and the sink nodes absorb the flow according to time consumption functions. This paper tries to introduce these networks and formulate minimum cost dynamic flow problem for a pre-specified time horizon T. Finally, some simple, efficient approaches are developed to solve the dynamic problem, in the general form when the capacities and costs are time varying and some other special cases, as a minimum cost static flow problem.     

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.