L'algorithme de Karmarkar est un algorithme de résolution de problèmes de programmation linéaire simple. Son principal attrait provient de ses performances théoriques meilleures que celles du célèbre algorithme du simplexe mis au point par Dantzig. Nous avons implémenté l'algorithme de Karmarkar en lui apportant quelques modifications permettant une réduction du nombre d'itérations et l'obtention de la solution duale. Nous nous sommes soucié des performances de place pour le stockage des données et de temps d'exécution. Cela nous a amené à utiliser des matrices creuses. Nous avons également réalisé un outil permettant un encodage simple et clair pour les problèmes de "faible" taille de manière à offrir un cadre de travail relativement agréable.
la date de réponse | 1989 |
---|
langue originale | Français |
---|
L'institution diplômante | |
---|
Superviseur | Jean FICHEFET (Promoteur) |
---|
Une implémentation de l'algorithme de Karmarkar
Van Kerm, A. (Auteur). 1989
Student thesis: Master types › Master en sciences informatiques