PROGRAMMATION NON LINÉAIRE: MÉTHODES ET EXERCICES - MATEMATIQUES - 2025

La programmation non linéaire est le processus d'optimisation d'une fonction qui dépend de plusieurs variables indépendantes, qui à leur tour sont soumises à des restrictions.

Si une ou plusieurs des contraintes, ou si la fonction à maximiser ou à minimiser (appelée fonction objectif), n'est pas exprimée comme une combinaison linéaire des variables, alors vous avez un problème de programmation non linéaire.

Figure 1. Problème de programmation non linéaire (NLP). où G est la fonction (non linéaire) à optimiser dans la région verte, déterminée par les contraintes. Source: F. Zapata.

Et par conséquent, les procédures et méthodes de programmation linéaire ne peuvent pas être utilisées.

Par exemple, la méthode Simplex bien connue ne peut pas être utilisée, qui ne s'applique que lorsque la fonction objectif et les contraintes sont toutes des combinaisons linéaires des variables du problème.

Méthodes de programmation linéaire

Pour les problèmes de programmation non linéaire, les principales méthodes à utiliser sont:

1.- Méthodes graphiques.

2.- Multiplicateurs de Lagrange pour explorer la limite de la région de solution.

3.- Calcul du gradient pour explorer les extrêmes de la fonction objectif.

4.- La méthode des étapes descendantes, pour trouver les points de gradient nuls.

5.- Méthode modifiée des multiplicateurs de Lagrange (avec la condition de Karush-Kuhn-Tucker).

Exemple de solution avec méthode graphique

Un exemple de solution avec la méthode graphique est celle que l'on peut voir sur la figure 2:

Figure 2. Exemple d'un problème non linéaire avec des restrictions non linéaires et sa solution graphique. Source: F. Zapata.

Exercices

- Exercice 1 (méthode graphique)

Le profit G d'une certaine entreprise dépend de la quantité vendue du produit X et de la quantité vendue du produit Y, en outre, le profit est déterminé par la formule suivante:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Les montants X et Y sont connus pour avoir les restrictions suivantes:

X≥0; Y≥0 et X + Y ≤ 7

Déterminez les valeurs de X et Y qui produisent le gain maximum.

Figure 3. Le profit d'une entreprise peut être modélisé mathématiquement pour trouver le profit maximum en utilisant la programmation non linéaire. Source: Pixabay.

Solution

Dans ce problème, la fonction objectif est non linéaire, tandis que les inégalités qui définissent les contraintes le sont. C'est un problème de programmation non linéaire.

Pour la solution de ce problème, la méthode graphique sera choisie.

Tout d'abord, la région de solution sera déterminée, ce qui est donné par les restrictions.

Comme X≥0; Y≥0, la solution doit être trouvée dans le premier quadrant du plan XY, mais comme il doit également être vrai que X + Y ≤ 7, la solution est dans le demi-plan inférieur de la droite X + Y = 7.

La région de solution est l'intersection du premier quadrant avec le demi-plan inférieur de la ligne, ce qui se traduit par une région triangulaire où la solution est trouvée. C'est le même que celui indiqué sur la figure 1.

Par contre, le gain G peut également être représenté dans le plan cartésien, puisque son équation est celle d'une ellipse de centre (2,3).

L'ellipse est représentée sur la figure 1 pour différentes valeurs de G. Plus la valeur de G est élevée, plus le gain est important.

Il existe des solutions qui appartiennent à la région, mais ne donnent pas la valeur G maximale, tandis que d'autres, comme G = 92,4, sont en dehors de la zone verte, c'est-à-dire la zone de solution.

Alors, la valeur maximale de G, telle que X et Y appartiennent à la région de solution, correspond à:

G = 77 (gain maximum), qui est donné pour X = 7 et Y = 0.

Fait intéressant, le profit maximum se produit lorsque le montant des ventes du produit Y est nul, tandis que la quantité de produit X atteint sa valeur la plus élevée possible.

- Exercice 2 (Méthode analytique: multiplicateurs de Lagrange)

Trouvez la solution (x, y) qui rend la fonction f (x, y) = x ² + 2y ² maximum dans la région g (x, y) = x ² + y ² - 1 = 0.

Solution

Il s'agit clairement d'un problème de programmation non linéaire, car la fonction objectif f (x, y) et la restriction g (x, y) = 0 ne sont pas une combinaison linéaire des variables x et y.

La méthode des multiplicateurs de Lagrange sera utilisée, ce qui nécessite d'abord de définir la fonction de Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

Où λ est un paramètre appelé multiplicateur de Lagrange.

Pour déterminer les valeurs extrêmes de la fonction objectif f, dans la région de solution donnée par la restriction g (x, y) = 0, procédez comme suit:

-Trouver les dérivées partielles de la fonction de Lagrange L, par rapport à x, y, λ.

-Égaliser chaque dérivée à zéro.

Voici la séquence de ces opérations:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Solutions système possibles

Une solution possible de ce système est λ = 1 pour que la première équation soit satisfaite, auquel cas y = 0 pour que la seconde soit satisfaite.

Cette solution implique que x = 1 ou x = -1 pour la troisième équation à satisfaire. De cette manière, deux solutions S1 et S2 ont été obtenues:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

L'autre alternative est que λ = 2 afin que la deuxième équation soit satisfaite, quelle que soit la valeur y.

Dans ce cas, la seule façon pour la première équation d'être satisfaite est de x = 0. En considérant la troisième équation, il n'y a que deux solutions possibles, que nous appellerons S3 et S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Pour savoir laquelle ou laquelle de ces solutions maximise la fonction objectif, nous procédons à la substitution dans f (x, y):

S1: f (1, 0) = 1 ² + 2,0 ² = 1

S2: f (-1, 0) = (-1) ² + 2,0 ² = 1

S3: f (0, 1) = 0 ² + 2,1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

Nous concluons que les solutions qui maximisent f, lorsque x et y appartiennent à la circonférence g (x, y) = 0 sont S3 et S4.

Les paires de valeurs (x = 0, y = 1) et (x = 0, y = -1) maximisent f (x, y) dans la région de solution g (x, y) = 0.

- Exercice 3 (Dégradé nul)

Trouvez des solutions (x, y) pour la fonction objectif:

f (x, y) = x ² + 2 y ²

Soit maximum dans la région g (x, y) = x ² + y ² - 1 ≤ 0.

Solution

Cet exercice est similaire à l'exercice 2, mais la région de solution (ou de restriction) s'étend à la région intérieure de la circonférence g (x, y) = 0, c'est-à-dire au cercle g (x, y) ≤ 0. Cela inclut à la circonférence et à sa région intérieure.

La solution à la frontière a déjà été déterminée dans l'exercice 2, mais la région intérieure reste à explorer.

Pour ce faire, le gradient de la fonction f (x, y) doit être calculé et mis à zéro, pour trouver des valeurs extrêmes dans la région de solution. Cela équivaut à calculer les dérivées partielles de f par rapport à x et y respectivement et à la mettre à zéro:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Ce système d'équations a la seule solution (x = 0, y = 0) qui appartient au cercle g (x, y) ≤ 0.

La substitution de cette valeur dans la fonction f résulte:

f (0, 0) = 0

En conclusion, la valeur maximale que prend la fonction dans la région de solution est 2 et se produit à la limite de la région de solution, pour les valeurs (x = 0, y = 1) et (x = 0, y = -1).

Références

1. Avriel, M. 2003. Programmation non linéaire. Éditions Douvres.
2. Bazaraa. 1979. Programmation non linéaire. John Wiley et fils.
3. Bertsekas, D. 1999. Programmation non linéaire: 2e édition. Athena Scientific.
4. Nocedal, J. 1999. Optimisation numérique. Springer-Verlag.
5. Wikipédia. Programmation non linéaire. Récupéré de: es.wikipedia.com