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
Editeur :	Setif:UFA
Année de publication :	2017
Importance :	1 vol (77 f .)
Format :	29 cm
Langues :	Français (fre) Langues originales : Français (fre)
Catégories :	Thèses & Mémoires:Mathématique
Mots-clés :	Programmation linéaire Méthode de Points Intérieurs Méthode barriè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 3 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 Convexité 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 résolution 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 lineaire . . . . . 26 2.2 Methode 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 théorique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Existence de la solution du probléme (DLr) . . . . . . . . . . . . . 54 3.2.2 Unicité 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 75
Côte titre :	DM/0122

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 . - [S.l.] : Setif:UFA, 2017 . - 1 vol (77 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)

Catégories :	Thèses & Mémoires:Mathématique
Mots-clés :	Programmation linéaire Méthode de Points Intérieurs Méthode barriè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 3 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 Convexité 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 résolution 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 lineaire . . . . . 26 2.2 Methode 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 théorique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Existence de la solution du probléme (DLr) . . . . . . . . . . . . . 54 3.2.2 Unicité 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 75
Côte titre :	DM/0122