Cours imprimé Filière Génie Electrique

Ecole Nationale des

Sciences Appliquées

Recherche Opérationnelle
Pr. REGAD Youssef ensao ump
Département de Mécanique et Maths
yregadprofensao@[Link] y
Année universitaire 2023-2024
1ère Année Cycle Ingénieur
Filière Génie Electrique

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle

Préambule

La recherche opérationnelle s’appuie sur des connaissances

mathématiques importantes et varies, telle que :
ü Structures algébriques, algèbre linéaire;
ü Théorie des graphes;
ü Probabilité, processus stochastique, statistique;
ü Algorithmes et ses complexités;
ü Programmation par Matlab.

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 2

Pr. [Link] / Recherche Opérationnelle 1

 Cours imprimé Filière Génie Electrique

Programme du module 3M11 : Recherche Opérationnelle

Elément : Recherche Opérationnelle

• Cours : 32 heures A artir de 14h15
• TD/TP : 16 heures
• TP/TP : 16 heures

Cours : 4h par Semaine en 8 semaines

TP/TD: 4h par Semaine en 8 semaines

Mode d’évaluation de l’élément:

• Contrôle1 : 50%
• Contrôle2 : 50%

• Note générale = 0,70.(C1+C2)/2 + 0,[Link]

P : Note de Simulation (Mini-Projet sous RWARENA ou autre)

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 3

Programme du module 3M11 : Recherche Opérationnelle

Contenu de l’élément selon le Descriptif GELC:

qProgrammation linéaire : méthode de simplexe ;

qEléments de théorie des graphes : chemins optimaux : algorithme de ford ;
qProblème d’ordonnancement : méthode pert ;
qProblème de transport et applications : algorithme de ford-fulkerson ;
qAffectation : algorithme hongrois ;
qPhénomènes d’attente ;
qGestion scientifique des stocks ;
qUsure et remplacement des équipements.

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 4

Pr. [Link] / Recherche Opérationnelle 2

 Cours imprimé Filière Génie Electrique

Partie

TD/TP

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 5

Travaux pratiques et TD

q TD1 : Programmation linéaire/Simplexe

q TP1 : Simplexe : Excel et Matlab
q TD2 : Théorie des graphes : Algorithmes
q TP2 : Programmation des graphes en Matlab/Excel
q TD3 : Gestion des Stocks
q TP3 : Gestion des Stocks en Matlab/Excel

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 6

Pr. [Link] / Recherche Opérationnelle 3

 Cours imprimé Filière Génie Electrique

Partie

Cours

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 7

Sommaire

Chapitre 1 : Introduction : Recherche Opérationnelle

Chapitre 2 : Méthode de Simplexe
Chapitre 3 : Théorie des graphes

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle

Pr. [Link] / Recherche Opérationnelle 4

 Cours imprimé Filière Génie Electrique

1
Chapitre
Introduction :
Recherche Opérationnelle
1. C’est quoi R.O ?
2. Introduction à l’Optimisation
3. Types des problèmes d’optimisation
4. Classification des méthodes d’optimisation

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 9

1. C’est quoi R.O ?

La recherche opérationnelle est née pendant la Seconde Guerre mondiale des
efforts conjugués d'éminents mathématiciens (dont Von Neumann, Dantzig,
Blackett) à qui il avait été demandé de fournir des techniques d'optimisation 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. Le qualificatif opérationnelle
vient du fait que les premières applications de cette discipline avait trait aux
opérations militaires. La dénomination est restée par la suite, même si le domaine
militaire n'est plus le principal champ d'application de cette discipline, le mot
opérationnelle prenant alors plutôt le sens « d’effectif ». Ce sont donc ces
mathématiciens qui ont créé une nouvelle méthodologie caractérisée par les
mots-clés modélisation et optimisation.

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 10

10

Pr. [Link] / Recherche Opérationnelle 5

 Cours imprimé Filière Génie Electrique

1. C’est quoi R.O ?

Introduction à la RO
•Origines de la RO
- Période : 2ème guerre,
- Responsable : armée britannique
- Problèmes posés : implantation
optimale de radars de surveillance, le
management des
• bombardements
• anti sous-marins
• opérations de miniers…
RO = Application des mathématiques et des méthodes
scientifiques aux opérations militaires

RO = Approche scientifique à la prise des décisions, qui cherche

à déterminer comment concevoir et faire fonctionner un
système d’une façon optimale.
UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 11

11

1. C’est quoi R.O ?

• Techniques de la RO (pour plus d’info voir la section 2 de ce chapitre)

ØLa programmation mathématique
• programmation linéaire
• programmation quadratique
• programmation en nombres entiers
• programmation dynamique
ØAnalyses de réseaux et graphes
ØThéories des files d’attentes
ØSimulation
ØAnalyse statistique

• Champs d’application de la RO
- Industries
- Gouvernement
- Agences
- Hôpitaux
- Réseaux électriques
- Institutions d’éducation…
UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 12

12

Pr. [Link] / Recherche Opérationnelle 6

 Cours imprimé Filière Génie Electrique

Objectifs du cours :
Pour cela, on essayera de développer une double compétence :
q La capacité de formuler ces problèmes en des modèles
mathématiques : c'est-à-dire, partant de problèmes énoncés
de manière littéraire, de les traduire sous formes d'équations
mathématiques.
q La connaissance d'outils de résolution de ces problèmes : en
effet, une fois le problème formulé, souvent on tombe sur
un problème classique (tel celui de la gestion de stock),
pour lequel il existe des méthodes de résolution adaptées.

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 13

13

1. C’est quoi R.O ?

Méthodologie (0) Problème
de la RO:
(1) Identification du problème

(2) Collecte des données

(3) Modélisation (Formulation mathématique)

(4) Vérification du modèle

(5) Recherche des solutions

(6) Présentation des solutions

(7) Implémentation et recommandation

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 14

14

Pr. [Link] / Recherche Opérationnelle 7

 Cours imprimé Filière Génie Electrique

2. Introduction à l’Optimisation

Optimisation ?
q Rendre optimal, donner à quelque chose les meilleures
conditions d'utilisation, de fonctionnement, de
rendement, notamment en économie.
q Raisonnement ou calcul permettant de trouver les valeurs
d'un ou plusieurs paramètres qui correspondent au
maximum d'une fonction

L'optimisation est une approche mathématique pour la recherche de la

"meilleure décision/action" à partir d'un "ensemble d'alternatives".
Mathématiquement, l'optimisation se traduit par la recherche des points du
domaine (valeurs des variables de décision) en lequel la fonction étudiée
prend la valeur maximale ou minimale. En ces points, la fonction admet un
extremum, appelé aussi : optimum. Le plus souvent dans la pratique, les
variables de la fonction à optimiser sont soumises à certaines conditions
appelées "contraintes". Ces dernières peuvent être exprimées par des égalités
ou bien des inégalités.

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 15

15

2. Introduction à l’Optimisation

Domaines d’utilisation :
ü Ingénierie Trouver la solution
ü Automatique (les valeurs des paramètres)
ü Recherche opérationnelle Qui maximisent ou minimisent
ü Analyse numérique certains facteurs d’étude
ü Economie
ü Industrie … etc

PROFIT Coûts

qModéliser le problème réel sous forme d’une fonction mathématique, appelée

Fonction objectif : 𝑧 ou 𝑓(𝑥!, 𝑥", … )

qTrouver les valeurs des paramètres qui maximisent (ou minimisent) cette fonction :
𝑥!=? , 𝑥" =? , …
UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 16

16

Pr. [Link] / Recherche Opérationnelle 8

 Cours imprimé Filière Génie Electrique

2. Introduction à l’Optimisation

Exemple d’un problème d’optimisation :

Problème :
Un agriculteur voudrait cultiver deux sortes de légumes : des brocolis et des laitues.
Il pourrait pour cela planter toute sa terre si le besoin nécessite. Il utilise deux sortes
d’engrais (A et B).
• Les rendements des brocolis et des laitues sont de 𝟒 Kg/m" et 𝟓 Kg/m"
respectivement.
• Ses stocks sont de 8 litres d’engrais A et 7 litres d’engrais B.
• Les besoins en ces matières sont de 2 L/m" d’engrais A et 1 L/m" d’engrais B pour
les brocolis contre 1 L/m" d’engrais A et 2 L/m" d’engrais B pour les laitues.

L’agriculteur veut produire le

maximum de poids de légumes. Il
vous demande de l’aider !!!

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 17

17

2. Introduction à l’Optimisation

Etapes pour résoudre un problème d’optimisation :

1. Analyse et formulation du problème :
q Identifier les différentes variables, leurs natures et leurs domaines d’étude;
q Définir l’objectif du problème;
q Définir d’éventuelles contraintes.
2. Modélisation mathématique du problème :
q Formuler une fonction mathématique, appelée fonction objectif, qui décrit
le problème;
qEcrire les contraintes sous forme mathématique.
3. Choix d’une méthode de résolution du problème modélisé:
q Choisir une méthode d’optimisation adéquate au type du problème;
q Appliquer la méthode d’optimisation pour résoudre le problème modélisé.
Modélisation = créer un MODELE
qMoyen pour mieux comprendre la réalité utilisée pour représenter les propriétés fondamentales d’un certain
phénomène (ou d’un système étudié).
qProblèmes de gestion souvent complexes.
qNécessité fréquente d’ignorer certains paramètres pour tirer une version idéale, épurée: c’est un modèle

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 18

18

Pr. [Link] / Recherche Opérationnelle 9

 Cours imprimé Filière Génie Electrique

2. Introduction à l’Optimisation

Résolution du problème de l’exemple précédent :

1. Analyse et formulation du problème : 2. Modélisation du problème :
q Les variables de décisions seront :

x1 : Surface pour les brocolis (m2) de type réel.

x2 : Surface pour les laitues (m2) de type réel.

q Objectif du problème :

L'objectif est de déterminer les valeurs de x1 et x2

qui maximisent le poids total de la production.
=> Formuler une fonction f qui calcule le poids 3. Résolution du problème :
total.
Utiliser la méthode du simplexe de la
q Contraintes : programmation linéaire.
o Les stocks d'engrais A sont limités à 8 litres.
=> x1 = 3 m2, x2= 2 m2
o Les stocks d'engrais B sont limités à 7 litres.
o Les surface x1 et x2 ont des valeurs positives => le poids maximal qui peut être
produit sera : f(x1, x2) = 22 kg

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 19

19

2. Introduction à l’Optimisation

Quelques définitions de base en optimisation :

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 20

20

Pr. [Link] / Recherche Opérationnelle 10

 Cours imprimé Filière Génie Electrique

2. Introduction à l’Optimisation

Quelques définitions de base en optimisation :

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 21

21

2. Introduction à l’Optimisation

Quelques définitions de base en optimisation :

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 22

22

Pr. [Link] / Recherche Opérationnelle 11

 Cours imprimé Filière Génie Electrique

2. Introduction à l’Optimisation

Quelques définitions de base en optimisation :

Ou Min z

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 23

23

2. Introduction à l’Optimisation

Quelques définitions de base en optimisation :

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 24

24

Pr. [Link] / Recherche Opérationnelle 12

 Cours imprimé Filière Génie Electrique

2. Introduction à l’Optimisation

Quelques définitions de base en optimisation :

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 25

25

3. Types des problèmes d’optimisation

Types des problèmes d’optimisation :

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 26

26

Pr. [Link] / Recherche Opérationnelle 13

 Cours imprimé Filière Génie Electrique

3. Types des problèmes d’optimisation

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 27

27

3. Types des problèmes d’optimisation

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 28

28

Pr. [Link] / Recherche Opérationnelle 14

 Cours imprimé Filière Génie Electrique

3. Types des problèmes d’optimisation

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 29

29

3. Types des problèmes d’optimisation

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 30

30

Pr. [Link] / Recherche Opérationnelle 15

 Cours imprimé Filière Génie Electrique

4. Classification des méthodes d’optimisation

Classification des méthodes d’optimisation

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 31

31

4. Classification des méthodes d’optimisation

Déterministes OU Stochastiques

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 32

32

Pr. [Link] / Recherche Opérationnelle 16

 Cours imprimé Filière Génie Electrique

4. Classification des méthodes d’optimisation

Objectif unique Vs Objectif multiple

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 33

33

4. Classification des méthodes d’optimisation

Unimodale Vs Multimodale

34

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle

34

Pr. [Link] / Recherche Opérationnelle 17

 Cours imprimé Filière Génie Electrique

Résumé :

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 35

35

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 36

36

Pr. [Link] / Recherche Opérationnelle 18

 Cours imprimé Filière Génie Electrique

Voilà en bref une introduction

à Métaheuristiques ! C’est
quoi ces méthodes
d’optimisation ?

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 37

37

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 38

38

Pr. [Link] / Recherche Opérationnelle 19

 Cours imprimé Filière Génie Electrique

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 39

39

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 40

40

Pr. [Link] / Recherche Opérationnelle 20

 Cours imprimé Filière Génie Electrique

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 41

41

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 42

42

Pr. [Link] / Recherche Opérationnelle 21

 Cours imprimé Filière Génie Electrique

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 43

43

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 44

44

Pr. [Link] / Recherche Opérationnelle 22

 Cours imprimé Filière Génie Electrique

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 45

45

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 46

46

Pr. [Link] / Recherche Opérationnelle 23

 Cours imprimé Filière Génie Electrique

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 47

47

Pour plus d’info : [Link]

s umé
Ré

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 48

48

Pr. [Link] / Recherche Opérationnelle 24

 Cours imprimé Filière Génie Electrique

RECHERCHE OPÉRATIONNELLE

CLASSIFICATION DES MODELES

q Modèles physiques
§ Modèles iconiques
o Pour visualiser une solution pratique
o Modèles réduits, maquettes
§ Modèles analogiques
o Phénomène qu’on étudie pour représenter un autre
o Analogie électrique en hydraulique
q Modèles symboliques
§ Modèles mathématiques
é
o Déterministiques
és um
o Probabilistes ou stochastiques R
§ Modèles verbaux

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 49

49

qModèles mathématiques
s umé
Ré
v Modèles déterministiques
o Incertitude négligeable
o Résultats du phénomène prévu avec certitude
v Modèles probabilistes ou stochastiques
o Incertitude considérée comme facteur important du phénomène ou système
analysé

qClasse de modèles déterministiques

v Modèles de programmation linéaire
o Équations ou inéquations du premier degré représentant les contraintes du
problème
o Fonction économique qui traduit l’objectif de l’entreprise

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle 50

50

Pr. [Link] / Recherche Opérationnelle 25

 Cours imprimé Filière Génie Electrique

u mé
Rés

UMP – ENSA d’OUJDA Pr. Y. REGAD | 1ère Année Génie Electrique | Recherche Opérationnelle

51

Pr. [Link] / Recherche Opérationnelle 26