doc/min_cost_flow.dox
 changeset 1221 1c978b5bcc65 parent 1164 f63ba40a60f4 child 1270 dceba191c00d
equal inserted replaced
6:435946b36771 7:75e70d7b0995
24 \section mcf_def Definition (GEQ form)
24 \section mcf_def Definition (GEQ form)
25
25
26 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
26 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
27 minimum total cost from a set of supply nodes to a set of demand nodes
27 minimum total cost from a set of supply nodes to a set of demand nodes
28 in a network with capacity constraints (lower and upper bounds)
28 in a network with capacity constraints (lower and upper bounds)
29 and arc costs \ref amo93networkflows.
29 and arc costs \cite amo93networkflows.
30
30
31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
32 \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
32 \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
33 upper bounds for the flow values on the arcs, for which
33 upper bounds for the flow values on the arcs, for which
34 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
34 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,