Embed Size (px)
Citation preview
Cours : Recherche Opérationnelle.
1
Université de Med Boudiaf M’sila Année Universitaire 2016/2017
Faculté des Technologies Option Modélisation et Productique
Département de Génie Mécanique Master 2ère
Année
Chapitre 1 : Introduction à la recherche opérationnelle (RO).
1.1 Définition de la recherche opérationnelle :
En faisant une recherche sur la définition du terme « recherche opérationnelle » sur le net,
on peut retrouver les définitions suivantes :
Notant que la ROADEF est la société de tous ceux qui ´élaborent ou utilisent des outils de RO
ou d’aide à la décision. La ROADEF regroupe environ 300 membres individuels (industriels,
chercheurs, enseignants-chercheurs et doctorants) ou institutionnels (laboratoires et services
universitaires ou industriels).
Donc on peut dire que la recherche opérationnelle présente :
la discipline des méthodes scientifiques utilisables pour élaborer de meilleures
décisions. Elle permet de rationaliser, de simuler et d’optimiser l’architecture et le
fonctionnement des systèmes de production ou d’organisation.
La discipline carrefour associant les mathématiques, l’économie et l’informatique.
Elle est par nature en prise directe sur l’industrie et joue un rôle-clé dans le maintien
de la compétitivité.
La recherche opérationnelle (aussi appelée “aide à la d´décision”) peut être définie comme
l’ensemble des méthodes et techniques rationnelles orientées vers la recherche de la meilleure
façon d’opérer des choix en vue d’aboutir au résultat visé ou au meilleur résultat possible. Elle
fait partie des “aides à la décision” dans la mesure où elle propose des modèles conceptuels en
vue d’analyser et de maitriser des situations complexes pour permettre aux décideurs de
comprendre et d’évaluer les enjeux et d’arbitrer et/ou de faire les choix les plus efficaces. Ce
domaine fait largement appel au raisonnement mathématique (logique, probabilités, analyse des
données) et `a la modélisation des processus. Il est fortement lié à l’ingénierie des systèmes, ainsi
qu’au management du système d’information.
Cours : Recherche Opérationnelle.
2
1.2 Historique de la recherche opérationnelle :
L’appellation « Recherche Opérationnelle » date des années quarante. N´néanmoins, les
problèmes qui lui sont relatifs sont bien plus anciens. Ainsi, les Carthaginois ont bâti leur ville
en arc de cercle autour de sa citadelle. Cela implique que les bâtisseurs connaissaient déjà, au
9`eme siècle avant Jésus Christ, la figure plane qui, à périmètre donné, présente la surface
maximale.
Léonard Euler, qui a résolu le problème des ponts de K¨onigsberg (`a l’origine de la théorie
des graphes). Gaspard Monge, qui a ´étudie le problème de transports (pan entier des
probabilités et d’analyse des Equations aux Dérivées Partielles). Augustin Cournot, qui a
´étudie l’´économétrie. André Ampère, qui a ´étudie la théorie des jeux. Emile Borel, qui a
´étudie la théorie des jeux.
La véritable naissance de la Recherche Opérationnelle a eu lieu pendant la seconde guerre
mondiale. Elle portait l’appellation « Operationnal research » (en Anglais) et « Operation
research » (en Américain).
Le mot « opération » est à comprendre dans le sens d’activité militaire. Son application est
donc avant tout militaire.
Lors de la naissance de cette science, l’objectif affiché était la préparation scientifique de
décisions militaires : problèmes d’organisation, de planifications, de transport, de
ravitaillements, implantations de radars, protection de convois maritimes contre les sous-
marins...
Patrick Maynard Stuart Blackett est le fondateur de la recherche opérationnelle. En eff et, sur
la demande du gouvernement britannique, Blackett a réuni autour de lui une équipe
hétérogène comprenant des mathématiciens (dont des statisticiens), des physiciens, des
biologistes, des ´économistes... Le but était d’avoir les points de vue les plus diff érents sur les
questions ´étudiées. Parallèlement, l’exigence était faite d’avoir accès `a toutes les sources
d’information pour pouvoir produire des rapports aussi objectifs que possibles. En fin,
Blackett insista sur le fait que les documents ne constituaient jamais qu’une opinion
raisonnable sur les décisions à prendre, le dernier mot revenant toujours aux responsables
politiques.
Puis, les Américains ont emboité le pas.
Apres la guerre, la démarche et les méthodes mises au point furent de plus en plus utilisées
dans le cadre industriel : coordination du travail pour en accroître la productivité et la
rentabilité (gestion, politique d’investissements, répartition de tâches...).
Ces applications furent bien sûr grandement facilitées par la commercialisation des premiers
ordinateurs dans les années cinquante.
Dans quel ordre doit-on eff ectuer les opérations de montage d’une voiture pour en minimiser
le coût de production? Comment découper des pièces géométriques dans une tôle
m´métallique pour en limiter les pertes ? Dérminer les contenances minimales des entrepôts
pour éviter les ruptures de stocks? Comment calculer les meilleurs itinéraires (temps, coût,
distance, etc) de livraison de marchandises ?
Il s’agit ainsi de problèmes d’ordonnancement de taches, d’optimisation de production, de
gestion des stocks, de détermination d’itinéraires, de répartitions de taches, de production
optimale (bénéfice maximal avec des ressources limitées, moindres coûts tout en satisfaisant
la demande...).
En fait, il n’y a pas de définition réellement satisfaisante et exhaustive de la Recherche
Opérationnelle car il n’y a pas vraiment de domaine spécifique ni de méthode unique de
résolution mais de nombreux champs d’application très divers.
Cours : Recherche Opérationnelle.
3
Les apports de la RO sont visibles tout autour de nous et dans les domaines les plus divers :
de l’organisation des lignes de production de véhicules `a la planification des missions
spéciales, de l’optimisation de portefeuilles bancaires à l’aide au séquençage de l’ADN, voire
dans la ”vie de tous les jours” dans l’organisation du traitement des produits recyclables,
l’organisation des ramassages scolaires ou la couverture satellite des téléphones portables...
L’essor véritable de la RO est dû a celui de l’informatique qui lui a apporté les moyens de
calculs nécessaires à la résolution des problèmes réels. Discipline jeune et en pleine
expansion, elle est devenue indispensable aux professionnels pour mieux gérer notre monde
complexe.
Depuis lors, la RO est devenue un élément important du processus de prise de décision dans
de nombreux contextes commerciaux, industriels et gouvernementaux, car elle permet
d'appréhender de façon systématique la complexité toujours grandissante des problèmes de
gestion auxquels sont confrontés tant le secteur privé que public. Elle représente une première
approche des problèmes techniques et est devenue un outil d’aide à la décision.
1.3 Tour d’horizon des techniques de recherche opérationnelle :
La recherche opérationnelle est une technique d’aide à la décision, elle présente les étapes
pratiques suivantes :
1. Détection d'un problème ;
2. Formulation du problème ;
3. Elaboration d'un modèle ;
4. Collecte de données ;
5. Résolution du modèle ;
6. Validation du modèle ;
7. Prise de décisions et implémentation de la solution.
Ces étapes peuvent être regroupés dans ce diagramme suivant :
Figure 1.1 : Les trois expertises employées dans RO.
Cours : Recherche Opérationnelle.
4
La méthodologie :
Les étapes les plus importantes sont la définition du problème (suppose un dialogue
avec le décideur) et la construction du modèle (prendre conscience des hypothèses
simplificatrices et de leur impact).
La phase de validation doit permettre de remettre en cause la validité du modèle.
Une approche globale nécessite donc un aller-retour constant entre le modèle et les
attentes du décideur.
Les Techniques principales :
Programmation linéaire
Programmation en nombres entiers
Optimisation dans les réseaux
Programmation non linéaire
"Optimisation" multi-critères
Programmation dynamique
Modèles stochastiques
Simulation.
1.4 Domaines d’application
La RO est utilisée dans l’industrie et le secteur public:
Systèmes de distribution des marchandises
Gestion des inventaires de marchandises
Planification des réseaux (transports, télécommunications)
Confection d’horaires (personnel, ligues sportives)
Gestion des files d’attente
Pourtant peu connue du grand public…
Enseignement dispersé (génies industriel, civil, électrique, informatique,
mathématiques, administration)
Enseignement surtout aux cycles supérieurs (M.Sc., Ph.D.)
Science jeune (contrairement à la physique)
N’est pas associée à une réalisation technologique visible (contrairement à
l’informatique).
1.5 Quelques exemples de modèles mathématiques :
[1]. Un premier problème
Exemple 1 (Achat de billets d’avion).
Un homme d’affaires doit effectuer 5 voyages entre Fayetteville (FYV) à Denver (DEN), en
partant le lundi de
FYV et revenant le mercredi de DEN à FYV.
Billet aller-retour : $400.
Réduction de 20 % si un weekend est inclus.
Aller simple : 75 % du prix aller-retour.
Question
Comment acheter les billets pour les 5 semaines (à prix minimum) ?
Cours : Recherche Opérationnelle.
5
Aide à la décision
Problème d’aide à la décision
1. Quelles sont les alternatives possibles ?
2. Quelles sont les restrictions à cette décision ?
3. Quel est l’objectif utilisé pour évaluer les alternatives ?
Restrictions
FYV-DEN le lundi et DEN-FYV le mercredi de la même semaine.
Evaluation des alternatives :
Acheter 5 FYV-DEN-FYV normaux. 5 x $400 = $2000
Acheter un FYV-DEN, 4 DEN-FYV-DEN comprenant un weekend et un DEN-FYV.
0.75 x 400$ + 4 x 0.8 x
400$ + 0.75 x 400$ = 1880$
Acheter un FYV-DEN-FYV pour le lundi de la première semaine et le mercredi de la
dernière semaine, et 4 DEN-FYV-DEN comprenant un weekend pour les autres
voyages. 5 x 0.8 x 400 =1600
La troisième alternative est la meilleure.
Modèle de recherche opérationnelle
Ingrédients principaux
Alternatives (variables, inconnues du problème).
Restrictions (contraintes).
Fonction objectif à optimiser (minimiser ou maximiser).
Définition 1 (Solution admissible). Une solution admissible est un ensemble de valeurs
données aux variables qui satisfait toutes les contraintes.
Définition 2 (Solution optimale). Une solution optimale est une solution admissible qui
optimise la fonction objectif.
Définition 3 (Modèle de recherche opérationnelle). Maximiser ou minimiser (fonction
objectif) Sujet à { contraintes}
Variables : continues (réelles), entières, booléennes (0/1), . . .
Objectif : linéaire / non-linéaire, concave / convexe, . . .
[2]. Un premier problème
Exemple 2 (Maximisation de la surface d’un rectangle). Supposons que l’on veut plier un fil
de fer de longueur L en rectangle de manière à maximiser la surface du rectangle.
Cours : Recherche Opérationnelle.
6
Méthodes de résolution
– Dans l’exemple, solution analytique au problème.
– La plupart des problèmes pratiques sont trop grands ou trop complexes pour être résolus
analytiquement.
Méthodes itératives
Déplacement de solution en solution pour atteindre l’optimum (méthodes exactes) ou une "bonne"
solution (heuristiques).
– Importance des algorithmes et des solutions informatiques.
