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$,