Problème de circulation - Circulation problem

Le problème de circulation et ses variantes sont une généralisation des problèmes de flux de réseau , avec la contrainte supplémentaire d'une borne inférieure sur les flux de bord, et la conservation du flux étant également nécessaire pour la source et le puits (c'est-à-dire qu'il n'y a pas de nœuds spéciaux). Dans des variantes du problème, il y a plusieurs produits qui circulent à travers le réseau, et un coût sur le flux.

Définition

Réseau de flux donné avec: ${\ displaystyle G (V, E)}$

${\ displaystyle l (v, w)}$, borne inférieure du flux de nœud à nœud ,${\ displaystyle v}$${\ displaystyle w}$

${\ displaystyle u (v, w)}$, borne supérieure du flux de nœud en nœud ,${\ displaystyle v}$${\ displaystyle w}$

${\ displaystyle c (v, w)}$, coût d'une unité de débit sur ${\ displaystyle (v, w)}$

et les contraintes:

${\ Displaystyle l (v, w) \ leq f (v, w) \ leq u (v, w)}$,

${\ displaystyle \ sum _ {w \ in V} f (u, w) = 0}$ (le flux ne peut pas apparaître ou disparaître dans les nœuds).

Trouver une affectation de flux satisfaisant les contraintes donne une solution au problème de circulation donné.

Dans la variante à coût minimum du problème, minimisez

${\ Displaystyle \ sum _ {(v, w) \ in E} c (v, w) \ cdot f (v, w).}$

Circulation multi-produits

Dans un problème de circulation multi-produits, vous devez également suivre le flux des produits individuels:

${\ displaystyle \, f_ {i} (v, w)}$	Le flux de marchandises de à . ${\ displaystyle i}$${\ displaystyle v}$${\ displaystyle w}$
${\ Displaystyle \, f (v, w) = \ somme _ {i} f_ {i} (v, w)}$	Le débit total.

Il existe également une limite inférieure pour chaque flux de marchandises.

${\ Displaystyle \, l_ {i} (v, w) \ leq f_ {i} (v, w)}$

La contrainte de conservation doit être respectée individuellement pour les produits:

${\ displaystyle \ \ sum _ {w \ in V} f_ {i} (u, w) = 0.}$

Solution

Pour le problème de circulation, de nombreux algorithmes polynomiaux ont été développés (par exemple, algorithme d'Edmonds et Karp , 1972; Tarjan 1987-1988). Tardos a trouvé le premier algorithme fortement polynomial.

Pour le cas de plusieurs produits, le problème est NP-complet pour les flux entiers. Pour les écoulements fractionnaires, il est résoluble en temps polynomial , car on peut formuler le problème sous forme de programme linéaire .

Problèmes connexes

Vous trouverez ci-dessous quelques problèmes et comment les résoudre avec la configuration générale de circulation donnée ci-dessus.

• Problème de circulation multi-produits à coût minimum - En utilisant toutes les contraintes données ci-dessus.
• Problème de circulation à coût minimum - Utiliser un seul produit
• Circulation multi-produits - Résolvez sans optimiser les coûts.
• Circulation simple - N'utilisez qu'un seul produit, sans frais.
• Flux multi-produits - Si indique une demande de produits de base de à , créez un avantage avec pour tous les produits . Laissez pour tous les autres bords.${\ displaystyle K_ {i} (s_ {i}, t_ {i}, d_ {i})}$${\ displaystyle d_ {i}}$${\ displaystyle i}$${\ displaystyle s_ {i}}$${\ displaystyle t_ {i}}$${\ displaystyle (t_ {i}, s_ {i})}$${\ displaystyle l_ {i} (t_ {i}, s_ {i}) = u (t_ {i}, s_ {i}) = d_ {i}}$${\ displaystyle i}$${\ displaystyle l_ {i} (u, v) = 0}$
• Problème de flux multi-produits à coût minimum - Comme ci-dessus, mais minimisez le coût.
• Problème de flux de coût minimum - Comme ci-dessus, avec 1 produit.
• Problème de débit maximum - Définissez tous les coûts sur 0 et ajoutez un bord du puits à la source avec , ∞ et .${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle l (t, s) = 0}$${\ displaystyle u (t, s) =}$${\ displaystyle c (t, s) = - 1}$
• Problème de débit maximum à coût minimum - Trouvez d'abord le débit maximum . Puis résolvez avec et .${\ displaystyle m}$${\ Displaystyle l (t, s) = u (t, s) = m}$${\ displaystyle c (t, s) = 0}$
• Chemin le plus court à source unique - Laissez et pour toutes les arêtes du graphique, et ajoutez une arête avec et .${\ displaystyle l (u, v) = 0}$${\ displaystyle c (u, v) = 1}$${\ displaystyle (t, s)}$${\ Displaystyle l (t, s) = c (t, s) = 1}$${\ displaystyle a (t, s) = 0}$
• Chemin le plus court pour toutes les paires - Laissez toutes les capacités être illimitées et trouvez un flux de 1 pour les produits, un pour chaque paire de nœuds.${\ displaystyle v (v-1) / 2}$

Les références