Méthodes et exercices de programmation non linéaire

La Programmation non linéaire C'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 restrictions, ou si la fonction pour maximiser ou minimiser (appelé Fonction objective), n'est pas exprimé comme une combinaison linéaire des variables, il y a donc un problème de programmation non linéaire.

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

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

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

[TOC]

Méthodes de programmation linéaire

Pour la programmation non linéaire, les principales méthodes à utiliser sont: 

1.- Méthodes graphiques.

2.- Multiplicateurs de Lagrange pour explorer la frontière de la région de la solution.

3.- Calcul du gradient pour explorer les extrémités de la fonction objectif.

4.- La méthode descendant descendant, pour trouver les points de gradient zéro.

5.- Méthode modifiée des multiplicateurs de Lagrange (avec l'état de Karush-Kuhn-Tucker).

Exemple de solution avec méthode graphique

Un exemple de solution avec la méthode graphique est ce qui peut être vu sur la figure 2:

Figure 2. Exemple de 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 gain g d'une certaine entreprise dépend du montant vendu du produit X et du montant vendu du produit et, en outre, le gain est déterminé par la formule suivante:

Peut vous servir: Binôme conjugué: comment il est résolu, exemples, exercices

G = 2 (x - 2)² + 3 (et - 3)²

Il est connu que les montants X et Y ont les restrictions suivantes:

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

Déterminer les valeurs de x et y qui produisent le gain maximal.

figure 3. Le gain de l'entreprise peut être modélisé mathématiquement pour trouver le gain maximal par la programmation non linéaire. Source: Pixabay.

Solution 

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

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

Premièrement, la région de solution sera déterminée, qui est donnée par les restrictions.

Comme x≥0; Y≥0, la solution doit être recherchée dans le premier quadrant du plan XY, mais comme il faut en outre être rempli que x + y ≤ 7, la solution est dans le semiplane inférieur de la ligne x + y = 7.

La région de solution est l'intersection du premier quadrant avec le semi-couloir inférieur de la ligne, qui donne naissance à une région triangulaire où la solution est située. Est le même que celui indiqué dans la figure 1.

D'un autre côté, le gain G peut également être représenté dans le plan cartésien, car son équation est celle d'une ellipse avec centre (2,3).

L'ellipse est illustrée à la figure 1 pour plusieurs valeurs G. Une valeur plus élevée de G, un plus grand gain.

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

Ensuite, la valeur maximale de g, de sorte que X e y appartient à la région de la solution correspond à: 

Peut vous servir: probabilité théorique: comment le sortir, exemples, exercices

G = 77 (gain maximal), qui se produit pour x = 7 e y = 0. 

Fait intéressant, le gain maximal se produit lorsque le montant des ventes de produits et est nulle, tandis que le montant du produit X atteint sa plus grande valeur possible.

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

Trouver la solution (x, y) qui fait la fonction f (x, y) = x² + 2 et² être maximum dans la région g (x, y) = x² + et² - 1 = 0.

Solution

Il s'agit clairement d'un problème de programmation non linéaire, car la fonction objective 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² + 2 et² - λ (x² + et² - 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, ces étapes sont suivies:

-Trouvez les dérivés partiels de la fonction Lagrange L, en ce qui concerne x, y, λ.

-Zéro chaque dérivé.

Ici, la séquence de ces opérations:

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

Solutions système possibles

Une solution possible de ce système est λ = 1 pour satisfaire la première équation, auquel cas y = 0 pour rencontrer le second.

Cette solution implique que x = 1 ou x = -1 pour que la troisième équation soit satisfaite. De cette façon, deux solutions S1 et S2 ont été obtenues:

S1: (x = 1, y = 0)

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

L'autre alternative est que λ = 2 pour la deuxième équation à satisfaire, quelle que soit la valeur et.

Il peut vous servir: Fermat Limit: ce qui consiste et les exercices résolus

Dans ce cas, le seul moyen pour la première équation d'être satisfait est que x = 0. Compte tenu de 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 lequel ou lequel de ces solutions maximisent la fonction objectif, procédez pour remplacer en 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² + vingt-et-un)² = 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) y (x = 0, y = -1) maximiser f (x, y) dans la région de la solution g (x, y) = 0.

- Exercice 3 (gradient nul)

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

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

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

Solution

Cet exercice est similaire à l'exercice 2, mais la région de solution (ou 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 frontalière était déjà déterminée dans l'exercice 2, mais il est nécessaire d'explorer la région intérieure.

Pour ce faire, le gradient de la fonction f (x, y) doit être calculé et égal à zéro, pour rechercher des valeurs extrêmes dans la région de la solution. Cela équivaut à calculer les dérivés partiels de F par rapport à X et respectivement et à égaliser 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.

Remplacement de cette valeur dans les résultats de la fonction F:

f (0, 0) = 0

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

 Les références

1. Avriel, m. 2003. Programme non linéaire. Dover Publishing.
2. Bazaraa. 1979. Programme non linéaire. John Wiley & Sons.
3. Bertsekas, D. 1999. Programme 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: est.Wikipédia.com