Parameters

Description

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 min_cap and max_cap fields of the graph edges_data_structure. 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 cost of the fields of the graph edges_data_structure. 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.

This function uses the out-of-kilter algorithm.

Examples

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

 
  

See Also