Recherche opérationnelle
Publié le 08/03/2014
Extrait du document
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 certaines 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 particuliers est cependant faisable et donne lieu à quelques applications intéressantes.
D’autres méthodes encore sont purement heuristiques, comme la méthode par séparation 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 programmation 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’Université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 :
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.
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.
– 4 –
Nous commençons par quelques exemples qui peuvent être résolus en termes de programmes linéaires.
«
–2–
-lam´ethode des coupes et la m´ethode par s´eparation et ´evaluation pour la
r´esolution de programmes lin´eaires qui imposent `a certaines variables d’ˆetre
` a valeurs enti`eres ou mˆeme binaires;
- l’analyse post-optimale, qui d´etermine la variation de la solution en fonction
d’un changement des valeurs des param`etres du programme.
Le troisi`eme chapitre traite de la th´eorie des jeux `a deux personnes et `a somme z´ero
et s’appuie fortement sur les deux chapitres pr´ec´edents.
Au quatri`eme chapitre nous exposons deux probl`emes d’optimisation de flots dans
des r´eseaux: le flot maximal (avec sa coupe minimale) et le flot `acoˆut total minimal.
Le dernier chapitre est une introduction aux m´ethodes ´el´ementaires de la program-
mation dyamique.
Ce domaine est tr`es vaste et de nombreux aspects ne sont pas
´etudi´es, en particulier l’aspect stochastique en cas d’incertitudes sur les param`etres.
Les algorithmes d’optimisation li´es aux graphes (chemin de longueur maximale ou
minimale par exemple) ne figurent pas dans ce cours parce qu’ils sont trait´es dans
les cours d’outils conceptuels et d’algorithmique ´egalement enseign´es `a la Miage de
Nancy.
Les versions initiales de ce cours, ont ´et´e largement inspir´ees par le trait´e (non publi´e)
intitul´e ”Recherche Op´erationnelle” de Francis Conrad, Professeur `a l’Universit´e
Henri Poincar´e Nancy 1.
Nous le remercions d’avoir mis ce texte `a notre dispo-
sition.
Nous n’avons pas connaissance d’un livre ou d’une monographie dont la
pr´esentation correspond `a ses notes, mais nous avons pu constater que les livres
r´ecents en Recherche Op´erationnelle, abordent les sujets trait´es dans ce cours.
Une
liste, certainement incompl`ete, d’ouvrages r´ecents est donn´ee ci-dessous.
Bibliographie :
C.
Gu´eret, C.
Prins, M.
Sevaux,Programmation lin´eaire, Eyrolles, 2000.
R.
Favre, B.
Lemaire, C.
Picouleau,Pr´ecis de recherche op´erationnel le,5`eme
´ed., Dunod, 2000.
Y.
Nobert, R.
Ouellet, R.
Parent,La recherche op´erationnel le,Ga¨etan Morin,
1995.
J.
F.
Ph´elizon,M´ethodes et mod`eles de la recherche op´erationnel le, Economica,
1998.
J.
F.
Maurras,Programmation lin´eaire, compl´exit´e, 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..
»
↓↓↓ APERÇU DU DOCUMENT ↓↓↓
Liens utiles
- Une théorie consiste-t-elle dans la recherche rationnelle de la vérité, ou dans la recherche opérationnelle d'une puissance ?
- opérationnelle (recherche).
- Recherche opérationnelle
- Récapitulatif sur les phases de recherche à opérer pour le commentaire
- Introduction à la recherche documentaire