Recherche Opérationnelle PDF

Recherche Opérationnelle 1 rodrique kafando, PhD Objectifs d'apprentissage Comment utiliser des algorithmes pour résoudre différents types de problèmes d'optimisation ? OS1: Connaître les concepts fondamentaux de la rec...

Recherche Opérationnelle 1 rodrique kafando, PhD Objectifs d'apprentissage Comment utiliser des algorithmes pour résoudre différents types de problèmes d'optimisation ? OS1: Connaître les concepts fondamentaux de la recherche opérationnelle. OS2: Comprendre comment résoudre un problème d’optimisation en utilisant la programmation linéaire OS3: Utiliser la programmation en nombres entiers (IP) pour résoudre des problèmes d’optimisation linéaires avec des contraintes d'intégralité imposées. OS4 : Utiliser la programmation non-linéaire pour résoudre des problèmes d’optimisation 2 rodrique kafando, PhD Définition La Recherche Opérationnelle (RO) est une discipline scientifique qui utilise des méthodes analytiques, en particulier la modélisation mathématique, pour aider à prendre des décisions complexes et optimiser les processus. Elle implique l'utilisation de techniques mathématiques et statistiques pour analyser des systèmes dans divers domaines. 3 rodrique kafando, PhD Motivation Elle est essentielle pour comprendre et améliorer les processus dans notre monde interconnecté. La RO offre des outils pour aborder des défis multidimensionnels dans des domaines variés comme la logistique, la santé publique, et les finances. 4 rodrique kafando, PhD Applications Gestion des catastrophes : Optimisation des plans d'évacuation et de distribution de l'aide. Transports publics : Amélioration des horaires et des itinéraires pour une efficacité et une économie maximales. Logistique : Optimisation des itinéraires de livraison pour réduire les coûts et améliorer la rapidité. Santé : Planification efficace des horaires du personnel médical. 5 rodrique kafando, PhD Programmation mathématique en RO La programmation mathématique est une technique utilisée en RO pour résoudre des problèmes de décision en formulant des modèles mathématiques. Elle implique la maximisation ou la minimisation d'une fonction objectif, tout en respectant un ensemble de contraintes. L'objectif est d'optimiser les processus et les décisions en trouvant la meilleure solution possible dans les limites données. 6 rodrique kafando, PhD Programmation mathématique en RO Types de problèmes Optimisation des ressources : Allocation efficace des ressources limitées, comme dans la gestion de l'inventaire ou la planification des ressources humaines. Planification de la production : Détermination des quantités optimales de produits à fabriquer pour maximiser les profits ou minimiser les coûts. Gestion des réseaux de transport : Optimisation des itinéraires de livraison pour réduire le temps et les coûts de transport. 7 rodrique kafando, PhD Programmation mathématique en RO Processus de résolution Formulation du problème : Définir clairement le problème, identifier la fonction objectif et les contraintes. Choix de la méthode : Sélectionner la méthode appropriée de résolution (par exemple, la programmation linéaire, la programmation en nombres entiers). Résolution et analyse : Utiliser des logiciels spécialisés pour trouver la solution optimale et analyser les résultats pour des décisions éclairées. 8 rodrique kafando, PhD Composantes d’un programme math. Une composante mathématique est un ensemble de méthodes utilisées pour formuler et résoudre des problèmes quantitatifs, en particulier dans les domaines de l'optimisation et de la prise de décision. Importance des composantes Chaque composante d'un programme mathématique joue un rôle crucial dans la définition et la résolution de problèmes complexes. La compréhension claire de ces composantes est essentielle pour l'élaboration de modèles mathématiques efficaces et pertinents. 9 rodrique kafando, PhD Composantes d’un programme math. Les composantes Clés ○ Fonction objectif : L'objectif à maximiser ou minimiser. ○ Contraintes : Les limites ou conditions que les solutions doivent respecter. ○ Variables de décision : Les variables qui seront manipulées pour atteindre l'objectif. ○ Paramètres et données : Les valeurs et informations nécessaires à la formulation du modèle. 10 rodrique kafando, PhD Fonction objectif Les composantes Clés La fonction objectif est une formule mathématique qui définit l'objectif à atteindre dans un problème d'optimisation. Elle peut être formulée pour maximiser (comme le profit) ou minimiser (comme le coût) une certaine quantité. Exemples de fonctions objectifs : ○ Maximisation : Maximiser les bénéfices d'une entreprise. ○ Minimisation : Minimiser les coûts de production ou de transport. Rôle clé de la fonction objectif : ○ La fonction objectif guide le processus de prise de décision en définissant précisément ce qui doit être optimisé. ○ Elle est au cœur de la formulation d'un modèle de programmation mathématique. 11 rodrique kafando, PhD Les contraintes Les contraintes sont des restrictions ou des conditions imposées aux variables de décision dans un modèle mathématique. Elles définissent les limites dans lesquelles la solution doit se situer. Types de contraintes : ○ Contraintes d'égalité : Exigences qui doivent être exactement satisfaites (par exemple, la somme des allocations ne doit pas dépasser le budget total). ○ Contraintes d'inégalité : Limites supérieures ou inférieures (par exemple, la quantité produite ne doit pas excéder la capacité de production). Rôle des contraintes : ○ Les contraintes assurent que les solutions trouvées sont non seulement optimales mais également réalisables et pratiques dans un contexte réel. 12 rodrique kafando, PhD Variables de décision Les variables de décision sont les éléments inconnus ou les choix à faire dans un problème de programmation mathématique. Elles représentent les aspects du problème qui peuvent être contrôlés ou modifiés pour atteindre l'objectif. Exemples de variables de décision : Quantités de produits à fabriquer. Nombre d'heures de travail à allouer. Allocation de ressources dans différents projets. Importance des variables de décision : Elles sont essentielles pour modéliser le problème et fournissent la base sur laquelle les optimisations sont réalisées. 13 rodrique kafando, PhD Paramètres et Données Les paramètres et les données sont les éléments numériques qui alimentent le modèle mathématique. Ils peuvent inclure des coûts, des capacités, des demandes, et d'autres valeurs quantitatives. Importance des paramètres et données : La précision et la fiabilité des paramètres et des données sont cruciales pour l'exactitude des solutions produites par le modèle. Gestion des Données : Collecte, vérification, et mise à jour régulière des données pour assurer la pertinence et l'actualité du modèle. 14 rodrique kafando, PhD  Modélisation en RO Introduction à la modélisation mathématique Les types de modèles en RO Études de cas simples 15 rodrique kafando, PhD Intro - Modélisation Mathématique Définition et Objectifs La modélisation est l'art de transformer des problèmes du monde réel en formulations mathématiques pour faciliter leur compréhension et leur résolution. L'objectif principal est de fournir un cadre structuré pour optimiser les décisions et prévoir les conséquences des actions. 16 rodrique kafando, PhD Intro - Modélisation Mathématique Étapes de la modélisation en RO - Identification du problème : Identifier le problème signifie comprendre le contexte, les objectifs à atteindre, et les défis à surmonter. - Définition des objectifs : Les objectifs doivent être clairs, mesurables, et directement liés aux décisions à prendre. - Sélection des variables de décision : Choisir les leviers d'action que le modèle contrôlera pour atteindre les objectifs. 17 rodrique kafando, PhD Intro - Modélisation Mathématique Étapes de la modélisation en RO (suite) - Formulation des contraintes : Les contraintes représentent les limitations ou conditions que les solutions doivent respecter. - Construction de la fonction objectif : La fonction objectif exprime mathématiquement ce que le modèle cherche à optimiser, comme maximiser le profit ou minimiser les coûts. 18 rodrique kafando, PhD Intro - Modélisation Mathématique 1- Détecter le pb 4- Collecter des données 3- Élaborer un modèle 5- Résolution du pb 2- Formuler le pb 7- Prise de 6- Validation du modèle décision/implementation 19 rodrique kafando, PhD Programmation Linéaire 20 rodrique kafando, PhD P. Linéaire Problème On veut acheter 4 types d'alimentations A, B, C et D qui ont chacun une teneur en calories et en vitamines comme suite : 21 rodrique kafando, PhD P. Linéaire But Le consommateur cherche à minimiser le coût sachant qu'il a besoin d'au moins 12 calories et 7 vitamines. Modélisation 22 rodrique kafando, PhD P. Linéaire Formulation Note: 23 rodrique kafando, PhD P. Linéaire Forme standard d’un PL 24 rodrique kafando, PhD P. Linéaire Exemple 25 rodrique kafando, PhD P. Linéaire Exemple Demo 26 rodrique kafando, PhD  27 rodrique kafando, PhD P. Linéaire Exemple Demo 28 rodrique kafando, PhD P. Linéaire Exemple Demo 29 rodrique kafando, PhD P. Linéaire Exemple Demo 30 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Principe de la méthode simplex La résolution de (PL) se fait en se déplaçant de solution de base réalisable non optimale en solution de base réalisable et optimale. 31 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Principe de la méthode simplex La résolution de (PL) se fait en se déplaçant de solution de base réalisable non optimale en solution de base réalisable et optimale. Forme standard 32 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Principe de la méthode simplex La résolution de (PL) se fait en se déplaçant de solution de base réalisable non optimale en solution de base réalisable et optimale. Forme standard 33 rodrique kafando, PhD  34 rodrique kafando, PhD  35 rodrique kafando, PhD  36 rodrique kafando, PhD  37 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Définition On appelle base tout sous-matrice carrée régulière (m × m) extrait de A (il existe au moins une, puisque rg(A) = m ) Soit I une base. Alors en permutant les colonnes de A, on peut toujours mettre A sous la forme où est la sous matrice formée par les colonnes de A qui ne sont pas dans la base. De même on peut partitionner la variable x en et la fonction coût f en comme il montre la figure 38 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Définition On appelle base tout sous-matrice carrée régulière (m × m) extrait de A (il existe au moins une, puisque rg(A) = m ) (1) On appel solution de base (associé à la base AI ), la solution particulière de (1) obtenue on faisant xI = 0. On peut alors déterminer xI de façon unique par la résolution du système : 39 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Définition Une solution de base est dite réalisable si xI ≥ 0, autrement dit si : (AI )−1.b ≥ 0. Une base correspondant à une solution de base réalisable est appelée base réalisable. Une solution de base est dite dégénéré si le vecteur xI à des composantes nulles. On a: 40 rodrique kafando, PhD  41 rodrique kafando, PhD  42 rodrique kafando, PhD  43 rodrique kafando, PhD  44 rodrique kafando, PhD  45 rodrique kafando, PhD