Programmation mathématique méthode Lagrange. Méthode du multiplicateur de Lagrange

méthode Lagrange─ est une méthode de résolution d'un problème d'optimisation sous contrainte dans laquelle des contraintes, écrites sous forme de fonctions implicites, sont combinées avec une fonction objectif sous la forme d'une nouvelle équation appelée Lagrangien.

Considérons un cas particulier du problème général de programmation non linéaire :

Étant donné un système d'équations non linéaires (1) :

(1) gi(x1,x2,…,xn)=bi (i=1..m),

Trouver la plus petite (ou la plus grande) valeur de la fonction (2)

(2) f (x1,x2,…,xn),

s'il n'y a aucune condition pour que les variables soient non négatives et que f(x1,x2,…,xn) et gi(x1,x2,…,xn) sont des fonctions continues avec leurs dérivées partielles.

Pour trouver une solution à ce problème, vous pouvez appliquer la méthode suivante : 1. Entrez un ensemble de variables λ1, λ2,…, λm, appelées multiplicateurs de Lagrange, composez la fonction de Lagrange (3)

(3) F(х1,х2,…,хn, λ1,λ2,…,λm) = f(х1,х2,…,хn)+ λi.

2. Trouvez les dérivées partielles de la fonction de Lagrange par rapport aux variables xi et λi et assimilez-les à zéro.

3. En résolvant le système d'équations, trouvez les points auxquels la fonction objective du problème peut avoir un extremum.

4. Parmi les points suspects pas un extremum, trouvez ceux où l'extremum est atteint, et calculez les valeurs de la fonction en ces points .

4. Comparez les valeurs obtenues de la fonction f et choisissez la meilleure.

Selon le plan de production, l'entreprise doit fabriquer 180 produits. Ces produits peuvent être fabriqués de deux manières technologiques. Lors de la production de produits x1 en utilisant la méthode I, les coûts sont de 4*x1+x1^2 roubles, et lors de la production de produits x2 en utilisant la méthode II, ils sont de 8*x2+x2^2 roubles. Déterminez combien de produits doivent être fabriqués en utilisant chaque méthode, afin que le coût total de production soit minime.

Solution : La formulation mathématique du problème consiste à déterminer la plus petite valeur d'une fonction de deux variables :

f = 4*x1+x1^2 +8*x2 +x2^2, à condition que x1 +x2 = 180.

Composons la fonction de Lagrange :

F(x1,x2,λ) = 4*x1+x1^2+8*x2+x2^2+λ*(180-x1-x2).

Calculons ses dérivées partielles par rapport à x1, x2, λ et assimilons-les à 0 :

Déplaçons λ vers les côtés droits des deux premières équations et égalisons leurs côtés gauches, nous obtenons 4 + 2*x1 = 8 + 2*x2, ou x1 − x2 = 2.

En résolvant la dernière équation avec l'équation x1 + x2 = 180, nous trouvons x1 = 91, x2 = 89, c'est-à-dire que nous avons obtenu une solution qui satisfait aux conditions :

Trouvons la valeur de la fonction objectif f pour ces valeurs des variables :

F(x1, x2) = 17278

Ce point est suspect pour un point extrême. En utilisant les dérivées partielles secondes, nous pouvons montrer qu'au point (91.89) la fonction f a un minimum.

Trouver un polynôme signifie déterminer les valeurs de son coefficient . Pour ce faire, en utilisant la condition d'interpolation, vous pouvez former un système d'équations algébriques linéaires (SLAE).

Le déterminant de ce SLAE est habituellement appelé déterminant de Vandermonde. Le déterminant de Vandermonde n'est pas égal à zéro pour for , c'est-à-dire dans le cas où il n'y a pas de nœuds correspondants dans la table de recherche. Cependant, on peut affirmer que le SLAE a une solution et que cette solution est unique. Après avoir résolu le SLAE et déterminé les coefficients inconnus vous pouvez construire un polynôme d'interpolation.

Un polynôme qui satisfait aux conditions d'interpolation, lorsqu'il est interpolé par la méthode de Lagrange, est construit sous la forme d'une combinaison linéaire de polynômes du nième degré :

Les polynômes sont généralement appelés basique polynômes. Pour Polynôme de Lagrange satisfait les conditions d'interpolation, il est extrêmement important que les conditions suivantes soient remplies pour ses polynômes de base :

Pour .

Si ces conditions sont remplies, alors pour tout nous avons :

De plus, le respect des conditions spécifiées pour les polynômes de base signifie que les conditions d’interpolation sont également satisfaites.

Déterminons le type de polynômes de base en fonction des restrictions qui leur sont imposées.

1ère condition :à .

2ème condition : .

Finalement, pour le polynôme de base on peut écrire :

Ensuite, en remplaçant l'expression résultante des polynômes de base dans le polynôme d'origine, nous obtenons la forme finale du polynôme de Lagrange :

Une forme particulière du polynôme de Lagrange at est généralement appelée formule d'interpolation linéaire :

.

Le polynôme de Lagrange pris en est généralement appelé formule d'interpolation quadratique :

Méthode Lagrange. - concept et types. Classification et caractéristiques de la catégorie "Méthode Lagrange". 2017, 2018.

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 est appelée 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 , est le prix (estimation) de la ième ressource, caractérisant l'évolution de la valeur extrême de la 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 Rechercher une solution

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 en surface 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.

Brève théorie

La méthode du multiplicateur de Lagrange est une méthode classique de résolution de problèmes de programmation mathématique (en particulier convexes). 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 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 sont continues et ont des dérivées partielles d'au moins du second ordre.

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 extremum conditionnel local et que le rang de la matrice soit égal à . 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 pour un extremum local. Souvent, l'étude est simplifiée si des conditions spécifiques du problème sont utilisées.

Exemple de solution de problème

La tâche

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

La 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

Il est donc nécessaire de libérer de la nourriture. marchandises du 1er type et unités. marchandises du 2ème type. Dans ce cas, le profit sera maximum et s'élèvera à 270.
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
Une méthode graphique pour résoudre un problème de programmation linéaire (LPP) avec deux variables est considérée. À l'aide de l'exemple d'un problème, une description détaillée de la construction d'un dessin et de la recherche d'une solution est donnée.

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é. Des indicateurs de modèle tels que la taille optimale du lot de commande, les coûts de stockage annuels, l'intervalle entre les livraisons et le point de passation des commandes ont été calculés.

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 matériels directs, de la matrice « entrées-sorties », de la matrice des coefficients des coûts indirects, des vecteurs de consommation finale et de production brute est présenté.

an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = f(t)

consiste à remplacer des constantes arbitraires ck dans la solution générale

z(t) = c1z1(t) + c2z2(t) + ...

Cnzn(t)

équation homogène correspondante

an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = 0

aux fonctions auxiliaires ck(t), dont les dérivées satisfont le système algébrique linéaire

Le déterminant du système (1) est le Wronskien des fonctions z1,z2,...,zn, ce qui assure son unique solvabilité par rapport à .

Si ce sont des primitives pour , prises à des valeurs fixes des constantes d'intégration, alors la fonction

est une solution à l'équation différentielle inhomogène linéaire originale. L'intégration d'une équation inhomogène en présence d'une solution générale de l'équation homogène correspondante se réduit ainsi à des quadratures.

Méthode de Lagrange (méthode de variation de constantes arbitraires)

Méthode pour obtenir une solution générale d'une équation inhomogène, connaissant la solution générale d'une équation homogène sans trouver de solution particulière.

Pour une équation différentielle homogène linéaire d'ordre n

y(n) + a1(x) y(n-1) + ... + an-1 (x) y" + an(x) y = 0,

où y = y(x) est une fonction inconnue, a1(x), a2(x), ..., an-1(x), an(x) sont connus, continus, vrais : 1) il y a n linéairement solutions indépendantes équations y1(x), y2(x), ..., yn(x) ; 2) pour toutes valeurs des constantes c1, c2, ..., cn, la fonction y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) est un solution à l'équation; 3) pour toute valeur initiale x0, y0, y0,1, ..., y0,n-1 il existe des valeurs c*1, c*n, ..., c*n telles que la solution y *(x)= c*1 y1(x) + c*2 y2(x) + ... + c*n yn (x) satisfait à x = x0 les conditions initiales y*(x0)=y0, (y *)"(x0) =y0,1 , ...,(y*)(n-1)(x0)=y0,n-1.

L'expression y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) est appelée la solution générale d'une équation différentielle homogène linéaire du nième ordre.

L'ensemble de n solutions linéairement indépendantes d'une équation différentielle homogène linéaire d'ordre n y1(x), y2(x), ..., yn(x) est appelé le système fondamental de solutions de l'équation.

Pour une équation différentielle homogène linéaire à coefficients constants, il existe un algorithme simple pour construire un système fondamental de solutions. Nous chercherons une solution à l'équation sous la forme y(x) = exp(lx) : exp(lx)(n) + a1exp(lx)(n-1) + ... + an-1exp(lx) " + anexp(lx) = = (ln + a1ln-1 + ... + an-1l + an)exp(lx) = 0, c'est-à-dire que le nombre l est la racine de l'équation caractéristique ln + a1ln-1 + . .. + an-1l + an = 0. Le côté gauche de l'équation caractéristique est appelé le polynôme caractéristique de l'équation différentielle linéaire : P(l) = ln + a1ln-1 + ... + an-1l + an. Ainsi, le problème de la résolution d'une équation linéaire homogène d'ordre n avec des coefficients constants se réduit à la résolution d'une équation algébrique.

Si l'équation caractéristique a n racines réelles différentes l1№ l2 № ... № ln, alors le système fondamental de solutions est constitué des fonctions y1(x) = exp(l1x), y2(x) = exp(l2x), . .., yn (x) = exp(lnx), et la solution générale de l'équation homogène est : y(x)= c1 exp(l1x) + c2 exp(l2x) + ... + cn exp(lnx).

un système fondamental de solutions et une solution générale pour le cas de racines réelles simples.

Si l'une des racines réelles de l'équation caractéristique est répétée r fois (r-racine multiple), alors dans le système fondamental de solutions, il y a r fonctions qui lui correspondent ; si lk=lk+1 = ... = lk+r-1, alors le système fondamental de solutions de l'équation comprend r fonctions : yk(x) = exp(lkx), yk+1(x) = xexp(lkx ), yk +2(x) = x2exp(lkx), ..., yk+r-1(x) =xr-1 exp(lnx).

EXEMPLE 2. Système fondamental de solutions et solution générale pour le cas de racines réelles multiples.

Si l'équation caractéristique a des racines complexes, alors chaque paire de racines complexes simples (de multiplicité 1) lk,k+1=ak ± ibk dans le système fondamental de solutions correspond à une paire de fonctions yk(x) = exp(akx) cos(bkx), yk+ 1(x) = exp(akx)sin(bkx).

EXEMPLE 4. Système fondamental de solutions et solution générale pour le cas de racines complexes simples. Des racines imaginaires.

Si une paire complexe de racines a une multiplicité r, alors une telle paire lk=lk+1 = ... = l2k+2r-1=ak ± ibk, dans le système fondamental de solutions correspond aux fonctions exp(akx)cos( bkx), exp(akx)sin(bkx), xexp(akx)cos(bkx), xexp(akx)sin(bkx), x2exp(akx)cos(bkx), x2exp(akx)sin(bkx), .. ...... ........ xr-1exp(akx)cos(bkx), xr-1exp(akx)sin(bkx).

EXEMPLE 5. Système fondamental de solutions et solution générale pour le cas de racines complexes multiples.

Ainsi, pour trouver une solution générale à une équation différentielle homogène linéaire à coefficients constants, il faut : écrire l'équation caractéristique ; trouver toutes les racines de l'équation caractéristique l1, l2, ... , ln ; écrire le système fondamental de solutions y1(x), y2(x), ..., yn(x) ; notez l'expression de la solution générale y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x). Pour résoudre le problème de Cauchy, vous devez substituer l'expression de la solution générale aux conditions initiales et déterminer les valeurs des constantes c1,..., cn, qui sont des solutions du système d'équations algébriques linéaires c1 y1( x0) + c2 y2(x0) + ... + cn yn (x0) = y0, c1 y"1(x0) + c2 y"2(x0) + ... + cn y"n(x0) =y0 ,1, ......... , c1 y1 (n-1)(x0) + c2 y2(n-1)(x0) + ... + cn yn(n-1)(x0) = y0,n-1

Pour une équation différentielle inhomogène linéaire d'ordre n

y(n) + a1(x) y(n-1) + ... + an-1 (x) y" + an(x) y = f(x),

où y = y(x) est une fonction inconnue, a1(x), a2(x), ..., an-1(x), an(x), f(x) sont connus, continus, valides : 1 ) si y1(x) et y2(x) sont deux solutions d'une équation non homogène, alors la fonction y(x) = y1(x) - y2(x) est une solution de l'équation homogène correspondante ; 2) si y1(x) est une solution d'une équation inhomogène et y2(x) est une solution de l'équation homogène correspondante, alors la fonction y(x) = y1(x) + y2(x) est une solution à l'équation inhomogène ; 3) si y1(x), y2(x), ..., yn(x) sont n solutions linéairement indépendantes d'une équation homogène, et ych(x) est une solution arbitraire d'une équation inhomogène, alors pour toutes valeurs initiales ​​x0, y0, y0 ,1, ..., y0,n-1 il existe des valeurs c*1, c*n, ..., c*n telles que la solution y*(x)=c *1 y1(x) + c*2 y2(x) + ... + c*n yn (x) + yч(x) satisfait à x = x0 les conditions initiales y*(x0)=y0, (y* )"(x0)=y0,1 , . ..,(y*)(n-1)(x0)=y0,n-1.

L'expression y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) + yч(x) est appelée la solution générale d'une équation différentielle inhomogène linéaire du nième ordre.

Pour trouver des solutions partielles d'équations différentielles inhomogènes à coefficients constants avec les membres droits de la forme : Pk(x)exp(ax)cos(bx) + Qm(x)exp(ax)sin(bx), où Pk(x ), Qm(x ) sont des polynômes de degré k et m, respectivement, il existe un algorithme simple pour construire une solution particulière, appelé méthode de sélection.

La méthode de sélection, ou méthode des coefficients indéterminés, est la suivante. La solution requise de l'équation s'écrit sous la forme : (Pr(x)exp(ax)cos(bx) + Qr(x)exp(ax)sin(bx))xs, où Pr(x), Qr(x ) sont des polynômes de degré r = max(k, m) à coefficients inconnus pr , pr-1, ..., p1, p0, qr, qr-1, ..., q1, q0. Le facteur xs est appelé facteur de résonance. La résonance se produit dans les cas où parmi les racines de l'équation caractéristique il y a une racine l =a ± ib de multiplicité s. Ceux. si parmi les racines de l'équation caractéristique de l'équation homogène correspondante il y en a une telle que sa partie réelle coïncide avec le coefficient de l'exposant de l'exposant, et la partie imaginaire coïncide avec le coefficient de l'argument de la fonction trigonométrique de droite côté de l’équation, et la multiplicité de cette racine est s, alors dans la solution particulière souhaitée il y a un facteur de résonance xs. S’il n’y a pas de telle coïncidence (s=0), alors il n’y a pas de facteur de résonance.

En substituant l'expression d'une solution particulière dans le côté gauche de l'équation, nous obtenons un polynôme généralisé de la même forme que le polynôme du côté droit de l'équation, dont les coefficients sont inconnus.

Deux polynômes généralisés sont égaux si et seulement si les coefficients de facteurs de la forme xtexp(ax)sin(bx), xtexp(ax)cos(bx) de mêmes puissances t sont égaux. En égalisant les coefficients de ces facteurs, nous obtenons un système de 2(r+1) équations algébriques linéaires pour 2(r+1) inconnues. On peut montrer qu’un tel système est cohérent et possède une solution unique.