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 nud 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 :

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

où $\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)$.