Résolution Flot Maximum avec Excel

Excel permet de résoudre le problème de flot maximum d’un noeud S vers un noeud T dans un graphe orienté.

Formuler le problème

Pour formuler le problème de flot, il faut répondre à ces trois interrogations.

  • Quelles sont les décisions à prendre ? Pour ce problème, nous avons besoin d’Excel pour trouver le flux sur chaque arc. Par exemple, si le débit sur SB est égal à 2, la cellule D5 est égale à 2. (en jaune)
  • Quelles sont les contraintes sur ces décisions ? Le flux net (Flot sortant – Flot entrant) des nœuds A, B, C, D et E doit être égal à 0. En d’autres termes, Flot sortant = Flot entrant. De plus, chaque arc a une capacité fixe. Le débit sur chaque arc doit être inférieur à cette capacité. (en bleu clair)
  • Quelle est la mesure globale de la performance pour ces décisions ? La mesure globale de la performance est le débit maximum, l’objectif étant donc de maximiser cette quantité. Le débit maximum est égal à la sortie du noeud S. (en bleu foncé)

LP49

Nommons les plages suivantes :

Nom de la plage Cellules
From B4:B15
To C4:C15
Flow D4:D15
Capacity F4:F15
SupplyDemand K5:K9
MaximumFlow D17

Et insérons les fonctions suivantes :

LP50

Résoudre le modèle

Entrons les paramètres du solveur :

LP51

La solution optimale est :

LP52

Publicités