scientific article; zbMATH DE number 3978784

From MaRDI portal
Publication:3743072





A class of flows on nets is discussed, called flows with linear capacity constraints or LCC-flows. The capacity of the arcs is given with the help of a linear constraints set \[ \sum_{(x,y)\in D_ i}b_ i(x,y)\cdot f(x,y)\leq C_ i\quad (i\in I_ i) \] where the coefficient \(b_ i(x,y)\) has a finite positive value, if \((x,y)\in D_ i\), and a null value in the opposite case; \(D_ i\subseteq U\); \(D_ i\neq \Lambda\) are arbitrary non-empty subsets of the arcs in the net \(U=\cup_{i\in I}D_ i\); the coefficients \(\{C_ i| i\in I\}\) are finite real numbers, and f(x,y) denotes the flow function on the arc (x,y)\(\in U\). The value of f(x,y) depends on the constraints subset that includes this value. The capacity on each cutting set r is defined by the functional C(r), its exact values being estimated with the help of a linear programming problem. It is proved that if the cutting set p is contained in the cutting set r, then C(p)\(\geq C(r)\). The cutting set r, which has the lowest value of the functional C(r) in comparison with all the other cutting sets, is defined as the minimum set. A theorem is proved, concerning the equality of the maximum LCC-flow and the minimum cutting set capacity. A comparison of the investigated LCC-flow and the classical flow is done with respect to the ways of capacity prescribing and defining.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3743072)