Mathématique : l'algorithme de Karmarkar

Pour faire plaisir à une amie qui trouvait mon énigme assez légère.

Elle voulait du plus lourd alors en voilà.

D’un côté rien d inutile puisque c’est pour notre savoir.

L'algorithme de Karmakar.

Il s'agit, pour simplifier, de maximiser la valeur d'une fonction du type A1X1 + A2X2 + ... + ANXN sur un polyèdre de l'espace à N dimensions (ce polyèdre intervient dans des milliers de problèmes d'optimisation : gestion d'une flotte d'avions (pour minimiser les coûts et éviter que tous les avions soient dans certains aéroports et les pilotes dans d'autres), alimentation animale (pour obtenir le maximum de viande avec un coût d'alimentation minimum, en tenant compte des cours variables des différents produits), organisation de tâches complexes comme dans le  bâtiment ou l'industrie (pour minimiser le temps d'inactivité de machines coûteuses), établissement de tableaux de service, etc...

Les méthodes classiques depuis 1945 reposaient sur l'algorithme du simplexe (Dantzig), où les solutions provisoires sont améliorées en sautant d'un sommet à l'autre d'un polyèdre, le maximum étant forcément atteint en un sommet.

L'algorithme de Karmarkar, lui, passe par l'intérieur d'un polyèdre, et aboutit en temps polynomial.

Y a encore du monde?