Le solveur utilise l'algorithme de réduction de gradient généralisé

Résumé

Le solveur de Microsoft Excel utilise l’algorithme Generalized Reduced Gradient (GRG2) pour optimiser les problèmes non linéaires. Cet algorithme a été développé par Leon Lasdon, de l’Université du Texas à Austin et Allan Waren, de l’Université de Cleveland.


Les problèmes linéaires et entiers utilisent la méthode simplex avec des bornes sur les variables et la branche et la méthode liée, mis en œuvre par John Watson et Dan Fylstra, de Frontline Systems, Inc.

Plus d'informations

Le solveur de Microsoft Excel utilise des méthodes numériques itératifs qui impliquent des valeurs d’évaluation « rebranchant » pour les cellules variables et en observant les résultats calculés par les cellules de contrainte et la cellule optimale. Chaque version d’évaluation est appelée une « itération ». Parce qu’une approche de pure « essai et erreur » prendrait un temps extrêmement long (en particulier pour des problèmes impliquant de nombreuses cellules variables et les contraintes), solveur de Microsoft Excel effectue des analyses complètes des sorties observées et leur taux de modification que les entrées sont différentes, pour guider la sélection des nouvelles valeurs d’évaluation.


Un problème typique, les contraintes et la cellule optimale sont des fonctions de (autrement dit, ils dépendent) les cellules variables. Le (la première dérivée d’une fonction de mesure son taux de modification que l’entrée est modifiée. Lorsqu’il y a plusieurs valeurs d’entrée, la fonction a plusieurs dérivées partielles mesurer son taux de changement par rapport à chacune des valeurs d’entrée ; les dérivées partielles forment un vecteur appelé le dégradé de la fonction.


Dérivés (et dégradés) jouent un rôle crucial dans les procédés itératifs dans le solveur de Microsoft Excel. Ils fournissent des indications sur la façon dont les cellules variables doivent être différenciées. Par exemple, si la cellule optimale est agrandie et ses dérivées partielles par rapport à une cellule variable est un grand nombre de positif, alors qu’une autre dérivée de partielle est proche de zéro, le solveur de Microsoft Excel augmentera probablement la première réglable valeur de la cellule pour l’itération suivante. Une dérivée partielle négative indique que la valeur de la cellule variables connexes doit être différenciée dans la direction opposée.


Transfert et centrale de différenciation


Le solveur de Microsoft Excel est une approximation de DERIVES numériquement en déplaçant les valeur de chaque cellule variable légèrement et en observant le taux de changement de chaque cellule de la contrainte et la cellule optimale. Ce processus est appelé une estimation de différence finie de la dérivée. Le solveur de Microsoft Excel peut utiliser différenciation ou la différenciation centrée, comme contrôlées par le choix de dérivés dans la boîte de dialogue Options du solveur.


Différenciation utilise un point unique (qui est, un ensemble de valeurs de cellules variables) qui est légèrement différent du point en cours pour calculer le dérivé, tandis que la différenciation centrée utilise les deux points dans des directions opposées. La différenciation centrée est plus précise si le dérivé change rapidement au point actuel, mais il nécessite davantage de recalculs. Est différenciation le choix par défaut, qui convient dans la plupart des situations.


Les problèmes linéaires peuvent être résolus avec beaucoup moins de travail que les problèmes non linéaires ; Le solveur de Microsoft Excel n’a pas besoin de recalculer les variables de DERIVES, et il peut extrapoler le long de lignes droites au lieu de recalculer la feuille de calcul. Ces gains de temps sont mis en jeu lorsque vous sélectionnez la case à cocher Modèle supposé linéaire dans la boîte de dialogue Options du solveur. Si vous n’activez pas cette case, le solveur de Microsoft Excel a toujours peut résoudre le problème, mais il passera ainsi plus de temps.


Lorsque vous savez qu’un problème est complètement linéaire, choisissez l’option Modèle supposé linéaire accélère le processus de résolution d’un facteur de deux à vingt fois (en fonction de la taille de la feuille de calcul). L’inconvénient est que, si cette option est sélectionnée et que les formules de la feuille de calcul réel sont non linéaires, vous résoudre le problème de mauvais.


Bien que le solveur de Microsoft Excel vérifie la solution finale lorsque l’option Modèle supposé linéaire est activée à l’aide d’un recalcul de la feuille de calcul complète, ce n’est pas une garantie absolue que le problème est réellement linéaire. Vous pouvez toujours vérifier de nouveau la solution en exécutant le même problème avec la case à cocher.


De nombreuses feuilles de calcul business contiennent principalement des formules linéaires plus quelques principales relations non linéaires. Ces problèmes ne sont pas directement les méthodes de programmation linéaire ou l’option Modèle supposé linéaire. Ils exigent la pleine puissance de programmation non linéaire. La méthode Generalized Reduced Gradient utilisée par le solveur de Microsoft Excel est très efficace pour les problèmes de ce type car il utilise des approximations linéaires pour les fonctions de problème à un nombre d’étapes dans le processus de solution ; Lorsque les fonctions sont linéaires, ces approximations sont exactes.


Conditions d’optimisation


Car la première dérivée (ou dégradé) de la cellule optimale mesure son taux de modifications par rapport aux (chaque) les cellules variables, lorsque toutes les dérivées partielles de la cellule optimale sont zéro (c'est-à-dire que le dégradé est le vecteur zéro), les conditions de premier ordre au caractère optimal ont été satisfaites (certains supplémentaire deuxième ordre conditions doivent être vérifiées ainsi) avoir trouvé le plus élevé (ou le plus bas) valeur possible pour la cellule optimale.


Plusieurs Points localement optimales


Certains problèmes ont de nombreux points localement optimales où les dérivées partielles de la cellule optimale sont égales à zéro. Affiche un graphe de la fonction de cellule optimale dans de tels cas de bosses et creux de différentes hauteurs et profondeurs. Lors du démarrage d’un ensemble donné de valeurs de cellules variables, les méthodes utilisées par le solveur de Microsoft Excel ont tendance à converger vers un sol hilltop ou valley unique proche du point de départ. Mais le solveur de Microsoft Excel n'a pas de moyen sûr de savoir s'il y a un colline plus élevée, par exemple, plus loin.


La seule façon pour rechercher les valeurs optimales globales est d’appliquer les connaissances externe du problème. Soit par le biais de bon sens sur le problème ou l’expérimentation, vous devez déterminer la zone générale dans lequel les valeurs optimales globales se trouve et démarrez le solveur de Microsoft Excel avec les valeurs de cellules variables qui se trouvent dans cette région. Sinon, vous pouvez démarrer le solveur de Microsoft Excel à partir de plusieurs points différents, largement séparées et voir quelle solution est préférable.


Pour plus d’informations sur le processus de résolution interne du solveur, contactez :


   Frontline Systems
P.O. Box 4288
Incline Village, Nevada 89450-4288
(702) 831-0300



Vous pouvez également trouver des informations sur les http://www.frontsys.com/

Les informations de contact de sociétés tierces incluses dans cet article sont fournies pour vous aider à trouver l’assistance technique dont vous avez besoin. Ces informations de contact sont sujettes à modification sans préavis. Microsoft ne garantit l’exactitude de ces informations de contact de sociétés tierces.


Le code du programme Solveur Microsoft Excel est copyright 1990, 1991, 1992 par Portions de Frontline Systems, Inc. copyright 1989 par Optimal Methods, Inc.

Références

« Guide de l’utilisateur du Solveur Microsoft Excel » pour Macintosh, version 3.0, page 2

« Guide de l’utilisateur du Solveur Microsoft Excel » pour Windows, version 3.0, page 2
Propriétés

ID d'article : 82890 - Dernière mise à jour : 9 janv. 2017 - Révision : 1

Commentaires