Programmation linéaire et algorithme du simplexe : la solution à tous les problèmes ?

Le jeudi 28 novembre 2024 12h00-13h00, (Chartreuse, salle 8C-244), Jacques-Olivier Lachaud (LAMA, USMB) nous fera un exposé intitulé : “Programmation linéaire et algorithme du simplexe : la solution à tous les problèmes ?”.

Résumé : La programmation linéaire ou optimisation linéaire désigne un problème où, en jouant sur des choix de variables, on cherche à maximiser un profit ou minimiser un coût, tout en veillant à respecter un ensemble de contraintes linéaires sur ces variables. Un nombre hallucinant de problèmes se formalisent ainsi, dans des domaines aussi divers que la gestion, l'économie, la logistique, l'imagerie, les réseaux, l'algorithmique, la géométrie, la compilation, la fabrication de processeur, l'agriculture, le militaire, etc. Nous verrons sur quelques exemples comment fabriquer un programme linéaire, puis nous présenterons l'algorithme du Simplexe (Danzig, 1947), qui reste une des méthodes les plus efficaces pour résoudre ce type de problème. Ses forces est ses faiblesses seront enfin évoqués.