Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 1 introduction a loptimisation combinatoire

Optimisation Combinatoire ème année Ing Filière Intelligence Arti ?cielle ?? ENSI Olfa BELKAHLA DRISS Ma? tre de Conférences à l ? ESCT Laboratoire LARIA LA Recherche en Intelligence Arti ?cielle ?? ENSI Université de la Manouba olfa belkahla esct uma tn CChapitre Introduction à la l ? optimisation Combinatoire ? Dé ?nitions ? Applications ? Modélisation ? Exemples de problèmes d ? optimisation Combinatoire ? Complexité théorique des problèmes CQu ? est-ce que l ? optimisation ? L ? optimisation est une branche des mathématiques et de l ? informatique en tant que discipline cherchant à ? Modéliser ? Analyser ? Résoudre analytiquement ou numériquement les problèmes réels CUn problème d ? optimisation ? Un problème d ? optimisation est un modèle mathématique formel d ? un problème réel ? On cherche à minimiser ou maximiser une fonction objectif f tout en respectant d ? éventuelles contraintes CClassi ?cation de l ? optimisation Par rapport à la nature des variables Par rapport aux critères Par rapport aux contraintes CClassi ?cation de l ? optimisation Par rapport à la nature des variables CClassi ?cation de l ? optimisation Par rapport à la nature des variables ? L'optimisation continue l ? espace de recherche est continu ? L ? optimisation discrète l ? espace de recherche est discret et in ?ni ? L ? optimisation combinatoire c ? est une optimisation discrète mais avec un espace de recherche ?ni dénombrable CClassi ?cation de l ? optimisation Par rapport aux critères ? L'optimisation Mono-objectif une seule fonction objectif min ou max ? L'optimisation Multi-objectifs plusieurs fonctions objectif à la fois CClassi ?cation de l ? optimisation Par rapport aux contraintes ? L'optimisation avec contraintes fonction objectif sous des contraintes ? L'optimisation sans contraintes fonction objectif sans contraintes CCombinatoire ? En mathématiques la combinatoire appelée aussi analyse Combinatoire relatif aux combinaisons ? Elle étudie les di ?érentes combinaisons pour la variable X d'un problème d'optimisation sur un ensemble discret et ?ni d'éléments ??Etudier les dénombrements de ces ensembles CL ? optimisation combinatoire ? L ? optimisation combinatoire est une branche de l'optimisation en mathématiques appliquées et en informatique également liée à la recherche opérationnelle l'algorithmique et la théorie de la complexité ? L ? optimisation combinatoire un sousensemble de l'optimisation discrète à nombre de solutions ?nies CUn problème d ? optimisation combinatoire ? Un problème d'optimisation combinatoire consiste à trouver la meilleure solution dé ?nie par une fonction objectif parmi un ensemble discret de solutions réalisables ? La résolution se ramène à l'examen d'un nombre ?ni de combinaisons mais très grand ? Pb cette résolution se heurte à une explosion du nombre de combinaisons à explorer CUn problème d ? optimisation combinatoire ? Une solution est une a ?ectation de valeurs aux variables du problème Elle spéci ?e la valeur de la fonction objectif ? Une solution est admissible réalisable si elle satisfait toutes les contraintes du problème ? Une solution est dite optimale si elle est réalisable et correspond à la meilleure valeur