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 JOUDAR Nour-Eddine n.joudar@um5r.ac.ma, 2021/2022 JOUD

Recherche opérationnelle JOUDAR Nour-Eddine n.joudar@um5r.ac.ma, 2021/2022 JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 1 Sommaire 2 3 4.1 4 O b j e c t i f s d e c e c o u r s Introduction Programmation mathématique Sur quelques problèmes de théorie des graphes: 3.1 Modélisation mathématique 3.2 Résolution graphique 3.3 Résolution via méthode de simplexe 4.1 Problème du flot maximal 4.1 Problème du transport Problème du plus court chemin JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Objectifs du cours O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s Recherche opérationnelle • S'initier à la modélisation et la résolution de problèmes du monde réel et de problèmes d'optimisation surgissant en sciences d’ingénieurs. • Comprendre les qualités et les limites de différents modèles par rapport aux hypothèses, à la complexité et l’effort de résolution. • Expérimenter la résolution de problèmes à l'aide de modèles mathématiques en utilisant les logiciels disponibles, et interpréter correctement les résultats. • Acquérir les compétences de concevoir des algorithmes à base théories des graphes. • ……. JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Introduction Recherche opérationnelle ‘La recherche opérationnelle peut être définie comme l'ensemble des méthodes et techniques rationnelles 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’. [Wikipédia]. Modélisation En Recherche Opérationnelle (RO), modéliser un problème consiste à identifier: les variables intrinsèques (inconnues), les différentes contraintes auxquelles sont soumises ces variables et l'objectif visé (optimisation). Théorie des graphes La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non-symétriques (les graphes sont alors dits orientés) et sont appelés des flèches. O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Programmation Mathématique JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Introduction La programmation mathématique vise l’étude théorique des problèmes d’optimisation ainsi que la conception et la mise en œuvre des algorithmes de résolution. Applications : - Systèmes Informatiques, réseaux et ordinateurs,… - Electronique, automatique, réseaux et télécoms,… - Economie: microéconomique, modèles d’entreprise,… - Chimies, optimisation des procèdes chimiques, chimie industrielle… O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Définitions et concepts Notions de bases Ou La fonction ‘f’ est appelée la fonction objectif ou fonction économique. L’ensemble ‘C’ et sont appelées les contraintes (P) ou (P’). D é f i n i t i o n : P r o g r a m m e M a t h é m a t i q u e l i n é a i r e Programme linéaire: modèle mathématique dans lequel la fonction objectif et les contraintes sont linéaires. Un programme mathématique est défini comme suit: O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Définitions et concepts R e m a r q u e s • Dans toute la suite nous ne considérons que les programmes linéaires de type (P). En effet, (1) • Dans le problème (P), il n’y a pas de contraintes égalités. En effet: (2) O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Définitions et concepts D é f i n i t i o n • On appelle solution réalisable ou bonne solution efficace du problème (P), tout vecteur vérifiant les contraintes de (P). • On appelle domaine réalisable de (P), l’ensemble de toute les solutions réalisables de (P). • On appelle solution optimale ou optimum global de (P), une solution réalisable qui minimise f(x) sur l’ensemble de toutes les solutions. D é f i n i t i o n On dit que est un minimum local de (P) s’il existe un voisinage de tel que soit optimum global du problème suivant: O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Définitions et concepts P r o g r a m m e l i n é a i r e Dans le cas où et où et toutes les et les sont des applications linéaires, on dit qu’il s’agit d’un programme mathématique linéaire. Ce programme s’écrit sous cette forme: Où, , et O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Ainsi, un modèle linéaire doit vérifier les conditions suivantes: Le modèle doit avoir une fonction objectif à minimiser ou maximiser. La fonction objectif ainsi que les membres de gauches de chacune des contraintes doivent être des fonctions linéaires. Toutes les variables doivent être non négatives. Toutes les contraintes s’écrivent avec des égalités ou avec des inégalités larges. Définitions et concepts Autres classes des PM apparaissent dans la littérature à savoir: Programmes mathématiques non linéaires. Programmes mathématiques quadratiques. Programmes mathématiques convexes ……. O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022 Avant de résoudre un problème issu des sciences d’ingénieurs, il faut bien commencer par sa traduction par des relations mathématiques. Cette tâche exige l’identification de quelque composantes relatives à ce problème: Modélisation mathématique L’ensemble des actions: (Activités ou variables) qui s’offrent à l’agent de décision Les contraintes définissant la nature du système à étudier. L’objectif visé exprimé sous forme d’une fonction mathématique (fonction objectif ou économique) O b j e c t i f s d u c o u r s I n t r o d u c t i o n P r o g r a m m a t i o n m a t h é m a t i q u e P r o b l è m e s d e s g r a p h e s uploads/Science et Technologie/ cours-de-recherche-operationnel.pdf