Optimisation linéaire (2D)

La programmation linéaire optimise une fonction objectif linéaire sous des contraintes d'égalité et d'inégalité linéaires. Statiquement, la région réalisable forme un polyèdre convexe. Le théorème fondamental montre que la solution optimale doit se situer à l'un des sommets, résolu par l'algorithme du Simplex.

En clair, vous jonglez avec des ressources limitées sous plusieurs règles à la fois, et chaque inégalité découpe une partie du plan. Là où toutes les règles se chevauchent se trouve la région réalisable, et chaque point à l'intérieur est un plan valide. Comme une fonction objectif linéaire s'améliore toujours dans une direction, la meilleure solution tombe sur un sommet où les contraintes se rencontrent. À retenir : pour optimiser, on ne teste jamais tous les points, seulement la poignée de sommets.

En 1945, l'économiste George Stigler a cherché le régime le moins cher couvrant tous les besoins nutritionnels, un problème linéaire à 77 aliments. Faute d'algorithme, il a fait une estimation astucieuse et obtenu environ $39.93 par an (prix de 1939). Quand la méthode du simplexe de Dantzig l'a résolu exactement en 1947, le vrai minimum était $39.69 — l'estimation à la main de Stigler ne s'écartait que d'environ 24 cents par an. L'économie aride est ainsi devenue l'un des cas fondateurs de la programmation linéaire.