UNIVERSITÉ DE SHERBROOKE

FACULTÉ DES SCIENCES

DÉPARTEMENT DE MATHÉMATIQUES

PLAN DE COURS

ROP 317 Programmation linéaire
Crédits : 3
Session: HIVER 2007

Professeur: Jean-Pierre Dussault
Local D4-1022-1 Téléphone 821-8000 poste 62031
Courriel: Jean-Pierre.Dussault@USherbrooke.CA

Horaire du cours: LU 13 h 30 -- 14 h 20 et ME 8 h 30 -- 10 h 20
Séances d'exercices: JE 15 h 30 -- 17 h 20
Période de consultation: 2 heures (à déterminer)

Mise en contexte
Le cours «Programmation linéaire» (ROP317) fait partie de la chaîne de cours de recherche opérationnelle offerts par le Département de mathématiques. Dans ce contexte, rappelons que la recherche opérationnelle est une discipline qui utilise des modèles mathématiques, des statistiques et des algorithmes pour aider la prise de décision.

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:

1. dégénérescence et cyclage;
2. décomposition de Dantzig-Wolfe;
3. rudiments de théorie des jeux.

Bibliographie

1. Notes de cours rédigées par le Professeur Abdelhamid Benchakroun (Obligatoire).
2. Laurence Wolsey, Modéliser avec AMPL.
3. R.J. Vanderbei, Linear Programming: Foundations and Extensions; excellente référence, disponible en ligne, sur les aspects mathématicaux-algorithmiques, quoique d'un niveau plus avancé que le cours.
4. Hillier and Lieberman, Introduction to operations research, Holden-day, 1995. Référence reconnue pour la présentation de nombreux exemples réalistes.

Le contenu de cette page est la responsabilité de son auteur et n'engage en rien l'Université de Sherbrooke.