Analyse de la complexité polynomiale de deux méthodes de points intérieurs basées sur la trajectoire centrale, en programmation linéaire

  • Françoise LESEULTRE

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

Résumé

L'objet du mémoire est d'étudier la complexité de deux méthodes de points intérieurs en programmation linéaire. Ces méthodes, dérivées de l'algorithme de Karmarkar, sont basées sur la trajectoire centrale. Cette courbe, le long de laquelle le coût diminue est l'ensemble des minimums de différentes fonctions auxiliaires basées sur la fonction barrière logarithmique : la fonction de pénalité intérieure et la fonction potentielle. Des algorithmes polynomiaux sont obtenus en suivant la courbe de manière approximative selon un critère de proximité.
Date de réussitejuin 1992
langueFrançais
Institution diplomante
  • Université de Namur
SuperviseurJean-Jacques Strodiot (Promoteur)

Citer ceci

Analyse de la complexité polynomiale de deux méthodes de points intérieurs basées sur la trajectoire centrale, en programmation linéaire
LESEULTRE, F. (Auteur). juin 1992

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