Résolution de problèmes d'optimisation

Un problème d'optimisation est une situation où l'on cherche à trouver la meilleure solution possible parmi un ensemble de solutions réalisables. Le terme "meilleure" peut signifier différentes choses selon le contexte : il peut s'agir de maximiser quelque chose (comme un profit, une surface, un volume) ou de minimiser quelque chose (comme un coût, une distance, une perte de temps).

L'objectif principal de l'optimisation est de 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 contraintes.

Exemples concrets :

• Une entreprise souhaite maximiser son profit en ajustant ses prix de vente et ses volumes de production.
• Un ingénieur veut minimiser la quantité de matériau nécessaire pour construire un pont tout en garantissant sa solidité.
• Un agriculteur cherche à maximiser le rendement de sa récolte en choisissant la meilleure quantité d'engrais.
• Un livreur essaie de minimiser le temps de trajet entre plusieurs points de livraison.

En mathématiques, cela se traduit souvent par la recherche des extrema (maximums ou minimums) d'une fonction.

La première étape cruciale pour résoudre un problème d'optimisation est de le modéliser mathématiquement. Cela implique trois éléments clés :

1. Identification des variables : Ce sont les quantités que l'on peut ajuster ou contrôler pour atteindre l'objectif. Elles sont généralement inconnues au début et sont souvent représentées par des lettres comme $x$, $y$, etc. Par exemple, si on optimise la production, les variables pourraient être le nombre d'unités de chaque produit.

2. Fonction objectif : C'est la fonction mathématique qui représente la quantité que l'on souhaite maximiser ou minimiser. Elle dépend des variables identifiées. On la note souvent $f(x)$ ou $f(x,y)$.

   • Si on veut maximiser le profit $P$, la fonction objectif sera $P(x)$.
   • Si on veut minimiser le coût $C$, la fonction objectif sera $C(x,y)$.

3. Contraintes : Ce sont les limitations ou les conditions que les variables doivent respecter. Elles peuvent être dues à des ressources limitées, des exigences techniques, des règles légales, ou des réalités physiques. Les contraintes sont exprimées sous forme d'équations ou d'inégalités.

   • Exemple : "la production ne peut pas dépasser 100 unités" se traduit par $x \le 100$.
   • Exemple : "la somme des longueurs des côtés d'un rectangle doit être égale à 20 cm" se traduit par $2L + 2l = 20$.
   • Souvent, les variables doivent être positives : $x \ge 0$, $y \ge 0$.

Une bonne modélisation est la clé d'une résolution efficace. Elle permet de transformer un problème concret en un problème mathématique que l'on peut résoudre avec les outils appropriés.

Les problèmes d'optimisation peuvent être classés selon plusieurs critères :

• Optimisation sans contraintes : Dans ce cas, les variables peuvent prendre n'importe quelle valeur réelle. On cherche simplement les extrema globaux d'une fonction. C'est le cas le plus simple et souvent une étape intermédiaire dans la résolution de problèmes plus complexes.

• Optimisation sous contraintes : C'est le type le plus courant dans la pratique. Les variables doivent satisfaire une ou plusieurs conditions (équations ou inégalités). La présence de contraintes rend la recherche des extrema plus complexe car la solution optimale peut se trouver sur la "frontière" définie par les contraintes, et non à l'intérieur du domaine.

• Optimisation linéaire vs non linéaire :

  • Optimisation linéaire : La fonction objectif et toutes les contraintes sont des fonctions linéaires des variables. Ces problèmes sont souvent résolus avec des méthodes spécifiques comme la programmation linéaire (par exemple, la méthode du simplexe).
  • Optimisation non linéaire : Au moins la fonction objectif ou l'une des contraintes est une fonction non linéaire. C'est le cas le plus général et souvent plus difficile à résoudre. La plupart des problèmes que nous aborderons en Terminale générale sont de ce type, notamment ceux qui impliquent des fonctions polynomiales, exponentielles ou trigonométriques.

La distinction entre ces types est importante car elle détermine les méthodes mathématiques à utiliser pour la résolution.

Pour trouver les extrema d'une fonction $f(x)$ sur un intervalle, on utilise principalement la dérivée première.

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

   • Si $f'(x) > 0$, la fonction $f$ est strictement croissante.
   • Si $f'(x) < 0$, la fonction $f$ est strictement décroissante.
   • Si $f'(x) = 0$, la fonction $f$ a un point critique. Ces points sont des candidats pour être des extrema locaux.

2. Tableau de variations : Il synthétise le signe de $f'(x)$ et les variations de $f(x)$.

   $x$	$a$	...	$x_0$ ($f'(x_0)=0$)	...	$b$
   $f'(x)$		$+$	$0$	$-$
   $f(x)$	$f(a)$	$\nearrow$	$f(x_0)$ (max local)	$\searrow$	$f(b)$

3. Extrema locaux et globaux :

   • Un maximum local est atteint en un point $x_0$ si $f(x_0)$ est la plus grande valeur de la fonction dans un petit intervalle autour de $x_0$. On a généralement $f'(x)$ qui change de signe de $+$ à $-$ en $x_0$.
   • Un minimum local est atteint en un point $x_0$ si $f(x_0)$ est la plus petite valeur de la fonction dans un petit intervalle autour de $x_0$. On a généralement $f'(x)$ qui change de signe de $-$ à $+$ en $x_0$.
   • Les extrema globaux (ou absolus) sont les plus grandes (maximum global) ou les plus petites (minimum global) valeurs que la fonction peut prendre sur tout son domaine de définition ou sur l'intervalle d'étude. Un extremum global est toujours un extremum local, mais la réciproque est fausse.

Lorsqu'on cherche à optimiser une fonction $f$ sur un intervalle fermé et borné $[a, b]$, on utilise le Théorème des bornes atteintes (ou Théorème des valeurs extrêmes) : Si $f$ est une fonction continue sur un intervalle fermé et borné $[a, b]$, alors $f$ atteint un maximum global et un minimum global sur cet intervalle.

Pour trouver ces extrema globaux, la méthode est la suivante :

1. Calculer la dérivée première $f'(x)$.
2. Trouver les points critiques : Résoudre l'équation $f'(x) = 0$ pour trouver les valeurs de $x$ dans l'intervalle $[a, b]$ où la dérivée s'annule.
3. Évaluer la fonction $f(x)$ à tous les points critiques trouvés dans l'intervalle.
4. Évaluer la fonction $f(x)$ aux bornes de l'intervalle, c'est-à-dire $f(a)$ et $f(b)$.
5. Comparer toutes ces valeurs :
   • La plus grande de ces valeurs est le maximum global de $f$ sur $[a, b]$.
   • La plus petite de ces valeurs est le minimum global de $f$ sur $[a, b]$.

Application à des problèmes simples : Un agriculteur clôture un champ rectangulaire le long d'une rivière (pas de clôture côté rivière). Il dispose de 100 mètres de clôture. Quelle est la surface maximale qu'il peut clôturer ?

• Variables : longueur $L$, largeur $l$.
• Contrainte : $L + 2l = 100$ (longueur de la clôture).
• Fonction objectif : Surface $S = L \times l$ (à maximiser).
• On exprime $L$ en fonction de $l$ : $L = 100 - 2l$.
• On substitue dans $S$ : $S(l) = (100 - 2l)l = 100l - 2l^2$.
• Intervalle : $l > 0$ et $100 - 2l > 0 \implies l < 50$. Donc $l \in ]0, 50[$.
• Dérivée : $S'(l) = 100 - 4l$.
• Point critique : $S'(l) = 0 \implies 100 - 4l = 0 \implies l = 25$.
• Pour $l=25$, $S'(l)$ change de signe de $+$ à $-$ (un maximum).
• $L = 100 - 2(25) = 50$.
• Surface maximale : $S(25) = 50 \times 25 = 1250 \text{ m}^2$.

Ces problèmes impliquent souvent des figures géométriques (rectangles, cylindres, cônes, sphères, etc.). La démarche est la même :

1. Identifier les variables pertinentes (dimensions, positions).
2. Exprimer la fonction objectif (aire, volume, périmètre, distance) en fonction de ces variables, en utilisant les formules de géométrie appropriées.
3. Identifier et exprimer les contraintes (par exemple, un volume fixe, un périmètre donné, un point sur une courbe).
4. Réduire la fonction objectif à une seule variable à l'aide des contraintes (par substitution).
5. Étudier la fonction obtenue (calcul de la dérivée, recherche des points critiques, tableau de variations) pour trouver les extrema.
6. Ne pas oublier de vérifier la pertinence de l'intervalle d'étude pour les variables géométriques (souvent positives).

Exemple : On veut fabriquer une boîte sans couvercle à partir d'une feuille carrée de 20 cm de côté, en découpant des carrés identiques aux quatre coins et en repliant les bords. Quelle doit être la taille des carrés découpés pour obtenir une boîte de volume maximal ?

• Variable : $x$ = côté du carré découpé.
• Dimensions de la boîte : largeur $20-2x$, longueur $20-2x$, hauteur $x$.
• Contraintes : $x > 0$ et $20-2x > 0 \implies x < 10$. Donc $x \in ]0, 10[$.
• Fonction objectif (volume) : $V(x) = (20-2x)(20-2x)x = x(20-2x)^2 = x(400 - 80x + 4x^2) = 4x^3 - 80x^2 + 400x$.
• Dérivée : $V'(x) = 12x^2 - 160x + 400$.
• Points critiques : $V'(x) = 0 \implies 12x^2 - 160x + 400 = 0 \implies 3x^2 - 40x + 100 = 0$.
  • $\Delta = (-40)^2 - 4(3)(100) = 1600 - 1200 = 400$.
  • $x_1 = \frac{40 - \sqrt{400}}{2(3)} = \frac{40 - 20}{6} = \frac{20}{6} = \frac{10}{3}$.
  • $x_2 = \frac{40 + \sqrt{400}}{2(3)} = \frac{40 + 20}{6} = \frac{60}{6} = 10$.
• $x_2=10$ n'est pas dans l'intervalle $]0, 10[$. Donc seul $x = \frac{10}{3}$ est un candidat.
• Le tableau de variations montrerait un maximum pour $x = \frac{10}{3}$.
• Le volume maximal est $V(\frac{10}{3}) = \frac{10}{3}(20 - \frac{20}{3})^2 = \frac{10}{3}(\frac{40}{3})^2 = \frac{10}{3} \times \frac{1600}{9} = \frac{16000}{27} \approx 592.6 \text{ cm}^3$.

Une fonction de plusieurs variables est une fonction dont la valeur dépend de plusieurs inputs (variables indépendantes). Par exemple, $f(x, y)$ est une fonction de deux variables $x$ et $y$.

Définition et exemples :

• $f(x, y) = x^2 + y^2$ (distance au carré par rapport à l'origine dans un plan).
• $g(x, y, z) = xy + z^2$ (fonction de trois variables).
• En économie, le profit d'une entreprise peut dépendre du prix de vente $p$ et du coût de production $c$, soit $P(p, c)$.
• Le volume d'un cylindre est $V(r, h) = \pi r^2 h$, où $r$ est le rayon et $h$ la hauteur.

Représentation graphique (surfaces) : Pour une fonction de deux variables $f(x,y)$, sa représentation graphique est une surface dans un espace à trois dimensions. Chaque point $(x, y, z)$ sur la surface correspond à $z = f(x, y)$.

• Exemple : $f(x, y) = x^2 + y^2$ représente un paraboloïde (forme de bol).
• Visualiser ces surfaces aide à comprendre les notions de maximums et minimums.

Notion de dérivées partielles (intuitive) : Puisqu'il y a plusieurs variables, la notion de "pente" doit être adaptée. Une dérivée partielle mesure le taux de variation de la fonction par rapport à une seule variable, en considérant les autres variables comme des constantes.

• La dérivée partielle de $f(x,y)$ par rapport à $x$, notée $\frac{\partial f}{\partial x}$ ou $f'_x$, est obtenue en dérivant $f$ par rapport à $x$ en traitant $y$ comme une constante.
• La dérivée partielle de $f(x,y)$ par rapport à $y$, notée $\frac{\partial f}{\partial y}$ ou $f'_y$, est obtenue en dérivant $f$ par rapport à $y$ en traitant $x$ comme une constante.
• Exemple : Pour $f(x,y) = x^2y + 3y^3$:
  • $\frac{\partial f}{\partial x} = 2xy$ (on dérive $x^2y$ par rapport à $x$, $3y^3$ est une constante)
  • $\frac{\partial f}{\partial y} = x^2 + 9y^2$ (on dérive $x^2y$ par rapport à $y$, $x^2$ est une constante, et $3y^3$ par rapport à $y$)

Pour une fonction de plusieurs variables, les points où la fonction peut atteindre un maximum ou un minimum sont appelés points critiques.

Gradient (introduction) : Le gradient d'une fonction $f(x,y)$ est un vecteur qui contient toutes ses dérivées partielles : $\vec{\nabla} f(x,y) = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right)$. Il indique la direction de la plus forte pente de la fonction.

Conditions nécessaires d'optimalité (première ordre) : Pour qu'un point $(x_0, y_0)$ soit un extremum local d'une fonction $f(x,y)$ (différentiable), il est nécessaire que le gradient soit nul en ce point. C'est-à-dire : $\frac{\partial f}{\partial x}(x_0, y_0) = 0$ ET $\frac{\partial f}{\partial y}(x_0, y_0) = 0$. Ces points où toutes les dérivées partielles sont nulles sont les points critiques. Attention : un point critique n'est pas nécessairement un extremum (il peut être un point selle, équivalent à un point d'inflexion en 1D).

Exemples simples de recherche : Trouver les points critiques de $f(x,y) = x^2 + y^2 - 4x + 2y + 5$.

1. Calculer les dérivées partielles :
   • $\frac{\partial f}{\partial x} = 2x - 4$
   • $\frac{\partial f}{\partial y} = 2y + 2$
2. Mettre le gradient à zéro :
   • $2x - 4 = 0 \implies x = 2$
   • $2y + 2 = 0 \implies y = -1$
3. Le seul point critique est $(2, -1)$. Pour savoir si c'est un min/max, il faudrait utiliser la dérivée seconde (matrice hessienne), ce qui dépasse le cadre de ce cours. Cependant, en voyant la forme de la fonction ($x^2$ et $y^2$ avec coefficients positifs), on peut deviner qu'il s'agit d'un minimum.

Lorsque la fonction objectif dépend de plusieurs variables mais est soumise à une contrainte, il est parfois possible de ramener le problème à une seule variable.

Substitution de variables : Si la contrainte est une équation qui permet d'exprimer une variable en fonction des autres, on peut substituer cette expression dans la fonction objectif. Exemple : Maximiser $f(x,y) = xy$ sous la contrainte $x+y=10$.

1. De la contrainte, on exprime $y = 10-x$.
2. On substitue dans la fonction objectif : $g(x) = x(10-x) = 10x - x^2$.
3. On a réduit le problème à une optimisation à une variable. On trouve $g'(x) = 10 - 2x$.
4. $g'(x) = 0 \implies x = 5$.
5. Si $x=5$, alors $y = 10-5 = 5$.
6. Le maximum est atteint pour $(5,5)$, et la valeur maximale est $f(5,5) = 25$.

Réduction à une variable : C'est la méthode de substitution. Elle est très efficace quand la contrainte est simple et permet une substitution directe.

Interprétation graphique des contraintes :

• Dans le cas de deux variables $(x,y)$, une contrainte $g(x,y)=c$ représente une courbe dans le plan.
• Optimiser $f(x,y)$ sous cette contrainte revient à trouver le point sur cette courbe où $f(x,y)$ est maximale ou minimale.
• Graphiquement, on peut imaginer les "courbes de niveau" de $f(x,y)$ (où $f(x,y)=k$, pour différentes valeurs de $k$). L'optimum se trouve au point où une courbe de niveau de $f$ est tangente à la courbe de la contrainte $g(x,y)=c$.

1. Méthode de dichotomie (pour trouver des zéros de $f'(x)$) : Cette méthode est utilisée pour trouver une racine d'une fonction (donc un point où $f'(x)=0$, ce qui est un candidat pour un extremum de $f$).

   • On part d'un intervalle $[a, b]$ où $f'(a)$ et $f'(b)$ ont des signes opposés (ce qui garantit une racine par le Théorème des Valeurs Intermédiaires).
   • On calcule le milieu $m = \frac{a+b}{2}$.
   • Si $f'(m)$ a le même signe que $f'(a)$, on remplace $a$ par $m$. Sinon, on remplace $b$ par $m$.
   • On répète le processus, l'intervalle est divisé par deux à chaque étape, convergeant vers la racine avec une précision désirée.
   • C'est une méthode robuste mais relativement lente.

2. Méthode de Newton (principe) : La méthode de Newton est une méthode itérative plus rapide pour trouver les racines d'une fonction $g(x)$ (ici, $g(x) = f'(x)$).

   • On part d'une estimation initiale $x_0$.
   • On calcule la tangente à la courbe $y=g(x)$ au point $(x_0, g(x_0))$.
   • L'intersection de cette tangente avec l'axe des abscisses donne la nouvelle estimation $x_1$.
   • La formule d'itération est : $x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)}$.
   • Dans notre cas, pour trouver $x$ tel que $f'(x)=0$, on applique Newton à $g(x) = f'(x)$, ce qui donne $x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}$.
   • Elle converge très vite si l'estimation initiale est bonne, mais peut échouer si elle est mauvaise ou si $g'(x_n)$ est proche de zéro.

3. Convergence et précision : Les méthodes numériques ne donnent généralement pas de solution exacte mais une approximation.

   • La convergence fait référence à la capacité de l'algorithme à se rapprocher de la vraie solution à mesure que le nombre d'itérations augmente.
   • La précision est la proximité de la solution numérique par rapport à la solution exacte. On fixe souvent un critère d'arrêt (par exemple, $|x_{n+1} - x_n| < \epsilon$ ou $|f'(x_n)| < \epsilon$) pour décider quand l'approximation est suffisante.

Les calculatrices graphiques sont des outils précieux pour l'optimisation, surtout pour les fonctions à une variable.

1. Tracé de fonctions :

   • Saisir la fonction objectif $f(x)$ dans l'éditeur de fonctions de la calculatrice.
   • Ajuster la fenêtre graphique (Xmin, Xmax, Ymin, Ymax) pour visualiser la courbe et les zones d'intérêt.

2. Recherche de maximum/minimum :

   • La plupart des calculatrices ont une fonction "CALC" ou "ANALYSE" qui permet de trouver les maximums et minimums locaux sur un intervalle donné.
   • Il faut souvent spécifier une borne inférieure, une borne supérieure et une estimation initiale pour la recherche.
   • La calculatrice utilise des algorithmes numériques internes pour trouver ces extrema avec une certaine précision.

3. Résolution graphique d'équations :

   • Pour trouver les points critiques (où $f'(x)=0$), on peut tracer la fonction dérivée $f'(x)$ et chercher ses racines (les points d'intersection avec l'axe des abscisses).
   • La fonction "ZEROS" ou "ROOT" de la calculatrice permet de trouver ces racines.

Pour des problèmes plus complexes, des outils informatiques sont indispensables.

1. Logiciels de calcul formel (par exemple, Wolfram Alpha, GeoGebra, Python avec SymPy) :

   • Ils peuvent calculer des dérivées symboliquement, résoudre des équations (y compris $f'(x)=0$) de manière exacte ou approchée.
   • Ils peuvent aussi tracer des fonctions et visualiser des surfaces.
   • Ils sont capables de gérer des problèmes d'optimisation plus sophistiqués, y compris l'optimisation sous contraintes.

2. Tableurs (par exemple, Excel, LibreOffice Calc) :

   • Utiles pour simuler des scénarios : On peut créer des colonnes pour les variables, la fonction objectif et les contraintes. En changeant les valeurs des variables, on observe l'impact sur la fonction objectif.
   • Fonctionnalités d'optimisation : Les tableurs intègrent souvent des modules de "solveur" (Solver) qui peuvent trouver les valeurs des variables qui maximisent ou minimisent une fonction objectif, sous des contraintes définies. Ces solveurs utilisent des algorithmes d'optimisation numérique.

3. Interprétation des résultats :

   • Les résultats numériques sont des approximations. Il est crucial de comprendre la précision des résultats et les limites des méthodes utilisées.
   • Toujours vérifier que les solutions obtenues sont physiquement ou économiquement réalistes (par exemple, une dimension ne peut pas être négative).
   • L'interprétation doit toujours revenir au problème initial : "Quelle est la signification de ce maximum/minimum dans le contexte du problème ?"

• Maximisation du profit : Une entreprise cherche à déterminer les niveaux de production et les prix de vente qui génèrent le profit le plus élevé. La fonction objectif est le profit (recettes - coûts), et les contraintes peuvent inclure la capacité de production, la demande du marché, les coûts des matières premières.
• Minimisation des coûts : Trouver la combinaison la moins chère de ressources (main-d'œuvre, matériaux, énergie) pour produire une certaine quantité ou pour réaliser une tâche.
• Gestion des stocks : Déterminer la quantité optimale de produits à commander et le moment de la commande pour minimiser les coûts de stockage, de commande et les ruptures de stock.

• Minimisation de l'énergie : En mécanique, les systèmes tendent à atteindre un état d'énergie minimale. Par exemple, la forme d'une structure peut être optimisée pour minimiser les contraintes et la quantité de matériau.
• Optimisation de trajectoires : Calculer la trajectoire la plus efficace pour un projectile, un satellite ou un robot pour minimiser le temps de trajet ou la consommation de carburant.
• Conception de structures : Concevoir des ponts, des bâtiments, des ailes d'avion pour maximiser la résistance, minimiser le poids, ou réduire les coûts de fabrication.

• Choix d'itinéraire : Trouver le chemin le plus court ou le plus rapide pour se rendre d'un point A à un point B (utilisé par les GPS).
• Gestion du temps : Allouer son temps entre différentes activités pour maximiser la productivité ou le plaisir.
• Problèmes de découpe : Comment découper un matériau (tissu, bois, métal) pour minimiser les chutes ou maximiser le nombre de pièces utiles.

Une fois la solution mathématique trouvée, il est essentiel de la présenter clairement et de l'interpréter dans le contexte du problème initial.

1. Présentation claire des étapes :

   • Reformuler le problème.
   • Définir les variables.
   • Formuler la fonction objectif.
   • Énoncer les contraintes.
   • Détailler la méthode de résolution (calcul de dérivée, substitution, etc.).
   • Présenter les calculs intermédiaires.
   • Indiquer la valeur optimale de la fonction objectif et les valeurs des variables qui l'atteignent.

2. Vérification de la pertinence des résultats :

   • Les valeurs obtenues sont-elles logiques dans le contexte du problème ? (Ex: une longueur négative est impossible).
   • Les unités sont-elles correctes ?
   • La solution respecte-t-elle toutes les contraintes ?

3. Réponse au problème initial :

   • La conclusion doit répondre clairement à la question posée dans l'énoncé du problème, en utilisant des phrases complètes et en expliquant ce que signifie la solution optimale.
   • Exemple : "Pour maximiser le volume de la boîte, il faut découper des carrés de $\frac{10}{3}$ cm de côté aux coins de la feuille. Le volume maximal obtenu sera alors de $\frac{16000}{27}$ cm$^3$."

Une bonne communication des résultats est aussi importante que la justesse des calculs pour un problème d'optimisation.