Programme de l'examen

Aucun document ne sera autorisé

• Il peut y avoir quelques questions sur ce qui a été vu avant le partiel
• Programmation linéaire : définitions, changement de forme (canonique <-> standard)
• Résolution d'un PL par méthode graphique (en dimension 2)
• Utilisation de l'algorithme du simplexe : si le PL est donné sous forme standard, on se ramène à une forme canonique et les variables d'écart (slack variables) donnent une base initiale. Itérations de l'algorithme jusqu'à trouver l'optimum.
• Simplexe à 2 phases
• Trouver le dual d'un PL. Théorème de dualité faible et forte.
• Programmation linéaire en nombre entiers : définition, relaxation.
• Branch and bound : principe de base, utilisation de la méthode (revoir l'exemple du sac à dos dans le cours, par exemple)