Résolution Flot Maximum avec Excel

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

Formuler le problème de flot maximum avec Excel

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é)

résolution flot maximum avec excel

Nommons les plages suivantes :

Nom de la plageCellules
FromB4:B15
ToC4:C15
FlowD4:D15
CapacityF4:F15
SupplyDemandK5:K9
MaximumFlowD17

Et insérons les fonctions suivantes :

résolution flot maximum avec excel

Résoudre le modèle

Entrons les paramètres du solveur :

résolution flot maximum avec excel

La solution optimale est :

résolution flot maximum avec excel

Partager
fr_FRFR
%d blogueurs aiment cette page :