300 Exemples

Problème du plus court chemin

Shortest Path Problem

Formuler le modèle | Essai et erreur | Résoudre le modèle





Utilisez le solveur dans Exceller pour trouver le le plus court chemin du nœud S au nœud T dans un réseau non orienté. Les points d'un réseau sont appelés nœuds (S, A, B, C, D, E et T). Les lignes d'un réseau sont appelées arcs (SA, SB, SC, AC, etc.).

Formuler le modèle

Le modèle que nous allons résoudre se présente comme suit dans Excel.





Problème de chemin le plus court dans Excel

comment trouver q1 et q3 dans excel

1. Pour formuler cela problème du chemin le plus court , répondez aux trois questions suivantes.



une. 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.

b. Quelles sont les contraintes de ces décisions ? Le flux net (flux sortant - flux entrant) de chaque nœud doit être égal à l'offre/la demande. Le nœud S ne doit avoir qu'un seul arc sortant (Net Flow = 1). Le nœud T ne doit avoir qu'un seul arc entrant (Net Flow = -1). Tous les autres nœuds doivent avoir un arc sortant et un arc entrant si le nœud est sur le chemin le plus court (Net Flow = 0) ou aucun flux (Net Flow = 0).

c. Quelle est la mesure globale de la performance pour ces décisions ? La mesure globale de la performance est la distance totale du chemin le plus court, l'objectif est donc de minimiser cette quantité.

2. Pour rendre le modèle plus facile à comprendre, créez ce qui suit plages nommées .

Nom de la plage Cellules
De B4 : B21
À C4:C21
Distance D4:D21
Aller F4:F21
NetFlow I4:I10
Offre et la demande K4 : K10
Distance totale F23

3. Insérez les fonctions suivantes.

Insérer des fonctions

Explication : Le SUMIF les fonctions calculent le flux net de chaque nœud. Pour le nœud S, la fonction SUMIF additionne les valeurs de la colonne Go avec un « S » dans la colonne From. Par conséquent, seule la cellule F4, F5 ou F6 peut être à 1 (un arc sortant). Pour le nœud T, la fonction SUMIF additionne les valeurs de la colonne Go avec un « T » dans la colonne À. De ce fait, seule la cellule F15, F18 ou F21 peut être à 1 (un arc amont). Pour tous les autres nœuds, Excel recherche dans les colonnes De et À. La distance totale est égale à la produit de somme de Distance et Aller.

Essai et erreur

Avec cette formulation, il devient facile d'analyser n'importe quelle solution d'essai.

1. Par exemple, le chemin SBET a une distance totale de 16.

Solution d'essai

Il n'est pas nécessaire d'utiliser des essais et des erreurs. Nous décrirons ensuite comment le Solveur Excel peut être utilisé pour trouver rapidement la solution optimale.

Résoudre le modèle

Pour trouver la solution optimale, exécutez les étapes suivantes.

1. Sous l'onglet Données, dans le groupe Analyser, cliquez sur Solveur.

Cliquez sur Solveur

Remarque : vous ne trouvez pas le bouton Solveur ? Cliquez ici pour charger le Complément de solveur .

Entrez les paramètres du solveur (lire la suite). Le résultat doit être conforme à l'image ci-dessous.

formule pour trouver des valeurs en double dans Excel

Paramètres du solveur

Vous avez le choix de saisir les noms des plages ou de cliquer sur les cellules de la feuille de calcul.

2. Entrez la distance totale pour l'objectif.

3. Cliquez sur Min.

4. Entrez Go pour les cellules variables changeantes.

comment faire exceller un histogramme

5. Cliquez sur Ajouter pour saisir la contrainte suivante.

Contrainte de flux net

6. Cochez « Rendre les variables non contraintes non négatives » et sélectionnez « Simplex LP ».

7. Enfin, cliquez sur Résoudre.

Résultat:

Résultats du solveur

La solution optimale :

Résultat du problème du plus court chemin

Conclusion : SADCT est le chemin le plus court avec une distance totale de 11.

4/7 terminé ! En savoir plus sur le solveur >
Aller au chapitre suivant : Outil d'analyse



^