Formuler le modèle | Essais et erreurs | 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.
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 faciliter la compréhension du modèle, créez les plages nommées suivantes.
| 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.
Explication : Les fonctions SUMIF 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 somme du produit Distance et Go.
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.
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.
Remarque : vous ne trouvez pas le bouton Solveur ? Cliquez ici pour charger le complément Solveur.
Entrez les paramètres du solveur (lire la suite). Le résultat doit être conforme à l'image ci-dessous.
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.
5. Cliquez sur Ajouter pour saisir la contrainte suivante.
6. Cochez « Rendre les variables non contraintes non négatives » et sélectionnez « Simplex LP ».
7. Enfin, cliquez sur Résoudre.
Résultat:
La solution optimale :
Conclusion : SADCT est le chemin le plus court avec une distance totale de 11.
