MET3220 - Plan de cours HB Été2021 PDF

Preview

Summary

Plan de cours...

Description

École des sciences de la gestion Département d’Analytique, Opérations & TI Université du Québec à Montréal

MET 3220 - RECHERCHE OPÉRATIONNELLE : Méthodes d’aide à la décision ÉTÉ 2021 - Groupe 020

Enseignant : Hocine Bourenane – Courriel : [email protected] Sites Web du cours sur Moodle: http://www.moodle2.uqam.ca

1. OBJECTIF GÉNÉRAL La Recherche Opérationnelle (RO) est une science jeune dont les origines remontent à la deuxième guerre mondiale. Parmi les premières applications de la RO on retrouve donc plusieurs applications militaires. La principale caractéristique de la RO est son approche scientifique des problèmes à résoudre. C’est cette caractéristique qui l’a rendue si populaire auprès des professeurs de gestion et dès la fin de la guerre, plusieurs facultés de gestion ont commencé à dispenser des cours de RO à leurs étudiants. Le début des années cinquante marque aussi le début fulgurant de l’ère des ordinateurs. L’invention de ce calculateur haute performance a propulsé la RO au rang de science à part entière. En fait, les deux principaux ingrédients de la RO sont la mathématique et l’informatique. Avant l’arrivée de la RO, les gestionnaires utilisaient leur expérience et leur intelligence pour déduire, souvent par essais et erreurs, des solutions approximatives à des problèmes de gestion malheureusement pour eux de plus en plus complexes. Avec l’aide de la RO on peut toutefois résoudre plusieurs problèmes de façon optimale. Les problèmes à résoudre sont d’abord modélisés par des modèles mathématiques dans lesquels contraintes et objectifs sont pris en considération. Ces modèles sont ensuite résolus par l’exécution sur ordinateur d’algorithmes performants, souvent spécialement adaptés au type de modèles sous considération. Les ordinateurs modernes peuvent résoudre des modèles contenant plusieurs milliers de contraintes et de variables de décision. La littérature scientifique de la RO cite plusieurs exemples de problèmes de gestion où la solution obtenue par la RO génère des solutions significativement avantageuses par rapport aux solutions calculées manuellement. Dans certains cas, la survie même de l’entreprise est en jeu et seules des techniques sophistiquées comme celle de la RO peut assurer leur survie à long terme. L'expérience et l'intuition, quoique d’une importance fondamentale, ne suffisent pas à la prise de décisions éclairées. Les gestionnaires ont besoin également d'outils et de méthodes d'analyse qui leur permettent d'extraire des informations utiles de leurs données et de tester des scénarios qui valideront ou infirmeront ce que leur dictent l’intuition et l’expérience. Ce cours a donc pour objectif d'initier l'étudiant à l'utilisation d'un cadre rigoureux pour formuler, analyser et résoudre les problèmes de gestion qui se posent au sein d'une entreprise, fût-elle privée ou publique, de type manufacturier ou de service. En particulier, l'étudiant sera initié aux modèles et méthodes d'optimisation (Comment maximiser son profit ou minimiser ses coûts sous contraintes) et de simulation (Quel profit ou quel coût espérer de telle ou telle situation, dans un contexte d'incertitude). L'objectif ultime est d'amener l'étudiant à maîtriser une méthodologie d'aide à la décision devenue incontournable et de lui apprendre à l’utiliser pour résoudre les problèmes concrets que l'on rencontre fréquemment, voire quotidiennement, dans les entreprises.

Plan de cours

MET 3220 – 001 - Été 2021

page 2

Dans ce cours, nous visons deux objectifs principaux. D’abord, à la fin du cours, les étudiants devraient être en mesure de « modéliser » un problème donné, c'est-à-dire identifier ses variables intrinsèques, ses contraintes technologiques, le ou les objectifs visés et la méthode appropriée pour le résoudre. Ce cours se veut une introduction à la recherche opérationnelle. Nous ne pouvons en un seul cours faire de l’étudiant un spécialiste de ce domaine. Il suffit de mentionner, pour appuyer cette affirmation, qu’il existe des programmes complets de 1er, 2e et 3e cycle en RO. Toutefois, nous voulons comme deuxième objectif, développer chez l’étudiant ce que l’on peut appeler de façon imagée l’intuition d’optimisation, intuition qui permettra à l’étudiant, dans sa pratique de gestionnaire, de reconnaître les problèmes qui peuvent être résolus par la RO. Il pourra par la suite entreprendre les démarches appropriées. 2. PRÉALABLES ECO2272 ou MAT2080 ou POL1800 3. ÉVALUATION ET PONDÉRATION Les étudiants seront évalués sur les travaux suivants : 1) 2 TP (format Quiz ou à rendre), travaux à réaliser en équipe à domicile 2) Examen intra (3 juin 2021) 3) Examen final (29 juin2021)

1

30 % 35 % 35 %

•

La participation active durant ce cours est requise. La présence au cours est fortement recommandées et les étudiants doivent être prêts pour discuter du matériel qui a été assigné. Une bonne préparation vous permettra de discuter avec le reste de la classe et de participer de manière constructive dans les exercices.

•

Absence au cours : Selon le règlement de l’ESG la présence au cours n’est pas obligatoire, cependant l’expérience a largement démontré que la réussite d’un cours universitaire est étroitement liée à cette présence de corps et d’esprit et que les explications additionnelles données en classe faciliteront grandement sa réussite. Les exemples et exercices résolus en cours sont une source essentielle pour la compréhension des concepts mathématiques complexes et seront d’une grande utilité pour la réussite des examens.

•

L’examen intra porte sur la matière vue aux cours no 1 jusqu’au cours no 7 inclusivement tandis que l’examen final porte sur la matière couverte subséquemment. Le barème d’évaluation est basé sur la grille officielle du département de Management & Technologie, disponible également sur Moodle

Note

Min inclus

A+

90

Max exclu 100

1

Note

Min inclus

Max exclu

Note

B+

77

80

C+

Min inclus

Max exclu

Note

Min inclus

Max exclu

67

70

D+

57

60

A

85

90

B

73

77

C

63

67

D

55

57

A-

80

85

B-

70

73

C-

60

63

E

0

55

Cette valeur est incluse

Plan de cours

MET 3220 – 001 - Été 2021

page 3

4. DOCUMENTATION PÉDAGOGIQUE Dans les références suivantes, seule la référence no 1 est obligatoire. 1. Y. Nobert, R. Ouellet et R. Parent, « Méthodes d’optimisation pour la gestion », Gaëtan Morin éditeur, Chenelière Éducation, 2ière édition, 2015, 454 pages. 2. Ragsdale, « Spreadsheet Modeling and Decision Analysis, South Western. 3. D. R. Anderson, D. J. Sweeney, T. A. Williams, “Quantitative methods for business”, 10th ed., Thomson 4. Bourjolly, MacPhail, Longo, «A learning tool for linear programming », http://www2.informs.org/Resources/Courses/ 5. F. S. Hillier et G. J. Lieberman, “Introduction to Operations Research”, 9th ed., McGraw-Hill. 5. MÉTHODES PÉDAGOGIQUES L'acquisition des connaissances et l'apprentissage des différents modèles et techniques de décision se feront par des cours magistraux. L'enseignement sera complété par des périodes de discussion, par l'application des techniques vues en classe dans des travaux individuels ou de groupes et par des laboratoires où des exercices sont effectués en classe par des démonstrateurs. 6. LOGICIEL Les modèles présentés dans ce cours seront résolus par le Solveur d’Excel. Votre version de MS Excel doit supporter les macro-commandes. L’accès à un ordinateur de type Pc/Windows sera nécessaire pour certaines applications. Il est fortement conseillé de venir au cours avec votre propre ordinateur car la majorité des problèmes seront résolus sur ordinateurs. Le cours est accès sur la modélisation, l’introduction des données du du modèle sur ordinateur, l’obtention de la solution et finalement l’analyse des résultats obtenus incluant l’analyse de sensibilité. La théorie à l’origine du modèle n’est que partiellement vue et seulement lorsque jugée nécessaire 7. DESCRIPTION DES COURS Cours no 1

Syllabus et introduction à la RO



Présentation du syllabus o Évaluation, matériel pédagogique, horaires des laboratoires.

  

Nature et méthode de la recherche opérationnelle. Recherche Opérationnelle vs Génie Industriel vs Gestion des Opérations : Différences et similitudes Exemples d’applications de la RO o Description du problème o Approche gourmande versus solution optimale o Implantation dans l’industrie La RO dans le monde et la RO au Québec Les programmes de l’ESG pertinents à la RO o Concentrations au baccalauréat o Spécialités à la maîtrise

 

Plan de cours

MET 3220 – 001 - Été 2021

page 4

Cours no 2 Modélisation I : Planification de la production et Solveur d’Excel Dans la plupart des entreprises où des biens destinés à la consommation sont fabriqués, une planification efficiente de la production constitue une des démarches les plus importantes. Trop produire implique des coûts de gestion des stocks élevés. À l’inverse, une production insuffisante par rapport à la demande implique une baisse du service à la clientèle et conduit à des manques à gagner importants. Une entreprise de taille importante fabrique souvent une grande gamme de produits différents. Décider pour chacun de ceux-ci la quantité optimale à fabriquer est une tâche très complexe. La Recherche Opérationnelle comporte plusieurs modèles qui ont été utilisés avec succès pour aider les entreprises dans cette opération de planification. Dans ce cours nous étudions la modélisation d’un problème de planification de la production sur une période (semaine, mois, année.). La démarche type suivante sera suivie dans tous les cours de modélisation:   



  

Description du contexte Résolution manuelle et logique gourmande Discussion et modélisation en mots du problème à résoudre : o Décisions concrètes et variables mathématiques de décision associées o Fonction objective à optimiser o Contraintes à respecter o Unités ($, heures, kg…) de l’objectif, des contraintes et des variables Modélisation mathématique : o Écriture mathématique de l’objectif, des contraintes o Contraintes définissant les valeurs acceptables des variables o Hypothèses sous-jacentes au modèle dont la linéarité o Limitations du modèle o Les modèles réels utilisés dans l’industrie Utilisation du Solveur d’Excel (Capsule vidéo) Interprétation concrète de la solution optimale Analyse de scénarios et extensions : o Ajout de contraintes ou de variables o Modification des données du modèle o Variations aléatoires et éléments de simulation

Cours no 3, 4 Résolution graphique et brève illustration de la méthode du simplexe Au cours no 2 nous avons vu des modèles linéaires associés à la planification de la production. Nous concentrons au cours no 3 notre étude sur ce type de modèles où seules deux variables de décision sont présentes. Nous montrons au cours no 3 les aspects géométriques à prendre en considération lors de la recherche d’une solution optimale de tels modèles. Nous montrons aussi comment un gestionnaire, se basant uniquement sur son intuition, peut en arriver à des solutions sous-optimales. On introduit la notion d’approche gourmande ou gloutonne qui simule une telle approche intuitive. Le cours no 4 quant à lui porte sur la méthode du simplexe, l’outil principal de la recherche opérationnelle. On donne dans ce cours une brève introduction à cette méthode en expliquant intuitivement sa démarche et en faisant le lien avec un gestionnaire astucieux qui corrigerait à la marge une solution qu’il aurait obtenue au préalable par tâtonnement.



Résolution graphique d’un modèle linéaire continu à deux variables de décision o Insertion des contraintes – Courbe de niveau de la fonction objective o Points extrêmes et théorème fondamental de la programmation linéaire Notion de variables d’écart ou d’excédent

 

Notion de lexique, point extrême associé et solution concrète correspondante Calcul d’un lexique adjacent et notion de coût ou profit marginal

 

Logigramme de la méthode du simplexe et commentaires Laboratoire sur le solveur d’Excel



Plan de cours

MET 3220 – 001 - Été 2021

page 5

Cours no 5 Modélisation II : planification de la production et de la main d’œuvre o Dans le cours n 2 nous avons vu des modèles simples de planification de la production où les décisions de production sont prises sur une seule période. Nous donnons dans ce cours d’autres exemples de ce type de modèles où plusieurs périodes sont considérées simultanément. Les modèles sont plus complexes mais sont d’une importance encore plus grande pour les entreprises. Dans certains de ces modèles, les décisions de production doivent spécifier non seulement la quantité optimale à produire mais aussi la façon générique dont chacun des produits de la compagnie doivent être fabriqués. La planification de la production a des impacts sur la planification des horaires des employés de la compagnie. Décider du nombre d’employés à mettre en service en fonction des besoins minimaux de la compagnie est une tâche très difficile à réaliser manuellement, tâche qui peut prendre à l’horairiste plusieurs jours de travail. Aujourd’hui, grâce à la recherche opérationnelle, des compagnies de transport, des corps de police, des hôpitaux utilisent des horaires d’employés économiques tout en respectant les conditions de travail des employés. Présentation, selon le déroulement type, de modèles portant sur les sujets suivants :



Planification de la production sur plusieurs périodes o Modèle mathématique o Illustration graphique (en préparation du cours 10) Problèmes de mélange

 

Gestion de la main-d’œuvre. Affectation ou couplage d’employés.



Localisation d’entrepôts.



Cours no 6 Modélisation III : le choix entre faire ou ne pas faire Dans plusieurs situations concrètes, le preneur de décision doit choisir entre poser ou ne pas poser une certaine action. À titre d’exemples mentionnons les options de :  Construire ou ne pas construire une usine, un centre de transbordement, un entrepôt…sur un site spécifique;  Affecter ou ne pas affecter un employé, une machine, un camion…à une tâche donnée; Ouvrir ou ne pas ouvrir une route de transport;  Coupler ou ne pas coupler deux employés ensemble pour l’exécution d’une certaine tâche. Les modèles associés à ce type de décisions comportent ce que l’on dénomme des variables binaires. On donne dans ce cours plusieurs exemples de tels modèles tout en insistant sur les applications types qui leurs sont associées. Présentation, selon le déroulement type, de modèles portant sur les sujets suivants : 





Modèles permettant de d’affecter ou de coupler : o Variables types et contraintes types o Généralisations o Applications Modèles de confection d’horaires : o Variables types et contraintes types o Généralisations o Applications Modèles de recouvrement d’ensemble : o Variables types et contraintes types o Généralisations o Applications

Plan de cours

MET 3220 – 001 - Été 2021

page 6

Cours no 7 Planification de la production en quantités entières Dans certains cas les décisions optimales de production doivent être entières. Cette restriction, bien que souvent naturelle, rend toutefois la tâche du preneur de décision beaucoup plus complexe. Le réflexe de plusieurs d’entre eux est souvent de ne pas prendre en considération cette restriction d’intégrité et d’arrondir les quantités obtenues. On montre ici qu’il est habituellement sous-optimale de procéder ainsi. De plus, on montre une nouvelle méthode, la méthode de séparation et d’évaluation progressive, qui permet de résoudre les modèles linéaires en nombres entiers. L’enseignement de cette méthode s’avère aussi utile pour les étudiants car on montre comment résoudre de façon structurée un problème complexe en le divisant en sous-problèmes.  Modèle de planification de la production avec deux variables entières. o Résolution graphique o Résolution par le Solveur :  Modèles en nombres entiers avec plus de deux variables : o Idée de la méthode SÉP o Quelques séparations avec l’aide du Solveur  Modèle mixte : Modèle de localisation et d’allocation

Cours no 8

Examen Intra

Cours no 9 & 10 Optimisation sur des réseaux : La notion de réseau est une des notions les plus importantes autant en recherche opérationnelle que dans la vie de tous les jours. Lorsque l’on se rend à son travail, on se déplace sur un réseau routier, lorsqu’on échange des courriels, on utilise le réseau Internet, lorsqu’on dirige une entreprise, on doit posséder un réseau d’affaires important. Le transport aérien repose sur un réseau d’aéroports, le transport ferroviaire repose sur un réseau de gares, le transport routier repose sur un réseau routier tandis que le transport maritime utilise un réseau de ports. On le voit la notion de réseau est partout dans notre quotidien. Dans les cours no 9 et no 10 on étudie plusieurs modèles et applications de la recherche opérationnelle dans lesquels la notion de réseau est sous-jacente. Les problèmes étudiés comptent parmi les plus importants en recherche opérationnelle.  Notion de réseau : sommets, arcs, flot, données pertinentes et réseaux réels  Problème de flot à coût minimum : o Modélisation mathématique o Modélisation graphique o Applications du problème de flot à coût minimum. o Problème du chemin le plus court o Problème de transport (brève intro) o Production multi périodes : livraisons anticipées ou en retard

Plan de cours

MET 3220 – 001 - Été 2021

Cours no 11 & 12

page 7

Techniques de planification et contrôle de projets

Les cours no 12 et 13 concernent la gestion de projet. Qu’il s’agisse de gérer la réalisation d’un édifice à bureaux, la construction d’un barrage, la rénovation d’un tronçon d’autoroute, l’élaboration d’un réseau intranet, le succès ou l’échec d’un tel projet dépend de sa bonne gestion. Encore ici plusieurs modèles de recherche opérationnelle viennent aider les gestionnaires dans la bonne marche du projet. Ces deux cours constituent une brève introduction à la science de la gestion de projet. L’ESG offre un programme de deuxième cycle dans ce domaine.    

Définition d’un projet et terminologie de base des réseaux CPM/PERT Représentation des tâches sur nœuds et construction de réseaux CPM/PERT Notion de chemin critique et modèle mathématique associé o Le modèle CPM : Moments au plus tôt, plus tard, marges et calcul chemin critique o Le modèle PERT : Modèle probabiliste de la durée d’une tâche Éléments de simulation

Cours no 13

Synthèse du cours

Correction du TP-2 – Synthèses et Révision en vue de l’examen final Cours no 14

Examen final

Note : Cette session, il y a 14 séances. La journée du 24 juin est un jour de congé (Fête nationale)

Plan de cours

MET 3220 – 001 - Été 2021

page 8

8. SVE - Soutien aux étudiants en situation de handicap 

L’utilisation des technologies mobiles n’est pas permise en classe sans la permission de l’enseignant. Cependant, les personnes en situation de handicap peuvent obtenir une autorisation permanen...