| UNIVERSITÉ DE SHERBROOKE |
|---|
| FACULTÉ DES SCIENCES |
| DÉPARTEMENT DE MATHÉMATIQUES |
| PLAN DE COURS |
Dans le vaste éventail des méthodes utilisées en recherche opérationnelle, la programmation linéaire est l'une des plus
importantes car d'une part, elle constitue un moyen naturel pour
modéliser une grande variété de problèmes et d'autre
part, des algorithmes très efficaces ont été développés depuis
longtemps pour résoudre les problèmes linéaires. Remarquons que le
terme programmation ne fait pas référence à l'ordinateur, mais
plutôt à la planification efficace d'utilisation de ressources;
la résolution des modèles réalistes de programmation linéaire est
toutefois impensable sans l'utilisation de techniques informatiques
sophistiquées et d'ordinateurs puissants.
Objectif général
L'objectif de ce cours est de permettre à l'étudiant d'une part, de développer sa capacité à modéliser des situations
réelles et d 'autre part, de maîtriser les aspects fondamentaux de la programmation linéaire pour en faire une application
efficace. Les outils de la programmation linéaire n'ont toutefois pas
réponse à tout, et un des objectifs est de développer l'esprit critique
qui permet de déceler les situations où la programmation linéaire est
l'outil de choix, mais également déceler les situations où elle n'est
pas le bon outil.
Méthodologie pédagogique et évaluation
Les concepts théoriques sont présentés lors d'exposés magistraux. Les devoirs et travaux pratiques constituent un complément
essentiel et permettent de consolider la compréhension des concepts, pas toujours simples, exposés en cours. Chaque
étudiant aura à faire 4 devoirs au cours de la session. Il y aura également un examen intra de 3 heures et un examen final de
3 heures. Ces activités interviennent dans la note finale selon les proportions suivantes:
Devoirs: 20%, Intra: 40% et Final 40%. Les devoirs
doivent être faits en équipe de deux ou trois personnes, et une
mauvaise qualité de rédaction pourra entraîner une pénalité de 5% dans l'évaluation des travaux.
Contenu détaillé
Dans le cadre de ce cours, nous nous pencherons principalement sur la
modélisation des problèmes linéaires, les propriétés fondamentales d'un
programme linéaire, la méthode simplexe, ses variantes et son efficacité, le concept de dualité
et l'analyse de sensibilité, le problème de transport, les problèmes
avec des structures de graphes--réseaux.
Plus spécifiquement, le contenu du cours est résumé dans les chapitres suivants
des notes cours (obligatoires),
Chapitre 1: Modélisation
Chapitre 2: Propriétés fondamentales d'un programme linéaire
Chapitre 3: La méthode du simplexe: définition et analyse
Chapitre 4: La méthode du simplexe: ses variantes
Chapitre 5: La dualité en programmation linéaire
Chapitre 6: Analyse de sensibilité
Chapitre 7: Résolution du problème de transport
et à l'étude d'extensions des notes, concernant notamment l'efficacité
de l'algorithme du simplexe, d'un point de vue théorique, ainsi que
pour la famille importante de problèmes avec contraintes de réseaux.
Bibliographie