Formuler le modèle | Essais et erreurs | Résoudre le modèle
Utilisez le solveur dans Exceller pour trouver le débit maximal du nœud S au nœud T dans un réseau dirigé. 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 de débit maximum, répondez aux trois questions suivantes.
une. Quelles sont les décisions à prendre ? Pour ce problème, nous avons besoin d'Excel pour trouver le flux sur chaque arc. Par exemple, si le débit sur SB est 2, la cellule D5 est égale à 2.
b. Quelles sont les contraintes de ces décisions ? Le flux net (Flow Out - Flow In) des nœuds A, B, C, D et E doit être égal à 0. En d'autres termes, Flow Out = Flow In. De plus, chaque arc a une capacité fixe. Le débit sur chaque arc doit être inférieur à cette capacité.
c. Quelle est la mesure globale de la performance pour ces décisions ? La mesure globale de la performance est le débit maximum, l'objectif est donc de maximiser cette quantité. Le débit maximal est égal au débit sortant du nœud S.
2. Pour faciliter la compréhension du modèle, créez les plages nommées suivantes.
| Nom de la plage | Cellules |
|---|---|
| De | B4:B15 |
| À | C4:C15 |
| Couler | J4:D15 |
| Capacité | F4:F15 |
| Offre et la demande | K5:K9 |
| Débit Maximum | D17 |
3. Insérez les fonctions suivantes.
Explication : Les fonctions SUMIF calculent le flux net de chaque nœud. Pour le nœud A, la première fonction SUMIF additionne les valeurs de la colonne Flow avec un "A" dans la colonne From (Flow Out). La deuxième fonction SUMIF additionne les valeurs de la colonne Flow avec un "A" dans la colonne À (Flow In). Le flux maximal est égal à la valeur de la cellule I4, qui correspond au flux sortant du nœud S. Étant donné que les nœuds A, B, C, D et E ont un flux net de 0, le flux sortant du nœud S sera égal au flux entrant du nœud T.
Essai et erreur
Avec cette formulation, il devient facile d'analyser n'importe quelle solution d'essai.
1. Par exemple, le chemin SADT avec un débit de 2. Le chemin SCT avec un débit de 4. Le chemin SBET avec un débit de 2. Ces chemins donnent un débit total de 8.
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 MaximumFlow pour l'objectif.
3. Cliquez sur Max.
4. Saisissez le flux pour les cellules variables changeantes.
5. Cliquez sur Ajouter pour saisir la contrainte suivante.
6. Cliquez sur Ajouter pour saisir la contrainte suivante.
7. Cochez « Rendre les variables non contraintes non négatives » et sélectionnez « Simplex LP ».
8. Enfin, cliquez sur Résoudre.
Résultat:
La solution optimale :
Conclusion : le chemin SADT avec un débit de 2. Le chemin SCT avec un débit de 4. Le chemin SBET avec un débit de 2. Le chemin SCET avec un débit de 2. Le chemin SACET avec un débit de 1. Le chemin SACDT avec un débit de 1. Ces chemins donnent un débit maximum de 12.
