Titre :	Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire
Type de document :	texte imprimé
Auteurs :	Menniche, Linda, Auteur ; Benterki,DJ, Directeur de thèse
Editeur :	Setif:UFA
Année de publication :	2017
Importance :	1 vol (78 f.)
Format :	29cm
Langues :	Français (fre)
Catégories :	Thèses & Mémoires:Mathématique
Mots-clés :	Programmation linéaire Méthode de Points Intérieurs Méthodebarrière logarithmique Fonction majorante
Index. décimale :	519 Mathématiques appliquées, probabilités (statistiques mathématiques)
Résumé :	Ce travail concerne l'étude théorique, algorithmique et numérique d'une méthode barrière logarithmique pour résoudre un problème de programmation linéaire (PL). Nous mettons l'accent sur le calcul de la direction moyennant l'approche de Newton, et le calcul du pas de déplacement en utilisant de nouvelles fonctions majorantes dans le but de réduire le coût de calcul. Des résultats théoriques sont présentés donnant lieu à l'existence et l'unicité de la solution optimale du problème approché de (PL) ainsi que sa convergence vers celle de (PL). Ce travail est consolidé par des tests numériques réalisés sur l'algorithme obtenu.
Note de contenu :	Sommaire Introduction 1 Préliminaires et notions fondamentales 7 1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Ensembles et fonctions affnes . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Notions de convexité. . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Convexite et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.4 Fonction barriére . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.5 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . 13 1.2 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3 Formes usuelles d'un programme linéaire . . . . . . . . . . . . . . . . . . . 19 1.3.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.4 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 20 2 Méthodes de resolution d'un programme linéaire 24 2.1 Domaines d'applications de la programmation linéaire . . . . . . . . . . . . 24 2.1.1 Exemples concrets de problemes de programmation linéaire . . . . . 26 2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.1 Caractéristiques de l'algorithme du simplexe . . . . . . . . . . . . . 34 2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.1 Méthodes affnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.2 Algorithme de la méthode affne primale . . . . . . . . . . . . . . . 39 2.3.3 Méthode de réduction du potentiel . . . . . . . . . . . . . . . . . . 42 2.3.4 Méthodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . . 43 2.3.5 Méthodes de trajectoire centrale primales-duales . . . . . . . . . . . 45 2.4 Résultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3 Méthode barriére logarithmique via les fonctions majorantes 52 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 Aspect theorique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Existence de la solution du probléme (DLr) . . . . . . . . . . . . . 54 3.2.2 Unicite de la solution du probléme (DLr) . . . . . . . . . . . . . . . 55 3.2.3 Convergence de (DLr) vers (DL) lorsque r tend vers zéro . . . . . . 56 3.3 Aspect numérique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . 57 3.3.1 Calcul du pas de déplacement tk . . . . . . . . . . . . . . . . . . . . 59 3.3.2 Calcul des différentes valeurs debt . . . . . . . . . . . . . . . . . . . 61 3.4 Fonctions majorantes de t . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.4.1 Premiére fonction majorante . . . . . . . . . . . . . . . . . . . . . . 63 3.4.2 Seconde fonction majorante . . . . . . . . . . . . . . . . . . . . . . 64 3.4.3 Troisiéme fonction majorante . . . . . . . . . . . . . . . . . . . . . 65 3.5 Tests numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.5.1 Exemples a dimension xe . . . . . . . . . . . . . . . . . . . . . . . 69 3.5.2 Exemple a dimension variable . . . . . . . . . . . . . . . . . . . . . 72 Conclusion 73 Bibliographie
Côte titre :	MD/122

Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire [texte imprimé] / Menniche, Linda, Auteur ; Benterki,DJ, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (78 f.) ; 29cm.
Langues : Français (fre)

Catégories :	Thèses & Mémoires:Mathématique
Mots-clés :	Programmation linéaire Méthode de Points Intérieurs Méthodebarrière logarithmique Fonction majorante
Index. décimale :	519 Mathématiques appliquées, probabilités (statistiques mathématiques)
Résumé :	Ce travail concerne l'étude théorique, algorithmique et numérique d'une méthode barrière logarithmique pour résoudre un problème de programmation linéaire (PL). Nous mettons l'accent sur le calcul de la direction moyennant l'approche de Newton, et le calcul du pas de déplacement en utilisant de nouvelles fonctions majorantes dans le but de réduire le coût de calcul. Des résultats théoriques sont présentés donnant lieu à l'existence et l'unicité de la solution optimale du problème approché de (PL) ainsi que sa convergence vers celle de (PL). Ce travail est consolidé par des tests numériques réalisés sur l'algorithme obtenu.
Note de contenu :	Sommaire Introduction 1 Préliminaires et notions fondamentales 7 1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Ensembles et fonctions affnes . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Notions de convexité. . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Convexite et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.4 Fonction barriére . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.5 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . 13 1.2 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3 Formes usuelles d'un programme linéaire . . . . . . . . . . . . . . . . . . . 19 1.3.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.4 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 20 2 Méthodes de resolution d'un programme linéaire 24 2.1 Domaines d'applications de la programmation linéaire . . . . . . . . . . . . 24 2.1.1 Exemples concrets de problemes de programmation linéaire . . . . . 26 2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.1 Caractéristiques de l'algorithme du simplexe . . . . . . . . . . . . . 34 2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.1 Méthodes affnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.2 Algorithme de la méthode affne primale . . . . . . . . . . . . . . . 39 2.3.3 Méthode de réduction du potentiel . . . . . . . . . . . . . . . . . . 42 2.3.4 Méthodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . . 43 2.3.5 Méthodes de trajectoire centrale primales-duales . . . . . . . . . . . 45 2.4 Résultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3 Méthode barriére logarithmique via les fonctions majorantes 52 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 Aspect theorique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Existence de la solution du probléme (DLr) . . . . . . . . . . . . . 54 3.2.2 Unicite de la solution du probléme (DLr) . . . . . . . . . . . . . . . 55 3.2.3 Convergence de (DLr) vers (DL) lorsque r tend vers zéro . . . . . . 56 3.3 Aspect numérique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . 57 3.3.1 Calcul du pas de déplacement tk . . . . . . . . . . . . . . . . . . . . 59 3.3.2 Calcul des différentes valeurs debt . . . . . . . . . . . . . . . . . . . 61 3.4 Fonctions majorantes de t . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.4.1 Premiére fonction majorante . . . . . . . . . . . . . . . . . . . . . . 63 3.4.2 Seconde fonction majorante . . . . . . . . . . . . . . . . . . . . . . 64 3.4.3 Troisiéme fonction majorante . . . . . . . . . . . . . . . . . . . . . 65 3.5 Tests numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.5.1 Exemples a dimension xe . . . . . . . . . . . . . . . . . . . . . . . 69 3.5.2 Exemple a dimension variable . . . . . . . . . . . . . . . . . . . . . 72 Conclusion 73 Bibliographie
Côte titre :	MD/122