Formuler le problème de plus court chemin avec Excel
Pour formuler ce problème de plus court chemin avec Excel, répondons aux trois questions interrogations suivantes.
- Quelles sont les décisions à prendre ? Pour ce problème, nous avons besoin d’Excel pour savoir si un arc est sur le chemin le plus court ou non (Oui = 1, Non = 0). Par exemple, si SB fait partie du chemin le plus court, la cellule F5 est égale à 1. Sinon, la cellule F5 est égale à 0. (en jaune)
- Quelles sont les contraintes sur ces décisions ? Le flot net (Flot sortant – Flot entrant) de chaque nœud doit être égal à l’offre – la demande en ce noeud. Le nœud S ne devrait avoir qu’un seul arc sortant (flot net = 1). Le nœud T ne doit avoir qu’un seul arc entrant (flot net = -1). Tous les autres nœuds doivent avoir un arc sortant et un arc entrant si le nœud se trouve sur le chemin le plus court (flot net = 0) ou sans flux (flot net = 0). (en bleu clair)
- Quelle est la mesure globale de la performance pour ces décisions ? La mesure globale de la performance est la distance totale du plus court chemin, l’objectif est donc de minimiser cette quantité. (en bleu foncé)
Nommons les plages suivantes:
| Nom de la plage | Cellules |
|---|---|
| From | B4:B21 |
| To | C4:C21 |
| Distance | D4:D21 |
| Go | F4:F21 |
| NetFlow | I4:I10 |
| SupplyDemand | K4:K10 |
| TotalDistance | F23 |
Et insérons les fonctions suivantes:
Résoudre le modèle
Entrons les paramètres du solveur:
La solution optimale est :
