OC-Cours

Optimisation combinatoireDéfinitionBeaucoup de problème d’ordre pratique ou théorique nécessite de prendre, parmi un en-semble de choix possibles (très large), le meilleur choix selon un critère donné.RemarqueDomaine largement étudié en informatique, en mathématiques appliquées, en sciences de gestion, en génie industriel…ObjetEtudier un ensemble de modèles et méthodes de résolution (méthodes dites gloutonnes, programmation dynamique, métaheuristiques, etc.)Plan1. Introduction2. Modèles3. Méthodes de résolution - Glouton - Programmation dynamique - Méthodes heuristiques / métaheuristiques4. Applications1. IntroductionExemples d’applications — Affectation de ressourcesRecouvre un grand nombre de problèmes réels tels que l’affectation de chauffeurs, l’affecta-tion des fréquences sur les antennes de télécommunications pour minimiser les interférences dans les réseaux de mobiles, ou le positionnement d’antennes. Les critères sont : le nombre de sites et la rentabilité les sites choisis. D’autres problèmes : la planification de prise de vue de Spot 5 (satellite avec 3 caméras), les tournées de véhicule ou la bioinformatique.2. Modèles2.1 PL (Programmation Linéaire)Problème facile2.2 PLNE (Programmation Linéaire en Nombre Entier)cf. PLNE 0/1, complexité exponentielle NP-complet, méthode de résolution Branch & Bound2.3 PNL (Programmation Non Linéaire)2.4 Programmation mixte2.5 Graphes• Coloration• Clique• Ensemble indépendant• PVCM1 Info 2005 ...