University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Menniche, Linda |
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 / 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 ; 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 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
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 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
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 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MD/122 MD/122 Mémoire Bibliothéque des sciences Français Disponible
Disponible
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
