RESOLUTION PAR DECOMPOSITION D’UN PROBLEME DE TRANSPORT SPECIAL

Auteurs-es

  • S HADDADI Université Badji Mokhtar BP 12, 23000 Annaba
  • A BENCHETTAH Université Badji Mokhtar BP 12, 23000 Annaba

Mots-clés :

Décomposition lagrangienne, flot entier, séparation et évaluation

Résumé

Dans cet article, on étudie un problème de transport spécial qu’on appelle problème de transport à destinations groupées. On montre qu’il est NP-dur. On propose ensuite une décomposition lagrangienne d’une partie des contraintes qui permettra de le réduire à un problème équivalent de flot entier à arcs homologues. On présente alors une méthode par séparation et évaluation pour résoudre ce dernier. La procédure d’évaluation est fondée sur la résolution du dual lagrangien par une méthode de sous-gradients. La fonction lagrangienne considérée est obtenue en relaxant les contraintes d’arcs homologues. Des résultats numériques obtenus sur plusieurs problèmes engendrés aléatoirement sont présentés.

Téléchargements

Les données relatives au téléchargement ne sont pas encore disponibles.

Bibliographies de l'auteur-e

S HADDADI, Université Badji Mokhtar BP 12, 23000 Annaba

Laboratoire de Mathématiques Appliquées

A BENCHETTAH, Université Badji Mokhtar BP 12, 23000 Annaba

Laboratoire de Mathématiques Appliquées

Références

- Ahuja R.K., Magnanti T.L. and Orlin J.B., "Network flows", in: G.L. Nemhauser, A.H.G. Rinnooy Kan et M.J. Todd (eds.): Handbooks in Operations Research and Management Science, Vol.1, "Optimization", North-Holland, Amsterdam, (1989), pp.211-369.

- Garey M.R. and Johnson D.S., "Computers and intractability: a guide to the theory of NP-completeness", W.H. Freeman and Co., New York, (1979).

- Guignard M., and Kim S., "Lagrangian decomposition: a model yielding stronger lagrangian bounds", Mathematical Programming, 39, (1987), pp.215-228.

- Held M., Wolfe P. and Crowder H.D., "Validation of subgradient optimisation", Mathematical Programming, 6, (1974), pp.62-88.

- Korte B. and Vygen J., "Combinatorial optimization: theory and algorithms", Springer-Verlag, Berlin, (2000).

- Legendre J.P. et Minoux M., "Une application de la notion de dualité en programmation en nombres entiers: sélection et affectation optimales d’une flotte d’avions", Rairo, 11, (1977), pp.201-222.

- Nicolas P., "Planification et allocation de ressources avec contraintes temporelles", thèse de doctorat de l’université Blaise Pascal, Clermont-Ferrand, France, (1991).

Téléchargements

Publié-e

2003-12-01

Comment citer

HADDADI, S., & BENCHETTAH, A. (2003). RESOLUTION PAR DECOMPOSITION D’UN PROBLEME DE TRANSPORT SPECIAL. Sciences & Technologie. A, Sciences Exactes, (20), 39–44. Consulté à l’adresse https://revue.umc.edu.dz/a/article/view/1048

Numéro

Rubrique

Articles