Une implémentation de l'algorithme de Karmarkar

  • Alain Van Kerm

Thèse de l'étudiant: Master typesMaster en sciences informatiques

Résumé

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éponse1989
langue originaleFrançais
L'institution diplômante
  • Universite de Namur
SuperviseurJean FICHEFET (Promoteur)

Contient cette citation

'