Recherche Opérationnelle (RO):

Introduction et principaux concepts

ENCGC-Université Hassan II

Pr: A. El Maliki

1
 OBJECTIF GÉNÉRAL
Permettre à l'étudiant de se familiariser avec les principales techniques
décisionnelles et d'optimisation de la recherche opérationnelle.

Objectifs
o appréhender les principaux modèles et méthodes de la recherche
opérationnelle,

o identifier les méthodes de résolution et les outils les plus adaptés face à un
problème pratique,

o savoir manipuler les outils informatiques pour résoudre un problème

d'optimisation sous contraintes
Développement au Maroc
- Favoriser une approche scientifique dans la prise de décision
- Intervention de la RO à tous les niveaux
* Gouvernements et administrations publiques
* Industries
* Transport
* Finance
*…
2
Decisions can be made by
a...

3
…and sometimes one can find
them very challenging...

4
 • Décrire la Réalité,
• Comprendre la Réalité,
• Gérer la Réalité.

2 Approches :
• Approche Qualitative,
• Approche Quantitative.
5
 Qu’est-ce que la R.O. ?
”Recherche Opérationnelle” vient de ”operations research” (Royaume-
Uni, 2nd guerre mondiale).
Où placer les stations radars ?
Comment planifier les vols de surveillance anti-sous-marins ? ...

Les organisations veulent toujours prendre les meilleures

décisions dans des situations complexes soit pour maximiser
les profits ou encore pour satisfaire la clientèle, l’électorat, etc.

Grand succès : amélioration de l’efficacité des opérations militaires

complexes
– déploiement des radars en Angleterre,
– détermination de la taille des convois,
– logistique …

6
D’après la Société de Recherche Opérationnelle de Grande Bretagne :
« La Recherche Opérationnelle consiste en l’application de méthodes
scientifiques pour résoudre les problèmes complexes rencontrés dans
la direction et la gestion de grands systèmes d’hommes, de
machines, de matériaux, et d’argent dans l’Industrie, le
Commerce, l’Administration et la défense. La caractéristique de
l’approche est le d´développement d’un modèle scientifique (incluant
la mesure de facteurs tels que le hasard et le risque) avec lequel on
tente de prévoir et de comparer les résultats de diverses d´décisions
ou stratégies. Le but est d’aider la direction à déterminer sa politique
de manière scientifique. »

RO: Etude des opérations d’une organisation ou d’un processus

(système) dans le but d’accroître son efficacité.

La recherche opérationnelle se veut un ensemble de méthodes

rationnelles qui cherche à optimiser la prise de décision.

7
La recherche opérationnelle :

• n'est pas une science pour des chercheurs purs, car elle
est axée sur la pratique
• est purement quantitative et utilisera donc des
techniques quantitatives
• repose sur la construction de modèles
• n'est pas une science exigeant des qualités de
leadership
• est une aide pour la préparation de décisions
• se situe dans un environnement complexe
est multidisciplinaire et repose sur un travail de groupe
• est performante lorsque la situation est complexe

8
Types de problèmes en recherche opérationnelle:

o Problèmes aléatoires:
- processus de Markov, etc.

o Problèmes déterministes:
- optimisation linéaire (programmation linéaire),
- optimisation non linéaire,
- programmation dynamique,
- problèmes combinatoires
- des situations conflictuelles

9
 Programmation linéaire (PL)
Le cours porte uniquement sur la partie déterministe et plus
spécifiquement sur l’optimisation linéaire ou programmation
linéaire (PL).

 Programme: terme militaire pour planification

 Lié à l’invention du radar à la deuxième guerre mondiale:

 Comment installer un réseau optimal d’antennes.

 La programmation linéaire a été inventée par George Dantzig,

John von Neumann et Leonid Kantorovich vers 1940.

 La méthode de base est la méthode du simplexe crée par George Dantzig

(1947).

 a connu un immense succès grâce à l’évolution informatique.

 en 1984, Narendra Karmarkar propose une autre méthode qui

est à la base des méthodes de point-intérieur.
10
 Problèmes aléatoires:
• files d'attente
• problème du stock économique
• problème du stock économique
• dimensionnement en construction (risques de rupture)
• usure et renouvellement (phénomènes de survie)
• planification stochastique

Problèmes combinatoires : Situations conflictuelles:

• optimisation de la production
• problème de transport • "jeux" entre adversaires
• problème d'affectation de personnel • décisions collectives d'un jury
• problème du commis voyageur
(globalisation des préférences)
• problème d'affectation de fréquences radio
• problème de la découpe optimale • achat d'un nouveau matériel
• problème de localisation et distribution (computer, Jeep)
• problème d'établissement d'horaire de • gestion du personnel (multicritère)
cours • organisation des fichiers
• problème d'ordonnancement de tâches (multicritère).
• organisation du travail dans un atelier
11
 Où celà sert-il ?
Dans de très nombreux domaines et en particulier en GESTION

Les applications sont nombreuses,

o en particulier en administration, management,
o organisation du travail, génie industriel,
o industries automobiles, pétrolières, etc.
o Gérer les soins de santé dans les hôpitaux
o Organiser les services policiers ou ambulanciers
o Planifier l'utilisation et gérer la production d'énergie
o Planifier des systèmes de livraison ou de transport en commun
o Gérer la production, les stocks et la distribution de produits usinés
o Concevoir des systèmes de communication et des systèmes
informatiques
o Établir des horaires de travail, de cours ou des calendriers sportifs
o Choisir des politiques économiques et financières

12
13
14
15
Investissement: Composition optimale de portefeuilles

16
17
18
19
20
Planification des télécommunications:

• Conception et dimensionnement de réseaux (câblés et cellulaires)

• Design de réseaux résistants aux pannes

• Tarification des services

21
Internet from wikipedia Courtesy of the Opte Project, License CC BY.

22
Social Networks Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/.
© Neil Cummings on Flickr. License CC BY-SA. This content is excluded from our Creative

23
Gestion de la chaîne logistique:

• Confection de tournées (véhicules de livraisons, routes

de facteurs, déneigement/ramassage des ordures,
transport en commun, aviation civile, etc.)

• Localisation d’entrepôts/usines (détermination du

nombre optimal, localisation, affectation des clients aux
entrepôts/usines)

• Gestion des inventaires (niveaux et stratégies de

commandes optimales)

• Gestion intégrée de la chaîne logistique (commandes

aux fournisseurs, localisation des entrepôts et usines,
gestion des inventaires, tournées de livraisons, etc.)

24
25
26
27
28
Supply chain

29
30
Planification de la production:
• Gestion des inventaires
• Ordonnancement des tâches

31
32
Gestion des resssources humaines:

• Affectation de personnel à des tâches/postes

• Confection d’horaires de personnel

• Négociations de conventions collectives

- Analyse de l’impact monétaire (et autres) de changements
envisagés aux conventions de travail

Marketing:

• Répartition d’un budget de publicité

• Nombre et localisation de succursales

• Partage des territoires de ventes

• Tarification (prix de vente, etc.) 33

34
SUDOKU

35
Africa Map

36
37
Excel
Solver

38
 Cadre d’application
Processus Application
traditionnel Situation réelle de la R.O.
de gestion
Abstraction

Retour/ Modèle
ajustements
Intuition/ Analyses
expérience
Résultats

Décisions Interprétation
(validation)

Payoff
Le schéma général suivi par la méthode RO est :
Problème concret (de type R.O)
-- modélisation
-- résolution par une méthode de R.O
-- interprétation des résultats
-- prise de décision.

Recherche opérationnelle = modélisation mathématique des processus de prise

de décision.
- Inconnues: les variables de décision.
- Evaluation de la décision = fonction économique ou fonction «objectif».
- Trouver les valeurs des variables de décision qui minimisent (ou maximisent)
la fonction objectif en respectant certaines contraintes.

En R.O, modéliser un problème consiste à identifier les variables

intrinsèques, les différentes contraintes auxquelles sont soumises ces
variables et l’objectif visé (optimisation).

Dans un problème de programmation linéaire (PL) les contraintes et

l’objectif sont des fonctions linéaires des variables.
40
41
Cas de deux variables Cas de plusieurs variables

42
43
 Modélisation
Pour analyser la situation (ou des propositions de solutions),
on a recours à des modèles c’est-à-dire à une représentation
abstraite (et souvent simplifiée) de la réalité.
Un modèle sera une représentation simplifiée de la réalité dans au
moins l'un des deux buts suivants :
o mieux comprendre la réalité ;
o aider à la prise de décision en fournissant des solutions
acceptables aussi bonnes que possible.

Modéliser un problème en R.O consiste à identifier:

o Les variables (inconnues)
o Les contraintes
o L’objectif à atteindre (optimisation)

La modélisation est un art, l’optimisation est une science.

44
 Modélisation
Exercice opérationnel
• On opère directement sur le système étudié
• Très réaliste mais très cher
• Difficile voire impossible de tester différentes solutions

Simulation
• On représente le système par des maquettes ou des programmes
informatiques
• Moins réaliste mais moins cher
• Intuition humaine génére les solutions testées

Modèles symboliques:
 On représente le système par des objets mathématiques
(variables, équations, etc.)
 Version abstraite et simplifiée de la réalité
 Moins cher, permet d’évaluer des multitudes de solutions
 Propose des solutions !
 Composantes d’un modèle symbolique

Entrées Résultats
Var. de décision Mesure de performance
(contrôlables) (fonction objectif)
Modèle
Paramètres/Données Variables de
(incontrôlables) conséquences

46
 Variables de décision:
c’est le décideur qui contrôle leurs valeurs

 Paramètres:
valeur connue (fixe) mais que le décideur ne contrôle pas
(p.ex. marché, météo, coûts matières premières …)

 Variables de conséquence:
mesurent l’impact des variables de décision (sur le
système)

 Mesure de performance:
mesure le degré d’atteinte des objectifs du décideur
correspondant à une valeur des variables de décision.

47
Exemple 1

Une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2.

Les temps d'usinage sont :
 pour P1: de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2
 pour P2: de 4 heures dans l'atelier A1 et de 3 heures dans l'atelier
A2.

Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160

heures et celui de l'atelier A2 de 180 heures.
La marge bénéficiaire est de 1200 € pour une pièce P1 et 1000 € pour
une pièce P2.

 Quelle production de chaque type doit-on fabriquer pour maximiser

la marge hebdomadaire?
Solution:
Modéliser sous forme de programme linéaire
1- Variables économiques :
X1 : quantité de pièces P1 à fabriquer
X2 : quantité de pièces P2 à fabriquer
2- Contraintes économiques :
3x1 + 4x2 <= 160 (contrainte due à l’atelier A1)
6x1 + 3x2 <= 180 (contrainte due à l’atelier A2)

3- Contraintes de signe :
x1 >= 0
x2 >= 0

4- Fonction économique (objectif) :

Z = 1200x1 + 1000x2
(à optimiser, dans notre cas, maximiser)
Exemple 2

Un fabricant produit 2 types de yaourts à la fraise A et B à partir de Fraise, de Lait

et de Sucre. Chaque yaourt doit respecter les proportions suivantes de matières
premières.

A B
Fraise 2 1
Lait 1 2
Sucre 0 1

 On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de sucre.

 La vente de 1 Kg de yaourts A et B rapporte respectivement 4$ et 5$.
 Le fabricant cherche à maximiser son profit.

50
Solution:

 Sur quelles quantités peut-on travailler ?

• Variables : xA et xB
• Que cherche-t-on à optimiser ?
• max z = 4xA + 5xB

• Quelles sont les contraintes du problème ?

2xA+ xB <= 800 (fraises)
xA+ 2xB <= 700 (lait)
xB<= 300 (sucre)
xA, xB >= 0 positivité

51
Exemple 3

Considérons un agriculteur qui possède des terres, de superficie égale à H

hectares, dans lesquelles il peut planter du blé et du maïs. L’agriculteur
possède une quantité E d’engrais et I d’insecticide. Le blé nécessite une
quantité Eb d’engrais par hectare et Ib d’insecticide par hectare.
Les quantités correspondantes pour le maïs sont notées Em et Im.

Soit Pb le prix de vente du blé et Pm celui du maïs. Si l’on note par xb et xm

le nombre d’hectares à planter en blé et en maïs, comment exprimer le fait
que l’agriculteur souhaite maximiser son gain, tout en restant dans les
limites de ses ressources?
Solution:

maximiser Pbxb + Pmxm (maximiser le revenu net)

Contraintes:
xb + xm <= H (surface)
Ebxb + Emxm <= E (engrais)
Ibxb + Imxm <=I (insecticide)
Xb >= 0
xm >= 0

52
Exemple 4

Les demandes journalières en chauffeurs dans une entreprise

de transport
Lu Ma Me Je Ve Sa Di
13 18 21 16 12 25 9

Les chauffeurs travaillent cinq jours d’affilée (et peuvent donc

avoir leurs deux jours adjacents de congé n’importe quand
dans la semaine).
Objectifs : déterminer les effectifs formant les sept équipes
possibles de chauffeurs de manière à
• couvrir tous les besoins,
• engager un nombre minimum de chauffeurs.

53
 Variables de décision : On associe une variable de décision à
chacune des sept équipes possibles
x1 : nombre de chauffeurs dans l’équipe du lundi
(repos le samedi et le dimanche),
x2 : nombre de chauffeurs dans l’équipe du mardi,
...
x7 : nombre de chauffeurs dans l’équipe du dimanche.

 Fonction objectif : On veut minimiser le nombre total de

chauffeurs engagés
min z = x1 + . . . + x7
 Contraintes : Le nombre de chauffeurs présents chaque jour
doit être suffisant

54
Contraintes de bornes : Le nombre de chauffeurs dans chaque équipe doit
non seulement être non négatif mais également entier !
xi >= 0 et entier, i = 1, . . . , 7.

Ce problème n’est pas un PL mais un programme linéaire en

nombres entiers (PLNE) !

55
Exemple 5

Planifier la production d’articles à moindre coût pour les 4

prochains mois.
Production maximale normale : 1200 articles / mois
Production maximale en heure sup : 400 articles / mois
Surcoût heures sup : 7 euros / article
Stockage : 3 euros / article / mois

mois 1 mois 2 mois 3 mois 4

Demandes 900 1100 1700 1300

56
Solution:

57
Exemple 6: (Régime diététique)

Le régime diététique consiste à trouver la meilleure combinaison

d’ingrédients pour satisfaire des exigences minimales et minimiser
le coût total du régime.
Un cuisinier de l’hôpital doit déterminer le menu approprié pour
les patients qui sont opérés dans le service de chirurgie générale.
Chaque opéré doit suivre un régime qui est composé :
- d’au moins 50 unités de protéines par repas
- d’au moins 15 unités de vitamines
- d’au moins 1200 calories/jour
- d’au plus 100 unités de glucides.
Le cuisinier a consulté la diététicienne de l’hôpital qui lui a donné
les composants en protéines, glucides, vitamines et calories pour
les aliments qui sont habituellement achetés par le service de
l’économat. Les informations sont consignées dans le tableau ci-
dessous. - poisson : 4,5 euros/kg
Le prix des aliments est le suivant - poulet : 1,8 euros/kg
- fromage : 3,5 euros/kg
- carottes : 0,6 euros/kg
- pommes de terre : 0,5 euros/kg
- spaghetti : 0,8 euros/kg.

58
Composition en éléments nutritifs des aliments.

Aliments Protéines Vitamines Glucides Calories

Poisson 100g 40 25 10 300
Poulet 100g 50 10 20 500
Fromage 100g 30 20 30 600
Carottes kg 20 30 50 1400
Spaghetti kg 22 15 100 2000
Pommes de T kg 15 25 80 1800

Le problème de notre cher cuisinier est de déterminer la composition

du menu au moindre coût.

59
Solution: Modélisation sous forme de programme linéaire.
Le problème se modélise de la façon suivante.
Définissons les variables de décision suivantes :
X1= quantités en centaines de grammes de poisson
X2= quantités en centaines de grammes de poulet
X3= quantités en centaines de grammes de fromage
X4= quantités en centaines de grammes de carottes
X5= quantités en centaines de grammes de pommes de terre
X6= quantités en centaines de grammes de spaghettis.
La fonction économique consiste à minimiser le coût du menu quotidien servi à chaque
patient opéré.

Min Z = 4.5X1+1.8X2+3.5X3+0.6X4+0.5X5+0.8X6

Il y a deux catégories de contraintes. D’abord, il y a celles qui expriment un besoin minimal

à satisfaire pour ne pas affecter la santé des patients. Ensuite, il y a celle qui est relative à
un seuil de glucides à ne pas dépasser pour chaque opéré.
Les contraintes qui expriment un besoin minimal sont en rapport avec les besoins vitaux en
éléments nutritionnels tels que protéines, vitamines, calories.

40X1+50X2+30X3+2X4+1,5X5+2,2X6 ≥50
25X1+10X2+20X3+3X4+2.5X5+1.5X6 ≥ 15
300X1+300X2+600X3+140X4+180X5+200X6 ≥ 1200
La dernière contrainte a trait au seuil maximal de glucides permis dans régime des patients.
10X1+20X2+30X3+5X4+8X5+10X6 ≤100
Xi>=0 i=1,…,6 (positivité)

60
Exemple 7 (Employee Scheduling Application)

Hong Kong Bank now employs 12 full-time tellers. Part-time

employees (four hours per day) are available. They can start
work anytime between 9 A.M. and 1 P.M.

Tellers requirements:

61
Solution: Employee Scheduling Application

Hong Kong Bank

Labor Constraints:
 Full-timers work from 9 A.M. to 5 P.M.
Allowed 1 hour for lunch.
Half of full-timers eat at 11 A.M. and other half at noon.
Full-timers thus provide 35 hours per week of productive
labor time.
 Part-time hours limited to a maximum of 50% of day’s total
requirement.
Costs:
Part-timers earn $6 per hour (or $24 per day) on average.
Full-timers earn $75 per day in salary and benefits, on average.

62
Hong Kong Bank.
Decision Variables:
F = number of. full-time tellers

P1 = part-timers starting at 9 A.M. (leaving at 1 P.M.)

P2 = part-timers starting at 10 A.M. (leaving at 2 P.M.)

P3 = part-timers starting at 11 A.M. (leaving at 3 P.M.)

P4 = part-timers starting at noon (leaving at 4 P.M.)

P5 = part-timers starting at 1 P.M. (leaving at 5 P.M.)

63
 Objective: minimize total daily labor cost
$75F + $24 ( P1 + P2 + P3 + P4 + P5 )
Subject to
F  P1  10 (9 A.M. - 10 A.M. needs)

F  P1  P2  12 (10 A.M. - 11 A.M. needs)

0.5 F  P1  P2  P3  14 (11 A.M. - noon needs)

0.5 F  P1  P2  P3  P4  16 (noon - 1 P.M. needs)

F  P2  P3  P4  P5  18 (1 P.M. - 2 P.M. needs)

F  P3  P4  P5  17 (2 P.M. - 3 P.M. needs)

F  P4  P5  15 (3 P.M. - 4 P.M. needs)

F  P5  10 (4 P.M. - 5 P.M. needs)

F  12 (full-time tellers available)

4 P1  4 P2  4 P3  4 P4  4 P5  0.050(112) Last constraint
F , P1 , P2 , P3 , P4 , P5  0
64
Last Constraint (Continued):

 Part-time worker hours cannot exceed 50% total

hours required each day, which is sum of tellers
needed each hour.

4( P1  P2  P3  P4  P5 )  0.50(10  12  14  16  18  17  15  10)

Simplifying yields,

4 P1  4 P2  4 P3  4 P4  4 P5  0.050(112)
F , P1 , P2 , P3 , P4 , P5  0
65
Exemple 8
La direction d’une usine de meubles a constaté qu’il y a des temps morts
dans chacun des départements de l’usine. Pour remédier à cette situation,
elle décide d’utiliser ces temps morts pour fabriquer deux nouveaux modèles
de bureaux, M1 et M2. Les temps de réalisation pour chacun de ces modèles
dans les ateliers de sciage, d’assemblage et de sablage ainsi que les temps
libres dans chacun de ces ateliers sont donnés dans le tableau ci-dessous.
Ces temps représentent le nombre d’heures nécessaires à un homme pour
effectuer le travail. Les profits que la compagnie peut réaliser pour chacun de
ces modèles sont de 300$- pour M1 et de 200$- pour M2.

M1 M2 Temps libres
Sciage 1 2 20
Assemblage 2 1 22
Sablage 1 1 12

La direction désire déterminer combien de bureaux de chaque

modèle elle doit fabriquer pour maximiser son profit,

66
Solution: Posons x1 le nombre de bureaux du modèle M1 et x2 le nombre de bureaux du
modèle M2. Les temps libres de chaque département imposent des contraintes qu’il faut
respecter. La contrainte imposée
par les temps libres à l’atelier de sciage : X1+2x2<=20
les autres contraintes sont :
2x1 + x2 <=22
x1 + x2 <= 12
Il s’ajoute à ces contraintes des contraintes de non-négativité puisque le nombre de
bureaux ne peut être négatif, on a donc : X1>=0 et x2 >= 0

67
68
69
70