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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
.TH min_lcost_cflow 1 "September 1995" "Scilab Group" "Scilab function"
.so ../sci.an
.SH NAME
min_lcost_cflow - minimum linear cost constrained flow
.SH CALLING SEQUENCE
.nf
[c,phi,v,flag] = min_lcost_cflow(i,j,cv,g)
.fi
.SH PARAMETERS
.TP 2
i
: integer, source node number
.TP 2
j
: integer, sink node number
.TP 3
cv
: scalar, value of constrained flow
.TP 2
g
: graph list
.TP 2
c
: value of cost
.TP 4
phi
: row vector of the values of flow on the arcs
.TP 2
v
: value of flow from source to sink
.TP 5
flag
: feasible constrained flow flag (0 or 1)
.SH DESCRIPTION
\fVmin_lcost_cflow\fR computes the minimum cost flow in the network \fVg\fR,
with the value of the flow from source node \fVi\fR to
sink node \fVj\fR constrained to be equal to \fVcv\fR.
\fVmin_lcost_cflow\fR returns the total cost of the flows on the arcs \fVc\fR,
the row vector of the flows on the arcs \fVphi\fR and the value of the flow
\fVv\fR on the virtual arc from sink to source. If \fVv\fR is less than
\fVcv\fR, a message is issued, but the computation is done: in this
case \fVflag\fR is equal to 0, otherwise it is equal to 1.
The bounds of the flows are given by the elements \fVedge_min_cap\fR and
\fVedge_max_cap\fR of the graph list.
The value of the minimum capacity must be equal to zero, and the value
of the maximum capacity must be non negative and must be integer
numbers.
If the value of \fVedge_min_cap\fR or \fVedge_max_cap\fR is not given (empty
row vector \fV[]\fR), it is assumed to be equal to 0 on each edge.
The costs on the edges are given by the element \fVedge_cost\fR of the
graph list.
The costs must be non negative.
If the value of \fVedge_cost\fR is not given (empty row vector \fV[]\fR),
it is assumed to be equal to 0 on each edge.
The demands, element \fVnode_demand\fR of the graph list, must be
equal to zero.
This function uses the algorithm of Busacker and Goven.
.SH EXAMPLE
.nf
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];
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];
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 181 276 278 276 103 174 281 177 86 175 90 290 397 399];
show_graph(g);
g1=g; ma=arc_number(g1); n=g1('node_number');
g1('edge_min_cap')=0*ones(1,ma);
rand('uniform');
g1('edge_max_cap')=round(20*rand(1,ma))+ones(1,ma);
g1('edge_cost')=10*rand(1,ma)+ones(1,ma);
source=15; sink=1; cv=5;
[c,phi,v]=min_lcost_cflow(source,sink,cv,g1);
x_message(['The cost is: '+string(c);
'Showing the flow on the arcs']);
nodetype=0*ones(1,n); nodetype(source)=2; nodetype(sink)=1;
g1('node_type')=nodetype;
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);
nodecolor=0*ones(1,n); nodecolor(source)=11; nodecolor(sink)=11;
g1('node_color')=nodecolor;
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);
.fi
.SH SEE ALSO
min_lcost_flow1, min_lcost_flow2, min_qcost_flow
|
