Recherche opérationnelle

0. Introduction.

Ce cours a étéenseignéjusqu’en 2002, en année de licence, à la MIAGE de NANCY.

L’objectif principal de ce cours est d’acquérir une connaissance approfondie de cer­taines techniques considérées à l’heure acutelle comme des méthodes de base en Recherche Opérationnelle. Celles-ci se retrouvent en effet, sous des formes plus complexes, dans les analyses professionnelles de faisabilitéou d’optimisation.

Les exercices qui accompagnent ce cours permettent aux étudiants de modéliser des problèmes simples en utilisant les techniques de la Recherche Opérationnelle. Ces exercies ne tiennent évidemment pas compte de tous les paramètres d’une véritable analyse professionnelle. Ils sont simplifiés volontairement et sont choisis suivant l’orientation des étudiants, en majoritédans le domaine de la gestion; mais les techniques utilisées s’appliquent également à la modélisation en ingéniérie et en sciences.

Certaines méthodes de la Recherche Opérationnelle se démontrent - au niveau mathématique - assez facilement. L’algorithme du simplexe, par exemple, repose sur des arguments élémentaires de l’algèbre linéaire.

D’autres méthodes présentées dans ce cours, par exemple celles de la programmation dynamique, sont des cas particuliers de développements analytiques et stochastiques plus avancés, qui, à un niveau général, ne sont plus à la portée d’un étudiant en licence (même en mathématiques). Une justification élémentaire de certains cas par­ticuliers est cependant faisable et donne lieu à quelques applications intéressantes.

D’autres méthodes encore sont purement heuristiques, comme la méthode par sépara­tion et évaluation (branch and bound) en programmation linéaire à valeurs entières.

Il est peut-être surprenant de constater que la presque totalitédes problèmes d’optimi-sations énoncés dans ce cours (hormis ceux relevant de la programmation dynamique) peuvent être résolus à l’aide d’un algorithme de programmation linéaire. Cependant, des solutions spécifiques, par exemple au problème du flot maximal ou du flot de coût total minimal dans un réseau, sont proposées. Elles sont souvent développées à partir d’un programme linéaire adaptéau problème spécifique et font partie des méthodes standards dans la littérature récente. Ainsi la question du flot de coût total minimal permet de présenter quelques éléments du simplexe des réseaux.

Le cours est diviséen cinq chapitres.

Les deux premiers traitent de la programmation linéaire. Ils contiennent :

- une introduction à la technique du simplexe, une méthode standard pour la

résolution d’un programme linéaire;

- la dualité;

– 2 –

- la méthode des coupes et la méthode par séparation et évaluation pour la résolution de programmes linéaires qui imposent à certaines variables d’être à valeurs entières ou même binaires;

- l’analyse post-optimale, qui détermine la variation de la solution en fonction d’un changement des valeurs des paramètres du programme.

Le troisième chapitre traite de la théorie des jeux à deux personnes et à somme zéro et s’appuie fortement sur les deux chapitres précédents.

Au quatrième chapitre nous exposons deux problèmes d’optimisation de flots dans des réseaux: le flot maximal (avec sa coupe minimale) et le flot à coût total minimal.

Le dernier chapitre est une introduction aux méthodes élémentaires de la program­mation dyamique. Ce domaine est très vaste et de nombreux aspects ne sont pas étudiés, en particulier l’aspect stochastique en cas d’incertitudes sur les paramètres.

Les algorithmes d’optimisation liés aux graphes (chemin de longueur maximale ou minimale par exemple) ne figurent pas dans ce cours parce qu’ils sont traités dans les cours d’outils conceptuels et d’algorithmique également enseignés à la Miage de Nancy.

Les versions initiales de ce cours, ont étélargement inspirées par le traité(non publié) intitulé”Recherche Opérationnelle” de Francis Conrad, Professeur à l’Universi^téHenri PoincaréNancy 1. Nous le remercions d’avoir mis ce texte à notre dispo‑

sition. Nous n’avons pas connaissance d’un livre ou d’une monographie dont la présentation correspond à ses notes, mais nous avons pu constater que les livres récents en Recherche Opérationnelle, abordent les sujets traités dans ce cours. Une liste, certainement incomplète, d’ouvrages récents est donnée ci-dessous.

Bibliographie :

C.    Guéret, C. Prins, M. Sevaux, Programmation linéaire, Eyrolles, 2000.

R. Favre, B. Lemaire, C. Picouleau, Précis de recherche opérationnelle, 5ème éd., Dunod, 2000.

Y. Nobert, R. Ouellet, R. Parent, La recherche opérationnelle, Gaëtan Morin, 1995.

J. F. Phélizon, Méthodes et modèles de la recherche opérationnelle, Economica, 1998.

J. F. Maurras, Programmation linéaire, compléxité, Springer, 2002.

D.    Alevra, M. Padberg, Linear optimization and extensions : problems and solutions, Springer, 2001.

V.K. Balakrishnan, Network optimization, Chapman and Hall, 1995. G.B. Dantzig, M.N. Thapa, Linear programming, Springer, 1997.

H.A. Eiselt, C.L. Sandblom, Integer programming and network models, Springer 2000.

B. Korte, J. Vygen, Combinatorial optimization, 2nd ed., Springer, 2002.

– 3 –

G. Sierksma, Linear and integer programming, Marcel Dekker, 2001.

R.J. Vanderbei, Linear programming foundations and extensions, Kluwer, 2001.

W. Domschke, A. Drexl, Einführung in Operations Research, 3. Auflage, Springer, 1995.

W. Domschke, A. Drexl, B. Schildt, A. Scholl, S. Voss, ^¨Ubungsbuch Opera-tions Research, Springer, 1995.

H.J. Zimmermann, Operations Research Methoden und Modelle. 2. Auflage., Vieweg, 1992.