THE LINEAR BALANCING FLOW PROBLEM

Giovanni Andreatta

doi:10.1016/0377-2217(93)90009-C

THE LINEAR BALANCING FLOW PROBLEM

1993-01-01

2

PRE

AI

Giorgio Romanin-Jacur

DOI：10.1016/0377-2217(93)90009-C

原文链接

原文求助

摘要

En 中文

The original motivation for investigating the Linear Balancing Flow Problem (LBFP) came from the optimization of a real-life production plan. Each instance of LBFP is a linear programming problem and can be interpreted as a flow problem on a bipartite network with gains. In the literature the typical flow problem on networks with gains is either a max flow or a min cost flow problem. Here we consider a different kind of objective, namely, how to optimally balance the flow out of a given set of nodes. An original algorithm is suggested which takes advantage of the particular problem structure. Theoretically it may be viewed as a specialized version of the Simplex. However it is more efficient than the latter: in fact, it requires much less memory and computing time. The key feature consists in associating a tree to the set of variables of the dual problem that are out of the current basis. The justification of the proposed algorithm does not immediately follow from that of the Simplex. A direct proof of its validity is provided and simple numerical examples are reported.

Keyword:

NETWORKS WITH GAINS

LINEAR PROGRAMMING

FLOW BALANCING

THE LINEAR BALANCING FLOW PROBLEM

摘要

AI总结

期刊

机构

引用论文