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 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é)
plus court chemin avec Excel

Nommons les plages suivantes:

Nom de la plageCellules
FromB4:B21
ToC4:C21
DistanceD4:D21
GoF4:F21
NetFlowI4:I10
SupplyDemandK4:K10
TotalDistanceF23

Et insérons les fonctions suivantes:

plus court chemin avec Excel

Résoudre le modèle

Entrons les paramètres du solveur:

plus court chemin avec Excel

La solution optimale est :

plus court chemin avec Excel
Partager
fr_FRFR
%d blogueurs aiment cette page :