Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Recherche Opérationnelle 1 Histoire de la Recherche Opérationnelle Née pendant

Recherche Opérationnelle 1 Histoire de la Recherche Opérationnelle Née pendant la seconde guerre mondiale avec la constitution d’équipes de chercheurs en vue d’étudier les problèmes stratégiques et tactiques dans les opérations militaires L’objectif étant de trouver la meilleure allocation des ressources militaires limitées à travers l’usage de techniques quantitatives Premier succès obtenu en 1940 par le Prix Nobel de physique Patrick Blackett qui résolut un problème d’implantation de radars de surveillance A partir des années 1950, la recherche opérationnelle fait son entrée dans les entreprises. Ces dernières créent à cette époque des services de recherche opérationnelle. La discipline comme à être enseignée dans les universités et les grandes écoles 2 Histoire de la Recherche Opérationnelle Au milieu des années 70, sans doute à cause d’un excès d’enthousiasme au départ et de l’inadéquation des moyens informatiques à l’application des méthodes de la recherche opérationnelle (RO), la discipline n’a pas été à la hauteur des attentes A partir du milieu des années 90, on assiste à un retour en force de la RO, les outils informatiques étant maintenant à la hauteur des méthodes proposées par la RO On assiste depuis à une explosion du nombre de logiciels commerciaux et d’applications dans divers domaines 3 Présentation de la Recherche Opérationnelle La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des cas d’utilisation optimale des ressources. 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’interet publics 4 Présentation de la Recherche Opérationnelle Dans l’expression « recherche opérationnelle », il y a recherche et il y a opération Recherche (en référence à une approche scientifique) est composée de: Analyse des besoins, collection des données Construction d’un modèle mathématique Résolutions, conception d’une méthode pour calculer la solution Validation, expérimentation pour tester l’adéquation de la solution au modèle, ajustements Opération : ensemble de moyens à employer afin d’obtenir un résultat Recherche opérationnelle: comment organiser les opérations (production, transport, construction, communication, planification, santé, militaire, …) d’une organisation d’une manière optimale 5 Définition de la Recherche Opérationnelle La recherche opérationnelle ou la science de la décision est la discipline des méthodes scientifiques utilisables pour élaborer de meilleures décisions Elle peut être définie comme l’ensemble des méthodes et techniques orientées vers la recherche du meilleur choix dans la façon d’opérer en vue d’aboutir au résultat visé ou au meilleur résultat possible La RO traduit des énoncés ou des cahiers de charge liés à des problématiques spécifiques sous forme de méthodes et des démarches à base d’équations mathématiques, des algorithmes et des outils statistiques La compétence à développer (en RO) est de: apprendre à modéliser mathématiquement un problème, et d’utiliser les outils disponibles pour le résoudre. 6 Introduction programmation linéaire La programmation linéaire (PL) est l’une des plus importantes techniques d’optimisation utilisées en recherche opérationnelle. Ceci est du à la facilité de la modélisation et l’efficacité des algorithmes développés en programmation linéaire. L’objectif de la PL est de déterminer de façon optimale l’utilisation des ressources Les situations économiques demandent souvent qu’on optimise une fonction sous plusieurs contraintes L'importance de l’optimisation et la nécessité d’un outil simple pour modéliser des problèmes de décision ont fait de la PL un des champs de recherche les plus actifs au milieu du siècle précèdent 7 Définition programmation linéaire La programmation linéaire est une branche des mathématiques appliquées et plus précisément de l’optimisation dont l’objectif est de minimiser ou de maximiser une fonction numérique à plusieurs variables sachant que ces dernières sont liées par des relations appelées contraintes Le principe de la PL est fondé sur le fait que: La fonction à optimiser appelée fonction objectif ou fonction économique a une expression linéaire Les expressions des contraintes sont toutes linéaires 8 Composantes d’un programme linéaire et exemple Soit une usine qui produit deux ciments rapportant 50 $ et 70 $ la tonne. Pour fabriquer une tonne de ciment 1, il faut 40 min de calcination dans un four et 20 min de broyage. Pour fabriquer une tonne de ciment 2, il faut 30 min de four et 30 min de broyage. Le four et l’atelier de broyage sont disponibles 6 h et 8 h par jour. Combien de ciment de chaque type peut-on produire par jour pour maximiser le bénéfice ? Ce problème se modélise par le programme linéaire (PL) suivant, en notant x1 et x2 les quantités de ciment à fabriquer. (1) Max z = 50x1 + 70x2 (2) 40x1 + 30x2 ≤ 360 (3) 20x1 + 30x2 ≤ 480 (4) x1, x2 ≥ 0 9 Composantes d’un programme linéaire et exemple La ligne (1) représente le profit total z qui est le critère à optimiser, appelé aussi fonction objectif (nom composé), fonction de coût ou fonction économique. Max signifie que ce critère doit être maximisé ; on écrirait Min pour minimiser. Les autres lignes désignent des contraintes. La contrainte (2) concerne la disponibilité du four : elle stipule que le temps total de calcination requis par les ciments ne doit pas dépasser 360 min ou 6 h. La contrainte (3) décrit de même la disponibilité du broyeur. Les contraintes (4) précisent les domaines des variables. 10 Forme générale d’un programme linéaire et extensions Plus généralement, on appelle programme mathématique un problème d’optimisation d’une fonction-objectif de plusieurs variables en présence de contraintes. Le programme est dit linéaire si la fonction et les contraintes sont toutes des combinaisons linéaires de variables. Il a la forme générique suivante. Il comporte n variables non négatives (3), m contraintes d’égalité ou d’inégalité (2), et la fonction-objectif à optimiser (1). Le coefficient de coût ou de profit de la variable xj est noté cj, celui de la variable xj dans la contrainte i est noté aij. La contrainte i a un second membre constant bi. Les contraintes simples de positivité ne sont pas incluses dans les m contraintes, car elles sont gérées à part par les algorithmes. (1) Max ou Min z = (2) i = 1 … m : ≤ , = ou ≥ b ∀ i (3) j= 1 … n: x ∀ j ≥ 0 • 11 Forme générale d’un programme linéaire et extensions Des valeurs de variables qui vérifient toutes les contraintes, comme x1 = 4 et x2 = 2 dans l’exemple des ciments, forment une solution réalisable (SR) du PL. Une solution réalisable est optimale si aucune autre solution n’a un profit supérieur. Si les variables sont astreintes à être entières, on obtient un programme linéaire en nombres entiers (PLNE). Un programme linéaire en 0-1 est un cas particulier de PLNE dont les variables ne peuvent prendre que deux valeurs 0-1 ; ces variables sont dites booléennes, binaires ou de décision. Un PL mixte comprend à la fois des variables continues et des variables entières. Enfin, à partir du moment où au moins une contrainte ou la fonction objectif n’est plus une combinaison linéaire de variables, on a affaire à un programme non linéaire (PNL). 12 Formes matricielles classiques et conversions Notons x = (x1, x2, ... , xn)T le vecteur des variables, b = (b1, b2, ... , bm)T celui des seconds membres des contraintes, c = (c1, c2, ... , cn) les coûts ou profits associés aux variables, et A la matrice m × n des aij On peut alors écrire un PL sous forme matricielle. Deux formes sont courantes : la forme canonique avec des contraintes ≤, utilisée pour la résolution graphique, et la forme standard avec égalités, pour la résolution algébrique par des algorithmes. Par convention, la forme standard est souvent exprimée avec des seconds membres positifs. Forme canonique Forme standard Max c.x Max c.x A.x ≤ b A.x = b x ≥ 0 x ≥ 0 13 Formes matricielles classiques et conversions Ces formes ne servent qu’à simplifier les présentations théoriques. Dans la réalité, un PL peut présenter des égalités et des inégalités, et les logiciels du marché acceptent heureusement ces mélanges. On peut facilement convertir les formes mixtes en formes classiques. Ainsi, toute contrainte d’égalité peut être remplacée par deux inégalités. ≤ bi - ≤ - bi = bi ↔ 14 Formes matricielles classiques et conversions On peut convertir une inégalité en égalité en ajoutant ou soustrayant une variable d’écart ei ≥ 0, propre à chaque contrainte i. À l’optimum, pour une inégalité ≤ concernant la disponibilité d’une ressource i, cette variable indique la quantité inutilisée de la ressource. D’autres conversions sont possibles. Ainsi, on peut passer d’une maximisation à une minimisation, car maximiser z revient à minimiser -z. Il ne faut pas oublier alors de multiplier par -1 la valeur de la fonction-objectif trouvée par la minimisation ! L’exigence de variables positives n’est pas restrictive, car une variable xj non contrainte en signe peut toujours s’écrire comme une différence x’j – x"j de deux variables non négatives. ≤ bi et ei ≥ uploads/Science et Technologie/ recherche-operationnelle-new1.pdf