scientific article; zbMATH DE number 3850794

From MaRDI portal
Publication:3320095





Given is an oriented network \(G=(X,U)\) with a sink \(x_ 0\in X\). A non- negative number q(x) is associated with each node \(x\in X\backslash \{x_ 0\}\). The problem consists in finding a flow, \(\alpha\) : \(X\to R\), from \(x_ 0\) to other nodes (fulfilling their demands) minimizing the total cost: \[ F(\alpha)=\sum_{u\in U}\phi_ u(\alpha(u))\to \min. \] It is assumed that there are no constraints on arc capacities in the network G. The main result proved by the author is: if the cost functions \(\phi_ u(\cdot)\) are concave, non-decreasing functions then there is such a flow among the optimal flows that a part of the graph G generated by the arcs with positive flows is a tree with the root \(x_ 0\in X\). This result suggests a way of searching for a flow of minimal cost. It consists in building in G all possible trees with root \(x_ 0\) and determining a flow in each of them which is simple and univocal. Then a flow of minimal cost should be chosen. Such a procedure is the easier the smaller is the set of destinations \(Y=\{x\in X\), \(q(x)>0\}\). When \(| Y| =1\) the problem resolves itself into finding the shortest path from \(x_ 0\) to y with the lengths of arcs \(\ell(u)=\phi_ u(q(y))\), \(u\in U\). The author presents also a detailed algorithm for the case when \(| Y| =2\).











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 Q3320095)