Résolution Plus court chemin avec Excel

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:

Et insérons les fonctions suivantes:

Résoudre le modèle

Entrons les paramètres du solveur:

La solution optimale est :