Dès que les coûts ne sont plus proportionnels aux quantités, les droites deviennent des courbes, l'optimum quitte les sommets, et le simplexe ne suffit plus. Comment trouver le meilleur point, et comment savoir qu'on l'a trouvé ?
Une fonction non linéaire n'est plus faite de droites : produire deux fois plus peut coûter plus de deux fois plus (heures supplémentaires, usure) ou moins (économies d'échelle). L'exemple de la page : un industriel produit avec deux usines dont les coûts croissent plus vite que les quantités, et cherche à servir sa demande au moindre coût.
Une descente de gradient : des billes partent de plusieurs points et suivent la pente jusqu'au fond. Sur une cuvette convexe, elles arrivent toutes au même endroit.
Les données sont inventées. Les résultats sont calculés sur place dans votre navigateur et confrontés à une seconde méthode : recherche exhaustive sur une grille fine, formule exacte ou différence finie. Cette page fait suite à La programmation linéaire et à Dualité et analyse de sensibilité : les multiplicateurs de Lagrange y généralisent les prix duaux.
Planche 1
Fonctions objectifs et contraintes non linéaires
Un atelier fabrique deux produits, x et y unités. Ils se vendent 40 € et 30 €. Si chaque unité coûtait toujours la même chose, le profit serait linéaire, et l'optimum serait sur un coin du domaine. Mais les coûts montent avec les quantités (heures supplémentaires, machines partagées) : coût = (x² + xy + 1,5 y²) / 2. Le profit devient une colline, avec un sommet.
Profit selon les quantités : plus c'est foncé, plus il est élevé ; les courbes relient les points de même profit. Zone hachurée : interdite par la capacité x + y ≤ C. Point rouge : l'optimum. Cliquez pour placer votre point (violet).
–
Votre point : profit–
Optimum (x ; y) : profit–
Contrôle : formule exacte (x ; y)–
Valeur d'une unité de capacité en plus–
Ce qu'il faut retenir. Avec des coûts proportionnels, les courbes de niveau sont des droites et l'optimum est toujours sur un sommet du domaine, comme en programmation linéaire. Avec des coûts croissants, ce sont des ellipses, et l'optimum peut être à l'intérieur : au-delà de C = 44, la capacité ne gêne plus (36 et 8 unités, 840 €), et une unité de capacité en plus ne vaut plus rien. En dessous, l'optimum est sur le bord, mais pas forcément sur un coin. On ne peut plus se contenter d'examiner les sommets.
Planche 2
Convexité : optimum local ou global ?
Un minimum local est le plus bas de son voisinage ; un minimum global est le plus bas de tous. Une fonction est convexe si toute corde entre deux points de la courbe reste au-dessus de la courbe : c'est une cuvette sans bosse. Alors, et c'est le grand résultat, tout minimum local est global. Ajoutez des ondulations et regardez les billes.
f(x) = x²/4 + 3a·sin(3x). Les billes descendent la pente depuis 12 départs ; vertes si elles atteignent le minimum global, orange si elles restent coincées. Une corde tirée au hasard clignote : rouge si elle passe sous la courbe.
–
Minimums locaux–
Départs atteignant le minimum global (sur 200)–
Cordes passant sous la courbe (sur 20 000)–
Courbure minimale f'' = 1/2 − 27a–
Ce qu'il faut retenir. Le test des cordes et le signe de f'' disent la même chose : la fonction est convexe tant que f'' ≥ 0 partout, ici jusqu'à a = 0,0185. Remarquez une subtilité : entre 0,0185 et environ 0,06, la fonction n'est plus convexe, mais n'a encore qu'un minimum ; la convexité est une garantie, pas la seule façon d'avoir un minimum unique. Au-delà, les billes se font piéger : une méthode de descente ne voit que la pente locale, elle trouve un minimum local, et rien ne dit qu'il est global.
Planche 3
Méthodes de descente et gradient
Le gradient est la flèche qui indique la plus forte montée ; on avance donc dans le sens opposé. Toute la difficulté est de choisir la longueur du pas. Trois méthodes, sur deux paysages.
Courbes de niveau de f, et les chemins depuis le même départ. Bleu : pas fixe. Vert : pas optimal (on cherche le meilleur point le long de la direction). Rouge : méthode de Newton, qui utilise aussi la courbure.
–
Pas fixe choisi : itérations–
Pas optimal : itérations–
Newton : itérations–
Théorie, meilleur pas fixe : ((κ − 1)/(κ + 1)) par itération–
La fonction de Rosenbrock : une vallée étroite et courbée, minimum en (1 ; 1). Mêmes couleurs.
Pas fixe 0,02 : après 50 000 itérations–
Pas optimal : itérations jusqu'à 10⁻⁸ de pente–
Newton : itérations–
Ce qu'il faut retenir. Le gradient pointe vers le bas le plus raide, pas vers le minimum. Dans une vallée allongée, il zigzague d'un versant à l'autre : le nombre d'itérations croît comme l'allongement κ, exactement comme le prévoit la théorie. Un pas trop grand (au-delà de 2/L) fait diverger la méthode. Newton tient compte de la courbure : sur une vallée elliptique, il arrive en un seul pas ; sur la banane, en une douzaine, là où le gradient en met des milliers.
Planche 4
Les multiplicateurs de Lagrange
Revenons aux deux usines. Il faut produire exactement D unités, q₁ dans l'usine 1 et q₂ dans l'usine 2. L'usine 1 coûte 2 € l'unité plus 0,05 q₁² ; l'usine 2, 5 € l'unité plus 0,02 q₂². Le coût total doit être minimal sous la contrainte q₁ + q₂ = D. Lagrange (1788) : à l'optimum, le gradient du coût est parallèle à celui de la contrainte. Le coefficient qui les relie, λ, est le multiplicateur.
Courbes de même coût total, et la droite q₁ + q₂ = D. Flèche rouge : gradient du coût au point choisi. Flèche verte : direction (1 ; 1), perpendiculaire à la droite. À l'optimum, elles sont alignées : la courbe de niveau touche la droite.
Le long de la droite : coût total (bleu) selon q₁, et coûts marginaux des deux usines (orange pour l'usine 1, violet pour l'usine 2). L'optimum est là où ils sont égaux.
–
Coûts marginaux usine 1 ; usine 2–
Angle entre les deux gradients–
Optimum q₁ ; q₂ : coût–
Multiplicateur λ–
Contrôle : coût d'une unité de demande en plus (différence finie)–
Ce qu'il faut retenir. Les équations de Lagrange se lisent en langage d'économiste : à l'optimum, les coûts marginaux des deux usines sont égaux. Sinon, on gagnerait à déplacer une unité de l'usine chère vers l'autre. Et λ, ce coût marginal commun, est exactement ce que coûte une unité de demande en plus : c'est le prix dual de la programmation linéaire, généralisé aux courbes.
Planche 5
Les conditions de Karush-Kuhn-Tucker : l'exemple complet
Ajoutons des contraintes d'inégalité : l'usine 1 ne peut pas dépasser 50 unités, l'usine 2 pas 80, et aucune ne produit une quantité négative. Les conditions de Karush (1939), Kuhn et Tucker (1951) étendent Lagrange : chaque contrainte reçoit un multiplicateur μ ≥ 0, nul si la contrainte n'est pas atteinte. Le curseur e change la forme des coûts : e = 2, ils croissent plus vite que les quantités (convexe) ; e = 1, ils sont proportionnels ; e < 1, il y a des économies d'échelle.
Coût total selon la part de l'usine 1, pour la demande choisie (seules les répartitions permises par les capacités sont tracées). Point rouge : le vrai minimum. Losanges : les points où les coûts marginaux sont égaux.
Le multiplicateur λ (coût d'une unité de plus) selon la demande, pour le e choisi. Ses cassures marquent les changements de régime : une usine qui démarre, une autre qui sature.
–
Production q₁ ; q₂ : coût–
λ (multiplicateur de la demande)–
Contrôle : coût d'une unité en plus (différence finie)–
Points où les coûts marginaux sont égaux : coût–
Ce qu'il faut retenir. Avec des coûts convexes (e = 2), les conditions KKT suffisent : le point qui les vérifie est l'optimum. Elles racontent l'histoire de la production : jusqu'à 30 unités, seule l'usine 1 tourne (l'usine 2, trop chère à la marge, a un μ positif) ; puis les deux, à coûts marginaux égaux ; au-delà de 100, l'usine 1 sature et son μ mesure ce qu'un peu plus de capacité ferait gagner. Mais avec des économies d'échelle (e < 1), le point où les coûts marginaux s'égalisent devient un maximum : mieux vaut concentrer la production. Les conditions KKT restent nécessaires, mais ne suffisent plus ; sans convexité, il faut comparer tous les candidats, ici les bords.
Ce qu'il faut garder
Le relief
Une fonction non linéaire a des vallées, des crêtes, des plateaux. L'optimum peut être à l'intérieur du domaine, sur un bord, ou en plusieurs endroits.
La convexité
Si la fonction est convexe et le domaine aussi, tout minimum local est global, les conditions KKT suffisent, et les méthodes de descente trouvent la réponse.
Les multiplicateurs
À l'optimum, les coûts marginaux s'équilibrent. Chaque multiplicateur dit ce que vaut l'assouplissement d'une contrainte : c'est le prix dual, sur des courbes.
Pour aller plus loin
Dans ce cahier.La programmation linéaire et Dualité et analyse de sensibilité ; Répartir une ressource entre plusieurs activités (égalisation des rendements marginaux) ; L'optimisation de portefeuille (un problème quadratique convexe) ; Les stocks et la chaîne d'approvisionnement (formule de Wilson).
Sur les calculs. Les optimums de la planche 1 sont trouvés par grille puis recherche locale, et comparés à la formule exacte. Dans la planche 2, les billes font une descente à pas 0,05 ; les minimums locaux sont trouvés par changement de signe de la dérivée, puis dichotomie. Dans la planche 3, on s'arrête quand la pente est inférieure à 10⁻⁸ ; le pas optimal est trouvé par section dorée ; Newton est muni d'un retour en arrière, qui réduit le pas si le coût ne baisse pas assez. Aux planches 4 et 5, l'optimum est trouvé sur une grille de 4 000 répartitions, raffinée par section dorée, puis comparé aux conditions de Lagrange et de KKT. Les coûts s'écrivent cᵢ(q) = mᵢ q + sᵢ · 2 500 · (q/50)ᵉ.