Résolution Plus court chemin avec Excel

Utilisons le solveur dans Excel pour trouver le chemin le plus court du noeud S au noeud T dans un réseau non dirigé (il y aura moins de contraintes dans un réseau dirigé).

Formuler le problème

Pour formuler ce problème de chemin le plus court, 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é)

LP45

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:

LP46

Résoudre le modèle

Entrons les paramètres du solveur:

LP47

La solution optimale est :

LP48