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é)
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 :
Résoudre le modèle
Entrons les paramètres du solveur :
La solution optimale est :
