min_lcost_flow2 — minimum linear cost flow
[c,phi,flag] = min_lcost_flow2(g)
value of cost
row vector of the value of flow on the arcs
feasible problem flag (0 or 1)
min_lcost_flow2
computes the minimum linear cost flow in the network
g
. It returns the total cost of the flows on the arcs c
and
the row vector of the flows on the arcs phi
. If the problem is not
feasible (impossible to find a compatible flow for instance), flag
is
equal to 0, otherwise it is equal to 1.
The bounds of the flow are given by the min_cap
and
max_cap
fields of the graph edges_data_structure.
The value of the minimum capacity must be equal to zero. The values of the
maximum capacity must be non negative and must be integer numbers.
If the value of min_cap
or max_cap
are not given , it is assumed to be equal to 0 on each edge.
The costs on the edges are given by the cost
field of the
graph edges_data_structure.
The costs must be non negative and must be integer numbers.
If the value of cost
is not given (empty row vector []
),
it is assumed to be equal to 0 on each edge.
The demand on the nodes are given by the demand
field of the
graph nodes_data_structure.
The demands must be integer numbers. Note that the sum of the demands must
be equal to zero for the problem to be feasible.
If the value of demand
is not given (empty row vector []
),
it is assumed to be equal to 0 on each node.
This functions uses a relaxation algorithm due to D. Bertsekas.
ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10 1 8]; he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1 12 14]; g=make_graph('foo',1,15,ta,he); g.nodes.graphics.x=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548]; g.nodes.graphics.y=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439]; show_graph(g); g=add_edge_data(g,'max_cap',[37,24,23,30,25,27,27,24,34,40,21,38,35,23,38,28,26,.. 22,40,22,28,24,31,25,26,24,23,30,22,24,35]); g=add_edge_data(g,'cost',[10,6,3,8,10,8,11,1,2,6,5,6,5,3,4,2,4,4,8,2,4,5,4,8,8,3,4,3,7,10,10]); g=add_node_data(g,'demand',[22,-29,18,-3,-16,20,-9,7,-6,17,21,-6,-8,-37,9]); [c,phi,flag]=min_lcost_flow2(g);flag g.edges.graphics.foreground(find(phi<>0))=color('red'); g=add_edge_data(g,'flow',phi) g.edges.graphics.display='flow'; g.nodes.graphics.display='demand'; show_graph(g);