Optimisation

Objectif

L'optimisation répond à une question de dosage: quelles quantités produire, quelles ressources affecter à quel usage, quel mélange retenir, lorsque les combinaisons admissibles sont trop nombreuses pour être comparées une par une.

Le livrable tient en deux parties. Le plan optimal donne une valeur à chaque variable de décision: produire tant d'unités de ceci et tant de cela. La lecture des contraintes dit laquelle des limites retient le résultat et ce que vaudrait son desserrement d'une unité. La seconde partie ouvre la discussion avec le décideur: une contrainte saturée assortie de sa valeur marginale transforme « nous manquons de capacité » en un montant que l'on compare au coût d'en acheter.

Usage

Quand l'utiliser

• Ressource partagée: un atelier, un budget, une équipe à répartir entre des usages qui ne rapportent pas la même chose.
• Objectif et limites chiffrables: une marge, un coût total, un écart à une cible; des capacités mesurées, des engagements contractuels, des plafonds réglementaires.
• Combinaisons trop nombreuses pour être énumérées: dès trois ou quatre variables, la comparaison manuelle des plans devient illusoire.
• Décision qui se rejoue: un plan de production mensuel, une tournée quotidienne, un horaire; le modèle s'amortit à chaque exécution.
• Arbitrage contesté entre services: la discussion se déplace des préférences vers les contraintes et l'objectif.

Quand ne pas l'utiliser

• Critères multiples sans commune mesure: pondérer coût, risque et image demande l'analyse multicritère.
• Incertitude logée dans les données plutôt que dans le choix: la simulation décisionnelle rend une distribution là où l'optimisation rend un point.
• Poignée d'options déjà listées: quatre variantes de fournisseur se départagent dans une matrice de décision.

Description

Les trois éléments et le modèle

Les variables de décision sont les grandeurs que le décideur contrôle: le nombre d'unités à produire de chaque référence, les heures affectées à chaque chantier, la part de chaque titre dans un portefeuille. Chacune porte un type, qui commande la difficulté du calcul: continue pour une grandeur qui prend n'importe quelle valeur d'un intervalle, des litres ou des heures; entière pour des objets qui se comptent en unités; binaire pour une décision de tout ou rien, ouvrir un site ou non. Dans l'entraînement d'un modèle d'apprentissage automatique, ce sont les poids attribués aux variables explicatives qui tiennent ce rôle.

La fonction objectif exprime en une formule ce que l'on cherche à rendre maximal ou minimal. Un modèle n'en porte qu'une. Selon le domaine d'application, elle s'appelle fonction de décision, fonction de coût ou fonction d'erreur. Un objectif comme « maximiser la marge et minimiser les délais » ne se résout pas tel quel: l'un des deux devient une contrainte, ou les deux entrent dans une somme pondérée dont les poids sont eux-mêmes une décision.

Les contraintes bornent le réalisable. Chacune s'écrit comme une inégalité ou une égalité portant sur les variables de décision: une capacité qui plafonne, un engagement de livraison qui impose un plancher, une composition qui doit tomber juste. Le guide de l'IIBA rattache aux contraintes la contribution de l'analyste: elles se découvrent par élicitation et dans les règles métier que documente l'analyse des règles métier.

Le modèle d'optimisation est une ligne d'objectif, une liste d'inégalités, une déclaration de type pour chaque variable. Ce texte est ce que le solveur consomme. Il tient en une page pour la plupart des problèmes de planification d'une entreprise.

Écrire les contraintes

Une contrainte utilisable porte quatre informations: la grandeur limitée, ce que chaque unité de chaque variable en consomme, la borne et l'origine de cette borne. Les trois premières sont des mesures. La quatrième est un nom de personne ou de document, sans quoi la contrainte est indiscernable d'un chiffre avancé en réunion.

Les bornes s'obtiennent auprès d'interlocuteurs différents: la capacité machine à l'atelier, le plafond d'achat au service des achats, l'obligation légale au juriste. Les coefficients de consommation se mesurent sur des séries d'exécution passées: une erreur y déplace la droite de contrainte, donc les coordonnées du sommet optimal. Un coefficient de la fonction objectif est plus tolérant: il varie souvent de plusieurs dizaines de pour cent avant que le plan change de sommet. Les contraintes implicites sont les plus coûteuses à oublier: un temps de changement de série entre deux références, un effectif minimal par équipe, une clause d'exclusivité qui interdit un mélange de fournisseurs.

Deux réponses du solveur signalent une formulation fautive plutôt qu'une mauvaise nouvelle. Infaisable veut dire qu'aucune combinaison ne satisfait toutes les contraintes à la fois, parce que deux limites se contredisent ou qu'un minimum imposé dépasse une capacité. Non borné veut dire que l'objectif croît sans fin, signe qu'une contrainte manque, le plus souvent celle qui plafonne la demande ou l'approvisionnement.

Le contrôle décisif est humain. On montre le plan optimal aux personnes qui auraient à le tenir et on leur demande si elles sauraient le faire. Ce qu'elles objectent est la contrainte manquante, formulée dans leurs mots.

Deux familles sous un même nom

Le guide de l'IIBA sépare les problèmes selon le degré d'incertitude qu'ils portent.

Quand l'objectif et les contraintes sont linéaires, le problème relève de la programmation linéaire: maximiser ou minimiser une fonction linéaire sur le domaine convexe que découpent des inégalités linéaires. George Dantzig en a conçu la méthode de résolution, le simplexe, en 1947 sur des problèmes de planification de l'armée de l'air américaine; le nom « programmation linéaire » revient à Tjalling Koopmans en 1948. Des algorithmes en temps polynomial ont suivi: la méthode des ellipsoïdes de Khachiyan en 1979, puis la méthode de point intérieur de Karmarkar en 1984. Le guide de l'IIBA relève son emploi étendu en logistique, en production et en gestion de projet.

Quand la relation cesse d'être linéaire, l'optimum se cherche pas à pas. Un modèle d'apprentissage automatique ajuste ses poids pour réduire une fonction d'erreur par descente de gradient, en suivant à chaque itération la direction de plus forte diminution. La volatilité d'un portefeuille relève du même cas: elle dépend de sa composition par une relation non proportionnelle. Le guide de l'IIBA en tire une limite: la solution optimisée n'est pas nécessairement la meilleure solution existante. Il ajoute que ces calculs consomment du temps machine sur les grands jeux de données.

Pourquoi l'optimum se trouve sur un sommet

Sur deux variables, la géométrie se dessine. Chaque contrainte linéaire coupe le plan en deux et n'en retient qu'une moitié. L'intersection de tous ces demi-plans est la région réalisable, un polygone convexe qui rassemble tous les plans exécutables. La fonction objectif y trace une famille de droites parallèles, une par niveau de résultat. On fait glisser cette famille vers les valeurs croissantes jusqu'au dernier contact avec le polygone. Ce dernier contact est un sommet.

Un sommet est le point où plusieurs contraintes se croisent, donc une solution optimale sature autant de contraintes qu'il y a de variables, les contraintes de positivité comprises; c'est ce qui rend les plans optimaux tranchés, avec des lignes de produit à zéro là où l'intuition attendait un peu de tout. Le simplexe exploite la même propriété: il passe d'un sommet à son voisin jusqu'à ce qu'aucun ne fasse mieux, ce qui lui épargne l'exploration de l'intérieur du domaine.

Lire la solution

Un solveur rend davantage qu'un plan. La valeur de chaque variable est le plan lui-même. Les contraintes saturées sont celles que la solution consomme jusqu'à la borne; les autres gardent un écart, une réserve inemployée qu'il est inutile d'augmenter. La valeur marginale d'une contrainte saturée chiffre le gain d'objectif qu'apporterait une unité de ressource supplémentaire, à comparer au prix d'achat de cette unité. Les plages de validité disent jusqu'où un coefficient de marge ou de coût peut bouger avant que le plan optimal change de sommet. La différence avec le plan en vigueur est le seul chiffre que le comité retiendra.

Les pièges

La contrainte implicite

Le guide de l'IIBA compte la formulation exacte des contraintes parmi les exigences de la technique. Une limite que personne n'a pensé à énoncer, parce qu'elle va de soi sur le terrain, produit un plan mathématiquement optimal et opérationnellement impossible. Le plan est alors rejeté, et avec lui la méthode.

L'objectif de substitution

Maximiser la marge du mois est facile à écrire et rarement ce que l'entreprise veut. Le modèle obéira à la lettre: il abandonnera un client de faible marge dont dépend un volume d'après-vente ou saturera une machine dont l'entretien est prévu. Ce que l'objectif ne dit pas doit entrer dans les contraintes, sous forme de planchers de service ou de parts minimales.

L'arrondi des entiers

Résoudre en continu puis arrondir est le raccourci le plus courant. Il sort du domaine réalisable dès que les contraintes sont serrées: 80,4 unités arrondies à 81 dépassent la capacité. Les solveurs traitent les variables entières nativement, à un coût de calcul supérieur qui reste modeste sur des modèles de cette taille.

La précision du solveur prise pour celle des données

Un solveur affiche CHF 43'200 sur des coefficients de marge estimés à 10% près. Le nombre de décimales appartient à la machine, la fiabilité appartient aux entrées. La parade est de rejouer le modèle avec les coefficients aux bornes de leur plage et de regarder si le plan tient, démarche que couvre l'analyse de sensibilité.

L'optimum local pris pour l'optimum

Sur un problème non linéaire, une descente de gradient s'arrête au fond de la cuvette qu'elle a trouvée, sans savoir si une cuvette plus profonde existe ailleurs. Relancer depuis plusieurs points de départ et comparer les arrivées est le contrôle usuel. Cette précaution disparaît en programmation linéaire, où la convexité du domaine garantit que l'optimum trouvé est l'optimum global.

Le modèle que personne ne sait expliquer

Le guide de l'IIBA le pose parmi les limites: les formulations complexes sont difficiles à expliquer aux parties prenantes. Un décideur ne signe pas un plan dont il ne sait pas d'où il sort. La contre-mesure est de présenter le modèle par ses contraintes, que chacun reconnaît, avant sa mécanique.

Considérations IA

Le premier emploi utile est la traduction en formulation. Un modèle de langue transforme « on ne peut pas dépasser 640 heures d'atelier par mois » en une inégalité sur les variables déclarées et écrit les quelques lignes de code qui appellent un solveur. Le résultat se vérifie, puisqu'un modèle d'optimisation est un texte court dont chaque ligne se relit contre la contrainte qu'elle prétend traduire.

Le deuxième est l'estimation des coefficients à partir de séries d'exécution, le temps de montage réel par référence ou la consommation matière par unité: un ajustement statistique sur des données que l'entreprise possède déjà. Le troisième est la génération de variantes: reformuler l'objectif, ajouter une deuxième équipe, relâcher un plafond, exécuter la série de scénarios et présenter les écarts. Le quatrième est la mise en mots du résultat à partir des contraintes saturées et des valeurs marginales, où les nombres sont fournis et rien ne s'invente.

Deux limites tiennent. Les contraintes appartiennent à l'organisation: une clause contractuelle, la capacité d'un banc d'essai, un plafond d'autorisation cantonale. Un modèle de langue en propose de plausibles, ce qui accélère la première liste et ne remplace pas la validation par la personne qui répond de chaque chiffre. Interrogé sur « quel est le plan optimal », un modèle de langue rédige un plan vraisemblable sans avoir rien résolu: aucune contrainte n'est garantie satisfaite. Que l'entraînement d'un tel modèle repose lui-même sur une optimisation ne le rend pas capable de résoudre celle du lecteur.

Exemples

Un atelier d'électronique jurassien assemble deux boîtiers de mesure. Le montage et l'étalonnage passent par les mêmes ressources et un module radio n'entre que dans le modèle connecté.

La lecture qui décide est celle des deux ressources saturées. Une heure de montage supplémentaire vaut CHF 45, une heure de banc d'essai CHF 60, dans un atelier qui compte quatre personnes au montage pour un seul banc tournant en deux équipes. La valeur marginale se compare au prix d'achat de l'unité, et les deux unités ne s'achètent pas de la même façon.

Une heure de montage s'achète à l'heure, en heures supplémentaires ou en intérim, à un tarif connu que l'on pose en face des CHF 45. Une heure de banc ne s'achète pas: le banc tourne déjà onze heures par jour ouvré, et la plus petite quantité disponible sur le marché est un second banc entier, un investissement à amortir sur plusieurs années. La ressource à desserrer en premier est donc le montage, malgré son montant plus faible; le banc relève d'une décision d'investissement. Négocier un contingent de modules radio plus large ne rapporterait rien, puisque cette contrainte n'est pas saturée.

Les marges unitaires restent des estimations. La plage CHF 75 à CHF 150 porte sur le coefficient de marge du Standard, aujourd'hui à CHF 120. La marge étant le prix de vente diminué du coût variable unitaire, une révision de ce coût la déplace d'autant en sens inverse: tant que la marge reste dans ces limites, le modèle n'est pas rouvert.

Visualisations

Une seule chose demande un dessin: le passage des contraintes à la solution. Les inégalités s'écrivent en lignes et la solution en colonnes, mais la raison pour laquelle l'optimum tombe sur un sommet plutôt qu'au milieu du domaine ne se lit que sur un plan. La formulation et la lecture du résultat restent des tableaux, chacun avec son origine ou son interprétation en regard.

Coût

Outils

Le tableur muni d'un solveur est le point d'entrée. Le solveur d'Excel, développé par Frontline Systems, traite les problèmes linéaires, linéaires en nombres entiers, quadratiques et non linéaires. Le guide de l'IIBA le cite comme outil de démonstration: un modèle à deux variables affiché sur le classeur que le contrôle de gestion sait déjà lire construit plus de confiance qu'un exposé de méthode. LibreOffice Calc embarque un solveur comparable.

Les bibliothèques de programmation prennent le relais dès que le modèle doit être versionné, rejoué ou branché sur un système. PuLP et Pyomo en Python posent le modèle dans une syntaxe proche de sa forme algébrique, scipy.optimize.linprog couvre le cas linéaire simple, OR-Tools de Google ajoute les problèmes de tournées et d'ordonnancement, lpSolve fait le même travail en R. Le fichier de code devient la documentation du modèle.

Les solveurs spécialisés se placent derrière ces bibliothèques quand la taille l'exige: Gurobi, IBM CPLEX et FICO Xpress du côté commercial, HiGHS, CBC et GLPK du côté libre. En production industrielle, les modules de planification avancée greffés sur un ERP portent le modèle nativement, avec les données de capacité et de nomenclature déjà en place. Du côté itératif, les bibliothèques d'apprentissage automatique comme scikit-learn, PyTorch et TensorFlow embarquent la descente de gradient et ses variantes.

Sources

• IIBA, Guide to Business Data Analytics, §3.14 Optimization: la définition, les trois éléments et leur assemblage en modèle, la séparation entre faible et forte incertitude, le rôle de l'analyste dans la découverte des contraintes, les forces et les limites.
• MacTutor History of Mathematics, George Dantzig, University of St Andrews: la conception du simplexe en 1947 sur des problèmes de planification militaire et l'attribution du nom « programmation linéaire » à Tjalling Koopmans en 1948.
• Wolfram MathWorld, Linear Programming: la forme standard du problème, le domaine convexe défini par les inégalités, le simplexe, la méthode des ellipsoïdes de Khachiyan et la méthode de point intérieur de Karmarkar, toutes deux en temps polynomial.
• Frontline Systems, Linear Programming in Excel: la documentation des concepteurs du solveur d'Excel et le périmètre des problèmes que ses moteurs traitent.