Méthodes ellipsoïdales et projectives de résolution des problèmes linéaires (Khachiyan et Karmarkar).

Abstract

Dans cette thèse, nous avons fait une étude adaptative et comparative de trois méthodes qui permettent la résolution d'un programme linéaire à savoir : • La méthode de Dantzig (simplexe). • La méthode de Khachiyan (ellipsoïdale). • La méthode de Karmarkar (projective). La méthode du simplexe, en générale n'est pas polynomiale comme ont signalé Klee et Minty en fournissant un exemple de programme linéaire pour lequel la méthode du simplexe croit en exponentiel. Ceci a motivé des chercheurs pour l'établissement de méthodes polynomiales pour résoudre des programmes linéaires. Ainsi Khachiyan et Karmarkar ont fourni dans les années 80 des algorithmes théoriquement polynomiaux. Dans ce mémoire, nous implémentons ces méthodes et nous comparons leur efficacité sur des exemples concrets. La méthode du simplexe reste en pratique la plus utilisée, vu sa simplicité dans son exécution et la complexité de la mise en ouvre des méthodes ellipsoïdales et projectives. Mots clés : La programmation linéaire, algorithme polynomial, méthode du simplexe, Méthode des ellipsoïdes, transformation affine, transformation projective.