1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
min_lcost_flow2 Scilab Group Scilab function min_lcost_flow2
NAME
min_lcost_flow2 - minimum linear cost flow
CALLING SEQUENCE
[c,phi,flag] = min_lcost_flow2(g)
PARAMETERS
g : graph list
c : value of cost
phi
: row vector of the value of flow on the arcs
flag
: feasible problem flag (0 or 1)
DESCRIPTION
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 elements
edge_min_cap and edge_max_cap of the graph list. 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 edge_min_cap or edge_max_cap is not given (empty row vector []), it is
assumed to be equal to 0 on each edge. The costs on the edges are given
by the element edge_cost of the graph list. The costs must be non
negative and must be integer numbers. If the value of edge_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 element node_demand of
the graph list. 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 node_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.
EXAMPLE
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('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
show_graph(g);
g1=g; ma=arc_number(g1); n=g1('node_number');
g1('edge_min_cap')=0.*ones(1,ma);
x_message(['Random generation of data';
'The first(s) generated problem(s) may be unfeasible']);
while %T then
rand('uniform');
g1('edge_max_cap')=round(20*rand(1,ma))+20*ones(1,ma);
g1('edge_cost')=round(10*rand(1,ma)+ones(1,ma));
rand('normal');
dd=20.*rand(1,n)-10*ones(1,n);
dd=round(dd-sum(dd)/n*ones(1,n));
dd(n)=dd(n)-sum(dd);
g1('node_demand')=dd;
[c,phi,flag]=min_lcost_flow2(g1);
if flag==1 then break; end;
end;
x_message(['The cost is: '+string(c);
'Showing the flow on the arcs and the demand on the nodes']);
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
g1('node_label')=string(g1('node_demand'));
show_graph(g1);
SEE ALSO
min_lcost_cflow, min_lcost_flow1, min_qcost_flow
|
