Programmation linéaire
Chaque aliment a un prix et des apports ; chaque nutriment a un minimum à atteindre. On cherche les quantités qui minimisent la dépense en respectant toutes ces bornes. L'économiste George Stigler a posé ce problème du régime en 1945 et l'a résolu à la main, par tâtonnements ; les méthodes exactes ont montré ensuite qu'il était passé à quelques centimes de l'optimum.
Chaque aliment a un prix et des apports ; chaque nutriment a un minimum à atteindre. On cherche les quantités qui minimisent la dépense en respectant toutes ces bornes. L'économiste George Stigler a posé ce problème du régime en 1945 et l'a résolu à la main, par tâtonnements ; les méthodes exactes ont montré ensuite qu'il était passé à quelques centimes de l'optimum.
Les contraintes découpent un polyèdre convexe. L'objectif étant linéaire, on pousse ses lignes de niveau dans une direction jusqu'à quitter le domaine : le dernier point touché est forcément un coin.
Klee et Minty ont construit en 1972 des polyèdres déformés où le simplexe visite tous les sommets un par un. Le pire cas est catastrophique, et pourtant on ne le rencontre jamais : sur des données réelles, la méthode s'arrête après un nombre d'itérations de l'ordre du nombre de contraintes.