next up previous
suivant: Quelques problèmes de flot monter: Les simplifications du problème précédent: Eliminer les arcs avec

Cas des capacités sur les sommets

Dans certains modèles de situations réelles, il est possible d'avoir des capacités sur les sommets. Par exemple, dans un n\oeud de répartition EDF, les équipements de rectification de la tension ne peuvent absorber plus d'une certaine quantité d'électricité. Ceci peut se modéliser par la contrainte suivante :

$\displaystyle \sum\limits_{i : (\ivj) \: \in \: G} x_{ij} \; \leqslant \: \lambda(j) \qquad
\forall\:j\: \in X
$

$ \lambda(j)$ est la capacité maximale du sommet $ j$. Afin de ne pas rajouter cette contrainte dans le système, on la remplace par une contrainte de capacité sur un arc en dédoublant le sommet $ j$ en $ j'$ et $ j''$ et en ajoutant l'arc $ (j',\,j'')$ de capacité $ \lambda(j)$.

Bruno Garcia 2000-12-17