Un modèle d'optimisation ne sert à rien tant qu'il n'est pas écrit dans un outil, résolu, lu correctement et validé. Cette page suit le chemin complet : du tableur et de son solveur au code Python, de la lecture d'un rapport de résolution à la vérification des données, jusqu'à une étude réelle de localisation d'entrepôts.
Le principe de cette page : tout ce que vous voyez est calculé par un vrai moteur d'optimisation, écrit en JavaScript dans la page : méthode du simplexe en deux phases, puis séparation et évaluation pour les variables entières. Il joue le rôle du solveur d'Excel ou de LibreOffice, ou des bibliothèques appelées depuis Python.
Le cycle d'une étude d'optimisation : chaque étape alimente la suivante, et la validation renvoie souvent aux données ou au modèle. Un point parcourt la boucle.
Les données sont inventées. Chaque résultat est vérifié par une seconde méthode : énumération des sommets, recherche exhaustive, différences finies ou recalcul indépendant. Cette page conclut la série de cours de recherche opérationnelle ; elle s'appuie en particulier sur La programmation linéaire, Dualité et analyse de sensibilité et Programmation en nombres entiers.
Planche 1
Utiliser un tableur et son solveur
Un atelier fabrique des tables, des chaises et des bureaux. Dans un tableur, le modèle tient en quelques cellules. Les cellules variables (en jaune) contiennent les quantités à produire. Une cellule objectif (en rouge) calcule la marge totale par une formule SOMMEPROD. Les cellules « Utilisé » calculent la consommation de chaque ressource, que le solveur doit maintenir sous « Disponible ». Cliquez une cellule pour voir sa formule ; modifiez les nombres en bleu.
E8fx=SOMMEPROD(B4:D4;B3:D3)
Paramètres du solveur
Objectif : $E$8 Max
Cellules variables : $B$3:$D$3
Contraintes : $E$5:$E$7 <= $F$5:$F$7
Méthode : Simplexe PL
Le chemin suivi par le simplexe : chaque pivot passe d'un sommet du domaine à un sommet voisin, et la marge totale monte (ou, en nombres entiers, l'arbre de séparation et évaluation).
–
Marge totale optimale–
Contrôle : meilleur des sommets du domaine, tous énumérés–
Contrôle des prix duaux : +1 de ressource, nouvelle résolution–
Ce qu'il faut retenir. Le tableur est idéal pour les petits modèles qu'on veut montrer et faire manipuler : les données, les formules et la solution sont au même endroit. Le rapport de sensibilité se lit comme en dualité. La finition a un prix dual de 25 € par heure : une heure de plus rapporterait 25 €. La menuiserie a un prix nul, car il en reste. Le bureau a un coût réduit de −6,67 € : il faudrait augmenter sa marge d'au moins 6,67 € pour qu'il vaille la peine d'en produire. Les limites : les formules se cachent dans les cellules, les modèles grossissent mal, et le solveur intégré plafonne vite (200 variables pour le solveur standard d'Excel).
Planche 2
Modéliser avec Python et des outils d'optimisation
Dès que le modèle grossit ou doit tourner régulièrement, on l'écrit dans un langage de programmation. En Python, des bibliothèques comme PuLP, Pyomo ou OR-Tools permettent d'écrire le modèle presque comme en mathématiques, puis de l'envoyer à un solveur (CBC, HiGHS, Gurobi, CPLEX…). Voici le même atelier, avec les données de la planche 1.
Solution–
Relaxation continue ; prix de l'intégrité–
Contrôle : recherche exhaustive des solutions entières–
Ce qu'il faut retenir. Le code sépare ce que le tableur mélange : les données (dictionnaires, fichiers), le modèle (variables, objectif, contraintes, écrits une fois pour toutes avec des boucles) et la résolution (un appel au solveur). Le même code traite 3 produits ou 3 000. Passer en nombres entiers ne change qu'un mot (cat="Integer") ; le solveur passe alors de la programmation linéaire à la séparation et évaluation. Ici, arrondir la solution continue (50,83 et 83,33) ne suffit pas : la meilleure solution entière produit 85 chaises, pas 83.
Planche 3
Lire les résultats : faisabilité, optimalité et écart à l'optimum
Un solveur ne rend pas toujours une solution. Il rend d'abord un statut, qu'il faut lire avant tout chiffre. Optimal : la solution est prouvée la meilleure. Infaisable : aucune solution ne respecte toutes les contraintes. Non borné : l'objectif peut croître sans limite, ce qui trahit presque toujours une erreur de modélisation. Limite atteinte : en nombres entiers, le temps est écoulé ; on a une solution et une borne, et l'écart entre les deux mesure ce qu'on risque de perdre.
–
–
Statut–
Valeur ; borne–
Diagnostic–
Contrôle–
Ce qu'il faut retenir. Devant un modèle infaisable, on cherche le plus petit groupe de contraintes incompatibles (un IIS) : ici, 100 bureaux demandent 500 heures de menuiserie quand il y en a 310. Devant un modèle non borné, on cherche la contrainte oubliée ou mal orientée. Pour un gros modèle en nombres entiers, on lit l'écart : écart = (borne − solution) / solution. À 1 %, la solution trouvée est garantie à moins de 1 % de l'optimum, même si l'on n'a pas fini la preuve ; c'est souvent suffisant en pratique. Ce problème de 28 lots, avec 2²⁸ ≈ 268 millions de combinaisons, est résolu et prouvé optimal en 467 nœuds ; au bout de 100 nœuds, on tient déjà une solution garantie à moins de 2 %.
Planche 4
Vérifier les données et valider le modèle
« Garbage in, garbage out » : un modèle parfait nourri de mauvaises données donne une mauvaise décision, avec toutes les apparences de la rigueur. Avant de résoudre, on vérifie les données par des contrôles automatiques. Après, on valide la solution : respecte-t-elle vraiment les contraintes, son coût se recalcule-t-il, est-elle cohérente avec ce qu'on observe dans la réalité ? Les données sont celles du projet de la planche 5. Injectez des erreurs typiques.
Contrôles des données
Validation de la solution
–
Ce qu'il faut retenir. Les contrôles automatiques (types, signes, doublons, totaux, valeurs aberrantes) attrapent la plupart des erreurs de saisie avant qu'elles ne coûtent cher. Mais certaines erreurs passent tous les contrôles : un coût de transport dix fois trop élevé reste un nombre positif et raisonnable. Seule la validation la démasque : on fait calculer au modèle le coût du réseau actuel, et on le compare à ce qui a réellement été dépensé l'an dernier. Le coût recalculé, le respect des contraintes et l'encadrement entre une borne et une heuristique complètent la panoplie. Un modèle n'est validé que s'il reproduit le passé connu.
Planche 5
Projet complet : où implanter les entrepôts ?
Une entreprise livre dix grandes villes depuis cinq entrepôts. Chaque entrepôt ouvert coûte un loyer fixe annuel, a une capacité limitée, et chaque livraison coûte selon la distance. Faut-il les garder tous ? C'est un problème de localisation avec capacités, qui mêle des décisions binaires (ouvrir ou fermer) et des flux continus (qui livre qui). Lancez l'étude : elle enchaîne les étapes des planches précédentes. Cliquez un entrepôt sur la carte pour l'imposer ouvert, puis fermé, puis le libérer.
Carré plein : entrepôt ouvert (cadre vert : imposé ouvert ; croix rouge : imposé fermé). Disque : client, de taille proportionnelle à sa demande. Traits : flux de livraison, d'épaisseur proportionnelle au volume.
Coût annuel de toutes les combinaisons d'entrepôts réalisables (énumération complète), triées. En rouge, l'optimum trouvé par le solveur ; en gris, le réseau actuel (tout ouvert).
–
Recommandation : coût annuel–
Économie par rapport au réseau actuel–
Contrôle : énumération des 31 combinaisons–
Nœuds de séparation et évaluation ; borne de la relaxation–
Deuxième meilleure solution–
Test de robustesse : demande +10 %–
Ce qu'il faut retenir. Avec la demande actuelle, garder Lyon, Bordeaux et Orléans suffit, pour 4 739 k€ par an au lieu de 5 096 k€ avec les cinq entrepôts, soit 7 % d'économie. Mais une étude ne s'arrête pas à l'optimum. La deuxième solution (garder aussi Rouen) ne coûte que 0,6 % de plus : c'est une information précieuse pour le décideur, qui peut avoir d'autres raisons de la préférer. Le test de robustesse montre que la recommandation change avec la croissance de la demande. La formulation compte aussi : en ajoutant les contraintes x ≤ d·y, redondantes en nombres entiers, la relaxation se resserre et le solveur explore moins de nœuds. Bien écrire un modèle, c'est aussi aider le solveur.
Ce qu'il faut garder
L'outil
Le tableur pour montrer et manipuler un petit modèle, Python et un solveur pour les modèles réels, répétés ou de grande taille.
La lecture
Le statut avant les chiffres ; les prix duaux et les coûts réduits pour comprendre ; l'écart à la borne pour juger une solution non prouvée.
La rigueur
Contrôler les données, valider sur le passé, tester la robustesse et présenter les alternatives proches : c'est ce qui rend une recommandation crédible.
Pour aller plus loin
Dans ce cahier.La programmation linéaire (simplexe) ; Dualité et analyse de sensibilité ; Programmation en nombres entiers et variables binaires ; La localisation des installations stratégiques ; Simulation et Monte-Carlo ; Heuristiques, métaheuristiques et complexité.
Sur les calculs. Simplexe en deux phases, avec la règle de Bland contre le cyclage ; les prix duaux et les coûts réduits sont lus dans le tableau final, puis contrôlés par différence finie. Séparation et évaluation : on explore d'abord le nœud de meilleure borne, en branchant sur la variable la plus fractionnaire. Le code Python affiché utilise la syntaxe de PuLP ; il n'est pas exécuté ici, mais le même modèle est résolu par le moteur de la page, dont le journal est reproduit. Jeu irréductible de contraintes (IIS) : filtre par suppression. Projet : énumération des 31 combinaisons d'entrepôts, chacune résolue comme un problème de transport, et comparée au modèle mixte complet. Le coût « réellement constaté » de la planche 4 est une donnée inventée, fixée 3 % au-dessus du coût calculé du réseau actuel.