Introduction à l'optimisation et la recherche opérationnelle

Examen de milieu de semestre

• Un examen sera organisé au milieu du semestre.
• Il couvrira les matières suivantes : "Introduction à l'optimisation et la recherche opérationnelle", "Introduction à l'optimisation linéaire", et "Algorithme du simplexe".
• L'examen comportera des questions liées au cours et aux exercices.
• La matière a connaître est constituée des parties du livre "Optimization: Principles and Algorithms" identifiées dans le plan du cours (voir ici).
• Cet examen comptera pour 20% de la note.
• Vous aurez droit exclusivement à deux pages de résumés manuscrits (4 faces A4) maximum.
• Tout résumé non écrit à la main (imprimé ou photocopié) ne pourra pas être utilisé pour l'examen.
• Les résumés doivent porter la date ainsi que nom de l'étudiant.
• Les résumés pourront être gardés pour être éventuellement réutilisés lors de l'examen final.
• Aucun moyen électronique (calculatrice, ordinateur, etc.) n'est admis lors de l'examen.
• L'examen comportera uniquement des questions à choix multiples (voir ci-dessous pour les conventions de notation).
• L'examen est corrigé automatiquement. Il est donc crucial de bien suivre les instructions pour la réponse aux questions.

Important: L'examen de mi-semestre va avoir lieu dans l'auditorium SG 1138, le 9 novembre 2018, à partir de 15:15. Présentez vous à l'auditorium au moins 10 min à l'avance.

Examen final

• L'examen final sera organisé lors de la session d'examen de janvier.
• Cet examen comptera pour 80% de la note.
• L'examen comportera des questions liées au cours et aux exercices.
• La matière a connaître est constituée des parties du livre "Optimization: Principles and Algorithms" identifiées dans le plan du cours (voir ici).
• La démonstration des théorèmes suivants est à connaître :
  • Thm. 3.13: Feasible directions: linear case (p. 62)
  • Thm. 3.35: Identification of vertices (p. 80)
  • Thm. 3.40: Equivalence between vertices and feasible basic solutions (p. 86)
  • Thm. 3.44: Feasible basic directions (p. 90)
  • Thm. 4.5: Bound from dual function (p. 98)
  • Cor. 4.6: Objective functions of the primal and the dual (p. 98)
  • Thm. 4.9: Weak duality (p. 100)
  • Thm. 4.10: Duality and feasibility (p. 100)
  • Thm. 4.11: Optimality of the primal and the dual (p. 100)
  • Cor. 6.32: Optimality of the dual (p. 168)
  • Thm. 6.33: Strong duality (p.169)
  • Thm. 11.9: Validity of the Wolfe conditions (p. 271)
  • Thm. 11.10: Finiteness of the line search algorithm (p. 275)
  • Lem. 16.1 (p. 364)
  • Thm. 16.2: Vertex solution (p. 365)
  • Lem. 21.5: Longest simple path (p. 496)
  • Lem. 21.6: Finite number of simple paths (p. 496)
  • Thm. 21.10: characterization of a tree (p. 498). Implications 1⇒3, 1⇒4, 1⇒5 and 1⇒6
  • Thm 22.4: Integrality of the basic solutions (p. 537)
  • Thm. 22.6: Total unimodularity of the incidence matrix (p. 538)
  • Thm. 23.1: Optimality conditions for the shortest path problem (p. 553)
  • Thm. 23.9: Invariants of the shortest path algorithm (p. 561)
  • Thm. 23.10: Termination of the shortest path algorithm (p. 564)
  • Thm. 23.11: Bellman's equation (p. 564)
  • Thm. 23.14: Invariants of Dijkstra's algorithm (p. 570 and errata)
  • Thm. 26.1: Optimal solution of a partitioned problem (p. 627)
  • Cor. 26.2: Optimal solution of a partitioned problem (p. 627).
• Vous aurez droit exclusivement à quatre pages de résumés manuscrits (8 faces A4) maximum.
• Tout résumé non écrit à la main (imprimé ou photocopié) ne pourra pas être utilisé pour l'examen.
• Les résumés doivent porter la date ainsi que nom de l'étudiant.
• Les résumés seront ramassés avec les copies à la fin de l'examen et ne seront pas restitués. Faites des copies si vous désirez garder des archives.
• Aucun moyen électronique (calculatrice, ordinateur, etc.) n'est admis lors de l'examen.
• Pour les questions à choix multiples comportant n possiblités dont une est correcte, le nombre de points est égal à
  • 1 si la réponse est correcte,
  • 0 si aucune réponse n'est donnée,
  • 0 si plusieurs réponses sont données,
  • -1/(n-1) si la réponse donnée est incorrecte.
• La note totale (100%) sera ramenée à une note sur 6 en utilisant les critères suivant:

  De (inclus)	A (exclus)	Note
  0%	3.75%	1.00/6
  3.75%	7.5%	1.25/6
  7.5%	11.25%	1.50/6
  11.25%	15%	1.75/6
  15%	21.25%	2.00/6
  21.25%	27.5%	2.25/6
  27.5%	33.75%	2.50/6
  33.75%	40%	2.75/6
  40%	45%	3.00/6
  45%	50%	3.25/6
  50%	55%	3.50/6
  55%	60%	3.75/6
  60%	63.75%	4.00/6
  63.75%	67.5%	4.25/6
  67.5%	71.25%	4.50/6
  71.25%	75%	4.75/6
  75%	78.75%	5.00/6
  78.75%	82.5%	5.25/6
  82.5%	86.25%	5.50/6
  86.25%	90%	5.75/6
  90%	100%	6.00/6