Optimisation

L'optimisation est l'art et la science de prendre les meilleures décisions. En mathématiques, cela signifie trouver les valeurs des variables qui rendent une certaine quantité (appelée fonction objectif) la plus grande ou la plus petite possible, tout en respectant certaines conditions (appelées contraintes).

Imaginez que vous gérez une usine. Votre objectif est de maximiser le profit. Pour cela, vous devez décider combien de produits fabriquer, quelles matières premières utiliser, etc. Ces décisions ne sont pas prises au hasard : vous êtes limité par la quantité de machines, le nombre d'employés, le budget disponible. L'optimisation vous aide à prendre la meilleure décision en tenant compte de toutes ces limites.

En résumé, l'optimisation cherche le "meilleur" parmi le "possible".

Exemples concrets :

• Maximisation :
  • Maximiser le profit d'une entreprise.
  • Maximiser la surface d'un champ avec une clôture de longueur donnée.
  • Maximiser la portée d'un projectile.
• Minimisation :
  • Minimiser le coût de production d'un bien.
  • Minimiser la distance parcourue par un transporteur.
  • Minimiser le temps de fabrication d'un produit.

Les problèmes d'optimisation nécessitent toujours trois éléments clés :

1. Une fonction objectif à maximiser ou minimiser.
2. Des variables de décision dont les valeurs affectent la fonction objectif.
3. Des contraintes qui limitent les valeurs possibles des variables de décision.

Pour bien poser un problème d'optimisation, il faut identifier clairement ces deux composantes essentielles :

Fonction objectif

La fonction objectif est la quantité que l'on souhaite optimiser (maximiser ou minimiser). Elle est généralement notée $f(x)$ ou $f(x_1, x_2, \dots, x_n)$, où $x$ ou $(x_1, x_2, \dots, x_n)$ représente les variables de décision.

• Exemple : Si vous voulez maximiser le profit $P$, votre fonction objectif pourrait être $P(x) = 10x - 2x^2$, où $x$ est le nombre d'articles produits.

Variables de décision

Ce sont les inconnues du problème, celles dont nous devons trouver les valeurs optimales. Elles sont souvent représentées par $x, y$ ou $x_1, x_2, \dots, x_n$. Ces variables sont sous notre contrôle et leurs valeurs influencent directement la fonction objectif.

• Exemple : Dans le cas de la production, $x$ (le nombre d'articles) est la variable de décision.

Types de contraintes

Les contraintes sont des conditions ou des restrictions qui doivent être respectées par les variables de décision. Elles définissent l'ensemble des solutions possibles, appelé le domaine de faisabilité.

Il existe plusieurs types de contraintes :

• Contraintes d'égalité : Elles imposent une relation exacte entre les variables. Par exemple, $x + y = 10$.
• Contraintes d'inégalité : Elles imposent une limite supérieure ou inférieure. Par exemple, $x \le 5$ (limite de production) ou $y \ge 0$ (impossibilité de produire une quantité négative).
• Contraintes de non-négativité : Très courantes, elles stipulent que les variables de décision ne peuvent pas prendre de valeurs négatives (par exemple, on ne peut pas produire un nombre négatif d'objets, ou avoir une surface négative).

Les contraintes définissent l'ensemble des solutions "réalisables".

Pour les problèmes d'optimisation avec une ou deux variables de décision, une représentation graphique est un outil très puissant pour visualiser et comprendre le problème.

Domaine de faisabilité

C'est l'ensemble de tous les points $(x,y)$ (ou valeurs de $x$) qui satisfont toutes les contraintes du problème. Graphiquement, il s'agit d'une région du plan.

• Pour une variable : Le domaine de faisabilité est un intervalle sur l'axe des réels.
• Pour deux variables : Le domaine est une région souvent polygonale dans le plan $xy$, délimitée par les droites ou courbes définies par les contraintes.

Lignes de niveau

Pour une fonction objectif $f(x,y)$, les lignes de niveau sont les courbes où la fonction prend une valeur constante. C'est-à-dire l'ensemble des points $(x,y)$ tels que $f(x,y) = k$, où $k$ est une constante.

• Exemple : Si $f(x,y) = 2x + 3y$, les lignes de niveau sont des droites d'équation $2x + 3y = k$. Plus $k$ augmente, plus la droite s'éloigne de l'origine (pour ce cas précis).

Recherche du point optimal

Une fois le domaine de faisabilité tracé et les lignes de niveau comprises, la recherche du point optimal devient visuelle :

1. Tracer le domaine de faisabilité : Représenter graphiquement toutes les contraintes. L'intersection de toutes ces régions est le domaine de faisabilité.
2. Tracer quelques lignes de niveau : Dessiner plusieurs lignes de niveau de la fonction objectif.
3. Déplacer la ligne de niveau : Déplacer mentalement ou physiquement une ligne de niveau dans la direction qui optimise la fonction (par exemple, vers le haut et la droite pour maximiser si la pente est négative, ou vers l'origine pour minimiser) jusqu'à ce qu'elle touche le domaine de faisabilité pour la dernière fois.
4. Identifier le point optimal : Le point (ou les points) où la ligne de niveau "sort" du domaine de faisabilité est la solution optimale. Ce point est souvent un sommet du polygone de contraintes.

Le point optimal est le point du domaine de faisabilité qui correspond à la valeur la plus grande (ou la plus petite) de la fonction objectif.

Pour optimiser une fonction $f(x)$ sur un intervalle, nous utilisons les outils de l'analyse : la dérivée.

Dérivée première

La dérivée première $f'(x)$ d'une fonction $f(x)$ nous renseigne sur le sens de variation de la fonction :

• Si $f'(x) > 0$ sur un intervalle, alors $f(x)$ est croissante sur cet intervalle.
• Si $f'(x) < 0$ sur un intervalle, alors $f(x)$ est décroissante sur cet intervalle.
• Si $f'(x) = 0$ en un point $x_0$, ce point est un point critique. Il peut s'agir d'un extremum local (maximum ou minimum) ou d'un point d'inflexion.

Sens de variation

En étudiant le signe de la dérivée, on peut construire un tableau de variation de la fonction, qui indique où la fonction monte et où elle descend.

Extrema locaux

Un extremum local est un point où la fonction atteint un maximum ou un minimum dans un voisinage restreint.

• Un maximum local se produit lorsque la fonction passe de croissante à décroissante (la dérivée change de signe de $+$ à $-$).
• Un minimum local se produit lorsque la fonction passe de décroissante à croissante (la dérivée change de signe de $-$ à $+$).
• Si la dérivée seconde $f''(x_0)$ existe et $f'(x_0) = 0$ :
  • Si $f''(x_0) > 0$, alors $x_0$ est un minimum local.
  • Si $f''(x_0) < 0$, alors $x_0$ est un maximum local.

Lorsqu'on cherche à optimiser une fonction $f(x)$ sur un intervalle fermé $[a, b]$, la méthode est la suivante :

Théorème des bornes atteintes

Ce théorème stipule que toute fonction continue sur un intervalle fermé et borné $[a, b]$ atteint son maximum et son minimum sur cet intervalle. Ces extrema peuvent être atteints soit aux points critiques à l'intérieur de l'intervalle, soit aux bornes de l'intervalle ($a$ ou $b$).

Points critiques

1. Calculer la dérivée $f'(x)$.
2. Résoudre l'équation $f'(x) = 0$ pour trouver les points critiques.
3. Filtrer les points critiques : Ne conserver que ceux qui appartiennent à l'intervalle $[a, b]$.

Comparaison des valeurs

1. Évaluer la fonction $f(x)$ aux points critiques trouvés.
2. Évaluer la fonction $f(x)$ aux bornes de l'intervalle, c'est-à-dire $f(a)$ et $f(b)$.
3. Comparer toutes ces valeurs :
   • La plus grande valeur est le maximum global de $f$ sur $[a, b]$.
   • La plus petite valeur est le minimum global de $f$ sur $[a, b]$.

Exemple : Optimiser $f(x) = x^3 - 3x$ sur $[-2, 2]$.

1. Dérivée : $f'(x) = 3x^2 - 3$.
2. Points critiques : $3x^2 - 3 = 0 \implies 3(x^2 - 1) = 0 \implies x = 1$ ou $x = -1$. Les deux points $x=1$ et $x=-1$ sont dans l'intervalle $[-2, 2]$.
3. Évaluation :
   • $f(-2) = (-2)^3 - 3(-2) = -8 + 6 = -2$
   • $f(-1) = (-1)^3 - 3(-1) = -1 + 3 = 2$
   • $f(1) = (1)^3 - 3(1) = 1 - 3 = -2$
   • $f(2) = (2)^3 - 3(2) = 8 - 6 = 2$
4. Comparaison : Le maximum est $2$ (atteint en $x=-1$ et $x=2$), le minimum est $-2$ (atteint en $x=-2$ et $x=1$).

La méthode générale pour résoudre un problème concret d'optimisation à une variable est la suivante :

1. Modélisation du problème :

   • Identifier la quantité à optimiser (maximiser ou minimiser). Ce sera votre fonction objectif.
   • Identifier la variable de décision (souvent une seule).
   • Traduire toutes les informations données en une expression mathématique pour la fonction objectif.
   • Déterminer l'intervalle (domaine de faisabilité) sur lequel la variable de décision peut exister, en tenant compte des contraintes physiques ou économiques.

2. Définition de la fonction objectif :

   • Écrire la fonction objectif $f(x)$ en fonction de la seule variable de décision $x$.
   • Préciser l'intervalle de validité de $x$.

3. Application de la méthode :

   • Calculer la dérivée $f'(x)$.
   • Trouver les points critiques en résolvant $f'(x) = 0$.
   • Évaluer $f(x)$ aux points critiques (à l'intérieur de l'intervalle) et aux bornes de l'intervalle.
   • Comparer les valeurs pour trouver le maximum/minimum global.

4. Interprétation du résultat :

   • Expliquer ce que signifient les valeurs optimales dans le contexte du problème initial.
   • Donner les unités et s'assurer que le résultat a un sens pratique.

Exemple : Un agriculteur veut clôturer un champ rectangulaire. Il dispose de 100 mètres de clôture et un côté du champ est le long d'un mur (donc pas besoin de clôture de ce côté). Quelle est la surface maximale qu'il peut clôturer ?

1. Modélisation :

   • Quantité à maximiser : l'aire du rectangle $A$.
   • Variables : Soient $l$ la longueur du côté parallèle au mur et $L$ la longueur des deux autres côtés.
   • Contrainte : La longueur totale de clôture est $100$ m. Donc $l + 2L = 100$.
   • Fonction objectif : $A = l \times L$.
   • Nous avons deux variables. Utilisons la contrainte pour en éliminer une. De $l + 2L = 100$, on tire $l = 100 - 2L$.
   • L'aire devient $A(L) = (100 - 2L)L = 100L - 2L^2$.
   • Domaine de faisabilité : $L$ doit être positif ($L > 0$). De plus, $l$ doit être positif, donc $100 - 2L > 0 \implies 100 > 2L \implies L < 50$. L'intervalle est donc $]0, 50[$.

2. Définition de la fonction objectif : $A(L) = 100L - 2L^2$ sur $]0, 50[$.

3. Application de la méthode :

   • Dérivée : $A'(L) = 100 - 4L$.
   • Points critiques : $100 - 4L = 0 \implies 4L = 100 \implies L = 25$.
   • Ce point est dans $]0, 50[$.
   • Pour déterminer si c'est un maximum, on peut regarder la dérivée seconde : $A''(L) = -4$, qui est négative. Donc, $L=25$ est un maximum.
   • Ou étudier le signe de $A'(L)$ : $A'(L) > 0$ si $L < 25$ (fonction croissante), $A'(L) < 0$ si $L > 25$ (fonction décroissante). Il s'agit bien d'un maximum.
   • La valeur maximale de l'aire est $A(25) = 100(25) - 2(25)^2 = 2500 - 2(625) = 2500 - 1250 = 1250$.

4. Interprétation du résultat : L'agriculteur peut clôturer une surface maximale de $1250$ mètres carrés en choisissant $L = 25$ mètres. Dans ce cas, la longueur $l$ sera $l = 100 - 2(25) = 50$ mètres.

Dans l'optimisation linéaire, les contraintes sont des inéquations linéaires de la forme $ax + by \le c$, $ax + by \ge c$, ou des égalités $ax + by = c$.

Demi-plans

Chaque inéquation linéaire à deux variables $(x, y)$ représente un demi-plan dans le plan cartésien.

• Pour tracer un demi-plan, on commence par tracer la droite d'équation correspondant à l'égalité ($ax + by = c$).
• Ensuite, on choisit un point test (souvent l'origine $(0,0)$ si elle ne se trouve pas sur la droite) et on vérifie si ses coordonnées satisfont l'inéquation. Si oui, le demi-plan contenant ce point est la solution ; sinon, c'est l'autre.

Représentation graphique

Pour un système de plusieurs inéquations, la région des solutions admissibles (ou domaine de faisabilité) est l'intersection de tous les demi-plans.

• Cette région est toujours un polygone convexe (ou une région non bornée mais toujours convexe).
• Les sommets de ce polygone sont les points d'intersection des droites frontières des demi-plans.

Fonction objectif linéaire

La fonction objectif est de la forme $Z = ax + by$, où $a$ et $b$ sont des constantes. On cherche à maximiser ou minimiser $Z$.

Pente des lignes de niveau

Les lignes de niveau de cette fonction objectif sont des droites d'équation $ax + by = k$, où $k$ est une constante.

• La pente de ces droites est constante et égale à $-\frac{a}{b}$ (si $b \ne 0$).
• Toutes les lignes de niveau sont donc parallèles entre elles.

Déplacement des lignes de niveau

• Pour maximiser $Z$, on déplace la ligne de niveau $ax + by = k$ dans la direction qui augmente $k$.
• Pour minimiser $Z$, on déplace la ligne de niveau $ax + by = k$ dans la direction qui diminue $k$.
• Le sens de déplacement dépend des coefficients $a$ et $b$. Par exemple, si $a, b > 0$, augmenter $k$ éloigne la droite de l'origine.

La méthode graphique est très efficace pour résoudre des problèmes d'optimisation linéaire à deux variables.

1. Tracer le domaine de faisabilité :

   • Pour chaque contrainte d'inégalité, tracer la droite associée et identifier le demi-plan correspondant.
   • Hachurer ou colorier la région qui satisfait toutes les contraintes (y compris les contraintes de non-négativité $x \ge 0, y \ge 0$). Cette région est le polygone de contraintes.

2. Identifier les sommets du polygone :

   • Calculer les coordonnées de tous les sommets (points d'intersection des droites frontières) du polygone de contraintes.

3. Tracer une ligne de niveau de la fonction objectif :

   • Choisir une valeur arbitraire pour $Z$ (par exemple, $Z=0$) et tracer la droite $ax + by = 0$.

4. Déplacer la ligne de niveau :

   • Déplacer virtuellement cette ligne de niveau, en la gardant parallèle à elle-même, dans la direction qui maximise (ou minimise) $Z$.
   • Le point optimal est le dernier point du domaine de faisabilité touché par la ligne de niveau avant qu'elle ne quitte complètement la région.

5. Recherche du point optimal :

   • Le théorème fondamental de l'optimisation linéaire stipule que si une solution optimale existe, elle est toujours atteinte à l'un des sommets (points extrêmes) du domaine de faisabilité.
   • Donc, il suffit d'évaluer la fonction objectif $Z = ax + by$ à chacun des sommets du polygone de contraintes.
   • Le sommet qui donne la plus grande valeur de $Z$ est la solution pour la maximisation.
   • Le sommet qui donne la plus petite valeur de $Z$ est la solution pour la minimisation.

Cas particuliers

• Solutions multiples : Si la ligne de niveau optimale est parallèle à l'une des arêtes du polygone de contraintes, alors tous les points sur cette arête (y compris les deux sommets qui la définissent) sont des solutions optimales.
• Pas de solution (domaine vide) : Si le système d'inéquations n'a pas de solution, le domaine de faisabilité est vide.
• Solution non bornée : Si le domaine de faisabilité est non borné et que la fonction objectif peut être augmentée (ou diminuée) indéfiniment dans cette région, il n'y a pas de solution optimale finie.

L'optimisation linéaire est largement utilisée dans l'industrie et l'économie pour résoudre des problèmes concrets :

• Problèmes de production : Comment allouer des ressources limitées (matières premières, main d'œuvre, temps machine) pour produire différents biens afin de maximiser le profit ou minimiser les coûts de production.

  • Exemple : Une entreprise fabrique deux types de produits, A et B. Chaque produit utilise une certaine quantité de matière première et de temps machine. Il y a des limites sur la disponibilité de la matière première et du temps machine. Le profit par unité de A et B est connu. Combien de A et B faut-il produire pour maximiser le profit ?

• Problèmes de mélange : Comment combiner différentes matières premières (avec des coûts et des compositions variés) pour obtenir un produit final répondant à certaines spécifications à moindre coût.

  • Exemple : Formuler un aliment pour bétail en mélangeant différentes céréales, chacune ayant un coût et un contenu nutritionnel (protéines, vitamines) spécifique. Les contraintes sont les besoins nutritionnels minimaux et maximaux, et l'objectif est de minimiser le coût total.

• Optimisation de ressources : Planification de l'utilisation de ressources (transport, énergie, personnel) pour optimiser un objectif donné.

  • Exemple : Déterminer la meilleure façon d'affecter des équipes à différentes tâches pour minimiser le temps total du projet.

L'optimisation linéaire est un outil puissant pour la prise de décision stratégique en entreprise.

Si l'on veut optimiser une fonction $f(x, y)$ sous une contrainte d'égalité de la forme $g(x, y) = c$, on peut souvent utiliser la méthode de substitution.

Substitution de variable

1. De l'équation de contrainte $g(x, y) = c$, on exprime une variable en fonction de l'autre. Par exemple, si $g(x, y) = x + y = 10$, on peut écrire $y = 10 - x$.
2. On substitue cette expression dans la fonction objectif $f(x, y)$. La fonction objectif devient alors une fonction d'une seule variable, par exemple $F(x) = f(x, 10-x)$.

Réduction à une variable

Le problème initial à deux variables sous contrainte est transformé en un problème d'optimisation à une seule variable sans contrainte (ou avec des contraintes sur l'intervalle de la variable restante).

Recherche d'extrema

On applique ensuite les méthodes d'optimisation à une variable :

1. Calculer la dérivée de $F(x)$.
2. Trouver les points critiques en résolvant $F'(x) = 0$.
3. Utiliser la dérivée seconde ou le tableau de variation pour déterminer si ces points sont des maxima ou des minima.
4. Calculer la valeur de la deuxième variable en utilisant la contrainte.

Exemple : Maximiser $f(x,y) = xy$ sous la contrainte $x+y=10$ ($x,y \ge 0$).

1. De $x+y=10$, on a $y = 10-x$.
2. Substitution dans $f(x,y)$ : $F(x) = x(10-x) = 10x - x^2$.
3. Intervalle : $x \ge 0$ et $y \ge 0 \implies 10-x \ge 0 \implies x \le 10$. Donc $x \in [0, 10]$.
4. Dérivée : $F'(x) = 10 - 2x$.
5. Point critique : $10 - 2x = 0 \implies x = 5$.
6. Ce point est dans $[0, 10]$. $F''(x) = -2 < 0$, donc c'est un maximum.
7. Si $x=5$, alors $y = 10-5 = 5$.
8. La valeur maximale est $f(5,5) = 5 \times 5 = 25$.

Pour des problèmes simples avec une contrainte d'inégalité, l'approche graphique peut être très intuitive.

Région admissible

La contrainte d'inégalité $g(x,y) \le c$ (ou $\ge c$) définit une région admissible dans le plan. Cette région peut être bornée ou non.

Gradient de la fonction objectif

Pour une fonction $f(x,y)$, le gradient $\nabla f(x,y) = \left(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\right)$ indique la direction de la plus forte augmentation de la fonction.

• Pour une fonction linéaire $f(x,y) = ax + by$, le gradient est constant $(a, b)$. C'est la direction dans laquelle on déplace les lignes de niveau pour maximiser la fonction.

Point de tangence

• Lorsque la fonction objectif ou les contraintes sont non linéaires, le point optimal n'est pas toujours un sommet.
• Graphiquement, le point optimal pour une maximisation (ou minimisation) est souvent le point où une ligne de niveau de la fonction objectif est tangente à la frontière du domaine de faisabilité, ou un point extrême de cette frontière.
• Si le maximum se trouve à l'intérieur du domaine (ce qui est rare avec des contraintes d'inégalité), cela signifierait que le gradient est nul en ce point (un extremum local sans contrainte).

Une fois la solution optimale trouvée, il est crucial de l'interpréter correctement :

Signification des valeurs optimales

• Que représentent les valeurs des variables de décision optimales $x^*, y^*$ dans le contexte du problème ? (Ex: nombre d'unités à produire, dimensions d'une forme géométrique).
• Quelle est la valeur optimale de la fonction objectif $f(x^*, y^*)$ ? (Ex: profit maximal, coût minimal, surface maximale).

Sensibilité aux contraintes

• Comment la solution optimale changerait-elle si les contraintes étaient légèrement modifiées ? C'est le domaine de l'analyse de sensibilité.
• Par exemple, si la quantité de matière première disponible augmentait, est-ce que le profit maximal augmenterait beaucoup ? Cela aide à prendre des décisions stratégiques (par exemple, investir pour augmenter une ressource).

Limites de la modélisation

• Il est important de reconnaître que les modèles d'optimisation sont des simplifications de la réalité.
• Les résultats sont aussi bons que les hypothèses et les données utilisées.
• Des facteurs non pris en compte dans le modèle (par exemple, des événements imprévus, des préférences humaines) peuvent affecter la pertinence du résultat. L'optimisation fournit une "meilleure solution théorique" dans le cadre des informations disponibles.