Recherche Opérationnelle

RECHERCHE OPERATIONNELLE

0. Introduction.

Ce cours a ´et´e enseign´e jusqu’en 2002, en ann´ee de licence, `a la MIAGE de NANCY.

L’objectif principal de ce cours est d’acqu´erir une connaissance approfondie de certaines

techniques consid´er´ees `a l’heure acutelle comme des m´ethodes de base en

Recherche Op´erationnelle. Celles-ci se retrouvent en effet, sous des formes plus

complexes, dans les analyses professionnelles de faisabilit´e ou d’optimisation.

Les exercices qui accompagnent ce cours permettent aux ´etudiants de mod´eliser des

probl`emes simples en utilisant les techniques de la Recherche Op´erationnelle. Ces

exercies ne tiennent ´evidemment pas compte de tous les param`etres d’une v´eritable

analyse professionnelle. Ils sont simplifi´es volontairement et sont choisis suivant

l’orientation des ´etudiants, en majorit´e dans le domaine de la gestion; mais les

techniques utilis´ees s’appliquent ´egalement `a la mod´elisation en ing´eni´erie et en

sciences.

Certaines m´ethodes de la Recherche Op´erationnelle se d´emontrent - au niveau

math´ematique - assez facilement. L’algorithme du simplexe, par exemple, repose

sur des arguments ´el´ementaires de l’alg`ebre lin´eaire.

D’autres m´ethodes pr´esent´ees dans ce cours, par exemple celles de la programmation

dynamique, sont des cas particuliers de d´eveloppements analytiques et stochastiques

plus avanc´es, qui, `a un niveau g´en´eral, ne sont plus `a la port´ee d’un ´etudiant en

licence (mˆeme en math´ematiques). Une justification ´el´ementaire de certains cas particuliers

est cependant faisable et donne lieu `a quelques applications int´eressantes.

D’autres m´ethodes encore sont purement heuristiques, comme la m´ethode par s´eparation

et ´evaluation (branch and bound) en programmation lin´eaire `a valeurs enti`eres.

Il est peut-ˆetre surprenant de constater que la presque totalit´e des probl`emes d’optimisations

´enonc´es dans ce cours (hormis ceux relevant de la programmation dynamique)

peuvent ˆetre r´esolus `a l’aide d’un algorithme de programmation lin´eaire. Cependant,

des solutions sp´ecifiques, par exemple au probl`eme du flot maximal ou du flot de

coˆut total minimal dans un r´eseau, sont propos´ees. Elles sont souvent d´evelopp´ees

`a partir d’un programme lin´eaire adapt´e au probl`eme sp´ecifique et font partie des

m´ethodes standards dans la litt´erature r´ecente. Ainsi la question du flot de coˆut

total minimal permet de pr´esenter quelques ´el´ements du simplexe des r´eseaux.

Le cours est divis´e en cinq chapitres.

Les deux premiers traitent de la programmation lin´eaire. Ils contiennent :

- une introduction `a la technique du simplexe, une m´ethode standard pour la

r´esolution d’un programme lin´eaire;

- la dualit´e;

– 2 –

- la m´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 `a coˆut total minimal.

Le dernier chapitre est une introduction aux m´ethodes ´el´ementaires de la programmation

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

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 :

...