Département Opérations et systèmes de décision PLAN DE COURS Faculté des sciences de l'administration Automne 2005 Université Laval

MQT–19219 Modélisation et aide à la décision Section A

Professeur : P. Lang Bureau : PAP-2626 Téléphone : 656-5873 Courriel : Pascal.Lang@fsa.ulaval.ca

Horaires : Cours: Jeudis 12h30-15h30, salle PAP-2317 Dépannage: à déterminer (dépanneur: Guillaume Carpentier)

1. INTRODUCTION

La capacité à modéliser certains aspects du monde de l’entreprise fait partie des aptitudes exigées des gestionnaires d’auhjourd’hui. Par modéliser, on entend un exercice de réflexion qui comporte trois étapes : (1) analyser une situation d’entreprise et en extraire les éléments importants (2) relier ces éléments entre eux de manière formelle, souvent en utilisant un langage mathématique, et (3) obtenir une nouvelle compréhension du phénomène et la retranscrire dans l’action concrète.

Ce cours vous propose d’approfondir cette démarche en vous appuyant sur une famille de modèles et d’outils à la fois efficaces, peu complexes, et répandus.

Objectifs généraux :

Ce cours porte sur une catégorie générale de problèmes de décision dans lesquels interviennent de nombreuses variables et contraintes. L'emphase principale du cours porte sur la modélisation de tels problèmes. En particulier, ce cours va amener l'étudiante ou l'étudiant à : − voir par des exemples concrets comment la modélisation et les méthodes quantitatives peuvent

aider la décision dans une variété de contextes en administration des affaires et en gestion; − reconnaître certaines structures de problèmes et les hypothèses sous-jacentes; − comprendre le fonctionnement de méthodes couramment utilisées pour trouver des solutions; − interpréter les informations fournies par ces méthodes de résolution et leurs implications pour la

prise de décision.

Objectifs spécifiques :

Au terme de ce cours, l'étudiante ou l'étudiant devra pouvoir : − reconnaître des structures courantes de problèmes : programme linéaire, en nombres entiers,

réseaux; décision dans l’incertitude ; − formuler des modèles mathématiques pour ces types de problèmes; − connaître les bases du fonctionnement de l'algorithme du simplexe; − représenter des situation de décision dans l’incertitude. − interpréter les principaux résultats d'une analyse de sensibilité et en connaître les limites; − maîtriser un logiciel d’optimisation ;

2. CONTENU

Les principaux sujets abordés sont la formulation et la résolution de programmes linéaires, et l’aide à la décision dans l’incertitude. On traite de problèmes de mélanges, de production, de gestion financière, de choix de médias, de gestion de stocks, de planification multipériodes, etc.. On examine également la formulation de problèmes en nombres entiers (coûts fixes, choix d'alternatives discrètes, etc.) et celle de problèmes ayant une structure de réseaux (plus court chemin, problèmes de flots, dimensionnement

- 2 -

de réseaux, etc.). On étudie l’algorithme du simplexe et l’analyse de sensibilité de la programmation linéaire, ainsi que l’approche de l’incertitude par les arbres de décision.

3. MÉTHODOLOGIE − Cours magistraux. − Exercices d'apprentissage autonome (documents de référence). − Lectures (documents de référence et volumes complémentaires). − Deux études de cas, avec utilisation du logiciel LINDO. − Dépannages sur les exercices et sur les concepts vus en classe. Initiation au logiciel LINDO. Il est essentiel pour la bonne assimilation du cours de faire les lectures et exercices régulièrement et à temps. Les lectures doivent permettre de faciliter et de vérifier la compréhension de la matière présentée en classe. Les exercices doivent aussi permettre de valider la compréhension de la matière. Les études de cas sont l'occasion de synthétiser plusieurs aspects du cours et fournissent une autre forme de validation.

4. ÉVALUATION

L’évaluation des apprentissages comporte deux examens et deux travaux longs.

Épreuve Pondération

Échéance

Travail 1 20 % 20 octobre Examen partiel 30 % Samedi 29 octobre (à confirmer : cette date peut

être modifiée par la Direction du 1er cycle) Travail 2 20 % 8 décembre

Examen final cumulatif 30 % Période d'examens: voir annonce du programme de baccalauréat

100 %

Les examens durent trois heures. L’examen partiel est à livres fermés : vous pouvez utiliser 4 pages (2 feuilles 8.5” x 11”) de notes à l’examen.

Il n'y aura pas d'examen de rattrapage.

L'examen final sera à livres ouverts et couvrira toute la matière du cours (cumulatif). Il aura lieu dans la période réservée à cette fin par la Direction des programmes du premier cycle, selon un horaire, différent de celui du cours, qui sera annoncé pendant le trimestre.

L'évaluation portera sur les éléments suivants : − Les examens visent avant tout à vérifier la compréhension de la matière. Les corrections d'examens

évaluent le raisonnement et la réponse finale. − Les réponses doivent être claires, sans ambiguïté et lisibles. La présentation et l'expression doivent

être correctes. Le raisonnement et les calculs doivent être détaillés.

Les travaux seront pour vous l’occasion de résoudre des problèmes de taille respectable (jusqu’à 200 variables) qui vous donneront un avant-goût de la pratique de la modélisation. Les cas sont inspirés d’applications réelles, ils sont spécialement adaptés pour une utilisation dans votre formation. Prévoyez de 10 à 20 heures de travail par cas pour chaque membre de l’équipe, voire plus si vous avez mal suivi le cours ou si vos méthodes de travail ne sont pas optimales…

Les cas sont conçus pour être faits en groupes de deux ou trois maximum. Il est possible mais déconseillé de faire un travail seul. Le professeur se réserve la possibilité de vérifier et d'évaluer séparément la contribution individuelle de chaque membre d'un groupe. Le Règlement disciplinaire de l’Université Laval est supposé connu de tous.

- 3 -

L'évaluation des travaux portera sur les éléments suivants : − Justesse du raisonnement et compréhension des concepts du cours. − Aptitude à communiquer de façon organisée, claire et concise, et à justifier un argument. − Qualité de la présentation

5. RÉFÉRENCES

Document de référence (obligatoire): − A. Gautier, B. Lamond, P. Lang: Documents supplémentaires. Exercices avec solutions portant

sur tous les chapitres du cours (les réponses pour certains problèmes de formulation seront distribuées en classe en cours de trimestre), guide du logiciel LINDO, notes sur l'analyse de sensibilité graphique, notes sur l'optimisation dans les réseaux. (Dernière mise à jour : janvier 2004)

Volumes complémentaires (facultatifs) : − W.L. Winston : Introduction to Mathematical Programming. PWS-Publications Inc., 2003. − W.L. Winston : Operations Research : Applications and Algorithms. PWS-Publications Inc., 1991. − F.S. Hillier, G.J. Lieberman : Introduction to Operations Research. McGraw Hill, 1990. − Y. Nobert, R. Ouellet, R. Parent : La recherche opérationnelle. 2ième édition, Gaétan Morin, 1999. − M. Nedzela : Introduction à la science de la gestion. P.U.Q., 1986 (3ième édition).

6. RESSOURCES

Informatique Logiciel de support : LINDO version 6.1 pour Windows. Cet logiciel est fourni sur l’ordinateur pour les étudiants inscrits au programme Ulysse. Il sera téléchargeable pour les autres.

Affichage Des annonces seront faites et des documents communiqués sur le site Web du cours, qu’il vous est demandé de consulter régulièrement. Pour ce faire :

− aller à : http://cours.fsa.ulaval.ca/html/ − cliquer sur Accès à l’intranet − identifiez-vous (nom, mot de passe) − cliquez sur votre section du cours.

Accès au réseau et utilisation des ordinateurs portables L’accès à un ordinateur en communication avec le réseau de l’Université Laval est requis pour suivre ce cours. L’ordinateur portable peut être utilisé en classe à quelques occasions (ex : démonstration du logiciel), sans être indispensable. L’ordinateur portable est proscrit dans les périodes d’examen.

7. FEUILLE DE ROUTE

Séance Sujet, Lectures(notes), exercices Durée approx.

08/09 Introduction à la programmation linéaire : 3h00 − Forme d'un programme linéaire; − résolution graphique d'un programme linéaire; − propriétés fondamentales des programmes linéaires. Exercices : 1.1, 1.2

- 4 -

Séance Sujet, Lectures(notes), exercices Durée approx.

15 et 22/09 Formulation d'un programme linéaire. 5h30

Lectures : Introduction à la formulation en programmation linéaire.

Exercices : 2.1 à 2.16, puis 2.17 à 2.22.

22/09 Introduction à LINDO (travaux pratiques). 0h30 Lectures : Section 4 - Guide d'utilisation du logiciel LINDO.

29/09 Équations et inégalités linéaires simultanées : 3h00 − rappels d'algèbre linéaire; − solutions de base, pivot; − solutions de base réalisables d'un système d'inégalités.

Exercices : 3.1 et 3.2.

06 et 13/10 Algorithme du simplexe : 6h00 − principe de l'algorithme; − obtenir une solution de base de départ; − cas particuliers : solutions multiples, sans bornes, dégénérées;

problèmes sans solutions.

Exercices : 3.3 à 3.11. 20/10 Formulation de programmes linéaires à variables entières I. 3h00 Exercices : 8.1 à 8.6. 27/10 Formulation de programmes linéaires à variables entières II. 3h00 Exercices : 8.7 à 8.12. Utilisation de Lindo avec variables entières (travaux pratiques). 29/10 * (à confirmer) EXAMEN PARTIEL (3 heures). 3h00

31/10-05/11. SEMAINE DE LECTURE. 10 et Décision dans l’incertitude 4h30 17/11 Exercices : 11.1 à 11.7 17 et 24/11 Introduction aux réseaux : 4h30

− structures de réseaux; − formulations équivalentes (progr. linéaire, représentation

graphique);

− structure d'une solution de base réalisable. Lectures : Optimisation dans les réseaux.

Exercices : 10.1 à 10.8. 01/12 Dualité en programmation linéaire : 3h00

− problèmes duaux; − relations entre leurs solutions; − interprétation économique du problème dual et de sa solution. Exercices : 5.1 à 5.3.

Lectures : Section 6 - Analyse de sensibilité graphique. 08/12 Analyse postoptimisation : 3h00

Changements possibles dans les données d'un problème (fonction objectif et côtés droits) qui ne modifient pas la base optimale.

Exercices : 7.1 et 7.2. 12/12 – 23/12 EXAMEN FINAL CUMULATIF (Horaire à communiquer). 3h00

* cette date peut être modifiée par la Direction du 1er cycle.