minimum linear cost flow
[c,phi,flag] = min_lcost_flow1(g)
value of cost
row vector of the value of flow on the arcs
feasible problem flag (0 or 1)
min_lcost_flow1
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
g.edges.data.min_cap
and
g.edges.data.max_cap
fields of the graph.
The value of the minimum capacity and of the maximum capacity must be non negative and must be integer numbers. The value of the maximum capacity must be greater than or equal to the value of the minimum capacity.
If the value of
min_cap
or max_cap
is not
given it is assumed to be equal to 0 on each edge.
The costs on the edges are given by the element
g.edges.data.cost
of the fields of the graph. The
costs must be non negative. If the value of
cost
is not given, it is assumed to be equal
to 0 on each edge.
If the min_cap
or max_cap
or cost
data fields are not present in the
graph structure they can be added and set using the add_edge_data function.
This function uses the out-of-kilter algorithm.
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=[155,153,85,155,237,244,244,334,338,346,442,440,439,333,438]; g.nodes.graphics.y=[45,145,221,222,221,82,139,225,142,69,140,72,232,318,319]; show_graph(g); g=add_edge_data(g,'min_cap',[3,7,1,3,6,15,11,3,5,3,12,5,0,5,15,6,2,3,16,7,7,2,8,4,1,7,5,17,20,1,9]); g=add_edge_data(g,'max_cap',[44,55,49,42,42,63,50,46,38,52,55,46,51,52,67,.. 57,51,38,57,46,45,52,46,42,52,49,47,58,66,38,46]); g=add_edge_data(g,'cost',[4,6,6,3,8,2,3,3,3,5,10,4,9,5,4,3,11,8,5,4,8,4,6,10,8,7,6,2,5,9,6]); [c,phi,flag]=min_lcost_flow1(g);flag g.edges.graphics.foreground(find(phi<>0))=color('red'); g=add_edge_data(g,'flow',phi) g.edges.graphics.display='flow'; show_graph(g); | ![]() | ![]() |