Recherche Opérationnelle
R.O.
Pr. Abdessamad Kamouss
Cycle Ingénieur
ENSAM Casablanca
Pr. Abdessamad KAMOUSS 1 Recherche opérationnelle 1 / 32
Contenu du module
Pr. Abdessamad KAMOUSS 2 Recherche opérationnelle 2 / 32
Introduction à la recherche opérationnelle
Pr. Abdessamad KAMOUSS 3 Recherche opérationnelle 3 / 32
Définitions de la Recherche
Opérationnelle
Définition (Cambridge Dictionary)
Operational research UK (US operations research) The systematic study of
how best to solve problems in business and industry.
Définition (Wikipedia)
Operational research is the use of mathematical models, statistics and
algorithms to aid in decision-making.
Définition (ROADEF)
Recherche Opérationnelle est une approche scientifique pour la résolution de
problèmes de gestion de systèmes complexes.
Pr. Abdessamad KAMOUSS 4 Recherche opérationnelle 4 / 32
Recherche Opérationnelle - autres
définitions
Définition
La recherche opérationnelle est une discipline qui utilise des méthodes
mathématiques et algorithmiques pour analyser des problèmes complexes et
optimiser des processus décisionnels.
Elle vise à aider les organisations à prendre des décisions efficaces en
modélisant des situations réelles, en évaluant différentes options et en
minimisant ou maximisant des critères spécifiques, comme le coût, le temps
ou la ressource. Ses applications couvrent divers domaines, tels que la
logistique, la finance, la production et la gestion des opérations.
Pr. Abdessamad KAMOUSS 5 Recherche opérationnelle 5 / 32
Un premier problème
Achat de billets d’avion
Un homme d’affaires doit effectuer 5 voyages entre Casa (CAS) et Paris (PAR)
selon les conditions suivantes :
Il doit partir le lundi de CAS à PAR et revenir le mercredi de PAR à CAS.
Un billet aller-retour : 400U.
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) ?
Pr. Abdessamad KAMOUSS 6 Recherche opérationnelle 6 / 32
Un premier problème
Evaluation des alternatives
Alternatives
Acheter 5 CAS-PAR-CAS normaux.
5 x 400 = 2000
Acheter un CAS-PAR, 4 PAR-CAS-PAR comprenant un weekend et un
PAR-CAS.
0.75 x 400 + 4 x 0.8 x 400 + 0.75 x 400 = 1880
Acheter un CAS-PAR-CAS pour le lundi de la première semaine et le
mercredi de la dernière semaine, et 4 PAR-CAS-PAR comprenant un
weekend pour les autres voyages.
5 x 0.8 x 400 =1600
La troisième alternative est la meilleure.
Pr. Abdessamad KAMOUSS 7 Recherche opérationnelle 7 / 32
Décision binaire
Voyage sans redondance (Problème de voyageur de commerce)
Un étudiant projette de visiter les campus de trois universités au cours d’un
voyage unique, débutant et finissant à l’aéroport de P.
Les trois établissements sont dans les villes de A, B, et C.
L’étudiant ne veut visiter chaque ville qu’une seule fois.
On veux maintenir le trajet total le plus court possible.
Les distances entre les aéroports de ces villes sont données dans la
table ci-après :
Pr. Abdessamad KAMOUSS 8 Recherche opérationnelle 8 / 32
Décision binaire
Ville P A B C
P - 30 38 73
A 35 - 18 53
B 32 19 - 51
C 79 50 59 -
Table – Les distances de vol inter-aéroports.
Question
L’objectif ici est de trouver une modélisation mathématique capable de
représenter ce problème et ses différentes contraintes tout en
permettant d’évaluer et minimiser la distance globale de ce voyage.
Pr. Abdessamad KAMOUSS 9 Recherche opérationnelle 9 / 32
Décision binaire : modélisation
Puisque n’importe quel trajet consiste en une série de petits
déplacements entre deux villes, on numérote les villes comme suit : 1
pour P, 2 pour A, 3 pour B et 4 pour C. Ainsi, nous aurons une variable
x1,2 égale à 1 si l’étudiant voyage de P à A au cours de son parcours total
et 0 sinon.
Puisqu’il n’y a pas de voyage d’une ville vers cette même ville, nous
avons les contraintes : xi,i = 0, i = 1, ..., 4
Chaque ville ne devant être visitée qu’une seule fois, elle ne peut
apparaître qu’une seule fois comme ville d’arrivé. Donc pour j fixé avec
j = 1, ..., 4,
x1,j + x2,j + x3,j + x4,j = 1
d’où :
4
∑ xi,j = 1, j = 1, ..., 4.
i=1
Pr. Abdessamad KAMOUSS 10 Recherche opérationnelle 10 / 32
Décision binaire : modélisation
Puisque la même ville ne peut pas être une source d’un trajet plus qu’une
fois, alors on pose la contrainte suivante :
4
∑ xi,j = 1, i = 1, ..., 4.
j=1
Afin d’obtenir un véritable trajet ayant même origine et départ, nous
devons rejeter les affectations qui décrivent des groupes déconnectés de
petits déplacements comme x1,2 = x2,1 = 1 ou x3,4 = x4,3 = 1, avec
toutes les autres variables égales à 0. Nous pouvons forcer ceci avec les
contraintes :
xi,j + xj,i ≤ 1, i = 1, ..., 4, j = 1, ..., 4.
On peut décrire la distance totale associé à n’importe quel parcours
autorisé par :
4 4
∑ ∑ xi,j ai,j .
i=1 j=1
Pr. Abdessamad KAMOUSS 11 Recherche opérationnelle 11 / 32
Décision binaire
Voyage sans redondance
Donc la modélisation du problème sera comme suit :
min ∑4i=1 ∑4j=1 xi,j ai,j
xi,j ∈ 0, 1, i = 1, ..., 4, j = 1, ..., 4.
xi,i = 0, i = 1, ..., 4.
∑4i=1 xi,j = 1, j = 1, ..., 4.
∑4j=1 xi,j = 1, i = 1, ..., 4.
xi,j + xj,i ≤ 1, i = 1, ..., 4, j = 1, ..., 4.
Pr. Abdessamad KAMOUSS 12 Recherche opérationnelle 12 / 32
R.O : Applications
Problème du voyageur de commerce
Un voyageur de commerce, basé à Casablanca doit visiter plusieurs
clients situés sur différentes villes au Maroc.
Il souhaite effectuer la tournée la plus courte possible
Pr. Abdessamad KAMOUSS 13 Recherche opérationnelle 13 / 32
R.O : Applications
Problème e transport
de marchandises.
des entrepôts vers les clients
coûts de transport, distance sur les arcs
trouver le meilleur plan de distribution
Pr. Abdessamad KAMOUSS 14 Recherche opérationnelle 14 / 32
R.O : Applications
Plus court chemin
entre deux villes
entre deux pays
entre un fournisseur et ses clients
...
Pr. Abdessamad KAMOUSS 15 Recherche opérationnelle 15 / 32
R.O : Applications
Mariages stables
consistant à trouver par exemple, étant donnés n hommes, n femmes et
leurs listes de préférences, une façon stable de les mettre en couple.
Une situation est dite instable s’il existe au moins un homme et une
femme qui préféreraient se mettre en couple plutôt que de rester avec
leurs partenaires actuels
Pr. Abdessamad KAMOUSS 16 Recherche opérationnelle 16 / 32
R.O : Applications
Applications du problème de mariage stable
En général, le problème de mariage stable est souvent utilisé dans des
situations nécessitant une répartition de biens rares ou hétérogènes :
Affectation des élèves à des écoles d’ingénieurs
Affectation des étudiants à des spécialités
Association des travailleurs à des postes clés
Attribution des medecins internes à des hopitaux
Dons d’organes
...
Pr. Abdessamad KAMOUSS 17 Recherche opérationnelle 17 / 32
R.O : Applications
Challenges ROADEF
2022 Problème d’optimisation de chargement de camion 3D
Planification de la maintenance des pannes basée sur l’exploita-
2020 tion du réseau
2018 Problème de stock de coupe
2016 Problème d’acheminement des stocks pour la distribution de gaz
2014 Les trains ne disparaissent pas
2012 Réaffectation de machines
Un problème de gestion d’énergie de grande taille comportant
2010 des contraintes diversifiées
2009 Gestion des perturbations dans le domaine aérien
Planification des techniciens et des interventions pour les télé-
2007 communications
Ordonnancement de véhicules pour une chaîne de montage au-
2005 tomobile
2003 Gestion des prises de vue réalisées par un satellite d’observation
2001 Alloction de fréquences avec polarisation
Pr. Abdessamad KAMOUSS 18 Recherche opérationnelle 18 / 32
R.O : Applications en ingénierie
A. Planifier et ordonnancer
Ordonnancement des chantiers
Pr. Abdessamad KAMOUSS 19 Recherche opérationnelle 19 / 32
R.O : Applications en ingénierie
A. Planifier et ordonnancer
Ordonnancement d’atelier
Pr. Abdessamad KAMOUSS 20 Recherche opérationnelle 20 / 32
R.O : Applications en ingénierie
A. Planifier et ordonnancer
Emplois du temps
Pr. Abdessamad KAMOUSS 21 Recherche opérationnelle 21 / 32
R.O : Applications en ingénierie
A. Planifier et ordonnancer
Planification des centres d’appels
Pr. Abdessamad KAMOUSS 22 Recherche opérationnelle 22 / 32
R.O : Applications en ingénierie
A. Planifier et ordonnancer
Planification des centres d’appels
Pr. Abdessamad KAMOUSS 23 Recherche opérationnelle 23 / 32
R.O : Applications en ingénierie
B. Stocker et Gérer
Gestion de la production, des stocks et de la
maintenance
Pr. Abdessamad KAMOUSS 24 Recherche opérationnelle 24 / 32
R.O : Applications en ingénierie
C. Transporter
Transport, logistique
Pr. Abdessamad KAMOUSS 25 Recherche opérationnelle 25 / 32
R.O : Applications en ingénierie
C. Transporter
Transport, logistique
Pr. Abdessamad KAMOUSS 26 Recherche opérationnelle 26 / 32
R.O : Applications en ingénierie
D. Emballer et ranger
Emballage
Pr. Abdessamad KAMOUSS 27 Recherche opérationnelle 27 / 32
R.O : Applications en ingénierie
D. Emballer et ranger
Emballage
Pr. Abdessamad KAMOUSS 28 Recherche opérationnelle 28 / 32
R.O : Applications en ingénierie
D. Emballer et ranger
Emballage
Pr. Abdessamad KAMOUSS 29 Recherche opérationnelle 29 / 32
R.O : Applications en ingénierie
E. Router et Relier
Router et sécuriser
Pr. Abdessamad KAMOUSS 30 Recherche opérationnelle 30 / 32
R.O : Applications en ingénierie
E. Router et Relier
Calcul d’itinéraires
Pr. Abdessamad KAMOUSS 31 Recherche opérationnelle 31 / 32
R.O : Conclusion
La R.O consiste à :
Faire le mieux : coût min, meilleur profit, plus court
parcours, plus rapide chemin, sécurité maximum, ...
Avec les ressources disponibles : ressources humaines,
matière première, temps machines, moyen de
transport, mémoire, ...
Pr. Abdessamad KAMOUSS 32 Recherche opérationnelle 32 / 32