Recherche opérationnelle

Modélisation mathématique

3éme année EHEI

Mohamed BARHDADI
[email protected]
 Définition

▰ La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des
questions d’utilisation optimale des ressources dans l’industrie et dans le secteur public.

▰ La recherche opérationnelle est née pendant la Seconde Guerre mondiale des efforts conjugués de
grands mathématiciens (dont von Neumann, Dantzig, Blackett) pour optimiser des ressources
militaires.
▰ Le premier succès de cette approche a été obtenue en 1940 par le Prix Nobel de physique. Patrick
Blackett qui résolut un problème d’implantation optimale de radars de surveillance.

▰ Depuis une dizaine d’années, le champ d’application de la RO s’est élargi à des domaines comme
l’économie, la finance, le marketing et la planification d’entreprise. Plus récemment, la RO a été
utilisée pour la gestion des systèmes de santé et d’éducation, pour la résolution de problèmes
environnementaux et dans d’autres domaines d’intérêt public
2
 Objectifs de la RO

➢ Trouver l’équilibre optimal entre des facteurs qui s’opposent dans un système complexe
Exemple : Dans une entreprise :
▻ Ressources limitées : Nombres d’ouvriers et de machines
▻ Besoins illimités : Commandes, ventes et profits

➢ Science du comment mieux faire avec moins. c’est un ensemble d’outils pour optimiser, planifier, … .

➢ L’aide à la décision: l’architecture et le fonctionnement des systèmes industriels et économiques ; ce

qui permet aux décideurs de faire des choix efficaces et robustes.

3
 Domaines d'applications

➢ Gestion de la chaine logistique

▻ Confection de tournées (véhicules de livraisons, routes de facteurs, ramassage des ordures,
transport en commun, aviation civile, etc.)
▻ Gestion des inventaires (niveaux et stratégies de commandes optimales)
▻ Localisation d’entrepôts/usines (détermination du nombre optimal, localisation, affectation des
clients aux entrepôts/usines)

➢ Finance
▻ Composition optimale de portefeuilles
4
 Domaines d'applications

➢ Marketing
▻ Répartition d’un budget de publicité
▻ Nombre et localisation des points de vente
▻ Tarification (prix de vente, etc.)

➢ Gestion des ressources humaines

▻ Affectation de personnel à des tâches/postes
▻ Confection d’horaires de personnel

5
 Exemples de Succès

➢ Le raffinage du pétrole
Un modèle adopté en 1989 chez Texaco, une grande compagnie pétrolière, dicte la quantité des
différents pétroles bruts à transformer en chacune des sortes d’essence. Le modèle tient compte des
14 caractéristiques à considérer dans la composition d’une essence (dont le pourcentage de plomb et
de soufre, l’indice d’octane...).Texaco estime les économies réalisées grâce à ce modèle à 30 millions
de dollars par année.

➢ La gestion des forces policières

En 1989, la réorganisation du déploiement des policiers à San Francisco a pris en compte plusieurs
contraintes, telles que les congés, les vacances, les absences pour maladie, ainsi que la nécessité
d'intervenir rapidement dans les zones à risque. Cette réorganisation a permis d'économiser 11
millions de dollars par an. De plus, le temps d'attente après une demande d'intervention a été réduit
de 20 %.
6
Étapes RO Problème

➢ Formulation du problème Formulation

- Donnés
- Objectifs Modèle
- Contraintes
➢ Construction du modèle
- Choix du type de modèle Algorithme
- Choix variables, FO, Contraintes
➢ Résolution du modèle
Solution
- Choix/création d'un algorithme
- Implémentation
➢ Validation des résultats Validation
- Réalisabilité
- Analyse de sensibilité
Mise en
➢ Mise en œuvre œuvre
- Prise de décision
7
 Objectifs et compétences ciblées

Vous sensibilisez aux outils de la recherche opérationelle et ses applications.

▻ Modélisation : Apprendre à modéliser quelques problèmes réels

▻ Choix de méthode : Argumenter vos stratégies de résolutions et d'analyse
▻ Techniques Algorithmiques : Résoudre des problèmes d'optimisationréels
▻ Post-Analyse : Analyser la / les solution(s) trouvée(s)
▻ Décision : Acquérir une démarche rigoureuse de prise de décision

8
 Programme linéaire

Un programme linéaire est un programme qui peut s’écrire sous la forme (forme
inéquationnelle)

𝑀𝑖𝑛 𝑐 𝑇 𝑥
𝑠. 𝑐. 𝐴𝑥 ≤ 𝑏
Où 𝑥, 𝑐 𝜖ℝ𝑛 , b 𝜖ℝ𝑚 et 𝐴 est une matrice réelle de taille 𝑛 × 𝑚

La programmation linéaire est peut-être le cas particulier de programmation mathématique

(d’optimisation d’une fonction sous contrainte) le plus fréquemment rencontré dans l’industrie.
Beaucoup de problèmes se modélisent comme des programmes linéaires.

9
 Introduction à la Modélisation

Les étapes de formulation d’un PL

▰ Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d’un programme
linéaire :
▻ Identifier les variables du problème à valeur non connues (variables de décision) et les
représenter sous forme symbolique (x1, x2, x2, y1, ... ).
▻ Identifier les restrictions (contraintes) du problème et les exprimer par un système
d’équations linéaires.
▻ Identifier le critère de sélection (fonction objectif) et le représenter sous une forme
linéaire en fonction des variables de décision. Spécifier si le critère de sélection est à
maximiser ou à minimiser.
10
 Exemple

Exemple : Problème d’agriculture

Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et
celles de piments. Il dispose de 480 heures de main-d’oeuvre et de 440𝑚3 d’eau. Un
hectare de tomates demande 1 heure de main-d’oeuvre, 4𝑚3 d’eau et donne un
bénéfice net de 1000 dirhams. Un hectare de piments demande 4 heures de main-
d’oeuvre, 2𝑚3 d’eau et donne un bénéfice net de 2000 dirhams.
Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui permet pas de
cultiver plus de 90 hectares de tomates. Quelle est la meilleure allocation de ses
ressources ?

11
 Etape 1

Variables de décision

Identification des variables de décision. Les deux activités que l’agriculteur doit
déterminer sont les surfaces à allouer pour la culture de tomates et de piments :
𝑥1 : la surface allouée à la culture des tomates.
𝑥2 : la surface allouée à la culture des piments.

On vérifie bien que les variables de décision 𝑥1 et 𝑥1 sont positives :

𝑥1 ≥ 0 et 𝑥2 ≥ 0

12
 Etape 2

Identification des contraintes.

Dans ce problème les contraintes représentent la disponibilité des facteurs de production :

▻ Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte liée à la

limitation de la surface de terrain est
𝑥1 + 𝑥2 ≤ 150

▻ Eau : la culture d’un hectare de tomates demande 4𝑚3 d’eau et celle d’un hectare
de piments demande 2𝑚3 mais l’agriculteur ne dispose que de 440𝑚3 . La
contrainte qui exprime les limitations des ressources en eau est
4𝑥1 + 2𝑥2 ≤ 440
13
Etape 2

▻ Main-d’oeuvre : Les 480 heures de main-d'œuvre seront partager (pas

nécessairement en totalité) ente la culture des tomates et celles des piments. Sachant
qu’un hectare de tomates demande une heure de main-d'œuvre et un hectare de
piments demande 4 heures de main-d’œuvre alors la contrainte représentant les
limitations des ressources humaines
𝑥1 + 4𝑥2 ≤ 480

▻ Les limitations du bureau du périmètre irrigué : Ces limitations exigent que

l’agriculteur ne cultive pas plus de 90 hectares de tomates. Lacontrainte qui
représente cette restriction est
𝑥1 ≤ 90
14
 Etape 3

la fonction objectif
Identification de la fonction objectif. La fonction objectif consiste à maximiser le profit
apporté par la culture de tomates et de piments. Les contributions respectives 1000 et
2000, des deux variables de décision 𝑥1 et 𝑥2 sont proportionnelles à leur valeur. La
fonction objectif est donc

𝑧 = 1000 𝑥1 + 2000 𝑥2

15
 Exemple

Le modèle linéaire ou Programme linéaire (PL) est :

𝑀𝑎𝑥 𝑧 = 1000 𝑥1 + 2000 𝑥2

S.C.
𝑥1 + 𝑥2 ≤ 150
4𝑥1 + 2𝑥2 ≤ 440
𝑥1 + 4𝑥2 ≤ 480
𝑥1 ≤ 90
𝑥1 ≥ 0 et 𝑥2 ≥ 0

16
 Exemple

Exemple : Problème de fabrication

Une entreprise spécialisée dans la fabrication de matérielle informatique propose à ses

catalogues deux nouveaux ordinateurs l’IM4 et IM5. Chacun d’eux comporte le même
processeur mais ils diffèrent par le nombre de barrettes mémoire. Pour l’IM4 il y en a
deux et pour l’IM5 il y en a six. La capacité du marché à fournir ses composantes ne
dépassent pas les 10.000 unités de processeurs et 48.000 barrettes. Le processus
d’assemblage ne dure qu’une minute pour l’IM5 tandis que cette durée s’élève à 3
minutes pour l’IM4 et on ne dispose apriori que de 24.000 minutes maximum avant la
date de commercialisation. IM4 procure un profit de 400 euros et l’IM5 procure le
double (800 euros).
Quelles quantités des deux ordinateurs doit-on fabriquer ?
17
 Exemple

Exemple : Problème de transport

Une entreprise disposant de deux lieux de production doit envoyer ensuite ses produits finis vers 3
entrepôts régionaux pour répondre aux besoins locaux. l’entreprise peut transiter ses produits de
n’importe quelle usine vers n’importe quels entropôt. la capacité de production de la premiere
usine est de 100 milliers de tonnes, la deuxième peut fournir jusqu’a 120 milliers de tonnes. Les 3
entrepôts doivent accueillir (demande), respectivement 50, 70 et 80 milliers de tonnes de produits.
Le coût de transport pour une tonne entre les usines et les entrepôts est resumé dans le tableau ci-
dessous en milliers d’euro :
E1 E2 E3
U1 4 3 6
Quelles quantités doit-on transporter de
U2 3 5 3
chaque usines vers chaque depôt ?
18
 Exemple

Exemple : Problème d’une Manufacture

Une manufacture, qui fabrique trois produits, utilise trois ressources pour cette
production : services techniques, main-d’oeuvre et services administratifs. Le tableau
suivant donne les ressources nécessaires à la production d’une tonne de chacun des
produits, ainsi que diverses autres données pertinentes.
Produit Service technique Main-d’oeuvre Service administratif Profit (dhs/t)
P1 1 (h/t) 10 (h/t) 2 (h/t) 100
P2 1 (h/t) 4 (h/t) 2 (h/t) 60
P3 1 (h/t) 5 (h/t) 6 (h/t) 40
Temps disp 100 h 600 h 300 h

Construire un modèle linéaire qui indique comment planifier la production de façon à

maximiser les profits. Résoudre ce modèle et déterminer un plan de production
optimal. 19
 Exemple

Exemple : Problème d’alimentation

On se propose de réaliser une alimentation économique pour des cheveax, qui contient
obligatoirement 4 sortes de composants nutritifs, A, B, C et D. L’industrie alimentaire
produit précisément deux aliments M et N qui contiennent ces composants : 1Kg
d’aliment M contient 100g de A, 100g de C, 200g de D ; 1Kg d’aliment N contient
100g de B, 200g de C, 100g de D. Un animal doit consommer par jour au moins : 0.4
Kg de A ; 0.6 Kg de B ; 2 Kg de C ; 1.7 Kg de D. L’aliment M coûte 100 DH le Kg et
N coûte 40 DH le Kg. Quelles quantités d’aliments M et N doit-on utiliser par jour et
par animal pourréaliser l’alimentation la moins coûteuse ?

20
 Exemple

Exemple : Problème de traiteur

Un traiteur doit organiser son festival culturel annuel en continu pendant les cinq prochains jours. Il y a un
arrangement de dîner pour chaque équipe invitée. L’exigence de serviettes pendant ces cinq jours est :
Jour 1 2 3 4 5
Serviettes 80 50 100 80 150

En conséquence, le traiteur a été prié de fournir les serviettes conformément au calendrier ci-dessus. Une fois le
festival terminé, le traiteur n’a plus besoin de serviettes. Une nouvelle serviette coûte 2 euro. Les frais de lavage
pour une serviette utilisée sont de 0,5 euro par service ordinaire et de 1euro si service express est utilisé.
Une serviette donnée pour le lavage par service ordinaire est retournée le troisième jour, tandis que sous service
express, elle est retournée le lendemain.
Comment le traiteur doit répondre aux exigences des organisateurs du festival afin que le coût total soit
minimisé ?
21