Recherche Opérationnelle : Origine et Méthodologie

Pr. Aidene Mohamed, Département de Mathématiques,

Faculté des Sciences, U.M.M.T.O

La recherche opérationnelle est une discipline des mathématiques appliquées qui s'intéresse
à l'application du savoir mathématique aux autres domaines. La programmation linéaire, la
programmation mathématique, la programmation floue, la programmation multicritère, la
programmation stochastique, la programmation dynamique, l'optimisation et la recherche
opérationnelle; la théorie des graphes; la théorie des jeux; la théorie du contrôle optimal, l’analyse
numérique, les bio-mathématiques, la bio-informatique, la théorie de l’information; les probabilités
et les statistiques, les mathématiques financières et l'actuariat; la cryptologie et, jusqu'à un certain
point, la combinatoire et la géométrie finie; telle qu'appliquée à l'analyse des réseaux, ainsi qu'une
bonne partie de ce qu'on appelle l'informatique sont autant de domaines d'application des
mathématiques.

Les premiers problèmes d’optimisation datent depuis l’antiquité et sont de types

géométriques, dont le premier problème est de délimiter la plus grande aire possible avec une
longueur L donnée. Cette question est donnée par la légende suivante :

La légende raconte qu'au 9è siècle avant Jésus-

Christ, Elissa, princesse de Tyr (en Phénicie,
actuels Liban, Israël et Syrie) devient reine de Tyr.
Mais son frère Pygmalion assassine son époux afin
de prendre le pouvoir. Horrifiée, Elissa s'enfuit.
Elle atteint l'Afrique du Nord à Byrsa ("la peau de
bœuf"), citadelle proche de l'actuel Tunis, et
demande asile aux autochtones. On ne lui concède
que ce que pourrait couvrir la peau d'un bœuf.
Astucieuse, elle découpe la peau en si fines
lanières qu'elle obtient, bout à bout, une longueur
fantastique (découpage quasi fractal...) : près de 4
km. Avec la corde ainsi formée, elle aurait encerclé
son territoire et fondé (814) la très célèbre ville de Carthage ("la ville neuve", proche de Tunis) en
prenant le nom latin de Dido. La fin de sa vie est bien triste puisque, plutôt que de se marier au roi
Iarbas de la peuplade nomade des Gétules, elle préféra se sacrifier sur un bûcher. D'après l'Énéide
de Virgile, version anachronique de son existence, elle se poignarde de dépit car Énée refuse son
amour et préfère s'embarquer vers l'Italie pour fonder Rome. L'idée de former un cercle plutôt qu'un
triangle, un rectangle, un carré ou tout autre forme géométrique fermée et sans point double, place
Didon au pinacle des mathématiques : elle avait donc admis sans hésiter le résultat isopérimétrique
ci-après que Jacques Bernoulli prouva dans le cadre du calcul des variations.En fait, d'aucuns disent
que voulant se réserver l'accès à la mer, Didon se contenta de tracer un arc de cercle, solution
isopérimétrique des courbes non fermées. Nous sommes ici en bord de mer, face au Bou Kornine,
près de Tunis. Nous allons définir notre domaine et procéder à la (re)construction de Carthage...

Les points A(a) et B(b) sont donnés sur (Ox). il nous faut trouver la nature de la courbe (c)
décrite par notre lanière de cuir, de longueur donnée , afin que l'aire intérieure obtenue, entre (c) et
l'axe des abscisses, soit maximale.

56 Revue Campus N°5

 Recherchons cette courbe sous la forme y = f(x), quitte à paramétrer ultérieurement. La
longueur de la lanière est donnée par la formule:

Compte tenu de cette contrainte, nous devons chercher à maximiser l'aire sous la courbe (c), à
savoir :

C'est un problème isopérimétrique: maximiser une aire pour un périmètre donné.

Le second exemple sera consacré à l’origine de la théorie des graphes : L’histoire de la théorie des
graphes débute peut-être avec les travaux d’Euler au XVIIIe siècle et trouve son origine dans
l’étude de certains problèmes, tels que celui des ponts deKönigsberg :

Les sept ponts de Königsberg

57 Revue Campus N°5

 Les habitants de Königsberg se demandaient s’il était possible, en partant d’un quartier
quelconque de la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir à
leur point de départ), la marche du cavalier sur l’échiquier ou le problème de coloriage de
cartes;etc.…)
Il fallait attendre le 16 eme siècle, avec l’apparition de l’algèbre pour rencontrer les premiers
problèmes d’optimisation de type algébrique.

Position et domaines d’application de certaines branches des mathématiques appliquées

Le boum de la recherche opérationnelle coïncide avec la seconde guerre mondiale.

Historiquement, le premier terme introduit fut celui de programmation linéaire inventé par George
Dantzig dans les années 1940. Le terme programmation vient de l’usage du mot programme par
les forces armées américaines pour établir des horaires de formation et des choix logistiques que
Dantzig étudiait à l’époque. L’emploi du terme « programmation » avait également un intérêt pour
débloquer des crédits en une époque où la planification devenait une priorité des gouvernements.
Outils scientifiques :
- Mathématiques Appliquées (Optimisation, Probabilités, Algèbre, Graphes, Jeux,
Décision,…) ;
- Informatique (Algorithmique, Complexité, Contraintes)
L’approche de la recherche opérationnelle face à un problème applicatif consiste à :
- élaborer un modèle (résultat d’un consensus entre le demandeur et le chercheur ) ;
- développer un algorithme de résolution exacte ou approchée ;
- évaluer la qualité des solutions produites par l’algorithme dans l’environnement réel du
problème.
Le chercheur opérationnel cherchera à fournir :
- un outil (logiciel) aussi générique que possible, i.e : utilisable et performant sur un
ensemble d’instances ;
- non une solution d’une instance particulière.

La programmation linéaire occupe une place centrale de l'optimisation, car les problèmes de
PL sont les problèmes d'optimisation les plus faciles - toutes les contraintes y étant linéaires.
Beaucoup de problèmes réels de recherche opérationnelle peuvent être exprimés comme un
problème de PL. Pour cette raison un grand nombre d'algorithmes pour la résolution d'autres
problèmes d'optimisation sont fondés sur la résolution de problèmes linéaires.La programmation
linéaire est essentiellement appliquée pour résoudre des problèmes d'optimisation à moyen et long
terme (problèmes stratégiques et tactiques, dans le vocabulaire de la recherche opérationnelle).
Les domaines d'application de ces problèmes sont très nombreux aussi bien dans la nature des
problèmes abordés ( planification et contrôle de la production, distribution dans les réseaux ) que
dans les secteurs d'industrie: industrie manufacturière, énergie ( pétrole, gaz, électricité, nucléaire ) ,
transport (aériens, routiers et ferroviaires), télécommunications, industrie forestière, finance. La
recherche opérationnelle a aussi des applications dans le domaine de l'énergie. Elle est couramment
utilisée dans l'industrie pétrolière, principalement dans l'établissement des plans de production à
long terme, à moyen terme, annuel, trimestriel et mensuel. Les résultats permettent aux décideurs
d'avoir un guide pour faire les meilleurs choix dans les investissements, dans l'approvisionnement
des bruts, dans l'utilisation des unités de raffinage, dans les canaux de distribution les plus rentables.
De même, les opérateurs du marché de l'électricité font largement appel à la recherche
opérationnelle tant pour des problèmes stratégiques (par exemple des investissements sur le réseau)
que pour des questions plus opérationnelles (stabilité du réseau, prévisions…).

58 Revue Campus N°5

 Dans le cadre de l’industrie manufacturiere, la recherche opérationnelle permet notamment
de trouver des plans de productions (ordonnancement de production), de disposer au mieux les
machines dans un atelier, de diminuer le gaspillage des matières premières (problèmes de découpe)
ou de l'énergie ou bien encore d'optimiser le conditionnement et la livraison des produits
intermédiaires ou finis.

La recherche opérationnelle peut aider le décideur lorsque celui-ci est confronté à un

problème combinatoire, aléatoire ou concurrentiel.

Un problème est dit combinatoire lorsqu'il comprend un grand nombre de solutions

admissibles parmi lesquelles on cherche une solution optimale ou proche de l'optimum.
La plupart des problèmes combinatoires de la R.O. ont un graphe comme support :
- TSP généralisé (graphe des communications);
- Ordonnancement (graphe des précédences) ;
- Transport (graphe des liaisons) ;
- Emplois du temps ( graphe des incompatibilités) ;
-Flots et circulations (graphe des liaisons)

La théorie des graphes sert de support à la résolution d'un vaste échantillon de problèmes,
notamment certains issus de l'algorithmique classique, tels que la recherche du plus cour chemin
entre deux endroits, le problème du voyageur de commerce (dans lesquels on cherche le chemin le
plus court passant par n points), les problèmes d'ordonnancement de tâche, les problèmes de
planning ou encore les problèmes d'optimisation de flux ( algorithme de Ford-Fulkerson). Elle s’est
également développée dans diverses disciplines telles que la chimie, la biologie, les sciences
sociales. Depuis le début du XXe siècle, elle constitue une branche à part entière des
mathématiques, grâce aux travaux de König, Menger, Cayley puis de Berge et d’Erdös.

De manière générale, un graphe permet de représenter la structure, les connexions d’un

ensemble complexe en exprimant les relations entre ses éléments : réseau de communication,
réseaux routiers, interaction de diverses espèces animales, circuits électriques,. . .

Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande
variété de problèmes en se ramenant à l’étude de sommets et d’arcs.
Les derniers travaux en théorie des graphes sont souvent effectués par des informaticiens, du fait de
l’importance qu’y revêt l’aspect algorithmique.

Exemple typique : déterminer où installer 5 centres de distribution parmi 30 sites

d'implantation possibles, de sorte que les coûts de transport entre ces centres et les clients soient
minimum. Ce problème ne peut être résolu par une simple énumération des solutions possibles par
l'esprit humain, puisqu'il en existe 30 x 29 x 28 x 27 x 26 / (5x4x3x2) = 142 506 (!). Et même si un
problème de cette taille peut être résolu par énumération par un ordinateur, les décideurs sont
régulièrement confrontés à des problèmes infiniment plus complexes, où le nombre de solutions
acceptables se compte en milliards de milliards. Heureusement, des techniques comme la méthode
branch and bound ou les (méta)heuristiques permettent de trouver une solution qui reste souvent
acceptable par une énumération partielle.

Un problème est dit aléatoire s'il consiste à trouver une solution optimale face à un problème
qui se pose en termes incertains. Exemple typique : connaissant la distribution aléatoire du nombre
de personnes entrant dans une administration communale en une minute et la distribution aléatoire

59 Revue Campus N°5

de la durée de traitement du cas d'une personne, déterminer le nombre minimum de guichets à
ouvrir pour qu'une personne ait moins de 5% de chances de devoir attendre plus de 15 minutes.

Un problème est dit concurrentiel s'il consiste à trouver une solution optimale face à un
problème dont les termes dépendent de l'interrelation entre ses propres agissements et ceux d'autres
décideurs. Exemple typique : fixer une politique de prix de vente, sachant que les résultats d'une
telle politique dépendent de la politique que les concurrents adopteront.

Ces problèmes sont, souvent résolus par la théorie des jeux, bien connue des économistes.
Elle s’applique à certaines situations du domaine de l’économie, celles où existe un nombre réduit
de compétiteurs. Elle cherche les stratégies rationnelles dans des situations où les gains d’un acteur
dépendent non seulement de son comportement et des conditions de marché, mais aussi de celui des
autres intervenants, lesquels peuvent poursuivre des objectifs différents ou contradictoires. On lui
trouve aussi des applications en science politique ou en stratégie militaire..

Les résultats peuvent être appliqués à des divertissements (comme le jeu télévisé « Friend or
Foe » sur une chaîne câblée spécialisée aux Etats Unis Game Show Network ) ou à des
considérations plus poignantes :
• la crise des missiles de Cuba
• les politiques de constitution de convois de bateaux en temps de guerre
• la façon de gérer un coup de surprise politique (Nasser à Suez, de Gaule au Québec, Ieltsine
lors du putsch, annonces électorales...) ou marketing
• la lutte contre le terrorisme.

Le Prix Nobel (2005): Professeur Schelling s'est spécialisé dans l'explication des diverses
stratégies utilisées (à utiliser) dans les conflits internationaux, tels la guerre froide et la guerre
nucléaire (dissuasion..) Albert W. Tucker a par exemple diffusé de nombreuses interprétations du
dilemme du prisonier dans la vie courante. Des biologistes ont utilisé la théorie des jeux pour
comprendre et prévoir les résultats de l’évolution, en particulier la notion d’équilibre évolutivement
stable introduit par John Maynard Smith dans son essais La théorie des jeux et l’évolution de la
lutte (Game Theory and the Evolution of Fighting). Voir aussi son livre Evolution and the Theory
of Games.

Les probabilités fournissent à la théorie des jeux un outil conceptuel. Les statistiques peuvent
l’alimenter en données, et les techniques d’optimisations lui fournir des résultats de calcul.
On rencontre aussi les processus stochastiques qui concernent tous les problèmes aléatoires, en
particulier des problèmes de fiabilité (de systèmes, de composants électroniques…) et des
phénomènes d'attente.

Un autre domaine de l’application de la recherche opérationnelle est la finance qui concerne

l'obtention de ressources monétaires (financement) et l'allocation de ces ressources monétaires
(placement, investissement), au fil du temps, et en présence de risque. Par opposition à la
comptabilité, la finance prend en compte la valeur temps et le risque (couple risque/rendement).
Cette "industrie" comprend notamment la banque, l ‘assurance et les bourses ( et par certains côtés
l’immobilier ), sans oublier les budjets publics. Les grandes disciplines au sein de la finance sont
constituées de corps théoriques, d'outils d'optimisation, de théorèmes, destinés à faciliter les prises
de décisions financières. Dans ce domaine on retrouve :
-Mathématiques financières: ensemble d'outils de calcul pour la modélisation et l'aide à la
décision utilisés dans les différentes branches de la finance, notamment les calculs sur les
taux d'intérêts et les instruments financiers.

60 Revue Campus N°5

 -Choix d'investissement : critères et méthodes pour sélectionner des investissements en
fonction de leur rentabilité prévisionnelle ou de leur création de valeur.
-Politique financière : choix des financements des sociétés.
-Les problèmes d'investissement sont des problèmes classiques de recherche opérationnelle.

Ils consistent en général à maximiser le profit (ou l'espérance de profit) obtenu à partir d'un
montant donné en combinant au mieux les différentes possibilités offertes à l'investisseur

Relations avec d'autres disciplines :

Informatique :

Les progrès de l'informatique sont intimement liés à l'accroissement des applications de la

recherche opérationnelle. Une puissance de calcul importante est nécessaire à la résolution de
problèmes de grande taille. Cette puissance est cependant loin de constituer une panacée : il a en
effet été prouvé que certains problèmes, parmi lesquels certains liés à la recherche opérationnelle,
ne peuvent être résolus de manière optimale par un ordinateur dans un temps raisonnable et cela,
même si l'on considère des ordinateurs un milliard de fois plus puissants que ceux d'aujourd'hui. En
théorie de la complexité, on dit que ces problèmes appartiennent à la classe des problèmes NP. Pour
eux, le chercheur opérationnel fera le plus souvent appel à des heuristiques, qui sont des solutions
approchées dont le calcul est possible dans un temps acceptable. Les applications dans le domaine
de l'informatique sont très nombreuses elles aussi. On peut citer, entre autres, le choix de la
localisation et du nombre de serveurs à mettre en place, de la capacité de stockage, de la puissance
de calcul et du débit du réseau, le choix d'une architecture informatique (application centralisée /
distribuée, traitements en temps réel ou en différé, réseau maillé ou en étoile, etc.), et
l'ordonnancement dans les systèmes d'exploitation

Plusieurs méthodes de résolution de problèmes sont issues de l'intelligence artificielle:

algorithme A*, programmation logique, méta heuristiques. Alors que l'approche de l'intelligence
artificielle est de proposer des méthodes de résolution génériques, la recherche opérationnelle utilise
ces méthodes en les spécialisant pour les rendre plus efficaces à résoudre des classes plus restreintes
de problèmes.

Simulation informatique

La simulation est souvent employée pour résoudre des problèmes de RO, notamment dans le
milieu non académique.

La simulation numérique est l'un des outils permettant de simuler des phénomènes réels.
Une simulation numérique (dite aussi simulation informatique) désigne un procédé selon lequel on
exécute un programme informatique sur un ordinateur en vue de simuler par exemple un
phénomène physique complexe (ex: chute d'un corps sur un support mou, résistance d'une
plateforme pétrolière à la houle, fatigue d'un matériau sous sollicitation vibratoire, usure d'un
roulement à billes, ...).

Les simulations numériques scientifiques reposent sur la mise en œuvre de modèles

théoriques utilisant souvent la technique dite des éléments finis. Elles sont donc une adaptation aux
moyens numériques de la modélisation mathématique, et servent à étudier le fonctionnement et les
propriétés d'un système modélisé ainsi qu'à en prédire son évolution. On parle également de calcul
numérique.

61 Revue Campus N°5

 Les interfaces graphiques permettent la visualisation des résultats des calculs par des images
de synthèse.

Ces simulations informatiques sont rapidement devenues incontournables pour la

modélisation des systèmes naturels en physique, chimie et biologie, mais également des systèmes
humains en économie et en science sociale.

Plusieurs problèmes de conception peuvent aussi être exprimés sous forme de programmes
d’optimisation. Cette application est appelée l’optimisation de forme. Un sous-ensemble récent et
croissant de ce domaine s’appelle l’Optimisation multidisciplinaire qui, bien qu’utile en plusieurs
problèmes, a été particulièrement appliqué aux problèmes du génie aérospatial L’optimisation est
un des outils centraux de la microéconomie qui est basée sur le principe de la rationalité et de
l’optimisation des comportements, le profit pour les entreprises, et l’utilité pour les
consommateurs.

Recherche Opérationnelle dans le monde

Discipline reconnue, enseignée et valorisée dans de nombreux pays

Production scientifique très importante dans des journaux de qualité :
• Revue Française de Recherche Opérationnelle 1956
Cahiers du BURO (Bureau Universitaire de Recherche Opérationnelle) 1957
Revue METRA 1962
Monographies de Recherche Opérationnelle 1964
RIRO (Revue d’Informatique et de Recherche Opérationnelle) 1967
Operations Research,
Management Science,
Discrete Optimization,
INFORMS, EJOR, RAIRO, Journal of Optimization Theory and Applications ,….

Des sociétés savantes efficaces :

(CORS, Live OR, AIRO, IFORS (fédération internationnelle), EURO (association européenne de
recherche opérationnelle), SMAI, ROADEF,…)
L’objectif de ces Sociétés est de contribuer au développement des mathématiques appliquées
à travers la recherche, les applications dans les entreprises, l’enseignement et la formation des
chercheurs et ingénieurs.
Elles proposent de faire connaître, d’encourager et de faciliter les nouveaux développements
en mathématiques appliquées, et se doivent donc des structures permettant la rencontre de
toutes les personnes intéressées par les applications des mathématiques, en particulier dans les
milieux universitaires, industriels et des services.
Elles contribuent également `a la réflexion sur l’enseignement des Mathématiques Appliquées aussi
bien dans les universités et les écoles d’ingénieurs que dans l’enseignement secondaire. Elle
souhaite aussi participer et encourager des actions de formation continue.
Des congrès internationaux réguliers généralistes et spécifiques (EURO, CO, MAPSP, PMS, COSI
(Algérie),MOAD (Algérie),CIRO(Maroc), FRANCORO,IFAC, IFIP , … )

62 Revue Campus N°5

Enseignement :
- Formation solide dans la plupart des universités, le plus souvent en Mathématiques
Appliquées et en Informatique.

La R.O. dans les entreprises

Très peu d'entreprises emploient des chercheurs opérationnels pour aider le décideur à
résoudre ses problèmes. Lorsque de tels problèmes se posent, ils sont généralement soumis à un
gros cabinet de conseil ou au département de recherche opérationnelle d'une université (bien que la
tendance actuelle soit à l'externalisation de ces compétences universitaires via de petites sociétés
privées appelées spin-off, répondant mieux aux besoins du monde industriel). Notons que certains
problèmes simples peuvent être résolus au sein même de l'entreprise, la plupart des universités
ayant intégré des cours d'introduction à la recherche opérationnelle.
Les collaborations université-industrie sont en progression importante depuis les années 1990 de par
le monde.

A PROPOS DE QUELQUES MOTS

1955 Ordinateur
1962 Informatique
années 60 Gestion automatisée, cybernétique
années 70 Science des systèmes, intelligence artificielle,
systèmes experts, informatique de gestion

BIBLIOGRAPHIE
1. C. Guéret, C. Prins, M. Sevaux, Programmation linéaire, Eyrolles, 2000.
2. R. Favre, B. Lemaire, C. Picouleau, Précis de recherche op´erationnelle, Dunod, 2000.
3. Y. Nobert, R. Ouellet, R. Parent, La recherche opérationnelle, Gaétan Morin,1995.
4. J. F. Phélizon, Méthodes et modèles de la recherche opérationnelle, Economica,1998.
5. J. F. Maurras, Programmation linéaire, complexité, Springer, 2002.
6. D. Alevra, M. Padberg, Linear optimization and extensions : problems and solutions,pringer,
2001.
7. V.K. Balakrishnan, Network optimization, Chapman and Hall, 1995.
8. G.B. Dantzig, M.N. Thapa, Linear programming, Springer, 1997.
9. H.A. Eiselt, C.L. Sandblom, Integer programming and network models, Springer2000.
10. B. Korte, J. Vygen, Combinatorial optimization, 2nd ed., Springer, 2002.
11. G. Sierksma, Linear and integer programming, Marcel Dekker, 2001.
12. R.J. Vanderbei, Linear programming foundations and extensions, Kluwer, 2001.
13. W. Domschke, A. Drexl, Einf¨uhrung in Operations Research, 3. Auflage, Springer,1995.
14. H.J. Zimmermann, Operations Research Methoden und Modelle. 2. Auflage.,Vieweg, 1992.
15. KARMARKAR, N., “!A New Polynomial-Time Algorithm for Linear Programming!”,
Combinatorica 4, 1984, p. 373–395.
16. CULIOLI J.-Ch., PARTOUCHE-ZEMBRA A., “ La Recherche Opérationnelle dans une
compagnie aérienne ”, Bulletin de la ROADEF, n°4, printemps–été 2000,p.1-3.
17. DANTZIG G.B., Linear Programming and Extensions, Princeton, Princeton University
Press, 1963.
18. DAVID A., “!L’aide à la décision entre outils et organisations!”, Entreprise et Histoire 13,
1996, p. 9–26.
19. M. Aidene, B. Oukacha. Recherche opérationnelle. Programmation linéaire. Edition Pages
Bleues.208p.2005.

63 Revue Campus N°5