Magazine Culture

Mathématique : l'algorithme de Karmarkar

Publié le 20 avril 2008 par Carlitablog666
Blog de carlitablog : Tendance et Rêverie, 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?


Retour à La Une de Logo Paperblog

A propos de l’auteur


Carlitablog666 102 partages Voir son profil
Voir son blog

l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte l'auteur n'a pas encore renseigné son compte

Magazine