Remerciez-le!

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

Support de cours de recherche opérationnelle Master1 MRI Dr SAMIA HARIZ Support

Support de cours de recherche opérationnelle Master1 MRI Dr SAMIA HARIZ Support de cours de recherche opérationnelle . Définition de recherche opérationnelle La recherche opérationnelle désigne l’ensemble des méthodes et des techniques quantitatives d'analyse et de synthèse, orientées vers la recherche de la meilleure manière d'effectuer des choix, ou bien de prendre les meilleures décisions, en vue d'aboutir au meilleur résultat possible. Il s’agit d’une branche des mathématiques appliquées, dans laquelle sont abordés des problèmes d’aide à la décision et d’optimisation, sujets qui ont pu être explorés en profondeur avec l’apparition et la vulgarisation de l’informatique et de l’algorithmique vers la fin du XXe siècle. Historique La recherche opérationnelle est apparue « officiellement » pendant la Seconde Guerre mondiale, lorsqu’une équipe de scientifiques anglais a été chargée de conseiller l’armée, afin de mieux utiliser les ressources miliaires. Néanmoins, plusieurs mathématiciens s’étaient déjà penchés sur des problèmes liés à la recherche opérationnelle par le passé, contribuant ainsi à son apparition. Formulation du problème Initialement nous avons besoin de bien comprendre le problème et le système dans lequel il s’inscrit. Pour cela, il est important d’identifier l’objectif, à savoir, ce qui va être optimisé (par exemple, nous pouvons chercher à maximiser un bénéfice ou à minimiser un coût). Ensuite, nous devons identifier les variables à considérer. Pour cela, il est important d’identifier les entrées et les sorties du système. Parfois, nous pourrons contrôler ces variables (par exemple une quantité à produire) et dans d’autres circonstances, ces variables seront en dehors de notre portée (par exemple, le prix d’une matière première). Finalement il est capital de déterminer les limitations du système donnant les restrictions à considérer. Construction du modèle Dans cette phase, nous devons établir le modèle mathématique nous permettant de représenter le système. Ce modèle doit relier les variables de décision avec les contraintes et l’objectif du système. Il est important de déterminer si le modèle est déterministe ou non-déterministe, c’est-à-dire, s’il se comporte de manière prévisible ou s’il contient une source de hasard. 1 Support de cours de recherche opérationnelle Master1 MRI Dr SAMIA HARIZ Ensuite, nous construirons des modèles mathématiques composés de trois éléments : une fonction économique ou (fonction objectif), des variables de décision et des contraintes. Solution du modèle Une fois le modèle établi, nous pouvons procéder à la recherche d’une solution satisfaisante. La solution est donnée par le meilleur résultat obtenu pour la fonction objectif en fonction de la valeur des variables de décision définies. Pour obtenir cette solution, nous pouvons utiliser différents algorithmes en fonction du type de problème. En plus de la solution du modèle, on peut effectuer une analyse de sensibilité, afin de connaître les réactions du modèle à des changements dans les spécifications et les paramètres du système. Cette analyse est particulièrement importante lorsque les paramètres ne sont pas exacts et les restrictions peuvent être erronées et/ou imprécises. Validation et mise en œuvre La dernière étape consiste à valider la pertinence du modèle pour représenter avec précision le comportement du système, puis mettre en œuvre les résultats obtenus. Pour cela, on peut soumettre le modèle à des données passées disponibles et voir s’il produit les résultats connus (cette technique est appelée « backtesting » lorsque des données historiques réelles sont utilisées). Nous devons donc interpréter les résultats afin d’identifier les actions d’amélioration du système. Lorsque le modèle construit peut servir dans un autre problème ou contexte, il est important de bien documenter chaque étape de cette méthode. Modèle mathématique Un modèle mathématique est une représentation formelle d'un phénomène industriel, physique, économique, humain, etc., réalisée afin de mieux étudier celui-ci à l’aide des outils, des techniques et des théories mathématiques. Tel qu’il est présenté par la Figure 1, un modèle mathématique comporte 3 éléments : 2 Support de cours de recherche opérationnelle Master1 MRI Dr SAMIA HARIZ Figure 1 : Composantes d’un modèle mathématique Variables de décision Les variables de décision sont les choix ou les inconnues qui doivent être déterminés par la solution du modèle. On les appelle « variables de décision » car le décideur contrôle leurs valeurs. Par exemple, on peut vouloir décider les quantités à produire de deux références catalogue x1 et x2. Fonction objectif La fonction objectif dépend des valeurs des variables de décision et sert à déterminer le comportement du système. Elle sert donc de critère pour trouver la meilleure solution au problème abordé. Le but du problème étant de minimiser ou maximiser cette fonction dans la recherche de l'optimum. La fonction objectif est souvent appelée « fonction économique » ou « fonction de coût ». Par exemple, on peut chercher à maximiser le gain donné par les quantités produites des références x1 et x2. Ce gain peut être calculé comme le résultat des ventes (quantité produite multipliée par le prix de vente) moins les coûts de revient des références (quantité produite fois coût unitaire). On a donc f(x) = x1*prix1 + x2*prix2 - x1*coût1 - x2*coût2. Contraintes Les contraintes sont des relations entre une ou plusieurs variables de décision qui permettent de limiter les valeurs qu’elles peuvent prendre. Les contraintes servent à tenir compte des limitations du système (technologiques, économiques, environnementaux etc.) afin de restreindre les variables de décision à un sous- ensemble de valeurs possibles et pertinentes. Par exemple, on peut avoir un contrat avec un client qui impose une production d’au moins une quantité b1 de la référence x1. On peut également admettre que l’entreprise ne peut pas produire des quantités négatives. 3 x ∈Rn, x x1, x2,..., xn x est un élément de l'espace réel à n dimensions Rn f (x) ∈Rn f(x) est un élément de l'espace réel R x ∈X ∈ Rn x est un élément du sous ensemble X de l'espace réel à n dimensions Rn VARIABLES DE DÉCISION FONCTION OBJECTIF CONTRAINTES Support de cours de recherche opérationnelle Master1 MRI Dr SAMIA HARIZ On a donc, x1 ≥ b1 et x2 ≥ 0. Autres éléments :les paramètres Les paramètres sont des valeurs qui mettent en relation les variables de décision avec les contraintes et la fonction objectif. Il s’agit de valeurs que le décideur ne contrôle pas (coûts des matières premières, demande client, délai d’approvisionnement, etc.). Ces paramètres peuvent être déterministes ou non-déterministes. Par exemple, si le délai de réapprovisionnement d’un stock est déterministe, on peut intégrer ce paramètre dans le modèle en admettant qu’il est égal à 1 semaine. En revanche, s’il n’est pas déterministe, on peut l’intégrer dans le modèle avec une approche statistique, en admettant que le délai suit une loi de probabilité normale dont la moyenne est égale à 1 semaine et l’écart type est égal à 2 jours. II.1 La programmation linéaire II.1 Méthode graphique La programmation mathématique recouvre un ensemble de techniques d’optimisation sous contraintes qui permettent de déterminer dans quelles conditions on peut rendre maximum ou minimum une fonction objectif Z(Xj) de n variables Xj liées par m relations ou contraintes Hi(Xj) ≤ 0. Nous commencerons les exemples des outils de la Recherche Opérationnelle par l'examen d'un outil auquel il est très souvent fait référence dans nombre de problèmes économiques, qu'ils concernent l'entreprise ou l'Etat : la programmation linéaire. Nous n'analyserons pas celle-ci sous l'angle de la signification économique des différents concepts qu'elle met en œuvre; nous nous préoccuperons plutôt des techniques de résolution usuelles des programmes linéaires. Nous serons amenés à introduire des notions économiques comme le « profit », le « coût », les « ressources », mais ce sera davantage par simple souci d'illustration que pour indiquer le champ d'application des techniques exposées. L'objectif de la programmation linéaire (P.L.) est de trouver la valeur optimale d'une fonction linéaire sous un système d'équations d'inégalités de contraintes linéaires. La fonction à optimiser est appeler "fonction économique" (utilisée en économie dans le cadre d'optimisations) et on la résout en utilisant une méthode dite "méthode simplexe" dont la représentation graphique consiste en un "polygone des contraintes". Lorsqu'on peut modéliser un problème sous forme d'une fonction économique à maximiser dans le respect de certaines contraintes, alors on est typiquement dans le cadre de la programmation linéaire.1 1 Paul Feautrier, recherche operationnelle, 2004. 4 Support de cours de recherche opérationnelle Master1 MRI Dr SAMIA HARIZ Soit une fonction économique Z telle que: Où les sont des variables qui influent sur la valeur de Z, et les les poids respectifs de ces variables modélisant l'importance relative de chacune de ces variables sur la valeur de la fonction économique2. Les contraintes relatives aux variables s'expriment par le système linéaire suivant: Sous forme générale et matricielle ce genre de problème s'écrit: 3 Voyons un exemple qui consiste à résoudre le problème simple suivant: Exemple 1 : Une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2. Les temps d'usinage sont pour P1 de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2 et pour P2 de 4 heures dans l'atelier A1 et de 3 heures dans l'atelier A2. Le temps de disponibilité de l'atelier A1 est de 160 heures et celui de uploads/Management/ support-ro-mri.pdf