Remerciez-le!

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

Cours de Recherche Opérationnelle et Optimisation Assuré par Mme Safa Chabouh 2

Cours de Recherche Opérationnelle et Optimisation Assuré par Mme Safa Chabouh 2ème année GM AU 2019-2020 Chapitre introductif Introduction à la Recherche Opérationnelle Qu’est-ce que la recherche opérationnelle? La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des questions d'utilisation optimale des ressources dans l'industrie et dans le secteur public. 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'intérêt public. S. Chabouh AU 2019/2020 3 Introduction à la Recherche Opérationnelle Il s’agit d’une discipline carrefour où se rencontrent aujourdhui l’économie, les mathématiques et l’informatique. Elle représente une démarche scientifique permettant de prendre rationnellement les bonnes décisions à engager dans une situation donnée. Ce qui revient à construire un « modèle » de la réalité, de déterminer la « décision» permettant d’optimiser (minimiser ou maximiser) une certaine « fonction économique», en présence de « contraintes » multiples. => Comment faire fonctionner un système d’une façon optimale sous conditions nécessitant l’allocation des ressources limitées S. Chabouh AU 2019/2020 4 Principe S. Chabouh AU 2019/2020 5 Problème réel de décision Contraintes imposées par l’environnement de l’entreprise : ressources limitées, capacité.. Objectifs économiques: Augmentation du profit, maitrise des coûts => survie économique de l’entreprise Modèle formulant ce problème (RO) Critères: fonction économique à optimiser Résolution du problème (RO) La bonne décision respectant les contraintes et assurant la meilleure valeur de la fonction économique Techniques de la RO 1. La programmation mathématique : programmation linéaire, programmation quadratique, programmation en nombres entiers, programmation dynamique, .. 2. la théorie des graphes et des réseaux, 3. La théorie des files d’attentes, 4. la simulation, 5. l’analyse statistique,.... S. Chabouh AU 2019/2020 6 Méthodes et techniques à étudier dans ce cours Partie 1: LA programmation linéaire PL Partie 2 Théorie de graphe Notions de bases Notions de bases Formulation des PL Problèmes de théories de graphes: formulation et résolution de chaque type de problèmes Résolution des PL: 2 méthodes Graphique / Simplexe 3 problèmes: - Plus court chemin; - Planification de projets, - Flot dans les réseaux S. Chabouh AU 2019/2020 7 INTRODUCTION À LA PL Chapitre 2 S. Chabouh AU 2019/2020 8 Introduction à la PL 1. Définition de la programmation linéaire 2. Formulation de PL a. Définitions et propriétés b. Exemple 3. Résolution graphique d’un PL a. Définitions et démarche b. Exemple 4. Notions géométriques : convexité et points extrêmes 5. Cas particuliers TD 1 : Modélisation et formulation des PL TD2 : Résolution Graphique S. Chabouh AU 2019/2020 9 Définition de la PL La programmation mathématique est la technique de la (RO) basée sur des modèles mathématiques. Elle met en jeu : (1) une fonction objectif, (2) des variables de décision à déterminer et (3) des contraintes à respecter. La programmation linéaire constitue la branche de la programmation mathématique pour laquelle toutes les fonctions du modèle (fonction objectif et contraintes) sont linéaires. Les problèmes de programmation linéaire sont généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit ou minimer un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat de la résolution d’un problème mathématique. S. Chabouh AU 2019/2020 10 Définition d’un PL S. Chabouh AU 2019/2020 11 Un programme linéaire (PL) est un 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. Formulation du PL Définitions & propriétés S. Chabouh AU 2019/2020 12 Formulation du PL Définitions & propriétés S. Chabouh AU 2019/2020 13 La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces hypothèses résument celles qui ont été données par G.B.Dantzig: 1. Les variables de décision du problème sont positives 2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces variables: fonction objectif (ou fonction économique, c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé de deux variables. 3. Les restrictions relatives aux variables de décision peuvent être exprimées par un ensemble d’équations linéaires. Ces équations forment l’ensemble des contraintes. Formulation du PL Définitions & propriétés La programmation linéaire impose un certain nombre de restrictions réduisant ainsi son champ d‟application. Ces restrictions sont :  la proportionnalité : les termes mesurant les coûts et les quantités de ressources utilisées doivent être proportionnels au niveau de chaque activité.  l‟additivité : les coûts et les ressources engagées par l‟utilisation conjointe de deux activités doivent être égaux aux termes correspondants à ces deux activités utilisées séparément. Les paramètres du problème en dehors des variables de décision ont une valeur connue avec certitude => Problème déterministe ! S. Chabouh AU 2019/2020 14 Formulation du PL Comment formuler un PL à partir d’une description d’un problème réel? => Exemple S. Chabouh AU 2019/2020 15 Formulation du PL Exemple S. Chabouh AU 2019/2020 16 L‟entreprise VITRE SAR SA. Fabrique des vitres de haute qualité pour portes et fenêtres. L‟entreprise souhaite lancer deux nouveaux produits : - Le produit 1 requiert des ressources dans l‟atelier 1 et 3 - Le produit 2 requiert des ressources dans l‟atelier 2 et 3. Dans l‟atelier 1, il s‟agit de construire des cadres en aluminium pour portes. Dans l‟atelier 2, il s‟agit de construire des cadres en bois pour fenêtres. L‟assemblage des vitres sur les cadres se fait dans l‟atelier 3 (voir figure 1). Formulation du PL Exemple S. Chabouh AU 2019/2020 17 Les deux types de produits sont fabriqués en lots de 20 unités. . Les responsables de cette entreprise se posent aujourd’hui la question suivante : Quel serait le mix de produits 1 et 2 le plus profitable à réaliser dans l’atelier 3 ? Afin de répondre à cette question, il faut disposer des données suivantes : Le nombre d’heures de production disponibles par semaine dans chaque atelier ; ce temps a été déterminé en tenant compte du temps déjà alloué aux autres produits. Le nombre d’heures de production nécessaires pour fabriquer un lot de produit donné dans chaque atelier. Le profit réalisé par la compagnie pour chaque lot de produit vendu. Formulation du PL Exemple S. Chabouh AU 2019/2020 18 L’entreprise cherche à déterminer le nombre de lots à réaliser par semaine pour les deux produits 1 et 2 dans l’objectif de maximiser le profit total, en respectant les restrictions imposées par les capacités limitées des machines des 3 ateliers. Démarche: 1) Chercher à identifier les variables de décisions = > les inconnus du problèmes 2) Traduire l’objectif en termes d’équation linéaire des Variables de décisions 3) Formuler les contraintes en fonction des variables de décision Formulation du PL Exemple S. Chabouh AU 2019/2020 19 S. Chabouh AU 2019/2020 20 Formulation du PL Exemple S. Chabouh AU 2019/2020 21 Formulation du PL Exemple Résolution des PL: la méthode Graphique Définitions: S. Chabouh AU 2019/2020 22 • Un vecteur x est une solution réalisable s‟il vérifie toutes les contraintes du problème (i.e. Ax ≤b et x ≥0). L’ensemble de tous les vecteurs, solution réalisable, est appelé domaine réalisable, noté (DR). • Une solution réalisable du problème de l’exemple précédent est représenté par le point (3, 2) : il suffit de vérifier que les contraintes sont satisfaites ; par contre le point (3, 6) n’est pas une solution réalisable du moment qu’il viole la contrainte (4.1). • Une solution réalisable x* est optimale si la valeur de Ct x* est la meilleure des valeurs de Ct x pour tout x, solution réalisable. Résolution des PL: la méthode Graphique La résolution graphique peut être utilisée pour des programmes linéaires ayant au plus deux variables de décision.  Démarche Dans le plan défini par les deux variables de décision: 1) on trace les différentes droites représentant les contraintes du problème. 2) Suivant le sens des inégalités, on détermine le domaine réalisable par l’ intersection des différents demi-plans réalisables. 3) On trace ensuite la ligne isoprofit (isocoût) représentant la fonction objectif. 4) Pour trouver une solution optimale, on déplace la ligne isoprofit dans la direction qui augmente la valeur de la fonction objectif (pour une maximisation). La ligne la plus haute coupant le domaine réalisable contient la ou les solutions optimales. S. Chabouh AU 2019/2020 23 S. Chabouh AU 2019/2020 24 Résolution Graphique de l’exemple (2,6) (4,3) x1 x2 X1=4 X2=6 3X1+2X2 = 18 0 , 18 2 3 12 2 4 5 3 2 1 2 1 2 1 2 1   +   + = x x x x x x sc x x Z Max (4,0) (0,6) (0,0) Remarque 2ème méthode: Recherche parmi les points extrêmes uploads/Finance/ cours-ro-2020.pdf