Recherche Opérationnelle - Notes de Cours 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 P. Linéaire Algorithme de Simplex Le but de cet algorithme est de calculer la solution optimale d'un programme linéaire (PL) et la valeur correspondante v(PL). 46 rodrique kafando, PhD P. Linéaire Dualité en PL En programmation linéaire, la dualité est un principe puissant qui établit une relation entre deux programmes linéaires : un problème primaire et son problème dual associé. Chaque contrainte dans le problème primaire correspond à une variable dans le problème dual, et chaque variable primaire correspond à une contrainte dans le dual. Le Théorème de dualité stipule que si le problème primaire a une solution optimale, alors le problème dual a également une solution optimale, et les valeurs des deux fonctions objectifs à ces solutions optimales sont égales. 47 rodrique kafando, PhD P. Linéaire Dualité en PL On considère un problème linéaire (PL) mis sous forme standard : A est une matrice d'ordre (m × n). On définit le dual de (PL) comme suit : 48 rodrique kafando, PhD P. Linéaire Dualité en PL Le problème dual (D) peut s'écrire sous forme : Modélisation de divers duaux : le dual associé La détermination du dual d'un programme linéaire présenté sous forme canonique Nécessite son écriture sous forme standard 49 rodrique kafando, PhD P. Linéaire Dualité en PL C'est un programme linéaire sous forme canonique en minimisation 50 rodrique kafando, PhD P. Linéaire Dualité en PL Note : En estimant que le nombre d'itération de l'algorithme du simplex est Θ(m) (m nombre de contrainte). Si A est d'ordre m × n avec m >> n, il est clair que le résolution du problème dual apporte un gain en nombre d'opération par rapport à la résolution de (P). Si on note x et u les solutions optimales respectives du problème (P) et de son dual (D). 51 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 1 52 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 1 53 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 1 54 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 55 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 2 56 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 2 57 rodrique kafando, PhD P. Linéaire Dualité en PL Théorème : Etant donné un problème de programme linéaire (P) et (D) son problème dual alors : le dual du dual du programme linéaire (P) est identique à (P). 58 rodrique kafando, PhD P. Linéaire Dualité en PL Théorème : Etant donné un problème de programme linéaire (P) et (D) son problème dual alors : le dual du dual du programme linéaire (P) est identique à (P). 59 rodrique kafando, PhD P. Linéaire Dualité en PL Théorème : Etant donné un problème de programme linéaire (P) et (D) son problème dual alors : le dual du dual du programme linéaire (P) est identique à (P). 60 rodrique kafando, PhD P. Linéaire Dualité en PL Théorème : Etant donné un problème de programme linéaire (P) et (D) son problème dual alors : le dual du dual du programme linéaire (P) est identique à (P). 61 rodrique kafando, PhD P. Linéaire Dualité en PL Théorème : Etant donné un problème de programme linéaire (P) et (D) son problème dual alors : le dual du dual du programme linéaire (P) est identique à (P). 62 rodrique kafando, PhD Théorie des graphes 63 rodrique kafando, PhD Th. Graphes 64 rodrique kafando, PhD Th. Graphes L'histoire de la théorie des graphes débute peut-être avec les travaux d'Euler au XVIIIe siècle et trouve son origine dans l'étude de certains problèmes, tels que celui des ponts de Königsberg (les habitants de Königsberg se demandaient s'il était possible, en partant d'un quartier quelconque de la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir à leur point de départ), la marche du cavalier sur l'échiquier ou le problème de coloriage de cartes. De manière générale, un graphe permet de Les graphes constituent donc une méthode de représenter la structure, les connexions pensée qui permet de modéliser une d'un ensemble complexe en exprimant les grande variété de problèmes en se ramenant à relations entre ses éléments : réseau de l'étude de sommets et d'arcs communication, réseaux routiers, interaction de diverses espèces animales, circuits électriques, 65 rodrique kafando, PhD Th. Graphes Un graphe non orienté est un couple formé de deux ensembles finis : un ensemble X = {x, x2,... , xn} dont les éléments sont appelés sommets, et un ensemble ni A = {a1, a2,... , am} partie de l'ensemble des liens reliant deux éléments de X, appelé des arêtes. On notera a = {x, y} lorsque a est l'arête reliant x à y (ou y à x). On dit aussi que l'arête a est d'extrémités x et y. les sommets x et y sont des adjacentes. y a x 66 rodrique kafando, PhD Th. Graphes On parle de graphe orienté quand les arêtes ont un sens : C B D A E D 67 rodrique kafando, PhD Th. Graphes Terminologie de la théorie des graphes - Ordre d'un graphe : le nombre de sommets de ce graphe. - Degré d'un sommet : le nombre d'arêtes reliées à ce sommet. - Chaîne : suite nie de sommets reliés entre eux par des arêtes. - Chaîne simple : chaîne qui n'utilise pas deux fois la même arête. - Chaîne eulérienne : chaîne simple passant par toutes les arêtes d'un graphe - - Chaîne hamiltonienne : chaîne simple passant par tous les sommets d'un graphe une et une seule fois. - Cycle : chaîne qui revient à son point de départ. - Cycle eulérien : cycle simple passant par toutes les arêtes d'un graphe une et une seule fois. 68 rodrique kafando, PhD Th. Graphes Terminologie de la théorie des graphes - Cycle hamiltonien : cycle simple passant par tous les sommets d'un graphe une et une seule fois. - Chemin : une suite de sommets reliés par des arcs dans un graphe orienté. - Circuit : un chemin dont les sommets de départ et de n sont les mêmes. - Arbre : graphe connexe sans cycle simple et sans boucle. - Graphe eulérien : graphe qui possède un cycle eulérien. - Graphe hamitonien : graphe qui possède un cycle hamiltonien. - Graphe valué : graphe où des réels sont associés aux arêtes (dans ce cours les réels sont positives). - Longueur d'une chaîne : nombre des arêtes qui composent la chaîne. 69 rodrique kafando, PhD Th. Graphes Terminologie de la théorie des graphes - Valeur d'une chaîne : somme des valeurs des arêtes (arcs) d'une chaîne d'un graphe valué. - Distance entre deux sommets : longueur de la plus courte chaîne joignant ces deux sommets. - Diamètre d'un graphe : maximum des distances entre les sommets d'un graphe. 70 rodrique kafando, PhD Th. Graphes 71 rodrique kafando, PhD