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.
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.
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.
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 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
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.
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.
Aller au chapitre suivant :