Remerciez-le!

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

Ecole Mohammadia d’Ingénieurs Polycopié de Recherche Opérationnelle N. SBIHI ww

Ecole Mohammadia d’Ingénieurs Polycopié de Recherche Opérationnelle N. SBIHI www.almohandiss.com 2 Plan du cours: Introduction générale à la recherche opérationnelle. Programmation linéaire. Algorithme du simplexe. Dualité. Post-optimisation. Problème de transport. Problème d’affectation. Optimisation dans les réseaux. Notions élémentaires de la théorie des graphes. Problème de l’arbre de poids minimal. Problèmes de cheminements optimaux dans un réseau. Problème central d’ordonnancement. (MPM, PERT, CPM) Problèmes de flot. Modélisation en recherche opérationnelle. Bibliographie : C. BERGE, "Graphes et hypergraphes", Dunod V. CHVATAL, "Linear programming ", 1983, Freeman. M. GONDRAN et M. MINOUX, "Graphes et algorithmes", Eyrolles F.S. HILLIER et G.J. LIEBERMAN, "Introduction to operations research", 2001, McGraw-Hill. M. MINOUX, ‚Programmation mathématique‛, Tome 1, 1983, Dunod. M. SAKAROVITCH, ‚Optimisation combinatoire, graphes et programmation linéaire‛, 1984, Hermann. www.almohandiss.com 3 Chapitre 1 Introduction générale à la recherche opérationnelle I Présentation générale La recherche opérationnelle (RO) est née de la nécessité d'adopter une approche scientifique dans la gestion des organisations, cette gestion devenant de plus en complexe. Le nom de la discipline est une traduction de l'anglais "operations research". Ainsi, la RO traite de problèmes qui visent à conduire et à coordonner des opérations (i.e des activités) dans une organisation. Pourquoi le terme "recherche"? La RO est apparue en Grande-Bretagne durant la Seconde Guerre mondiale, lorsqu'on décida de faire appel à des chercheurs pour développer des méthodes scientifiques pour l'étude de divers aspects des opérations militaires. À la suite des succès obtenus dans le domaine militaire durant la Seconde Guerre mondiale, la RO a été appliquée à des problèmes de nature opérationnelle que ce soit dans l'industrie ou dans le secteur public. Le champ d'application de la RO s'est ensuite élargi à des domaines comme l'économie, la finance, le marketing et la planification d'entreprise et ce, grâce au développement des moyens de calcul informatiques et bien entendu des méthodes de solution (algorithmes de résolution). Son principal atout est qu'elle permet d'appréhender de façon systématique la complexité toujours grandissante des problèmes de gestion auxquels sont confrontées les organisations de nos jours, de quelque secteur qu'elles soient et ce, dans le but d'élaborer de bonnes décisions sinon les meilleures décisions. Elle peut s'appliquer dans un contexte déterministe, aléatoire ou concurrentiel. Le tableau suivant tiré du livre d'Hillier et Lieberman donne quelques exemples d'économies très importantes réalisées grâce à l'utilisation d'outils de RO: www.almohandiss.com 4 www.almohandiss.com 5 II Quelques exemples Dans un contexte déterministe, on peut citer les problèmes ci-dessous:  Le problème du plus court chemin d'une ville A à une ville B qui consiste à déterminer, parmi tous les chemins reliant A à B, un chemin de longueur minimum (notons ici que l'on parle d'un chemin de longueur minimum et non du chemin de longueur minimum pour la simple raison qu'il peut en exister plusieurs).  Le problème d'allocation de ressources: plusieurs ressources disponibles en quantité limitée peuvent être utilisées pour la production de plusieurs types de produits différents dans leur consommation en ressources et dans leur profit unitaire. Il s'agit de déterminer un plan de production optimal dans le sens où le profit global généré par les produits effectivement fabriqués soit maximum.  Le problème du voyageur de commerce: Etant données n villes et les distances intervilles, trouver une tournée qui passe une et une seule fois par chaque ville et qui minimise la distance totale parcourue. Dans le contexte aléatoire, on peut citer  Le problème de gestion des barrages  Le problème de la détermination du nombre de guichets à ouvrir dans une banque pour qu'un client ait moins de 10% de chances de devoir attendre au moins 10 mn avant d'être servi. Comme exemples de problèmes concurrentiels, on peut citer le problème de la détermination d'une politique de prix de vente. III Modélisation Un aspect très important concerne la modélisation. Les problèmes que l’on traite émanent de situations concrètes. Il s’agit alors de définir la situation en termes mathématiques et dans un souci d’efficacité de schématiser (modéliser) le problème. www.almohandiss.com 6 Voici comment on procède en général lorsqu’on est confronté à un problème dont on pense qu’il peut être résolu à l’aide de méthodes de programmation mathématique : 1. relever les facteurs les plus importants et établir les lois qui les régissent. 2. Déterminer une fonction économique. 3. Résoudre le modèle. 4. Confronter les résultats du 3. avec la réalité. Si la solution obtenue est acceptée alors adopter le modèle sinon modifier le modèle en conséquence et aller en 3. www.almohandiss.com 7 Chapitre II Généralités sur la programmation linéaire La programmation linéaire est une sous-classe de la programmation mathématique I Problématique de la programmation mathématique Contexte : Problèmes d’extrema Typiquement, il s’agit de problèmes qui s’expriment typiquement comme suit : Optimiser (i.e. maximiser ou minimiser) une fonction f sur un domaine D. Ces problèmes interviennent dans des problèmes de décision. On peut citer à titre d’exemples :  Les problèmes de gestion et de planning industriels  L’établissement de projets à moyen et/ou à long terme  La coordination de chaînes logistiques. L’objectif est de fournir des méthodes analytiques ou des algorithmes de résolution ou à défaut des procédures efficaces de calcul d’une solution approchée (on peut parler alors d’heuristiques). Définition 1 :  Un programme mathématique (P) est défini par la donnée d’un domaine DRn et d’une fonction f : DR et consiste à déterminer x*D (sous réserve d’existence) tel que : f(x*)  f(x) xD (si (P) est un problème de minimisation) et f(x*) ≥ f(x) xD (si (P) est un problème de maximisation)  si x  D alors x est appelé solution réalisable  x* est appelé solution optimale  f(x*) est appelé optimum de f sur D (minimum ou maximum)  L’ensemble D s’appelle domaine des solutions réalisables www.almohandiss.com 8  La fonction f s’appelle « fonction objective » ou « fonction objectif » ou « fonction économique » ou encore critère. Remarque : Pourquoi dit-on dans la définition 1 « sous réserve d’existence » ? La raison est que tout simplement x* n’existe pas toujours. En fait, il y a 4 cas possibles (on parle aussi de diagnostics) : 1. D= ; exemple : max{x/x≥0 et x-1} Le diagnostic ici est « Problème non réalisable » 2. D≠ et (P) admet une solution optimale ; exemple : max{x /x0} Le diagnostic ici est « Optimum fini » 3. D≠ et (P) n’admet pas de solution optimale ; exemple : max{x /x≥0} Le diagnostic ici est « Problème non borné » II Classification de la programmation mathématique Dans la programmation mathématique, on distingue essentiellement deux branches :  La programmation mathématique déterministe traite de problèmes où toutes les données nécessaires sont connues avec certitude.  La programmation mathématique stochastique traite, quant à elle, de problèmes où l’information nécessaire comporte des éléments aléatoires définis par des caractéristiques probabilistes connues. Dans le cas déterministe, on peut répertorier entre autres : - La programmation linéaire : f est linéaire et D est défini par des contraintes linéaires. Exemples : problèmes de transport et d’affectation. - La programmation convexe : f et D sont tous deux convexes. - La programmation en nombres entiers. III Exemples de programmes linéaires www.almohandiss.com 9 A- Un problème de production Une firme fabrique deux produits 1 et 2 à l’aide de trois matières premières I, II et III selon le mode décrit dans le tableau ci-dessous : www.almohandiss.com 10 1 2 Quantités disponibles I 2 1 8 II 1 2 7 III 0 1 3 Profit unitaire 4 5 6 L’objectif est de déterminer un plan de production qui maximise le profit global. Définition des variables : xj = nombre d’unités du produit j fabriquées (j=1,2) Contraintes : xj ≥0 2x1 + x2  8 x1 + 2 x2  8 x2  3 Fonction objective à maximiser : z(x) = 4x1 + 5x2 On peut résoudre ce problème graphiquement : pour cela, on procède de la manière suivante : 1. On représente le domaine des solutions réalisables. 2. On trace la courbe de niveau 0 de la fonction objective (i.e. z(x)=0). 3. On déplace cette droite le plus loin possible dans le domaine réalisable et ce dans le sens croissant des niveaux. La solution optimale se trouve à l’intersection du domaine des solutions réalisables avec la courbe de niveau de z de plus haut niveau. www.almohandiss.com 11 B- Un problème de transport Une entreprise de fabrication d’appareils électroménagers possède trois usines situées à Casablanca, Fès et Rabat. Un certain matériel nécessaire à la fabrication des appareils est disponible aux ports de Casablanca et Tanger. Les quantités (en tonnes) hebdomadaires de métal requises par les trois usines sont de 400, 300 et 200 respectivement. Les quantités (en tonnes) hebdomadaires de métal disponibles à Casablanca et Tanger sont de 550 et 350 respectivement. Les coûts unitaires (par tonne) de transport sont : Casa Fès Rabat Casa 1 5 3 Tanger 5 7 4 L’objectif est de déterminer un plan de transport optimal, i.e. quelles quantités acheminer de chaque port à chaque usine de manière à satisfaire la demande des uploads/Management/ sbihi.pdf