D	L	M	M	J	V	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

19/11/2010

La méthode du Lagrangien

3.4 La méthode du Lagrangien

La méthode que nous étudions dans cette séance est, en fait, une généralisation de la règle du multiplicateur de Lagrange pour résoudre des problèmes d’optimisation avec des contraintes d’égalité. Nous examinerons le cas d'une seule contrainte à deux variables .

Définition Soit le problème : s.c. .

On appelle Lagrangien associé à ce problème la fonction :

Le Lagrangien permet d’introduire la contrainte dans la fonction objectif avec une certaine pénalité . On se retrouve ainsi à maximiser une fonction à trois variables sans contrainte.

Si, maintenant, on cherche les points stationnaires du Lagrangien , cela veut dire que nous cherchons tel que .

Nous déduisons alors le système suivant comportant trois équations:

Dans les deux premières équations, on reconnaît les conditions d’optimum du premier ordre : , alors que la troisième est équivalente à la contrainte de départ imposée par le modèle : , au point (point admissible).

La méthode du Lagrangien transforme donc un problème d'optimisation d'un modèle avec contraintes d'égalité à celui de recherche des points stationnaires d’une fonction sans contrainte. De plus, puisque pour tout point optimal , la valeur du Lagrangien est la même que celle de l'objectif en ce point :

Exemple Résoudre par la méthode du Lagrangien :

s.c. .

On forme d'abord le Lagrangien : . On optimise ensuite , une fonction à trois variables pour laquelle on cherche les points stationnaires tel que :

Þ .

Avec et dans la troisième équation, on a : ,

d'où Þ .

Reportant à son tour la valeur de dans les deux premières expressions, on retrouve :

et .

Donc est le seul point stationnaire du Lagrangien, et par conséquent, est le seul point extrémal du problème original avec contrainte (trouvé sans avoir à énoncer les conditions d’optimum du premier ordre!).

Remarque sur la nature du point extrémal Il faut faire attention car il n’est pas certain que soit un maximum (sous contraintes) pour l'objectif. Pour les contraintes d'égalité, le seul cas facile à résoudre au complet est celui impliquant des contraintes affines parce qu'elles définissent automatiquement un domaine convexe. On peut alors vérifier la convexité/concavité de la fonction objectif. En pratique, on choisit généralement de construire des modèles mathématiques que l'on est capable de résoudre !

Dans l'exemple précédent, la contrainte est affine et on peut donc vérifier que l'objectif est strictement concave (le Hessien est toujours défini négatif). L'optimum sous contrainte trouvé est bel et bien un maximum absolu.

Dans les autres cas, il faut avoir recours à des outils mathématiques plus complexes, par exemple, les conditions du second ordre qui utilisent la notion de Hessien bordé (voir Breton et Haurie, p. 185-193).

3.5 Interprétation de

Considérons le problème d'optimisation suivant, où le côté droit de la contrainte d'égalité est exprimé par la quantité b : .

Le Lagrangien associé à ce problème est donné par . À l'optimalité, nous avons déjà mentionné que . Ainsi,

Le coefficient de b est . Ainsi, ce multiplicateur de Lagrange représente l'effet sur la valeur optimale de la fonction objectif si l'on modifie d'une unité la valeur de b. Il faut bien s'entendre que c'est un calcul approximatif.

donne une approximation de la variation de lorsqu’on augmente d'une unité le côté droit b de la contrainte .

Ainsi, si f est une fonction de profit (en $) et b représente la main-d’œuvre en nombre d’employés, alors signifie que le profit augmenterait (approximativement) de 200$ si on augmentait la main-d’œuvre d'un employé additionnel. À noter que si l'on diminue le nombre d'employés, l'effet est en sens inverse !

Mentionnons finalement que dans le cas d'un modèle d'optimisation comportant plusieurs contraintes, un tel multiplicateur est associé spécifiquement à chacune d'entre elles.

Exemple s.c. .

Pour ce problème, on a trouvé : . Si on augmente b de une unité (donc ), alors la valeur optimale de devrait diminuer de 2 unités (environ). Résoudre ce problème en utilisant EXCEL et montrer que la nouvelle solution est donnée par :

et … une diminution de 2,04.

Vérifier que la valeur du multiplicateur est maintenant .

Exercice Une entreprise fabrique deux modèles de vélos de montagne: le modèle X est plus abordable et se vend 500$ l'unité, tandis que le modèle Y se vend 1000$ l'unité. Les coûts totaux de fabrication (en $) sont exprimés par la fonction suivante: où x est le nombre de vélos du modèle X et y est le nombre de vélos du modèle Y, produits mensuellement. On suppose que chaque vélo produit peut être vendu sur le marché.

a) Donner , la fonction des profits totaux mensuels. ¨ Cette fonction est-elle convexe, concave ou sans forme particulière?

b) La capacité de production de l'entreprise est de 150 vélos par mois. En supposant que l'entreprise désire utiliser à pleine capacité son usine, trouver la répartition de la production mensuelle permettant de maximiser les profits. ¨ Prouvez qu'il s'agit bien d'un maximum absolu. ¨ Donnez la valeur du profit mensuel.

c) Le patron de l'entreprise s'interroge sur la pertinence de vouloir produire à pleine capacité. Il se demande si la solution qu'il obtiendrait sans cette contrainte serait plus intéressante. Aidez-le à répondre à cette question en trouvant la solution qui maximise les profits sans cette contrainte. ¨ Prouvez qu'il s'agit bien d'un maximum absolu. ¨ La solution obtenue est-elle réalisable pour l'entreprise? ¨ Donnez la valeur du profit mensuel.

d) Déterminez le signe du multiplicateur de Lagrange du problème résolu en b). ¨ Interpréter ce signe en vous appuyant sur les résultats obtenus en b) et c).

Solution

; det(H(x, y))>0 et -10<0, "(x, y); p(x, y) est strict. concave.

b) Par substitution : y = 150 – x.

; x = 55 (Þ y = 95).

, "x Þ p(x) est une fonction strictement concave.

Þ x= 55 est un maximum absolu de p(x) .

Þ (x, y) = (55, 95) est un maximum absolu de p(x, y) avec p(55, 95) = 65 312,50$.

Ce problème peut aussi se résoudre par la méthode du Lagrangien.

Par a), ce point stationnaire est un maximum absolu car la fonction est concave.

La solution n'est pas réalisable pour l'entreprise, dépassant la capacité de 150.

Le profit p(80, 120) = 70 000$.

d) On a vu que toute augmentation de capacité est rentable. Le multiplicateur est donc de signe positif. Par calcul, on trouve

Exercice Résoudre le problème précédent à l'aide d’EXCEL.

Problèmes résolus

Problème 1 Résoudre le problème suivant par la méthode du lagrangien:

Réponse

Le Lagrangien est . Les conditions du premier ordre sont :

On a (1) = (2)

On remplace dans (3):

Problème 2 Une grande brasserie veut allouer un budget de 500 000$ à la publicité au cours des six prochains mois. Les annonces publicitaires seront présentées dans deux médias : la télévision et les journaux. Les profits générés par cette campagne sont estimés par la fonction suivante :

s.c. x + y = 500

où x = montant investi dans la publicité dans les journaux (en milliers de $) et

y = montant investi dans la publicité à la télévision (en milliers de $).

En considérant que le budget est totalement dépensé, déterminer l'allocation aux deux médias qui permette de maximiser les profits de la brasserie en utilisant la méthode du Lagrangien. Quel est le profit maximum obtenu ? Vérifier que le point stationnaire est un maximum absolu. Interpréter le multiplicateur de Lagrange.

Réponse

Le Lagrangien est:

Les conditions du premier ordre sont :

En remplaçant y = 250 + x dans L'_l, on obtient :

, et .

Le domaine est convexe car la contrainte est affine. Il suffit alors de vérifier que P(x,y) est concave pour que (125,375) soit un maximum absolu :

est strictement concave.

Le point (125,375) est donc un maximum absolu du problème d’optimisation sous contrainte.

L’interprétation économique que l’on peut donner à = 250 est que si les dépenses en publicité augmentent de 1000$, les profits augmenteront de 250$. Ce n’est donc pas rentable, même si le signe du multiplicateur de Lagrange est positif, car les unités relatives à la contrainte sont en milliers de $, ce qui amènerait une perte de 750$ dans l'éventualité où une augmentation d'une unité sur la contrainte de publicité se produisait.

Problème 3 Au ministère de l'agriculture, on a établi la fonction de profit suivante pour les fermes cultivant des germes de soja et des pistaches :

où P(x, y) sont les profits annuels en $, x représente le nombre d'acres plantés en germes de soja, et y donne le nombre d'acres plantés en pistaches. Un fermier possède une terre de 500 acres. Comment devrait-il allouer ses terres à ces deux cultures pour obtenir un profit maximal ? Utiliser la méthode du Lagrangien. Montrer qu'il s'agit d'un maximum absolu et donner le montant du profit obtenu. Interpréter le multiplicateur de Lagrange. En vous basant sur cette interprétation, suggéreriez-vous au fermier d’augmenter la surface totale consacrée à ces deux cultures ou, au contraire, de la diminuer ?

Réponse

Le Lagrangien est: et les conditions du premier ordre sont :

En remplaçant y^* = 100 dans L'_l:, on a = 600 - 2x^*- 2y* = - 400.

Le point (400,100) est un maximum absolu du problème d’optimisation sous contrainte car on maximise une fonction concave sous un domaine convexe (contrainte affine).

L’interprétation économique que l’on peut donner à = -400 signifie qu’en ne cultivant pas tous les champs (c.-à-d. ses 500 acres de champs), le fermier augmenterait ses profits, à cause du signe négatif de . En effet, lorsque le fermier satisfait la contrainte, ses profits ne sont que de 60 000$, alors qu'ils sont de 110 000$ lorsque l'on ne tient pas compte de la contrainte (il cultive alors 300 acres de champs).