Méthodes de points intérieurs de type primal-dual pour la programmation linéaire basées sur des nouvelles directions. Etude numérique et comparative / Sebaoune ,Basma  

Public ISBD Titre : Méthodes de points intérieurs de type primal-dual pour la programmation linéaire basées sur des nouvelles directions. Etude numérique et comparative Type de document : texte imprimé Auteurs : Sebaoune ,Basma, Auteur ; Mohamed Achache, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (49 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 point intérieur Algorithme primal- dual de type trajectoire centrale Index. décimale : 510 Mathématique Résumé : Dans ce mémoire, nous présentons une méthode de point intérieur de type primal-dual de trajectoire centrale avec un pas de Newton complet pour résoudre les problèmes de la programmation linéaire. La spéciÂ…cité de notre méthode est de calculer le pas de Newton en utilisant un système modi…é qui contient l’équation de centralité. Pour ce but, nous considérons trois fonctions connues dans la littérature appliquées à l’équation de centra- lité et donc de nouvelles directions de Newton sont déterminées. La convergence de ces algorithmes est achevée. Finalement, des expériences numériques de ces trois algorithmes à pas court sur des programmes linéaires connus dans la littérature sont présentées suivi par une étude comparative entre les résultats numériques obtenus a travers ces trois fonctions. Finalement, on terminera le mémoire par une conclusion et des perspectives. Note de contenu : Sommaire Programmation linéaire et méthodes de résolution 11 1.1 Théorie générale de la programmation linéaire . . . . . . . . . . . . . . . 11 1.2 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Méthodes de résolution dÂ’un programme linéaire . . . . . . . . . . . . . . 14 1.3.1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.2 Méthodes modernes de points intérieures . . . . . . . . . . . . . . 15 1.3.3 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . 16 2 Méthodes primales duales pour la programmation linéaire 21 2.1 Méthodes de trajectoire centrale classiques basées sur lÂ’approche barrière logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Méthodes barrières logarithmiques de type primal dual de TC pour PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.3 Concept de proximité ou de centralisation . . . . . . . . . . . . . 23 2.1.4 Directions de Newton classiques . . . . . . . . . . . . . . . . . . . 24 3 Méthodes nouvelles primales-duales pour la programmation linéaire 25 3.1 Principe de ces méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Nouvelle classe de directions de Newton . . . . . . . . . . . . . . . . . . . 26 3.3 Directions de Newton pour le choix de '(t) = t: . . . . . . . . . . . . . . 28 2 3.3.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 28 3.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 Directions de Newton pour le choix de '(t) = pt . . . . . . . . . . . . . 29 3.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5 Directions de Newton pour le choix de '(t) = pt 2(1+pt) . . . . . . . . . . . 31 3.5.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.6 Complexité polynomiale de ces trois algorithmes . . . . . . . . . . . . . . 33 4 Expérimentation numérique et comparaison 35 4.0.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.0.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 36 4.0.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.1.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Comparaison numérique entre les trois algorithmes . . . . . . . . . . . . 44 4.3 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Côte titre : MAM/0290 En ligne : https://drive.google.com/file/d/1ajKp3JhKjRkiTsuVvDcAyfkEMbV27t5Y/view?usp=share [...] Format de la ressource électronique : PDF Méthodes de points intérieurs de type primal-dual pour la programmation linéaire basées sur des nouvelles directions. Etude numérique et comparative [texte imprimé] / Sebaoune ,Basma, Auteur ; Mohamed Achache, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (49 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 point intérieur Algorithme primal- dual de type trajectoire centrale Index. décimale : 510 Mathématique Résumé : Dans ce mémoire, nous présentons une méthode de point intérieur de type primal-dual de trajectoire centrale avec un pas de Newton complet pour résoudre les problèmes de la programmation linéaire. La spéciÂ…cité de notre méthode est de calculer le pas de Newton en utilisant un système modi…é qui contient l’équation de centralité. Pour ce but, nous considérons trois fonctions connues dans la littérature appliquées à l’équation de centra- lité et donc de nouvelles directions de Newton sont déterminées. La convergence de ces algorithmes est achevée. Finalement, des expériences numériques de ces trois algorithmes à pas court sur des programmes linéaires connus dans la littérature sont présentées suivi par une étude comparative entre les résultats numériques obtenus a travers ces trois fonctions. Finalement, on terminera le mémoire par une conclusion et des perspectives. Note de contenu : Sommaire Programmation linéaire et méthodes de résolution 11 1.1 Théorie générale de la programmation linéaire . . . . . . . . . . . . . . . 11 1.2 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Méthodes de résolution dÂ’un programme linéaire . . . . . . . . . . . . . . 14 1.3.1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.2 Méthodes modernes de points intérieures . . . . . . . . . . . . . . 15 1.3.3 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . 16 2 Méthodes primales duales pour la programmation linéaire 21 2.1 Méthodes de trajectoire centrale classiques basées sur lÂ’approche barrière logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Méthodes barrières logarithmiques de type primal dual de TC pour PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.3 Concept de proximité ou de centralisation . . . . . . . . . . . . . 23 2.1.4 Directions de Newton classiques . . . . . . . . . . . . . . . . . . . 24 3 Méthodes nouvelles primales-duales pour la programmation linéaire 25 3.1 Principe de ces méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Nouvelle classe de directions de Newton . . . . . . . . . . . . . . . . . . . 26 3.3 Directions de Newton pour le choix de '(t) = t: . . . . . . . . . . . . . . 28 2 3.3.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 28 3.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 Directions de Newton pour le choix de '(t) = pt . . . . . . . . . . . . . 29 3.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5 Directions de Newton pour le choix de '(t) = pt 2(1+pt) . . . . . . . . . . . 31 3.5.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.6 Complexité polynomiale de ces trois algorithmes . . . . . . . . . . . . . . 33 4 Expérimentation numérique et comparaison 35 4.0.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.0.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 36 4.0.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.1.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Comparaison numérique entre les trois algorithmes . . . . . . . . . . . . 44 4.3 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Côte titre : MAM/0290 En ligne : https://drive.google.com/file/d/1ajKp3JhKjRkiTsuVvDcAyfkEMbV27t5Y/view?usp=share [...] Format de la ressource électronique : PDF

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
MAM/0290	MAM/0290	Mémoire	Bibliothéque des sciences	Français	Disponible Disponible

---

1 (1 - 1 / 1)