Recherche opérationnelle

« FACULTE DES SCIENCES JURIDIQUES ECONOMIQUES ET SOCIQLES RABAT - AGDAL MASTER MONNAIE FINANCE BANQUE RECHERCHE OPERATIONNELLE ANIME PAR : Adil ELMARHOUM L’optimisation Les problèmes d'optimisation se rencontrent très fréquemment aussi bien dans le monde économique que dans le monde technique. Par exemple :  dans le domaine des télécommunications par exemple, on a souvent besoin d'optimiser un réseau en fonction du coût, du trafic etc...  dans la gestion d'entreprise, ces techniques sont des aides à la prise de décision (Recherche Opérationnelle) 2 Recherche Opérationnelle  Définition : « Outil mathématique de l’aide à décision qui permet de trouver une solution optimale ou bien une solution la plus proche possible de l’optimum » 3 Recherche Opérationnelle  Historique :  Deuxième guerre mondiale  Opérations militaires efficaces  Révolution industrielle  succès de la RO aux opérations militaires  RO dans l’industrie  Programmation linéaire  Méthode du simplexe (Dantzig 1947)  L’apparition des ordinateurs 4 Recherche Opérationnelle  Applications aux problèmes réels de grande envergure  arrivée des processeurs rapides  développement des bases de données  techniques d ’optimisation appliquées à de nombreux domaines  Domaines d’utilisation  militaire  transport  aéroport  route, trajet, livraison  horaire  contrôle des réseaux  infrastructures, distribution  Économie  Gestion d’entreprises  Analyse des décisions  etc. 5 Recherche Opérationnelle  Modélisation Problème réel : Modèle Solution Moyen pour mieux comprendre la réalité utilisée pour représenter les propriétés fondamentales d’un certain phénomène version idéale et épurée 6 Recherche Opérationnelle  Techniques de modélisation :  Techniques mathématiques  Techniques statistiques  Modèles de gestion des stocks  Modèles d’affectation  Modèles de files d’attente,  théorie des graphes  Modèles séquentiels  Modèles de remplacement  Modèles de compétition  Techniques de simulation  Méthodes heuristiques  etc. 7 Problème de Programmation Linéaire  Modèles mathématiques  Modèles déterministes  Incertitude négligeable  Résultats du phénomène prévu avec certitude  Modèles probabilistes ou stochastiques  Incertitude considérée comme facteur important du phénomène ou système analysé  Classe de modèles déterministes  Modèles de programmation linéaire 8 Problème de Programmation Linéaire Recherche Opérationnelle  Modélisation Formulation Problème réel : Algorithme Modèle mathématique Solution Programmation linéaire 10 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 ? 11 Application : Gestion optimale des ressources  Faire le mieux : coût minimum Meilleur profit …  Avec des ressources disponibles : Temps machines Ressources humaines Matières premières Postes de travail … 12 Programme linéaire  Problème Linéaire est un Problème d’optimisation consistant à maximiser ou minimiser une fonction objective linéaire de plusieurs variables de décision (fonction économique) soumise à un ensemble de contraintes exprimées sous forme d’équations ou d’inéquations linéaires.  La programmation linéaire est utilisée dans le domaine bancaire, forestier, industriel, pétrolier, du transport, de l’éducation, …  La terminologie est due à George B.

Dantzig, inventeur du programme de simplexe (1947) 13 Mise en forme d’un programme linéaire  Définir les variables de décision  ensemble des variables qui régissent la situation à modéliser  variables réelles, entières  Préciser la fonction objective  fonction mathématique composée des variables de décision qui représente le modèle  fonction 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  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 de la solution 14 Formulation mathématique d’un problème linéaire: Forme générale  Fonction objective : max (ou min) z c1 x1  c2 x2    cn xn  Contraintes : a11 x1  a12 x2    a1n xn  , ,  b1 a21 x1  a22 x2    a2 n xn  , ,  b2  am 1 x1  am 2 x2    amn xn  , ,  bm  Contraintes de non négativité : x j 0 , Avec, j 1,2, , n xj : variables de décision (inconnues) aij, bi, cj : paramètres du programme linéaire 15 Programmation linéaire Modèle linéaire :  fonction linéaire de plusieurs variables à optimiser  variables soumises à des contraintes :  Linéaires  restriction de non négativité 16      Terminologie du modèle Activités  Ensemble des actes et opérations à effectuer  j=1,2, … , n activités Ressources  Moyens disponibles pour effectuer les activités  bi, i=1,2, … , m ressources Quantités requises de ressources  Quantité unitaire de ressources consommées pour chaque activité  aij Niveau activation  Quantité de ressources affectée à une activité  xj niveau d’activation de l’activité j coût ou profit  Mesure de performance de l’allocation des ressources aux activités  cj 17 Terminologie de la solution  Solution réalisable (solution admissible)   Zone de solutions admissibles (région admissible)   Solution où toutes les contraintes du modèle sont satisfaites Ensemble de toutes les solutions réalisables Solution optimale   Solution réalisable où la fonction objective atteint la meilleure valeur (maximum ou minimum) Plusieurs solutions optimales possibles 18 Problème d’allocation des ressources Trois types de machines A, B et C produisent quatre produits différents I, II, III et IV. Chaque produit doit être traité par chacune des machines dans l’ordre Produits Type de machine I A B C 1,5 1 1,5 II 1 5 3 Profit par unité 5,24 7,30 III IV 2,4 1 3,5 1 3,5 1 8,34 4,18 Disponibilité hebdomadaire de chaque machine 2000 8000 5000 19 Modélisation But:  Établir la production hebdomadaire de chaque produit de façon à maximiser le profit Le modèle : xj : production hebdomadaire de chaque produit j Trouver les valeurs x1, x2, x3 et x4 qui maximisent le profit, considérant la limite de temps d’utilisation de chaque machine 20 Disponibilité Type de hebdomadaire de I II III IV chaque machine machine  Définissons 4 variables de décision : 1,5 1 2,4 1 2000 A x1 : la production hebdomadaire du produit I 1 5 1 3,5 8000 B x2 : la production hebdomadaire du produit II 1,5 3 3,5 1 5000 C x3 : la production hebdomadaire du produit III Profit xpar unité 5,24 7,30 8,34 4,18 4 : la production hebdomadaire du produit IV Produits Formulation du problème  Le profit associe à une production (x1, x2, x3, x4) est : z  5 ,24 x1  7 ,30 x2  8 ,34 x3  4 ,18 x4  Il ne faut pas dépasser la disponibilité hebdomadaire de chaque machine:A : 1 ,5 x  x2  2 ,5 x3  x4 2000 1 B: x1 C : 1 ,5 x1  5 x2  x3  3 ,5 x4 8000  3 x2  3 ,5 x3  x4 5000  On ne peut pas produire des produits négatifs : x1 , x2 , x3 , x4 0 21 Formulation du problème  Objectif : max z  5 ,24 x1  7 ,30 x2  8 ,34 x3  4 ,18 x4  Contraintes des machines : A: B: 1 ,5 x1 x1  x2  5 x2  2 ,4 x3  x3  x4  3 ,5 x4 2000 8000 C : 1 ,5 x1  3 x2  3,5 x3  x4 5000  Contraintes de non négativité : x1 , x2 , x3 , x4 0  En fait, il faudrait également imposer à x , x , x , x de ne 1 2 3 4 prendre que des valeurs entières. 22 Problème de recouvrement  Données : Les demandes journalières en chauffeurs dans l’entreprise de transport CTMLN Lu Ma Me Je Ve Sa Di 13 18 21 16 12 25 9 Les chauffeurs travaillent 5 jours d’affilée (et peuvent donc avoir 2 jours adjacents de congé n’importe quand dans la semaine)  Objectif : Déterminer les effectifs formant les 7 équipes possibles de chauffeurs de manière à :  Couvrir tous les besoins  Engager un nombre minimum de chauffeurs 23 Modélisation  Variables décision : on associe une variable de décision à chacune des 7 équipes possibles :  x1 : nombre de chauffeurs dans l’équipe du Lundi (repos le samedi et dimanche)  x2 : nombre de chauffeurs dans l’équipe du Mardi (repos le dimanche et Lundi) …  x7 : nombre de chauffeurs dans l’équipe du Dimanche (repos le Vendredi et Samedi)  Fonction objective : On peut minimiser le nombre total de chauffeurs.... »