Emplacement de l’entrepôt et GrG Multistart et Evolutionary Moteurs solveurs

■■ Aux États-Unis, où une entreprise de transport par Internet devrait-elle localiser un seul entrepôt pour minimiser la distance totale à laquelle les colis sont expédiés?

■■ Aux États-Unis, où une entreprise de transport par Internet devrait-elle localiser deux entrepôts afin de minimiser la distance totale à laquelle les colis sont expédiés?

Dans Microsoft Excel , Solver a été doté de nombreuses nouvelles fonctionnalités intéressantes. Ce article (et l’article36, «Pénalités et solveur évolutif», et l’article 37, «Le problème du vendeur ambulant») expliquent comment ces algorithmes peuvent vous aider à résoudre de nombreux problèmes d’optimisation importants.

Comprendre les moteurs GRG multistart et Evolutionary Solver

Comme indiqué à l’article 28, «Présentation de l’optimisation avec Excel Solver», Excel  Solveurr utilise trois moteurs pour résoudre les problèmes d’optimisation: Simplex LP, GRG Nonlinear et Evolutionary. Les sections suivantes fournissent plus de détails sur la façon dont les deux derniers de ces moteurs sont utilisés pour résoudre les problèmes d’optimisation.

comment Solveur résout-il les problèmes de Solveur linéaire?

Comme cela a été souligné dans les articles 28 à 33, un modèle de solveur est linéaire si toutes les références aux changements

Les cellules dans les cellules cibles et les contraintes sont créées en additionnant les termes de la forme (cellules changeantes) * (constantes). Pour les modèles linéaires, vous devez toujours sélectionner le moteur Simplex LP, qui est conçu pour trouver efficacement des solutions aux modèles de solveurs linéaires. Le solveur Excel  peut gérer des problèmes avec jusqu’à 200 cellules changeantes et 100 contraintes. Des versions de Solver qui peuvent gérer des problèmes plus importants sont disponibles sur le site Web Solver.com.

comment le moteur non linéaire GrG résout-il les modèles d’optimisation non linéaire?

Si votre cellule cible, l’une de vos contraintes ou les deux contiennent des références à des cellules changeantes qui ne sont pas de la forme (cellule changeante) * (constante), vous avez un modèle non linéaire. Si x et y changent de cellule, des références telles que les suivantes dans la cellule cible, toute contrainte ou les deux rendent votre modèle non linéaire:

Si vos formules non linéaires impliquent des opérateurs mathématiques ordinaires tels que les exemples précédents, une utilisation appropriée du moteur GRG non linéaire devrait rapidement trouver la solution optimale à votre modèle de solveur. Pour illustrer le fonctionnement du moteur non linéaire GRG, supposons que vous souhaitiez maximiser –x² + 4x + 2. Cette fonction est représentée sur la figure .

FIGURE 1: Voici comment le moteur non linéaire GRG maximise une fonction.

Vous pouvez voir que cette fonction est maximisée pour x = 2. Notez également que pour x = 2, la fonction a une pente de 0. Le moteur non linéaire GRG résout ce problème en essayant de trouver un point auquel la pente de la fonction est 0. De même, si vous voulez minimiser y = x², le moteur GRG non linéaire résout ce problème en déterminant que la pente de cette fonction est 0 pour x = 0. Voir la figure ci-dessous.

FIGURE 2: Voici comment le moteur non linéaire GRG minimise une fonction.

Malheureusement, de nombreuses fonctions ne peuvent pas être maximisées simplement en localisant un point où la pente de la fonction est égale à 0. Par exemple, supposons que vous souhaitiez maximiser la fonction illustrée à la figure 3, lorsque x est compris entre –5 et +10.

FIGURE  3: Ceci maximise une fonction avec plusieurs pics.

Vous pouvez voir que cette fonction a plus d’un pic. Si vous commencez avec une valeur de x proche de 1, vous trouvera la bonne solution au problème (x = 1). Si vous commencez près d’un autre pic – disons près de x = 5 – vous trouverez une solution de x = 5, ce qui est incorrect. Parce que dans la plupart des problèmes (en particulier ceux avec plus d’une cellule changeante), vous ne connaissez pas un bon point de départ, il semble que vous ayez un obstacle majeur nettoyer. Heureusement, Excel 2013 a une option à plusieurs départs. Vous pouvez sélectionner Multi-démarrage après avoir choisi Options, puis en cliquant sur l’onglet GRG Non linéaire. Lorsque l’option Multistart est sélectionnée, Excel choisit de nombreuses solutions de départ et trouve la meilleure réponse après avoir commencé par ces points de départ. Cette approche résout généralement le problème des pics et des vallées multiples.

Soit dit en passant, une pression sur Esc arrête le solveur. Gardez également à l’esprit que GRG Multistart fonctionne mieux lorsque vous placez des limites supérieures et inférieures raisonnables sur vos cellules changeantes. (Par exemple, vous ne spécifiez pas de changement de cellule <= 100 millions.)

Le moteur GRG rencontre également des problèmes si la cellule cible, les contraintes ou les deux utilisent des fonctions non lisses telles que MAX, MIN, ABS, SI, SOMME.SI, NB.SI, SOMME.SI.ENS, NB.SI.ENS et d’autres qui impliquent le changement de cellules. Ces fonctions créent des points où il n’y a pas de pente définie de façon unique car la pente change brusquement. Par exemple, supposons qu’un problème d’optimisation vous oblige à modéliser la valeur d’ une option d’achat européenne avec un prix d’exercice de 40 $. Cette option d’achat vous permet d’acheter le stock pour 40 $. Si le cours de l’action est s à l’expiration de l’option, alors la valeur de l’option d’achat peut être calculée avec la relation de formule max (0, s-40) ou SI (s> 40, s-40,0) gr aphé dans la figure 4. Il est clair que lorsque s = 40, la valeur de l’option n’a pas de pente, de sorte que le moteur GRG tomberait en panne.

FIGURE 4 : La valeur de l’option n’a pas de pente pour un prix de l’action de 40 $.

Comme le montre la figure ci-dessous, les modèles de solveurs qui incluent la fonction de valeur absolue (rappelez-vous que la valeur absolue d’un nombre n’est que la distance du nombre à 0) n’auront pas de pente pour x = 0. Dans Excel, l’ABS La fonction (x) renvoie la valeur absolue d’un nombre x.

FIGURE 5: La fonction de valeur absolue n’a pas de pente pour x = 0.

Les problèmes d’optimisation dans lesquels la cellule cible, l’une des contraintes ou les deux n’ont pas de pente pour les valeurs de cellule changeantes sont appelés problèmes d’optimisation non lisses. Même GRG Multistart a des difficultés avec ce type de problèmes. Dans ces situations, vous devez appliquer le moteur Solver Evolutionary. Pour les modèles de solveurs non linéaires, le solveur est limité à 100 cellules changeantes et 100 contraintes.

comment le moteur Evolutionnaire Solver résout-il les problèmes d’optimisation non lisses?

Evolutionnaire Solver dans Excel  est basé sur des algorithmes génétiques, un concept découvert par John Holland, professeur d’informatique à l’Université du Michigan. Pour utiliser le solveur évolutionnaire, commencez par prendre 50 à 100 points dans la région réalisable du problème (c’est-à-dire l’ensemble des points qui répondent aux contraintes). Cet ensemble de points s’appelle la population. Ensuite, la cellule cible est évaluée pour chaque point. En utilisant l’idée de survie du plus apte de la théorie de l’évolution, vous changez les points dans la population d’une manière qui augmente la probabilité que les futurs membres de la population soient situés près des membres de la population précédents qui ont une bonne valeur de cellule cible. Parce que cette approche est basée sur des valeurs de cellules cibles et non sur des pentes, plusieurs pics et vallées ne posent aucun problème. De plus, les fonctions qui n’ont pas de pente (les fonctions dites non lisses) deviennent également un problème moins important. Le moteur de solveur évolutionnaire (comme GRG Multistart) fonctionne également mieux lorsque des limites supérieures et inférieures raisonnables sont placées sur vos cellules changeantes. Après avoir sélectionné le moteur Evolutionary Solver, il est préférable pour choisir Options, cliquez sur l’onglet Évolutionnaire et modifiez le taux de mutation à 0,5. Sélectionnez également la Case à cocher Limites requises sur les variables et augmentez la durée maximale sans amélioration pour 3600 secondes. L’augmentation du taux de mutation diminue la probabilité que le solveur se coince près d’une mauvaise solution. L’augmentation du temps maximum sans amélioration à 3 600 secondes permet au solveur de fonctionner jusqu’à ce qu’il ne parvienne pas à améliorer la cellule cible pendant 3 600 secondes. De cette façon, le Solveur continue de fonctionner si vous quittez votre ordinateur.

Maintenant, utilisez Solver pour résoudre deux problèmes intéressants de localisation des installations.

Aux États-Unis, où une entreprise de transport par Internet devrait-elle localiser un seul entrepôt pour minimiser la distance totale à laquelle les colis sont expédiés?

Le nombre d’envois (en milliers) effectués chaque année vers diverses villes est illustré à la figure 6. (Voir la feuille de calcul Un entrepôt dans le fichier .)

FIGURE 6 : Voici les données pour le problème de l’entrepôt unique.

Une clé de ce modèle est la formule suivante, qui donne la distance approximative entre deux

Les villes américaines ayant une latitude et une longitude données par (Lat1, Long1) et (Lat2, Long2).

Pour commencer, entrez les valeurs d’essai dans les cellules F4: G4 pour la latitude et la longitude de l’entrepôt. Ensuite, en copiant la formule 69 * SQRT ((C7- $ F $ 4) ^ 2 + (D7- $ G $ 4) ^ 2) de F7 à F8: F27, vous calculez la distance approximative de chaque ville de l’entrepôt . Ensuite, en copiant la formule E7 * F7 de G7 à G8: G27 calcule la distance parcourue par les expéditions vers chaque ville. Dans la cellule H5, la formule SUM (G7: G27) calcule la distance totale parcourue par tous les envois. Votre cellule cible est de minimiser H5 en changeant F4: G4. Après avoir sélectionné le moteur non linéaire GRG, la boîte de dialogue Paramètres du solveur apparaît, comme dans la figure 7.

Après avoir cliqué sur Résoudre, vous constaterez que l’entrepôt doit être situé à 36,81 degrés de latitude et 92,48 degrés de longitude, près de Springfield, Missouri. (Voir la figure ci-dessous)

FIGURE 7 : Il s’agit de la boîte de dialogue Paramètres du solveur pour le problème Un entrepôt.

Aux États-Unis, où une entreprise de transport par Internet devrait-elle localiser deux entrepôts pour minimiser la distance totale à laquelle les colis sont expédiés?

Le problème est résolu dans la feuille de calcul Deux entrepôts du fichier , illustrée dans Figure ci-dessous.

Pour commencer, entrez les latitudes et longitudes d’essai pour les entrepôts dans F4: G5. Ensuite, copiez le 69 * SQRT ((C7- $ F $ 4) ^ 2 + (D7- $ G $ 4) ^ 2) formule de F7 à F8: F27 pour calculer la distance de chaque ville de l’entrepôt 1. En copiant le 69 * SQRT (( C7- $ F $ 5) ^ 2 + (D7- $ G $ 5) ^ 2) formule de G7 à G8: G27, vous calculez la distance de chaque ville à l’entrepôt 2. Parce que les expéditions de chaque ville seront envoyées du plus proche vaisselle  maison, vous calculez maintenant la distance de chaque ville à l’entrepôt le plus proche en copiant la formule MIN (F7, G7) de H7 à H8: H27. Dans I7: I27, vous calculez la distance parcourue par les expéditions de chaque ville en copiant la formule H7 * E7 de I7 à I8: I27. Dans la cellule I5, vous calculez la distance totale parcourue par les envois avec la formule SOMME (I7: I27).

FIGURE 8: Cette figure montre un modèle de localisation de deux entrepôts.

Vous êtes maintenant prêt à utiliser Solver pour déterminer les emplacements d’entrepôt optimaux. La configuration de La boîte de dialogue Paramètres du solveur est illustrée à la figure ci-dessous

Commencez par sélectionner le moteur non linéaire GRG, puis utilisez la mauvaise solution, qui place chaque entrepôt à 0 latitude et longitude. Cette solution est mauvaise pour deux raisons: elle localise les entrepôts en Afrique et place deux entrepôts au même endroit. Après avoir exécuté Solver, vous constatez que Solver recommande de placer les deux entrepôts au même endroit. Bien sûr, c’est une solution sous-optimale.

Le problème est double: la fonction MIN crée des situations sans pente, et peut-être que votre cellule cible, en fonction des quatre cellules changeantes, a plusieurs pics et vallées. Si votre cellule cible a plusieurs pics et vallées (en quatre dimensions), votre mauvaise solution de départ n’est peut-être pas proche de la vallée la plus basse, qui est la vraie solution optimale. Lorsque vous suspectez l’existence de plusieurs pics et vallées, c’est une bonne idée d’utiliser GRG Multistart, qui essaie plusieurs points de départ et trouve la meilleure réponse de chacun. La plupart du temps, la meilleure des meilleures découvertes à plusieurs départs sera la solution optimale au problème. Pour utiliser le démarrage multiple, placez des limites supérieure et inférieure sur les cellules changeantes. Pour les limites des cellules qui changent de latitude, vous pouvez sélectionner 0 et 90 degrés. Cela garantit que l’entrepôt est au nord de l’équateur. Pour les limites des cellules qui changent de longitude, choisissez 0 et 150, ce qui garantit que votre emplacement est à l’ouest de Greenwich, en Angleterre, et à l’est d’Anchorage, en Alaska.

FIGURE 8: Le solveur est configuré pour localiser deux entrepôts.

Vous êtes maintenant prêt à utiliser Solver pour déterminer les emplacements d’entrepôt optimaux. La configuration de La boîte de dialogue Paramètres du solveur est illustrée à la figure ci-dessous

Commencez par sélectionner le moteur non linéaire GRG, puis utilisez la mauvaise solution, qui place chaque entrepôt à 0 latitude et longitude. Cette solution est mauvaise pour deux raisons: elle localise les entrepôts en Afrique et place deux entrepôts au même endroit. Après avoir exécuté Solver, vous constatez que Solver recommande de placer les deux entrepôts au même endroit. Bien sûr, c’est une solution sous-optimale.

Le problème est double: la fonction MIN crée des situations sans pente, et peut-être que votre cellule cible, en fonction des quatre cellules changeantes, a plusieurs pics et vallées. Si votre cellule cible a plusieurs pics et vallées (en quatre dimensions), votre mauvaise solution de départ n’est peut-être pas proche de la vallée la plus basse, qui est la vraie solution optimale. Lorsque vous suspectez l’existence de plusieurs pics et vallées, c’est une bonne idée d’utiliser GRG Multistart, qui essaie plusieurs points de départ et trouve la meilleure réponse de chacun. La plupart du temps, la meilleure des meilleures découvertes à plusieurs départs sera la solution optimale au problème. Pour utiliser le démarrage multiple, placez des limites supérieure et inférieure sur les cellules changeantes. Pour les limites des cellules qui changent de latitude, vous pouvez sélectionner 0 et 90 degrés. Cela garantit que l’entrepôt est au nord de l’équateur. Pour les limites des cellules qui changent de longitude, choisissez 0 et 150, ce qui garantit que votre emplacement est à l’ouest de Greenwich, en Angleterre, et à l’est d’Anchorage, en Alaska.

FIGURE 9 : Le solveur est configuré pour localiser deux entrepôts.

Après avoir exécuté le moteur GRG Multistart, vous constatez que la distance totale parcourue était de 119 676 miles, et la distance moyenne parcourue par expédition est de 502 miles. Les emplacements des entrepôts sont indiqués dans les cellules F4: G5 de la figure 35-8. L’entrepôt 1 est situé près de Lexington, Kentucky; L’entrepôt 2 est situé près de Lancaster, en Californie.

Pour confirmer que Solver a trouvé la solution optimale, exécutez le moteur Evolutionary Solver. Vous ne trouvez pas amélioration de la solution optimale.

Supposons que vous ayez défini une limite supérieure pour la longitude de 110 degrés. Après avoir exécuté Solver, vous auriez constaté que Solver recommande une longitude proche de 110 degrés. Si vous placez des limites sur une cellule changeante et que le solveur force la cellule changeante à prendre une valeur près d’une limite, vous devez relâcher la limite.

S’abonner
Notifier de
0 Commentaires
Inline Feedbacks
Voir tous les commentaires

Initiation à Excel

Fonctions Excel

Excel VBA

Macros VBA Utiles

Plus d'outils

Sur Facebook

Sur YouTube

0
Nous aimerions avoir votre avis, veuillez laisser un commentaire.x
()
x