University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Linda Menniche |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheEtude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire / Linda Menniche
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 : Linda Menniche, Auteur ; D BENTERKI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (78 f.) Format : 29 cm Catégories : Mathématique Mots-clés : Programmation linéaire,
Méthode de Points Intérieurs,
Méthode
barrière logarithmique,
Fonction majorante.Index. décimale : 510 Mathématique Résumé : 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 : Table des matières
Introduction 3
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affines . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexité et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barri`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation math´ematique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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´eaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 M´ethodes 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 problèmes de programmation linéaire . . . . . 26
2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caract´eristiques de l’algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 M´ethodes affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affine 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´esultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barri`ere 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`eme (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`eme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de d´eplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs de bt . . . . . . . . . . . . . . . . . . . 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´eriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples `a dimension fixe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple `a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie 75Côte titre : DM/0122 En ligne : https://drive.google.com/file/d/11YNbdvBMZXfjDwFmTZBiBGCOU5vlXVmh/view?usp=shari [...] Format de la ressource électronique : Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire [texte imprimé] / Linda Menniche, Auteur ; D BENTERKI, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (78 f.) ; 29 cm.
Catégories : Mathématique Mots-clés : Programmation linéaire,
Méthode de Points Intérieurs,
Méthode
barrière logarithmique,
Fonction majorante.Index. décimale : 510 Mathématique Résumé : 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 : Table des matières
Introduction 3
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affines . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexité et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barri`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation math´ematique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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´eaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 M´ethodes 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 problèmes de programmation linéaire . . . . . 26
2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caract´eristiques de l’algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 M´ethodes affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affine 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´esultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barri`ere 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`eme (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`eme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de d´eplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs de bt . . . . . . . . . . . . . . . . . . . 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´eriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples `a dimension fixe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple `a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie 75Côte titre : DM/0122 En ligne : https://drive.google.com/file/d/11YNbdvBMZXfjDwFmTZBiBGCOU5vlXVmh/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0122 DM/0122 Mémoire Bibliothéque des sciences Français Disponible
Disponible
