RESOLUTION PAR DECOMPOSITION D’UN PROBLEME DE TRANSPORT SPECIAL

Authors

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

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

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

References

- 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).

Published

2003-12-01

How to Cite

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

Issue

Section

Articles