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 Plan du cours: Introduction générale à la recherche op

Recherche Opérationnelle 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’aﬀectation. 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 ﬂot. Chapitre 1 Introduction générale à la recherche opérationnelle 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 plus complexe. Le nom de la discipline est une traduction de l'ʹanglais "ʺoperations research"ʺ. 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). Elle peut s'ʹappliquer dans un contexte déterministe, aléatoire ou concurrentiel. 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. 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: 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éﬁnir la situation en termes mathématiques et dans un souci d’eﬃcacité de schématiser (modéliser) le problème. 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. Déterminer une fonction économique. 2. Resoudre le modèle. 3. Confronter les résultats du 2. avec la réalité. Si la solution obtenue est acceptée alors adopter le modèle sinon modiﬁer le modèle en conséquence et aller en 3. • Exemples illustra.fs • A-‐ Un problème de produc.on • Une ﬁrme fabrique deux produits 1 et 2 à l’aide de trois ma9ères premières I, II et III selon le mode décrit dans le tableau ci-‐dessous : • L’objec.f est de déterminer un plan de produc9on qui maximise le proﬁt global. 1 2 Quantités disponibles I 2 1 8 II 1 2 7 III 0 1 3 Profit unitaire 4 5 6 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#≤#7# # #############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 ce^e 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. x*=(3,2) z*=22 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 usines, respecter les contraintes de disponibilité dans les ports et ce en minimisant le coût global de transport. Définition des variables : xij = quantité acheminée du port i à l’usine j avec i=C,T et j=C,F,R Contraintes : xij≥0 xCC + xCF + xCR ≤ 550 xTC + xTF + xTR≤ 350 xCC + xTC ≥ 400 xCF + xTF ≥ 300 xCR + xTR ≥ 200 Fonction objective à minimiser : z(x) = xCC + 5xCF +3xCR +5xTC +7xTF +4xTR Dans ce cas, une résolution graphique est exclue. Déﬁnition : • Un programme mathématique (P) est déﬁni 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 • La fonction f s’appelle « fonction objective » ou « fonction objectif » ou « fonction économique » ou encore critère. Remarque : Pourquoi dit-‐‑on dans la déﬁnition 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 ﬁni » 3. D≠∅ et (P) n’admet pas de solution optimale ; exemple : max{x /x≥0} Le diagnostic ici est « Problème non borné » 4. D≠∅, f est bornée sur D et (P) n’admet pas de solution optimale ; exemple : max{x /x<0}. On n’étudiera pas ce type de situation. Dans la pratique, on peut se ramener à des domaines fermés. Classiﬁcation 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éﬁnis 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éﬁni par des contraintes linéaires. Exemples : problèmes de transport et d’aﬀectation. • La programmation convexe : f et D sont tous deux convexes. • La programmation en nombres entiers. Les problèmes de programmation mathématique 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 eﬃcaces de calcul d’une solution approchée (on peut parler alors d’heuristiques). Logiciels pour la programmation linéaire Il y a plusieurs logiciels pour résoudre un programme mathématique et non seulement linéaire (la spécification de la linéarité du programme au logiciel lui permet d'ʹutiliser un outil spécifique à la PL et d'ʹaller par conséquent plus vite). Les plus connus sont: § Le solveur de Microsoft Excel qui permet de résoudre un programme de petite taille § Le logiciel LINDO et son modeleur LINGO (des versions étudiants sont uploads/Science et Technologie/cours-ro-seance-1.pdf