RESOLUTION PAR DECOMPOSITION D’UN PROBLEME DE TRANSPORT SPECIAL
Mots-clés :
Décomposition lagrangienne, flot entier, séparation et évaluationRé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
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).
