Changeset 687:6c408d864fa1 in lemon for doc/groups.dox
 Timestamp:
 04/29/09 03:15:24 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r658 r687 353 353 in a network with capacity constraints (lower and upper bounds) 354 354 and arc costs. 355 Formally, let \f$G=(V,A)\f$ be a digraph, 356 \f$ lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and355 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$, 356 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and 357 357 upper bounds for the flow values on the arcs, for which 358 \f$ 0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.359 \f$cost: A\rightarrow\mathbf{Z} ^+_0\f$ denotes the cost per unit flow360 on the arcs ,and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the358 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, 359 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow 360 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the 361 361 signed supply values of the nodes. 362 362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ 363 363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with 364 364 \f$sup(u)\f$ demand. 365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z} ^+_0\f$ solution365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution 366 366 of the following optimization problem. 367 367 … … 405 405 The dual solution of the minimum cost flow problem is represented by node 406 406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. 407 An \f$f: A\rightarrow\mathbf{Z} ^+_0\f$ feasible solution of the problem407 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem 408 408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ 409 409 node potentials the following \e complementary \e slackness optimality … … 414 414  if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; 415 415  if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. 416  For all \f$u\in V\f$ :416  For all \f$u\in V\f$ nodes: 417 417  if \f$\sum_{uv\in A} f(uv)  \sum_{vu\in A} f(vu) \neq sup(u)\f$, 418 418 then \f$\pi(u)=0\f$. 419 419 420 420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc 421 \f$uv\in A\f$ with respect to the node potentials\f$\pi\f$, i.e.421 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. 422 422 \f[ cost^\pi(uv) = cost(uv) + \pi(u)  \pi(v).\f] 423 423 424 All algorithms provide dual solution (node potentials) as well 424 All algorithms provide dual solution (node potentials) as well, 425 425 if an optimal flow is found. 426 426
Note: See TracChangeset
for help on using the changeset viewer.