University Sétif 1 FERHAT ABBAS Faculty of Sciences
Résultat de la recherche
1 résultat(s) recherche sur le mot-clé 'Programmation linéaire Méthode de Points Intérieurs Méthode barrière logarithmique Fonction majorante'
Ajouter le résultat dans votre panier Affiner la recherche Générer le flux rss de la recherche
Partager le résultat de cette recherche
Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire / Menniche, Linda
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 majoranteIndex. 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 75Cô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 majoranteIndex. 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 75Côte titre : DM/0122 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MD/0122 MD/0122 Mémoire Bibliothéque des sciences Français Disponible
Disponible