doc/min_cost_flow.dox
changeset 755 134852d7fb0a
parent 663 8b0df68370a4
child 788 c92296660262
equal deleted inserted replaced
0:c60ebd4b1c89 1:c4104acc14db
    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$,