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é.
    la date de réponsejuin 1992
    langue originaleFrançais
    L'institution diplômante
    • Universite de Namur
    SuperviseurJean-Jacques STRODIOT (Promoteur)

    Contient cette citation

    '