Université de Montréal Automne 2011
Département d’Informatique et
de Recherche Opérationnelle
IFT2505: Techniques d’Optimisation I
Plan de Cours
1 Objectifs du cours
Ce cours vise à introduire la modélisation linéaire, et les deux grandes classes
de méthodes servant à les réseaux, à savoir l’algorithme du simplexe, incluant
ses variantes, et les méthodes de points intérieurs. Une classe importante
de problèmes fera en outre l’objet d’un traitement particulier, à savoir les
modèles de flots dans les réseaux.
Le cours examinera en détail les méthodes de résolution plutôt que de
développer l’apprentissage des logiciels implantant ces méthodes. L’utilisant
du lagange matriciel de MATLAB sera toutefois abordé afin d’automatiser
certaines étapes calculatoires présentes dans l’application de ces techniques.
2 Place du cours dans le programme
Il s’agit du premier cours de techniques d’optimisation, et prend comme
préalables MAT 1600 ou MAT 1640.
Le cours IFT 3515, Techniques d’optimisation 2, fait suite au cours IFT
2505 en traitant de la programmation linéaire en nombres entiers et de la
programmation non linéaire. Le cours IFT 3545, Graphes et réseaux, permet
d’approfondir les notions introduites dans la seconde partie du cours IFT
2505, portant sur les méthodes de flot dans les réseaux et sur la théorie des
graphes.
3 Contenu du cours
1. Introduction : Modélisation linéaire.
2. Propriétés de base des modèles linéaires.
1
3. La méthode du simplexe.
4. La dualité en programmation linéaire.
5. Les méthodes de points intérieurs.
6. Problèmes de transport et de flot dans les réseaux.
4 Évaluation et travaux
4.1 Barème
• Examen intra: 30%
• Examen final: 40%
• Devoirs: 30%
Pour réussir le cours, il faut conserver une moyenne pondérée de 45%
pour les deux examens et une moyenne pondérée de 50% pour les deux
examens et les devoirs.
4.2 Travaux
Devoirs hebdomadaires comportant des exercices à remettre. Tous les de-
voirs ont la même pondération pour établir la note des devoirs. Ils sont à
remettre pour la fin de chaque séance de démonstration. Aucun retard ne
sera toléré, et le règlement sur le plagiat sera d’application stricte.
4.3 Examens
• Intra: vendredi 21 octobre, 8h30, au B-3270 du pavillon Jean-Brillant.
• Final: samedi 17 décembre, de 9:00 à 12:00, au 1355 du pavillon A.-
Aisenstadt.
5 Détails pratiques
5.1 Horaire
• Lundi, 14h30-15h30, local 1175, pavillon A. Aisenstadt.
• Mercredi, 13h30-15h30, local 1175, pavillon A. Aisenstadt.
2
5.2 Auxiliaire
Géraldine GEMIEUX, [email protected]
5.3 Disponibilté
Mercredi, de 16h à 18h.
6 Support de cours et références
Le cours se basera sur le livre ”Linear and Nonlinear Programming”, Third
Edition, Luenberger and Ye, Springer, 2008. Les chapitres 1 à 6 seront
couverts.
