COURS : Recherche Opérationnelle
Cours : 3A IGE
Dr. Soufia BENHIDA
[email protected] Casablanca
Recherche Opérationnelle
1) INTRODUCTION À LA RECHERCHE
OPÉRATIONNELLE
2) RÉSOLUTION DE PROGRAMMES LINÉAIRES
3) CAS PARTICULIERS
4) DUALITÉ
5) SOLVEURS ET LANGAGES DE
MODÉLISATION
6) ANALYSE DE LA SENSIBILITÉ
7) PLANIFICATION ET ORDONNANCEMENT
Introduction à la
Recherche
Opérationnelle
Histoire
En 1940, Patrick Blackett est
appelé par l'état-major anglais à
diriger la première équipe de
recherche opérationnelle, pour
résoudre certains problèmes tels
que l'implantation optimale
de radars de surveillance…
RO = Application des
mathématiques et des
méthodes scientifiques aux
opérations militaires
La Recherche Opérationnelle
Objectifs:
• Résoudre des problèmes concrets à l’aide des
Méthodes Scientifiques,
• Fournir à l’Agent de décision l’information qui lui
permet de prendre « les Meilleures Décisions »
La Recherche Opérationnelle traite des problèmes
rencontrés dans l’industrie, le commerce,
l’administration, la défense ………
5
La Recherche Opérationnelle
Aider l’entreprise à déterminer sa politique de
manière scientifique:
La direction : l’aide à la décision,
Le Transport : Optimisation des coûts de transport
Les Réseaux (Réseaux informatiques, Réseaux de
distribuions, …) : Optimisation – Flot de valeur
maximale- Flot de valeur maximale à coût minimum, ..
La Gestion des Grands Systèmes et de machines
Gestion du personnel
Gestion d’argent
….
6
La Recherche Opérationnelle
Les deux aspects de la Recherche Opérationnelle sont :
Définition d’un modèle mathématique,
Résolution de ces problèmes mathématiques à l’aide
d’Algorithmes
Introduction à la PL
La programmation linéaire = méthode permettant d’optimiser,
c'est-à-dire rendre le plus grand ou le plus petit possible, une
fonction linéaire, cela sous certaines contraintes définies par des
inégalités.
Il s’agit de problèmes d’optimisation ; elle traite le cas particulier
où la fonction que l’on cherche à optimiser est linéaire tandis que
les contraintes sont définies par des équations et/ou des
inéquations linéaires
PROGRAMME LINÉAIRE
PL
• problème d’optimisation consistant à
• maximiser (ou minimiser) une fonction objectif linéaire
• de n variables de décision
• soumises à un ensemble de contraintes exprimées sous
forme d’équations ou d’inéquations linéaires
La terminologie est due à George B. Dantzig,
inventeur de l’algorithme du simplexe (1947)
Programmation Linéaire
Formulation du modèle mathématique
• Définir le problème
Quelle est la nature exacte du problème?
Quel est l’objectif recherché?
Quelles sont les conditions d’opération?
Quels sont les paramètres à considérer? Quelle
influence?
Quel est le degré de précision requis?
MISE EN FORME MATHÉMATIQUE
Définir les variables de décision
• ensemble des variables qui régissent la situation à modéliser
• variables réelles, entières, binaires
Préciser la fonction objectif
• fonction mathématique composée des variables de décision qui
représente le modèle physique modélisé
• fonction linéaire, non-linéaire
Préciser les contraintes du problème
• ensemble des paramètres qui limitent le modèle réalisable
• équations ou inéquations composées des variables de décision
Préciser les paramètres du modèle
• constantes associées aux contraintes et à la fonction objective
PROGRAMMATION LINÉAIRE
Validation du modèle et des résultats
• S’assurer
que le modèle développé est conforme à la réalité
que les résultats sont valides dans toutes les conditions
Conception du système d’application
• Possibilité d’utiliser des logiciels spécialisés
Implantation
FORMULATION MATHÉMATIQUE
D’UN PROGRAMME LINÉAIRE
FONCTION OBJECTIF
• Maximiser ou minimiser
• z = c1x1 + c2x2 + c3x3 + … + + cnxn
Contraintes
• a11x1 + a12x2 + a13x3 + … + a1nxn (, =, ) b1
• a21x1 + a22x2 + a23x3 + … + a2nxn (, =, ) b2
• am1x1 + am2x2 + am3x3 + … + amnxn (, =, ) bm
Contraintes de non-négativité
• xj 0 ; j = 1, 2, 3, … n
avec
• xj variables de décision (inconnues)
• aij, bi, cj paramètres du programme linéaire
TERMINOLOGIE DE LA SOLUTION
Solution réalisable
• Solution où toutes les contraintes du modèle sont
satisfaites
Zone de solution
• Ensemble de toutes les solutions réalisables
Solution optimale
• Solution réalisable où la fonction objectif atteint la
meilleure valeur, maximum ou minimum
• Plusieurs solutions optimales possibles
EXEMPLE: PROBLÈME D'ALLOCATION DE
RESSOURCES
Exemple 1
Vous disposez de
• 8 kg de pommes
• 2,5 kg de pâte
• 6 plaques
pour confectionner des chaussons et des tartes
Pour faire un chausson, il vous faut:
• 150 g de pommes
• et 75 g de pâte
Chaque chausson est vendu 3 $
Pour faire une tarte, il vous faut
• 1 kg de pommes
• 200 g de pâte
• et 1 plaque
Chaque tarte est divisée en 6 parts vendues chacune 2 $
Que faut-il cuisiner pour maximiser le chiffre d'affaires de
la vente ?
PROBLÈME D'ALLOCATION DE
RESSOURCES
Définissons 2 variables de décision
• x1 : le nombre de chaussons confectionnés
• x2 : le nombre de tartes confectionnées
Le chiffre d’affaires associé à une production (x1; x2) est
z = 3x1 + (6 x 2)x2 = 3x1 + 12x2
Il ne faut pas utiliser plus de ressources que disponibles
• 150x1 + 1000x2 8000 (pommes)
• 75x1 + 200x2 2500 (pâte)
• x2 6 (plaques)
On ne peut pas cuisiner des quantités négatives :
x1 et x2 0
MODÈLE: PROBLÈME
D'ALLOCATION DE RESSOURCES
Pour maximiser le chiffre d’affaires de la vente, il faut
déterminer les nombres x1 et x2 de chaussons et de
tartes a cuisiner, solution du problème
Max z = 3x1 + 12x2
Sujet à
150x1 + 1000x2 8000
75x1 + 200x2 2500
x2 6
x1 ; x2 0
En fait, il faudrait également imposer à x1 et x2 de ne
prendre que des valeurs entières
Exemple 2
TRAITEMENT DE DONNÉES
QUELLE EST MA FONCTION OBJECTIF ?
QUELLES SONT MES VARIABLES DE DECISIONS ?
JE DOIS CHERCHER L’OBJECTIF SOUS QUELLES CONTRAINTES ?
QUELLE EST MA FONCTION OBJECTIF ?
Pour déterminer la fonction objectif il faut déterminer l’objectif du problème
MAXIMISER LE PROFIT DU FABRIQUANT
FO: Max F
QUELLES SONT MES VARIABLES DE DECISIONS ?
X1 : Nombre d’Armoire
X2 : Nombre de Tables
QUELLES SONT MES CONTRAINTES ?
On dispose de 6H de travail
On dispose de 45 m2 de bois
1 Armoire 1h de travail et 9m2 de Bois
1 Table 1h de travail et 5m2 de Bois
LE PROFIT?
1 Armoire 8 Euro
1 Table 5 Euro
Matrice de Modélisation
X1 X2 Q
H 1 1 6
B 9 5 45
C 8 5
MERCI POUR VOTRE ATTENTION
