Mémoires de Fin d’Etudes
Etablissement
Université de Sétif 1 - Ferhat Abbas
Affiliation
Département de Mathématique
Auteur
ANANE, Nassima
Directeur de thèse
Achache Mohamed (Professeur)
Co-directeur
Benterki Djamel (Professeur)
Filière
Mathématiques
Diplôme
Magister
Titre
Méthodes de points intérieurs pour la programmation linéaire basées sur les fonctions noyaux
Mots clés
Programmation linéaire, Méthode de points intérieurs, Algorithmes primal-dual de trajectoire centrale; Fonctions Noyaux; Complexité des Algorithmes, Résultats Numérique
Résumé
Le but de ce mémoire est de proposer une méthode de points intérieurs de trajectoire centrale de type primal-dual pour résoudre les problèmes de la programmation linéaire (PL). Cette méthode est basée sur une classe de direction de Newton et d’une nouvelle mesure de proximité introduits par une nouvelle fonction de Noyau. Contrairement aux fonctions de Noyaux proposées par beaucoup de chercheurs, notre fonction est d’une part paramètrisée et d’autre part elle possède une double barrière terme. On montre que l’algorithme correspondant admet une complexité polynomiale qui est de l’ordre O( log(n)log ( ))pour les algorithmes à grand pas et O(q2 log ( ))pour les algorithmes à petit pas où n est la taille de la matrice associée à (PL). Cette étude est suivie d’une implémentation numérique de ces algorithmes sur des problèmes de (PL). On constate que les résultats numériques donnés par le choix q= log n dans les algorithmes à grand pas sont les meilleurs
Date de soutenance
2012
Cote
TH844
Pagination
73P
Format
CD
Statut
Soutenue