Network::minCost
-- computes a
minimal cost flow
computes a minimal
cost flow for the network Network::minCost
(G)G
, taking into consideration
supply and demand, capacities and transportation cost.
Network::minCost(G)
G |
- | network |
a sequence, consisting of a number and two tables
Network::minCost
(G)
computes a minimal
cost flow in G
with respect to the edge capacities, the
edge weights and the vertex weights of G
.
The vertex weights are interpreted as supply and demand. The edge capacities give restrictions for the flow on every edge. The edge weights are the cost for one unit flow over an edge.
The algorithm computes a flow, if there is any, which is possible and satisfactory, i.e., it is within the supply and demand range, which respects the capacities and which has minimal cost.
Network::minCost
(G)
is a
sequence of the price of a minimal cost flow, the minimal cost flow
itself (in form of table), and a table with the dual prices.We construct a network with five nodes and seven edges. One of the nodes is a pure source (1), another one is a pure sink (5). No other nodes supply or demand any goods, they only serve as transportation junctions.
>> V := [1,2,3,4,5]: Vw := [25,0,0,0,-25]: Ed := [[1,2], [1,3], [2,3], [2,4], [3,4], [3,5], [4,5]]: Ew := [7, 6, 5, 4, 2, 2, 1]: Ecap := [30, 20, 25, 10, 20, 25, 20]: N1 := Network(V,Ed,Eweight=Ew, Capacity=Ecap, Vweight=Vw): Network::minCost(N1)
table( [4, 5] = 5, table( [3, 5] = 20, 5 = 2, [3, 4] = 0, 4 = 3, 220, [2, 4] = 5, , 3 = 4, [2, 3] = 0, 2 = 7, [1, 3] = 20, 1 = 14 [1, 2] = 5 ) )
All 25 units could be transported from node 1 to node 5, for a total cost of 220.
Network::MinCost