No label defined (Q3320095)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3850794
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3850794 |
Statements
1983
0 references
oriented network
0 references
optimal flows
0 references
flow of minimal cost
0 references
shortest path
0 references
0.8707740306854248
0 references
0.8230423927307129
0 references
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\).
0 references