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 provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur

Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 1 SOMMAIRE Chapitre 1 : Généralités a. La RO b. Les applications c. Méthodologie utilisée d. Références bibliographiques Chapitre 2 : Connaissances de base et compléments e. Plan, droites du plan : f. Ensemble g. Calculs sur les matrices h. Systèmes d’équations linéaires i. Systèmes d’inéquations linéaires Chapitre 3 : Optimisation Optimisation sans contraintes Optimisation avec contrainte Chapitre 4 : Programmation linéaire j. Motivation k. Bases et points extrêmes l. L’algorithme du simplexe Chapitre 5 : Théorie des graphes et application en RO m. Généralités : définitions ; chemins et circuits d’un graphe ; longueur d’un chemin ; graphe sans circuit ; graphe valué, chemin optimal n. Problème d’ordonnancement : - Enoncé d’un problème de recherche opérationnelle dans l’industrie - Formulation mathématique de la méthode MPM - Résolution du problème d’ordonnancement par MPM - Formulation mathématique de la méthode PERT - Résolution du problème d’ordonnancement par MPM o. Problèmes de flots - Enoncé d’un problème de recherche opérationnel dans le trafic routier - Formulation du problème sous forme de graphe valué - Résolution du problème Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 2 Chapitre 1 : Généralités I. Définitions de la R.O La recherche opérationnelle est l’approche scientifique pour la résolution des problèmes de gestion des systèmes complexes. C’est aussi l’ensemble des méthodes scientifiques pour résoudre des problèmes d’optimisation liées aux organisations du monde réel. II. Caractéristiques Cette discipline est à la croisée des mathématiques et de l’informatique. En effet, c’est un prolongement de l’algorithmique : domaine d’application de la théorie de la complexité algorithmique. Elle manipule des structures plus complexes comme les graphes, les polyèdres, etc. III. Quelques applications Parmi les applications classiques de cette discipline on peut citer : 1. Le voyageur de commerce (TSP) Un voyageur de commerce, basé à Abidjan, doit visiter ses clients à travers la Côte d’Ivoire. Il souhaite effectuer la traversée la plus courte possible. Modélisation : Instance : villes avec une matrice de distance Solution : tournée visitant chaque ville et revenant à Abidjan 2. Conception, configuration et exploitation des systèmes techniques complexes Réseaux de communication Système d’information 3. Gestion de la chaîne logistique Transport : Minimiser la distance totale parcourue selon la quantité de matière à transporter, la capacité des transporteurs, les points de ravitaillement en carburant, … Production : Maximiser le profit selon la disponibilité de la main d’œuvre, la demande du marché, la capacité de production, le prix de revient du matériel brut Stocké. Remarque : Très important dans le milieu industriel : production, transport, finance IV. Méthodologie Face à un problème pratique de décision on doit : o Faire ressortir les aspects mathématiques : contraintes, objectifs, simplification o Modéliser : Théorie des graphes, programmation linéaire, programmation par contraints (PPC), etc. o Analyser les modèles puis résoudre : étude de complexité, mise au point d’algorithmes. o Implémentation et analyse des résultats : valider par rapport à la demande o Déploiement des solutions V. Les outils (ou modèles) Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 3 1. Programmation linéaire Minimiser le coût/ maximiser le profit : Satisfaire la demande : avec des ressources limitées : quantités produites : 2. Optimisation combinatoire (OC) i. Trouver la meilleur solution parmi un nombre fini mais très grand de choix ii. un problème d’OC se caractérise par : - La présence de choix à faire parmi un ensemble fini d’alternance - Une notion de coût ou de gain, ou de perte - La nécessité de faire globalement les bons choix de manière à optimiser la valeur objectif. 3. Les graphes Valuation des arêtes= coût, temps, distances, capacité.  Meilleur chemin de i à j  Meilleur parcours : o Passant par chaque ville o Passant par chaque arête, etc. Bibliographie [1] De Werra, D., Liebling, T-M, and Hêche, J.-F, Recherche Opérationnelle pour ingénieurs, Tome 1. Presses Polytechniques et universitaire Romandes, 2003 [2] SAKAROVITCH, M, Optimisation combinatoire, Graphes et programmation linéaire. Hermann, Enseignement des sciences, Paris, 1984. [3] GUIDY WANDA JOSEPHINE, Recherche Opérationnelle : initiation. Tome 1. Collection Alpha Omega. 1993. Conclusion partielle Discipline à l’interface de l’informatique (algorithmique) des mathématiques (modélisation) et de l’économie (gestion, stratégies, etc.) la recherche opérationnelle permet d’opérer le meilleur choix avec les ressources disponibles. Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 4 Chapitre 2 : Connaissances de base et compléments. 1. Matrices blocs 1. Décomposition d’une matrice sous forme de blocs Définitions Soit , la matrice est une matrice bloc Exemple Soit la matrice bloc , on a : Soit . Donc A est une matrice bloc à deux lignes et deux colonnes. Par ailleurs on a : avec ; , , . De plus, Indices des lignes Indices des colonnes Somme Ecrite sous cette forme, A est appelée matrice-bloc Remarque - Soit A une matrice représentée par un tableau rectangulaire. En traçant des parallèles aux bords de ce tableau, on partage la matrice A en un certain nombre de sous-matrice appelées blocs. On dit qu’on a décomposé A en blocs. Notons les différents blocs, est le bloc situé sur la horizontale et la verticale. Une matrice décomposée en blocs est aussi appelée matrice blocs. Dans l’exemple précédent on a une parallèle au bord horizontal et une autre au bord vertical, donc A est une matrice bloc. - Les blocs situés sur la même ligne (portant le même numéro de ligne) doivent avoir le même nombre de lignes Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 5 - Les blocs situés sur la même colonne (portant le même numéro de colonne) doivent avoir le même nombre de colonnes. - Attention !!! la matrice suivante n’est pas définie par blocs : car les blocs situés sur la première ligne n’ont pas le même nombre de lignes. 2. Opérations sur les matrices blocs Dans le cas général, dans la mesure où les opérations sur les matrices sont compatibles les opérations sur les matrices par blocs s’effectuent comme sur les matrices ordinaires, le terme général étant une matrice. a. Addition Soient et deux matrices de même taille décomposée en bloc respectivement ( ) et ( ) ayant même nombre de lignes et même nombre de colonnes. La matrice se décompose sous forme de blocs ( ) avec : Il s’agit de l’addition des matrices. Ainsi, le bloc s’obtient en additionnant les blocs et . Exemple Dans le cas où et on a : a. Multiplication Soient et deux matrices décomposée en bloc respectivement ( ) et ( ). Si le nombre de colonnes de ( est égale au nombre de lignes de ( ) alors la matrice se décompose sous forme de blocs ( ) avec : Il s’agit de la multiplication et d’addition des matrices. Ainsi, le bloc s’obtient en additionnant les blocs et . Exemples Dans le cas où et on a : Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 6 Exercice Effectuer lorsque cela est possible les opérations sur les matrices blocs suivantes : Exercice 1 Soit la matrice 1. Découpé A en blocs pour que l’opération suivante soit définie : La décomposition de A est-elle unique ? 2. Effectuer le calcul précédent par blocs avec les différentes décompositions de A. Comparer les résultats obtenus avec le produit Exercice 2 Soit la matrice 1. Découpé A en blocs pour que l’opération suivante soit définie en bloc : Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 7 La décomposition de E est-elle unique ? Justifier 2. Effectuer le calcul précédent par blocs avec le produit . Exercice 3 Soit les matrices suivantes : 2. Droites, plans et hyperplans Activité 1 (Equations de droites, demi-plan) Le plan est rapporté à un repère orthonormé Oxy. Soit les droites d’équations suivantes . . . . 1. Représenter graphiquement ces droites. 2. Quelles sont les positions relatives de ces droites. 3. Déterminer les coordonnées des points d’intersection de D1 avec les axes Ox et Oy 4. Déterminer les coordonnées du point d’intersection de D1 et D3 (méthode de substitution ou combinaison) Activité 2(Intersection de droites, de plans) Le plan est rapporté à un repère orthonormé . Soit la droite d’équations suivantes . 1. Représenter graphiquement cette droite. En combien de régions elle partage le plan ? Quel est l’intersection de deux droites non parallèles ? Support de cours provisoire de Recherche Opérationnelle Classe : STIC 1 Auteur : Dr KIMOU Prosper 8 2. On se place dans muni de sa base canonique. Que représente l’équation suivante : . En combien de sous-espace ce plan divise t-il l’espace (appelé demi- espace). Quelle est l’intersection de deux plans non parallèles ? On généralise les résultats de l’activité 3 à . Dans ce cas, on parle d’hyperplans et de uploads/Science et Technologie/ moncourderostic-1-2018.pdf