equal
deleted
inserted
replaced
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. |
29 and arc costs \ref 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$, |