University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Fatima Zohra Batoul Bouchareb |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Application De Quelques Méthodes Métaheuristiques Au Problème De Transport Type de document : document électronique Auteurs : Insaf Bouhafs, Auteur ; Fatima Zohra Batoul Bouchareb, Auteur ; Rachid Zitouni, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2025 Importance : 1 vol (41 f.) Format : 29 cm Note générale : Langues : Français (fre) Mots-clés : Programmation Linéaire
Problème De Transport
Algorithme De Transport
Métaheuristiques
Algorithmes GénétiquesRésumé : Afin d'améliorer la résolution du problème de transport classique (à deux indices), nous avons proposé
dans ce mémoire des adaptations de quelques métaheuristiques telles que les algorithmes génétiques
(AG), l'optimisation par essaim de particules (PSO), ainsi qu'une méthode hybride PSO-AG pour
résoudre ce problème. Ces méthodes offrent des mécanismes de recherche flexibles et adaptatifs,
capables d'explorer de vastes espaces de solutions et d'échapper aux optima locaux, offrant ainsi des
solutions quasi optimales dans des temps de calcul raisonnables. Pour tester l'efficacité et les
performances de chacun de ces méthodes approchées, nous avons effectué une comparaison numérique
entre eux, d'une part, et avec la méthode exacte appelée ‘algorithme de transport ‘, d'autre part. Nos
différentes expérimentations numériques montrent que les solutions fournies par ces algorithmes sont
généralement proches des solutions optimales obtenues par la méthode exacte. Nous pouvons
également noter que ces méthodes sont faciles à mettre en oeuvre et efficaces pour résoudre ce type de
problème, notamment dans le cas de problèmes de grande taille.Note de contenu : Table des matières
Introduction 2
1 Généralités 5
1.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Formulations des problèmes de programmation linéaire . . . . 5
1.2.1 Forme générale . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Forme standard . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Forme canonique . . . . . . . . . . . . . . . . . . . . . 6
1.3 Quelques définitions . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Notion de dualité . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Résolution d’un programme linéaire . . . . . . . . . . . . . . . 8
1.5.1 Méthode graphique : . . . . . . . . . . . . . . . . . . . 8
1.5.2 Méthode de simplexe : . . . . . . . . . . . . . . . . . . 9
1.5.3 Méthode de points intérieurs . . . . . . . . . . . . . . . 9
2 Problème de transport à deux indices 10
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Position du problème . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Interprétation économique . . . . . . . . . . . . . . . . 11
2.2.2 Formulation mathématique . . . . . . . . . . . . . . . . 11
2.3 Conditions de faisabilité et d’optimalité . . . . . . . . . . . . . 12
2.4 Méthodes de résolution d’un problème de transport . . . . . . 13
2.4.1 Simplexe : . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.2 Algorithme de transport : . . . . . . . . . . . . . . . . 14
2.5 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Quelques métaheuristiques pour résoudre le PT2 19
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Fonctionnement des GA . . . . . . . . . . . . . . . . . 22
3.3 Particle Swarm Optimization (PSO) . . . . . . . . . . . . . . 23
3.3.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.2 Principes de base de PSO . . . . . . . . . . . . . . . . 24
3.4 Application des métaheuristiques pour résoudre le problème
de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.1 Algorithme génétique pour PT2 . . . . . . . . . . . . . 27
3.4.2 Algorithme PSO pour PT2 . . . . . . . . . . . . . . . . 29
3.4.3 Algorithme PSO-GA pour PT2 . . . . . . . . . . . . . 31
3.5 Implémentation numérique . . . . . . . . . . . . . . . . . . . . 33
3.5.1 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . 33
3.5.2 Commentaires . . . . . . . . . . . . . . . . . . . . . . . 39
Conclusion 40
Bibliographie 41Côte titre : MAM/0831 Application De Quelques Méthodes Métaheuristiques Au Problème De Transport [document électronique] / Insaf Bouhafs, Auteur ; Fatima Zohra Batoul Bouchareb, Auteur ; Rachid Zitouni, Directeur de thèse . - [S.l.] : Sétif:UFS, 2025 . - 1 vol (41 f.) ; 29 cm.
Langues : Français (fre)
Mots-clés : Programmation Linéaire
Problème De Transport
Algorithme De Transport
Métaheuristiques
Algorithmes GénétiquesRésumé : Afin d'améliorer la résolution du problème de transport classique (à deux indices), nous avons proposé
dans ce mémoire des adaptations de quelques métaheuristiques telles que les algorithmes génétiques
(AG), l'optimisation par essaim de particules (PSO), ainsi qu'une méthode hybride PSO-AG pour
résoudre ce problème. Ces méthodes offrent des mécanismes de recherche flexibles et adaptatifs,
capables d'explorer de vastes espaces de solutions et d'échapper aux optima locaux, offrant ainsi des
solutions quasi optimales dans des temps de calcul raisonnables. Pour tester l'efficacité et les
performances de chacun de ces méthodes approchées, nous avons effectué une comparaison numérique
entre eux, d'une part, et avec la méthode exacte appelée ‘algorithme de transport ‘, d'autre part. Nos
différentes expérimentations numériques montrent que les solutions fournies par ces algorithmes sont
généralement proches des solutions optimales obtenues par la méthode exacte. Nous pouvons
également noter que ces méthodes sont faciles à mettre en oeuvre et efficaces pour résoudre ce type de
problème, notamment dans le cas de problèmes de grande taille.Note de contenu : Table des matières
Introduction 2
1 Généralités 5
1.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Formulations des problèmes de programmation linéaire . . . . 5
1.2.1 Forme générale . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Forme standard . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Forme canonique . . . . . . . . . . . . . . . . . . . . . 6
1.3 Quelques définitions . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Notion de dualité . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Résolution d’un programme linéaire . . . . . . . . . . . . . . . 8
1.5.1 Méthode graphique : . . . . . . . . . . . . . . . . . . . 8
1.5.2 Méthode de simplexe : . . . . . . . . . . . . . . . . . . 9
1.5.3 Méthode de points intérieurs . . . . . . . . . . . . . . . 9
2 Problème de transport à deux indices 10
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Position du problème . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Interprétation économique . . . . . . . . . . . . . . . . 11
2.2.2 Formulation mathématique . . . . . . . . . . . . . . . . 11
2.3 Conditions de faisabilité et d’optimalité . . . . . . . . . . . . . 12
2.4 Méthodes de résolution d’un problème de transport . . . . . . 13
2.4.1 Simplexe : . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.2 Algorithme de transport : . . . . . . . . . . . . . . . . 14
2.5 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Quelques métaheuristiques pour résoudre le PT2 19
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Fonctionnement des GA . . . . . . . . . . . . . . . . . 22
3.3 Particle Swarm Optimization (PSO) . . . . . . . . . . . . . . 23
3.3.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.2 Principes de base de PSO . . . . . . . . . . . . . . . . 24
3.4 Application des métaheuristiques pour résoudre le problème
de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.1 Algorithme génétique pour PT2 . . . . . . . . . . . . . 27
3.4.2 Algorithme PSO pour PT2 . . . . . . . . . . . . . . . . 29
3.4.3 Algorithme PSO-GA pour PT2 . . . . . . . . . . . . . 31
3.5 Implémentation numérique . . . . . . . . . . . . . . . . . . . . 33
3.5.1 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . 33
3.5.2 Commentaires . . . . . . . . . . . . . . . . . . . . . . . 39
Conclusion 40
Bibliographie 41Côte titre : MAM/0831 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0831 MAM/0831 Mémoire Bibliothèque des sciences Français Disponible
Disponible
