Méthode extremum conditionnelle des multiplicateurs de Lagrange indéterminés. Méthode des multiplicateurs de Lagrange indéterminés. Résoudre un système d'équations non linéaires à deux inconnues à l'aide de l'outil Solution Finder

Il est utilisé pour résoudre des problèmes avec une expression analytique du critère d'optimalité et en présence de restrictions sur l'indépendance taper des variables est égal Pour recevoir solution analytique il est nécessaire que les restrictions aient une forme analytique. Application multiplicateurs non définis Lagrange permet de réduire le problème d'optimisation avec restrictions à un problème résolu par des méthodes d'étude des fonctions de l'analyse classique. Dans ce cas, l'ordre du système d'équations résolu pour trouver l'extremum du critère d'optimisation augmente du nombre de contraintes. La méthode est efficace lorsque le nombre de variables est de trois ou moins. La méthode est également utilisée lorsque le nombre de variables est supérieur à trois, si le processus est décrit par des équations finies.

Supposons qu'il soit nécessaire de trouver l'extremum d'une fonction qui dépend de n variables, elles-mêmes reliées par des relations. L'extremum atteint par une fonction, compte tenu du respect des conditions, est dit relatif ou conditionnel. Si le nombre de variables est égal au nombre de relations (), alors les inconnues inconnues sont trouvées en résolvant le système d'équations décrit par les relations. Résoudre le problème d'optimisation revient à vérifier les valeurs des variables ainsi trouvées par rapport aux fonctions. Ainsi, le problème extrême peut être résolu recherche simple variables qui satisfont aux conditions.

Si m< n , alors à partir des équations de communication, nous pouvons trouver la dépendance m variables de n-m variables restantes, c'est-à-dire

La fonction peut être obtenue en substituant les variables résultantes dans la fonction. Cela dépendra alors uniquement de variables qui ne sont pas liées par des conditions supplémentaires. Par conséquent, en supprimant les restrictions, il est possible de réduire la dimension du problème d’optimisation initial. Souvent, le problème ne peut pas être résolu analytiquement de cette manière. Par conséquent, pour résoudre les problèmes de recherche de l'extremum d'une fonction de plusieurs variables, la méthode de Lagrange des multiplicateurs indéfinis est généralement utilisée.

Lors de l'introduction de nouvelles variables appelées multiplicateurs de Lagrange indéfinis, il devient possible d'introduire une nouvelle fonction

ceux. fonction m+n variables, dans lesquelles les restrictions imposées par le système de fonctions sont incluses comme partie intégrante.

Une valeur extrême d'une fonction coïncide avec une valeur extrême d'une fonction si la condition de contrainte est remplie. Une condition nécessaire pour l'extremum d'une fonction à plusieurs variables est que la différentielle de cette fonction au point extrême soit égale à zéro, c'est-à-dire

Pour que cette expression soit satisfaite pour toutes valeurs des différentielles indépendantes, il faut que les coefficients de ces différentiels soient égaux à zéro, ce qui donne un système d'équations

Dans ce cas, de nouveaux indépendants sont déterminés à partir de la condition

La combinaison des systèmes (4.3.1) et (4.3.2) peut être obtenue

Ainsi, le problème sous la forme (4.3.3) se réduit à la tâche : trouver

Par ailleurs, il convient de noter que dans cas général La méthode du multiplicateur de Lagrange permet de trouver uniquement conditions nécessaires existence d'un extremum conditionnel pour fonctions continues, ayant des dérivées continues. Cependant, à partir de signification physique le problème à résoudre sait généralement s'il s'agit du maximum ou du minimum de la fonction ; de plus, en règle générale, dans les problèmes de conception, la fonction sur le segment considéré est unimodale. Par conséquent, dans les problèmes de conception, il n'est pas nécessaire de vérifier les valeurs des variables trouvées lors de la résolution des systèmes d'équations considérés pour l'extremum en utilisant l'analyse des dérivées d'ordre supérieur.

Brève théorie

La méthode du multiplicateur de Lagrange est une méthode classique de résolution de problèmes programmation mathématique(notamment convexe). Malheureusement, quand application pratique La méthode peut rencontrer d’importantes difficultés de calcul, réduisant ainsi le champ de son utilisation. Nous considérons ici la méthode de Lagrange principalement parce qu'il s'agit d'un appareil activement utilisé pour justifier diverses méthodes numériques modernes largement utilisées dans la pratique. Quant à la fonction de Lagrange et aux multiplicateurs de Lagrange, ils jouent un rôle indépendant et extrêmement important dans la théorie et les applications non seulement de la programmation mathématique.

Considérons un problème d'optimisation classique :

Parmi les restrictions de ce problème, il n'y a pas d'inégalités, il n'y a pas de conditions pour la non-négativité des variables, leur discrétion et les fonctions et sont continues et ont des dérivées partielles par rapport à au moins deuxième commande.

L'approche classique pour résoudre le problème fournit un système d'équations (conditions nécessaires) qui doit être satisfaite par le point qui fournit à la fonction un extremum local sur l'ensemble des points qui satisfont aux restrictions (pour un problème de programmation convexe, le point trouvé sera également le point extrême global).

Supposons qu'en un point la fonction (1) ait un conditionnel extrême et le rang de la matrice est . Ensuite les conditions nécessaires seront écrites sous la forme :

il existe une fonction de Lagrange ;

– Multiplicateurs de Lagrange.

Il existe également des conditions suffisantes dans lesquelles la solution du système d'équations (3) détermine le point extrême de la fonction. Cette question est résolue à partir de l'étude du signe de la différentielle seconde de la fonction de Lagrange. Cependant, les conditions suffisantes ont surtout un intérêt théorique.

Vous pouvez spécifier la procédure suivante pour résoudre le problème (1), (2) à l'aide de la méthode du multiplicateur de Lagrange :

1) composer la fonction de Lagrange (4) ;

2) trouver les dérivées partielles de la fonction de Lagrange par rapport à toutes les variables et les égaliser

zéro. Ainsi, on obtiendra un système (3), constitué d'équations. Résolvez le système résultant (si cela s'avère possible !) et trouvez ainsi tous les points stationnaires de la fonction de Lagrange ; 3) à partir de points stationnaires pris sans coordonnées, sélectionner les points auxquels la fonction a des extrema locaux conditionnels en présence de restrictions (2). Ce choix se fait par exemple en utilisant des conditions suffisantes extrême local

. Souvent, l'étude est simplifiée si des conditions spécifiques du problème sont utilisées.

Exemple de solution de problème

Condition problématique

L'entreprise produit deux types de biens en quantités et . La fonction de coût utile est déterminée par la relation. Les prix de ces biens sur le marché sont égaux et en conséquence.

Déterminer à quels volumes de production le profit maximum est atteint et à quoi il est égal si les coûts totaux ne dépassent pas

Vous avez du mal à comprendre l’avancée d’une décision ? Le site propose un service Résolution de problèmes en utilisant des méthodes de solutions optimales sur commande

Solution du problème

Modèle économique et mathématique du problème

Fonction bénéfice :

Restrictions de coûts :

On obtient le modèle économique et mathématique suivant :

De plus, selon le sens de la tâche

Méthode du multiplicateur de Lagrange

Composons la fonction de Lagrange :

On retrouve les dérivées partielles du 1er ordre :

Créons et résolvons un système d'équations :

Depuis lors

Bénéfice maximal :

Répondre
Un exemple de résolution d'un problème de programmation quadratique convexe à l'aide d'une méthode graphique est donné.

Résoudre un problème linéaire par méthode graphique
Considéré méthode graphique résolution de problèmes programmation linéaire(ZLP) avec deux variables. Un exemple de la tâche est donné description détaillée construire un dessin et trouver une solution.

Le modèle de gestion des stocks de Wilson
À l'aide de l'exemple de résolution du problème, le modèle de base de gestion des stocks (modèle Wilson) est considéré. Les indicateurs de modèle suivants ont été calculés : taille optimale quantités commandées, frais de détention annuels, intervalles de livraison et point de commande.

Matrice du ratio des coûts directs et matrice des entrées-sorties
En utilisant l'exemple de la résolution d'un problème, le modèle intersectoriel de Léontiev est considéré. Le calcul de la matrice des coefficients des coûts directs des matières, de la matrice des « entrées-sorties », de la matrice des coefficients des coûts indirects, des vecteurs de consommation finale et de production brute est présenté.

Méthode du multiplicateur de Lagrange est une méthode classique pour résoudre des problèmes de programmation mathématique (en particulier la programmation convexe). Malheureusement, l’application pratique de la méthode peut se heurter à d’importantes difficultés de calcul, réduisant ainsi la portée de son utilisation. Nous considérons ici la méthode de Lagrange principalement parce qu'il s'agit d'un appareil activement utilisé pour justifier diverses méthodes numériques modernes largement utilisées dans la pratique. Quant à la fonction de Lagrange et aux multiplicateurs de Lagrange, ils jouent un rôle indépendant et extrêmement important dans la théorie et les applications non seulement de la programmation mathématique.

Considérons le problème d'optimisation classique

max (min) z=f(x) (7.20)

Ce problème se distingue du problème (7.18), (7.19) en ce sens que parmi les restrictions (7.21) il n'y a pas d'inégalités, il n'y a pas de conditions pour que les variables soient non négatives, leur discrétion et les fonctions f(x) sont continues et ont des dérivées partielles d'au moins le second ordre.

L'approche classique de résolution du problème (7.20), (7.21) donne un système d'équations (conditions nécessaires) qui doit être satisfaite par le point x*, qui fournit à la fonction f(x) un extremum local sur l'ensemble des points satisfaisant contraintes (7.21) (pour le problème de programmation convexe, le point trouvé x*, conformément au théorème 7.6, sera simultanément un point d'extremum global).

Supposons qu'au point x* la fonction (7.20) ait un extremum conditionnel local et que le rang de la matrice soit égal à . Ensuite les conditions nécessaires seront écrites sous la forme :

(7.22)

il existe une fonction de Lagrange ; - Multiplicateurs de Lagrange.

Il existe également des conditions suffisantes dans lesquelles la solution du système d'équations (7.22) détermine le point extremum de la fonction f(x). Cette question est résolue à partir de l'étude du signe de la différentielle seconde de la fonction de Lagrange. Cependant, les conditions suffisantes ont surtout un intérêt théorique.

Vous pouvez spécifier la procédure suivante pour résoudre le problème (7.20), (7.21) en utilisant la méthode du multiplicateur de Lagrange :

1) composer la fonction de Lagrange (7.23) ;

2) trouver les dérivées partielles de la fonction de Lagrange par rapport à toutes les variables et mettez-les égaux à zéro. Cela donnera lieu au système (7.22), composé d’équations. Résolvez le système résultant (si cela s'avère possible !) et trouvez ainsi tous les points stationnaires de la fonction de Lagrange ;

3) à partir de points stationnaires pris sans coordonnées, sélectionner les points auxquels la fonction f(x) a des extrema locaux conditionnels en présence de restrictions (7.21). Ce choix se fait par exemple en utilisant des conditions suffisantes pour un extremum local. Souvent, l'étude est simplifiée si des conditions spécifiques du problème sont utilisées.

Exemple 7.3. Trouver répartition optimale ressource limitée dans une unité. entre n consommateurs, si le profit tiré de l'allocation de x j unités de ressource au jème consommateur est calculé par la formule .

Solution. Le modèle mathématique du problème a vue suivante:

On compose la fonction de Lagrange :

.

Nous trouvons dérivées partielles de la fonction de Lagrange et assimilons-les à zéro :

En résolvant ce système d'équations, on obtient :

Ainsi, si le jème consommateur se voit attribuer des unités. ressource, alors le profit total atteindra sa valeur maximale et s'élèvera à den. unités

Nous avons examiné la méthode de Lagrange appliquée à problème classique optimisation. Cette méthode peut être généralisée au cas où les variables sont non négatives et où certaines contraintes sont données sous forme d'inégalités. Cependant, cette généralisation est avant tout théorique et ne conduit pas à des algorithmes de calcul spécifiques.

En conclusion, donnons les multiplicateurs de Lagrange interprétation économique. Pour ce faire, tournons-nous vers le problème d’optimisation classique le plus simple

maximum (min) z=f(x 1 , X 2); (7.24)

𝜑(x 1, x 2)=b. (7.25)

Supposons que l'extremum conditionnel soit atteint au point . La valeur extrême correspondante de la fonction f(x)

Supposons que dans les restrictions (7.25) la quantité b peut changer, alors les coordonnées du point extremum, et donc la valeur extrême f* fonctions f(x) deviendront des quantités en fonction de b, c'est-à-dire ,, et donc la dérivée de la fonction (7.24)

La méthode de détermination d'un extremum conditionnel commence par la construction d'une fonction de Lagrange auxiliaire qui, dans la région des solutions réalisables, atteint un maximum pour les mêmes valeurs de variables x 1 ,x 2 , ..., x n , qui est la même que la fonction objectif z . Laissez le problème de la détermination de l'extremum conditionnel de la fonction être résolu z = f(X) sous restrictions φ je ( x 1 , x 2 , ..., x n ) = 0, je = 1, 2, ..., m , m < n

Composons une fonction

qui s'appelle Fonction de Lagrange. X , - facteurs constants ( Multiplicateurs de Lagrange). A noter que les multiplicateurs de Lagrange peuvent avoir une signification économique. Si f(x 1 ,x 2 , ..., x n ) - des revenus conformes au plan X = (x 1 ,x 2 , ..., x n ) , et la fonction φ je (x 1 ,x 2 , ..., x n ) - les coûts de la ième ressource correspondant à ce plan, puis X , - prix (évaluation) de la ième ressource, caractérisant l'évolution de la valeur extrême fonction objectif en fonction de l'évolution de la taille de la ième ressource (estimation marginale). L(X) - fonction n+m variables (x 1 ,x 2 , ..., x n , λ 1 , λ 2 , ..., λ n ) . La détermination des points stationnaires de cette fonction conduit à résoudre le système d'équations

C'est facile de voir ça . Ainsi, la tâche de trouver l'extremum conditionnel de la fonction z = f(X) se réduit à trouver l’extremum local de la fonction L(X) . Si un point stationnaire est trouvé, alors la question de l'existence d'un extremum dans les cas les plus simples est résolue sur la base de conditions suffisantes pour l'extremum - étudier le signe du deuxième différentiel d 2 L(X) en un point stationnaire, à condition que la variable incrémente Δx je - reliés par des relations

obtenu en différenciant les équations de couplage.

Résoudre un système d'équations non linéaires à deux inconnues à l'aide de l'outil Solution Finder

Paramètres Trouver une solution permet de trouver une solution à un système d'équations non linéaires à deux inconnues :

Où
- fonction non linéaire des variables x Et oui ,
- constante arbitraire.

On sait que le couple ( x , oui ) est une solution du système d'équations (10) si et seulement si c'est une solution de l'équation suivante à deux inconnues :

AVEC par contre, la solution du système (10) est les points d'intersection de deux courbes : f ] (x, oui) = C Et f 2 (x, y) = C 2 dans l'avion XOOui.

Cela conduit à une méthode permettant de trouver les racines du système. équations non linéaires :

Déterminer (au moins approximativement) l'intervalle d'existence d'une solution au système d'équations (10) ou à l'équation (11). Ici, il faut prendre en compte le type d'équations incluses dans le système, le domaine de définition de chacune de leurs équations, etc. Parfois, la sélection d'une première approximation de la solution est utilisée ;

Calculez la solution de l'équation (11) pour les variables x et y sur l'intervalle sélectionné, ou construisez des graphiques de fonctions f 1 (x, oui) = C, et f 2 (x,y) = C 2 (système (10)).

Localisez les racines supposées du système d'équations - trouvez plusieurs valeurs minimales dans le tableau répertoriant les racines de l'équation (11), ou déterminez les points d'intersection des courbes incluses dans le système (10).

4. Trouvez les racines du système d'équations (10) à l'aide du complément Trouver une solution.

Méthode multiplicatriceLagrange(dans la littérature anglaise « LaGrange's method of undetermined multiplicateurs ») ˗ il s'agit d'une méthode numérique pour résoudre problèmes d'optimisation, qui permet de déterminer l'extremum « conditionnel » de la fonction objectif (valeur minimale ou maximale)

en présence de restrictions spécifiées sur ses variables sous forme d'égalités (c'est-à-dire que la plage de valeurs admissibles est définie)

˗ ce sont les valeurs de l'argument de la fonction (paramètres contrôlables) sur le domaine réel auquel la valeur de la fonction tend vers un extremum. L’utilisation du nom d’extremum « conditionnel » est due au fait que les variables sont soumises à condition supplémentaire, ce qui limite la plage de valeurs acceptables lors de la recherche de l'extremum d'une fonction.

La méthode du multiplicateur de Lagrange permet de transformer le problème de recherche d'un extremum conditionnel d'une fonction objectif sur un ensemble de valeurs admissibles en problème sans optimisation conditionnelle fonctions.

Dans le cas où les fonctions Et sont continues avec leurs dérivées partielles, alors il existe de telles variables λ qui ne sont pas simultanément égales à zéro, sous lesquelles la condition suivante est satisfaite :

Ainsi, conformément à la méthode du multiplicateur de Lagrange, pour trouver l'extremum de la fonction objectif sur l'ensemble des valeurs admissibles, je compose la fonction de Lagrange L(x, λ), qui est encore optimisée :

où λ ˗ est un vecteur de variables supplémentaires appelées multiplicateurs de Lagrange indéterminés.

Ainsi, le problème de trouver l’extremum conditionnel de la fonction f(x) a été réduit au problème de recherche extrême inconditionnel fonctions L(x, λ).

Et

La condition nécessaire pour l'extremum de la fonction de Lagrange est donnée par un système d'équations (le système est constitué d'équations « n + m ») :

La résolution de ce système d'équations permet de déterminer les arguments de la fonction (X) pour lesquels la valeur de la fonction L(x, λ), ainsi que la valeur de la fonction cible f(x) correspondent à l'extremum.

La grandeur des multiplicateurs de Lagrange (λ) présente un intérêt pratique si les contraintes sont présentées sous la forme d'un terme libre dans l'équation (constante). Dans ce cas, nous pouvons envisager une valeur supplémentaire (augmentation/diminution) de la fonction objectif en modifiant la valeur de la constante dans le système d'équations. Ainsi, le multiplicateur de Lagrange caractérise le taux de variation du maximum de la fonction objectif lorsque la constante limite change.

Il existe plusieurs façons de déterminer la nature de l'extremum de la fonction résultante :

Première méthode : Soient les coordonnées du point extremum, et - valeur correspondante fonction cible. Un point proche du point est pris et la valeur de la fonction objectif est calculée :

Si , alors il y a un maximum au point.

Si , alors il y a un minimum au point.

Deuxième méthode : Une condition suffisante à partir de laquelle la nature de l'extremum peut être déterminée est le signe de la deuxième différentielle de la fonction de Lagrange. La deuxième différentielle de la fonction de Lagrange est définie comme suit :

Si dans point donné minimum, si , alors la fonction objectif f(x) a une condition maximum.

Troisième méthode : Aussi, la nature de l'extremum de la fonction peut être déterminée en considérant le Hessien de la fonction de Lagrange. La matrice hessienne est une matrice symétrique matrice carrée dérivées partielles secondes d'une fonction au point où les éléments de la matrice sont symétriques par rapport à la diagonale principale.

Pour déterminer le type d’extremum (maximum ou minimum d’une fonction), vous pouvez utiliser la règle de Sylvester :

1. Pour que la différentielle seconde de la fonction de Lagrange soit de signe positif il faut que les mineurs angulaires de la fonction soient positifs. Dans de telles conditions, la fonction à ce stade a un minimum.

2. Pour que la deuxième différentielle de la fonction de Lagrange soit de signe négatif , il faut que les mineurs angulaires de la fonction alternent, et le premier élément de la matrice doit être négatifv. Dans de telles conditions, la fonction a à ce stade un maximum.

Par mineur angulaire, nous entendons le mineur situé dans les k premières lignes et k colonnes de la matrice d'origine.

Les bases signification pratique La méthode Lagrange est qu'elle permet de passer de l'optimisation conditionnelle à l'optimisation inconditionnelle et, par conséquent, d'élargir l'arsenal méthodes disponibles résoudre le problème. Cependant, le problème de la résolution d'un système d'équations, auquel il se réduit cette méthode, dans le cas général, n’est pas plus simple que le problème initial de trouver un extremum. De telles méthodes sont dites indirectes. Leur utilisation s'explique par la nécessité d'obtenir une solution à un problème extrême sous forme analytique (par exemple, pour certains calculs théoriques). Lors de la résolution de problèmes spécifiques problèmes pratiques Des méthodes directes sont généralement utilisées, basées sur des processus itératifs de calcul et de comparaison des valeurs des fonctions à optimiser.

Méthode de calcul

1 étape: Nous déterminons la fonction de Lagrange à partir de la fonction objectif et du système de restrictions donnés :

Avant

Afin d'ajouter votre commentaire à l'article, veuillez vous inscrire sur le site.