RECHERCHE OPERATIONNELLE
Jihan KHODER
18/02/19
Plan du cours
18/02/19
Plan du cours
•Partie 2: Graphes.
•Chapitre 1: Notions fondamentales sur les graphes.
•Chapitre 2: Probleme du plus court chemin.
•Chapitre 3: Probleme de planifications d’un projets.
Jihan KHODER 18/02/19
INTRODUCTION A LA RO
Jihan KHODER 18/02/19
INTRODUCTION A LA RO
1. Introduction : Historique de la RO
2. Domaines d’applications
3. Notions de modèles.
4. Qu’est-ce que la R.O. ?
Jihan KHODER 18/02/19
HISTORIQUE
Théorie des Programmation Combinatorique,
décisions mathématique Théorie des graphes
Pascal (1654) Fourier (1824) Sainte-Laguë (1926)
Fermat (1654) D. König (1936)
Bernouilli (1713)
RO 2e guerre mondiale:
1ère application: militaire
Simplexe
Premier “grand” algorithme (1947)
1er ordinateur 1ère application commerciale (1956)
INTRODUCTION A LA RO
• Origines de la RO:
• Periode : 2nd guerre mondiale.
• Responsable: Armee britanique.
• Problemes poses: implantation optimale de radars de
surveillance, le management des:
1. Bombardements.
2. Anti – sous marins
3. Operations de miniers.
Jihan KHODER 18/02/19
INTRODUCTION A LA RO
• Qu’est-ce que la recherche opérationnelle ?
L’étude des opérations d’une organisation ou d’un
processus (système) dans le but d’accroître son efficacité
d’une facon optimale..
• Où celà sert-il
Dans de très nombreux domaines et en particulier
en GENIE ( MECANIQUE- CIVIL ----- etc)
QUELQUES APPLICATIONS
• 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.)
o Localisation d’entrepôts/usines (détermination du nombre optimal,
localisation, affectation des clients aux entrepôts/usines)
o Gestion des inventaires (niveaux et stratégies de commandes optimales)
o 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.)
QUELQUES APPLICATIONS
• Gestion des resssources humaines:
o Affectation de personnel à des tâches/postes
o Confection d’horaires de personnel.
o Négociations de conventions collectives
• Analyse de l’impact monétaire (et autres) de
changements envisagés aux conventions de travail
QUELQUES APPLICATIONS
• Planification de la production:
o Gestion des inventaires
o Ordonnancement des tâches
• Planification des télécommunications:
o Conception et dimensionnement de réseaux (câblés et cellulaires)
o Design de réseaux résistants aux pannes
o Tarification des services
• Etc …
Critère 1: le temps
Critère 2 : le coût
Calcul du chemin de
temps (ou coût)
minimal
Jihan KHODER 18/02/19
Chemin
trouvé
facilement
par un
algorithme
de
graphe
Jihan KHODER 18/02/19
Ordannnancement d’atelier
Ordonnancer les passages sur les
machines
Jihan KHODER 18/02/19
Gestion de la production,
des stocks et de la maintenance
• Suivi de production
• Respect des délais
• Gain de temps
• Respect du client
• Meilleure compétitivité
• Organisation du travail
• résistance aux aléas
• …
Jihan KHODER 18/02/19
Ordannnancement De Chantier
Jihan KHODER 18/02/19
Gestion des ressources
• Gestion de la forêt
• Gestion de l'eau
• …
17
Jihan KHODER 18/02/19
Constellation de satellites
• Objectif:
• couvrir un territoire à moindre coût
• Déterminer
• Le nombre de satellites à lancer
• Leurs orbites
Jihan KHODER 18/02/19
Router Calcul d’itinéraires
• en fonction du traffic :
• Données actualisées toutes les 5
minutes
• Informations nécessaires en temps réel
• Temps disponible pour calculer un
itinéraire
Jihan KHODER 18/02/19
C’est Quoi la RO
• RO = Applications mathematiques et des methodes
scientifiques aux operations militaires.
• RO= Approche scientifique a la prise des decisions, qui
cherche a determiner comment concevoir et faire
resoudre un systeme d’une facon optimale.
Jihan KHODER 18/02/19
C’est Quoi la RO
• Définition :
« Outil mathématique de l’aide à la décision qui
permet de trouver une solution optimale ou bien, pour
des problèmes difficiles : un problème qui remplit la
seconde condition,
une solution la plus proche possible de l ’optimum ».
Jihan KHODER 18/02/19
• PARTIE I
• PROGRAMMATION LINEAIRE
Jihan KHODER 18/02/19
Programmation Linéaire
• Modèle linéaire
o fonction linéaire, de plusieurs variables, à
optimiser
o variables soumises à des contraintes :
• linéaires
• restrictions de non négativité
Jihan KHODER 18/02/19
Programmation Linéaire
• Modélisation
Formulation Algorithme
Problème Modèle
Solution
réel mathématique
Programmation
Linéaire
Jihan KHODER 18/02/19
Programmation Linéaire
• Gestion optimale de ressources
o Faire le mieux :
• coût minimum
• meilleur profit
o Avec les ressources disponibles :
• temps machine
• ressources humaines
• matière première
• postes de travail
.
.
.
Jihan KHODER 18/02/19
Modèle Linéaire
• Exemple :
3 types de machines A, B et C
pour produire
4 produits différents I, II, III et IV.
Chaque produit doit être traité par chacune des
machines dans l’ordre
Jihan KHODER 18/02/19
Modèle Linéaire
• Exemple :
Caractéristiques des produits & machines
Disponibilité
Type de
Produits hebdomadaire de
machine I II III IV
chaque machines
A 1,5 1 2,4 1 2000
B 1 5 1 3,5 8000
C 1,5 3 3,5 1 5000
Profit par unité 5,24 7,30 8,34 4,18
Jihan KHODER 18/02/19
Modèle Linéaire
• Exemple :
– But : établir la production hebdomadaire de chaque
produit de façon à maximiser le profit.
• Le modèle :
xj - production hebdomadaire du produit j.
but : trouver les valeurs de x1 , x2 , x3 et x4 qui
maximisent le profit, considérant la limite de temps
d’utilisation de chaque machine
Jihan KHODER 18/02/19
Modèle Linéaire
• Exemple :
o But : max z = 5,24 x1 + 7,30 x2 + 8,34 x3 + 4,18 x4
o Contraintes des machines :
A : 1,5 x1 + x2 + 2,4 x3 + x4 2000
B: x1 + 5 x2 + x3 + 3,5 x4 8000
C : 1,5 x1 + 3 x2 + 3,5 x3 + x4 5000
o Contraintes de non négativité :
x1 , x2 , x3 , x4 0
Jihan KHODER 18/02/19
Formulation
Forme générale :
max (ou min) z = c1 x1 + c2 x2 + ... + cr xr
Sous contraintes
ai 1 x1 + ai 2 x2 + ... + ai r xr , , bi , i = 1,2, … , m
xj 0 , j = 1,2, … , r
Jihan KHODER 18/02/19
Remarques
max (ou min) z = c1 x1 + c2 x2 + ... + cr xr
sc
ai 1 x1 + ai 2 x2 + ... + ai r xr , , bi , i = 1,2, … , m
xj 0 , j = 1,2, … , r
contraintes de
• xj - variables de décision non négativité
• z, fonction à optimiser - fonction objectif ( f. o. )
• cj , ai j et bi - constantes connues (expressions
linéaires)
Jihan KHODER 18/02/19
Résolution Graphique
• Problème à deux variables de décision x1 et x2 :
o f. o. - droite dans 2
o contraintes - hemi-plans de 2
o P = (x1 , x2 ) - solution admissible (réalisable) si P satisfait
toutes les contraintes
o région admissible - l’ensemble des solutions admissibles
o solution optimale - solution admissible qui optimise la f.o.
Jihan KHODER 18/02/19
Exemple 1
x2 max z = 5 x1 + 3 x2
sc
3 x1 + 5 x2 15
5 x1 + 2 x2 10
x1 , x2 0
O x1
3x1 + 5x2 = 15
5x1 + 2x2 = 10
Jihan KHODER 18/02/19
Exemple 1
z1 x A z3 ;
z 2 z3 max z = 5 x1 + 3 x2
2
A intersection des
deux contraintes sc
3 x1 + 5 x2 15
z = 5x1 + 3x2
5 x1 + 2 x2 10
A
x1 , x2 0
O x1 z
3x1 + 5x2 = 15
direction = - c1 / c2
5x1 + 2x2 = 10 = -5/3
Jihan KHODER 18/02/19
z2
z1 Exemple 2
x2 max z = 2,5 x1 + x2
AB z2 sc
3 x1 + 5 x2 15
z = 2,5x1 + x2
5 x1 + 2 x2 10
A
x1 , x2 0
O
B x1 z
3x1 + 5x2 = 15
direction = - c1 / c2
5x1 + 2x2 = 10 = -2,5
Jihan KHODER 18/02/19
RESUME
• Région admissible borné :
o polygone dont les côtés sont des segments des droites représentant les
contraintes linéaires du problème
o un point P à l ’intersection de 2 côtés du polygone est un point extrême
o solution optimale:
• point extrême solution optimale unique
• côté du polygone infinité de solutions optimales
( la valeur de la f. o. est unique )
Jihan KHODER 18/02/19
Cas spéciaux
• Région admissible non borné
contraintes : Une solution
unique x x = 1
max z = -3 x1 + 4 x2 x2 1 2 z3
sc z2 0,5x1 + x2 = 2
xx11 -- xx22 -1
-1 z1
-0,5 xx11 ++
-0,5 xx22 22 A
xx11,, xx22 00
x1
Jihan KHODER 18/02/19
Cas spéciaux
• Région admissible non borné
contraintes :
Une infinité
de solutions
max z = -x1 + 2 x2 x2 x1 x2 = 1
sc z1 0,5x1 + x2 = 2
x1 - x2 -1 z3
-0,5 x1 + x2 2 z2
x1 , x2 0
x1
Jihan KHODER 18/02/19
Cas spéciaux
• Région admissible non borné
contraintes :
Pas de solution
max z = x1 + x2 x2 finie x1 x2 = 1
sc z3 0,5x1 + x2 = 2
x1 - x2 -1 z2
-0,5 x1 + x2 2
z1
x1 , x2 0
x1
Jihan KHODER 18/02/19
RESUME
• Région admissible non borné :
o solution optimale:
• point extrême solution optimale unique
• côté de la région admissible
infinité de solutions optimales
( la valeur de la f. o. est unique )
• pas de solution optimale finie
Jihan KHODER 18/02/19
Un dernier cas spécial
• Région admissible vide
contraintes incompatibles
er
1 cas :
x2 2x1 + 3x2 = 6 des hemi
x1 + x2 = 5
plans est vide
x1 x2 = 1 x1 + x2 5
- 2 x1 + 3 x 2 6
x1 - x2 1
x1
x 1 , x2 0
Jihan KHODER 18/02/19
Un dernier cas spécial
• Région admissible vide
contraintes incompatibles
x2 ème
2 cas :
x1 + x2 = 1
contrainte de
x1 + x2 = 1
non négativité
1 + x2 -1
pasxsatisfaite
x1
- x1 + x2 1
x1 , x2 0
Jihan KHODER 18/02/19
GENERALISATION
• Problème à r > 2 variables de décision solution
graphique ?!?!
• Vocabulaire suggéré par la méthode graphique :
1 - région admissible : région convexe d’un espace de dimension r ( polyèdre
convexe )
2 - un point P à l’intersection de s 2 hyperplans représentant les contraintes est
un point extrême du polyèdre
Jihan KHODER 18/02/19
Généralisation
• Problème à r > 2 variables de décision
solution graphique ?!?!
• Vocabulaire suggéré par la méthode graphique :
3 - solution optimale:
• unique point extrême du polyèdre
• infinité de solutions optimales frontière
du polyèdre = hyperplan de dimension < r
( la valeur de la f. o. est unique )
Jihan KHODER 18/02/19
RESUME
• Région admissible :
– polyèdre convexe (polygone, dans 2) dont les côtés
représentent les contraintes linéaires du problème
– borné ou non borné
– un point P à l ’intersection de s 2 contraintes est un
point extrême
– solution optimale:
» point extrême solution optimale unique
» côté de la région admissible infinité de solutions
{{ optimales ( la valeur de la f. o. est unique )
» pas de solution optimale finie
• METHODE DE SIMPLEXE