🍞 Le problème du boulanger
Tu es boulanger. Tu peux faire deux produits :
- Pain : 1 kg de farine, 0,5 h de travail, marge 4 DH
- Gâteau : 2 kg de farine, 1 h de travail, marge 7 DH
Tu as 100 kg de farine et 30 h de travail dispo par jour. Question : combien de pains x et de gâteaux y faut-il produire pour maximiser ta marge ?
Ce problème, sous une forme ou une autre, est le quotidien de millions d'industries. Sa formulation mathématique s'appelle programmation linéaire.
🎛️ Région réalisable et optimum
🎛️ Maximisation 2D interactive
Bouge les coefficients de la fonction objectif. L'optimum se déplace sur un sommet du polygone.
Optimum trouvé
x* = 20, y* = 40 → marge = 360 DH
📐 Formulation mathématique
En programmation linéaire, on cherche à :
Maximiser : f(x, y) = ax + by (objectif linéaire)
Sous contraintes :
x + 2y ≤ 100 (farine)
0,5x + y ≤ 30 (travail)
x ≥ 0, y ≥ 0 (positivité)
🎯 Théorème clé : l'optimum est sur un sommet
Théorème fondamental : pour un programme linéaire, l'optimum est toujours atteint sur un sommet de la région réalisable (un polygone convexe).
Pour notre exemple : les 4 sommets sont (0, 0), (60, 0), (20, 40) et (0, 30). On évalue f en chacun :
- (0, 0) : marge = 0 DH
- (60, 0) : marge = 240 DH
- (20, 40) : marge = 80 + 280 = 360 DH ← optimum
- (0, 30) : marge = 210 DH
🌟 La méthode du simplexe (Dantzig, 1947)
En 1947, le mathématicien américain George Dantzig, alors au Pentagone, invente la méthode du simplexe : un algorithme qui se déplace de sommet en sommet du polygone, choisissant toujours la direction qui améliore l'objectif.
Pour n variables et m contraintes, le simplexe trouve l'optimum en quelques itérations en pratique (même si la complexité théorique est exponentielle dans le pire cas). En 2026, on résout couramment des problèmes à millions de variables en quelques secondes.
🏭 Applications industrielles
📚 Le « problème du régime » (Stigler, 1945)
En 1945, l'économiste George Stigler (futur prix Nobel) pose le problème suivant : quel est le menu hebdomadaire le moins cher qui fournit tous les nutriments dont a besoin un adulte ?
Il définit 9 nutriments essentiels, étudie 77 aliments avec leurs prix et compositions, et résout à la main (3 mois de calcul). Coût annuel optimal : 39,93 $ en 1945. Quand le simplexe arrive en 1947, on refait le calcul en quelques heures, on trouve 39,69 .
🎓 Au programme BAC SM ?
La programmation linéaire n'est pas explicitement au programme du BAC SM, mais ses ingrédients y sont :
- Systèmes d'inéquations linéaires : étudiés en 1BAC SM
- Régions du plan : visualisation des contraintes
- Maximum/minimum d'une fonction linéaire : lien avec les extrema
- Matrices (concept Atlas) : contraintes sous forme Ax ≤ b
🚀 Aller plus loin
- Programmation linéaire en nombres entiers (PLNE) : les variables doivent être entières → NP-complet, beaucoup plus dur
- Programmation convexe : objectif convexe et contraintes convexes (toujours résoluble)
- Programmation non linéaire : optimisation générale (gradient descent, etc.)
- Recherche opérationnelle : la discipline qui englobe tout ça
🧠 Réflexion finale
La programmation linéaire est l'un des outils mathématiques les plus rentables jamais inventés. Selon une estimation, le simplexe et ses descendants génèrent chaque année plusieurs centaines de milliards de dollars d'économies mondiales, juste en optimisant des décisions logistiques.
Apprends à poser un problème de manière mathématique — avec un objectif et des contraintes claires. Cette compétence vaut de l'or, que tu deviennes ingénieur, économiste, data scientist ou entrepreneur.