Etude comparative de deux algorithmes pour le probleme de transport

Voir Plus Voir Moins

Afficher le Résumé

Le sujet du présent mémoire consiste en une étude comparative de deux algorithmes :l’algorithme primal du simplexe (forme révisée) et l’algorithme primal-dual, appliqués aule problème de transport.Dans le chapitre 1, nous donnons une introduction des concepts nécessaires en programmationlinéaire (P.L). Ainsi nous exposons l’algorithme le plus utilisé pour résoudre unproblème de P.L : l’algorithme primal simplexe (forme révisée).Dans le chapitre 2, nous allons discuter un des aspects importants de la P.L, la notion dedualité. La connaissance des propriétés de la dualité permet d’illustrer de manière plussaisissante la démarche des divers algorithmes comme l’algorithme dual et l’algorithmeprimal-dual qui sont bien exposés dans les sections de ce chapitre.Nous allons traiter un cas spécial des problèmes de P.L dans les réseaux de transport. Ils’agit du problème de flot maximum, et l’algorithme utilisé pour résoudre ce problèmeest celui de Ford-Fulkerson. Dans le chapitre 4, nous allons exposer le problème de transport et les deux algorithmesutilisés habituellement pour résoudre ce problème : l’algorithme primal du simplexeadapté aux réseaux (Network simplex) et l’algorithme primal-dual. Dans le chapitre 5, l’expérimentation menée semble indiquer que l’algorithme primal-dualest plus rapide que l’algorithme primal du simplexe.5