Formulez le modèle | Trial and Error | Résoudre le modèle

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

qu’élaborer modèle

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

Shortest Path Problem in Excel

  1. Pour formuler ce problème de 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 égal à 1. Dans le cas contraire, la cellule F5 est égale à 0.

\ B. Quelles sont les contraintes qui pèsent sur ces décisions? Le flux net (réacheminés – Débit In) de chaque nœud doit être égale à l’offre / demande. Noeud S doit avoir un seul arc sortant (débit net = 1). Noeud T doit avoir un seul arc entrant (débit net = -1). Tous les autres nœuds doivent avoir une arc sortant et un arc entrant si le nœud est sur le chemin le plus court (Net Débit = 0) ou pas de débit (débit net = 0).

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

  1. Pour rendre le modèle plus facile à comprendre, nommez les plages suivantes.

Range Name

Cells

From

B4:B21

To

C4:C21

Distance

D4:D21

Go

F4:F21

NetFlow

I4:I10

SupplyDemand

K4:K10

TotalDistance

F23

  1. Insérez les fonctions suivantes.

Insert Functions

Explication: Le lien: exemples sumif / [SUMIF] fonctions calculer le flux net de chaque nœud. Pour le noeud S, la fonction SUMIF résume les valeurs de la colonne Go avec un « S » dans la colonne De. En conséquence, la cellule ne F4, F5 ou F6 peut être de 1 (un arc sortant). Pour le noeud T, la fonction SUMIF résume les valeurs de la colonne Go avec un « T » dans la colonne. Par conséquent, seulement des cellules F15, F18 ou F21 peuvent être 1 (un arc entrante). Pour tous les autres noeuds, Excel regarde dans De et à la colonne. Distance totale est égale à la distance et de SUMPRODUCT Go.

Trial and Error

Avec cette formulation, il devient facile d’analyser toute solution d’essai.

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

Trial Solution

Il est pas nécessaire d’utiliser tâtonnement. Nous allons décrire ensuite comment Excel Solver 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. Dans l’onglet Données, dans le groupe Analyser, cliquez sur Solver.

Click Solver

Remarque: ne peut pas trouver le bouton Solver? Cliquez ici pour charger le complément Solver.

Entrez les paramètres du solveur (lire). Le résultat devrait être compatible avec l’image ci-dessous.

Solver Parameters

Vous avez le choix de taper les noms de plage ou en cliquant sur les cellules dans la feuille de calcul.

  1. Entrez cumulLa pour l’objectif.

  2. Cliquez sur Min.

  3. Entrez Go pour le changement des cellules variables.

  4. Cliquez sur Ajouter pour saisir la contrainte suivante.

Net Flow Constraint

  1. Cochez la case ‘Make Variables non sans contrainte négative’ et sélectionnez ‘Simplex LP’.

  2. Enfin, cliquez sur Résoudre.

Résultat:

Solver Results

La solution optimale:

Shortest Path Problem Result

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