Remerciez-le!

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

Optimisation Combinatoire 3ème année Ing., Filière Intelligence Artificielle –

Optimisation Combinatoire 3ème année Ing., Filière Intelligence Artificielle – ENSI Olfa BELKAHLA DRISS Maître de Conférences à l’ESCT Laboratoire LARIA LA Recherche en Intelligence Artificielle – ENSI Université de la Manouba olfa.belkahla@esct.uma.tn Chapitre 1 Introduction à la l’optimisation Combinatoire Définitions Applications Modélisation Exemples de problèmes d’optimisation Combinatoire Complexité théorique des problèmes Qu’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 3 Un 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 4 Classification de l’optimisation 1. Par rapport à la nature des variables 2. Par rapport aux critères 3. Par rapport aux contraintes 5 Classification de l’optimisation 1. Par rapport à la nature des variables 6 Classification de l’optimisation 1. 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 infini L’optimisation combinatoire : c’est une optimisation discrète mais avec un espace de recherche fini (dénombrable) 7 Classification de l’optimisation 2. 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 8 Classification de l’optimisation 3. Par rapport aux contraintes L'optimisation avec contraintes : fonction objectif sous des contraintes L'optimisation sans contraintes : fonction objectif sans contraintes 9 Combinatoire En mathématiques, la combinatoire, appelée aussi analyse Combinatoire, relatif aux combinaisons Elle étudie les différentes combinaisons pour la variable X d'un problème d'optimisation sur un ensemble discret et fini d'éléments Etudier les dénombrements de ces ensembles 10 L’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 sous- ensemble de l'optimisation discrète à nombre de solutions finies. 11 Un problème d’optimisation combinatoire Un problème d'optimisation combinatoire consiste à trouver la meilleure solution définie par une fonction objectif parmi un ensemble discret de solutions réalisables. La résolution se ramène à l'examen d'un nombre fini de combinaisons, mais très grand. Pb : cette résolution se heurte à une explosion du nombre de combinaisons à explorer. 12 Un problème d’optimisation combinatoire Une solution est une affectation de valeurs aux variables du problème. Elle spécifie 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 de la fonction objectif. 13 Un problème d’optimisation combinatoire Etant donnés un ensemble Ωde combinaisons et une fonction f : Ω→IR, il s'agit de trouver la combinaison de Ω minimisant f Formellement : s* ∈Ω, f(s*) ≤f(si), ∀si ∈Ω Terminologie :  Ωou S : espace de recherche, espace des états/configurations/solutions/alternatives  f : fonction objectif, fonction coût/économique  x* (ou s*) : optimum, minimum 14 Applications Problème du voyageur de commerce TSP Ses extensions : les problèmes de transport (VRP, DARP, SARP, etc) Problème du sac à dos Ses généralisations : Bin-Packing problem, problème de stockage de conteneurs Problème SAT Job shop Scheduling problem (ordonnancement de tâches dans un atelier de production) Healthcare scheduling problems (patients admission, nurse, operation room, surgery, etc.) Allocation de fréquences pour les réseaux radio-mobiles Routage dans les réseaux de télécommunication Planification des activités d’une mission spatiale … 15 Les problèmes d’optimisation de base La complexité est connue Problèmes théoriques très étudiés : Plusieurs problèmes réels peuvent se ramener à ces problèmes classiques Benchmarks 16 Modélisation Outils de modélisation pour la résolution des problèmes d’O.C : Théorie des graphes : modélisation naturelle dans certains problèmes (plus court chemin, ordonnancement, etc.) PLNE (programmes linéaires en nombres entiers) : un ensemble de contraintes linéaires et une fonction objectif linéaire portant sur des variables à valeurs entières (problèmes de type sac à dos, ordonnancement, etc.) 17 Exemple : TSP Traveling Salesman Problem 18 Explosion combinatoire Le problème du voyageur de commerce (TSP) où un voyageur de commerce doit parcourir les N villes d’un pays en effectuant le trajet le plus court Il doit visiter chaque ville une et une seule fois et revenir à la ville de départ Etant données des distances entre chaque paire de villes, il doit minimiser la distance totale parcourue Une résolution par énumération nécessite de calculer (N-1)!/2 trajets entre les villes Pour N=24 villes, il faut en générer 23!/2=(2.585201673888498e+22)/2 combinaisons Modélisation : TSP On peut représenter ce problème par un graphe : chaque ville correspond à un sommet et chaque arête correspond à une paire de villes pouvant être visitées l’une à la suite de l’autre Formellement, une instance est un graphe complet G=(V,A,w) avec V un ensemble de sommets, A un ensemble d’arêtes et w une fonction de coût sur les arcs. 19 T.A.F : Recherche sur les VARIANTES de TSP Le problème est de trouver le plus court cycle hamiltonien dans le graphe G = un tour complet dans ce graphe qui minimise la somme des distances Formulation  Les variables de décisions  L’objectif  Les contraintes Max Z = A.X sous : C.X ≤B X ≥0 20 Formulation : Exercice n°1 • 3 produits P1, P2 et P3 • Contribution unitaire dans le profit est respectivement 5d, 8d et 4d • Chaque unité de P1 nécessite 2 heures ouvriers et 7 kg matière 1ère • Chaque unité de P2 nécessite 4 heures ouvriers et 6 kg matière 1ère • Chaque unité de P3 nécessite 3 heures ouvriers et 5 kg matière 1ère 250 heures ouvriers 100 kg matières premières • Fabriquer au moins 10 unités de P1 Ecrire un programme linéaire pour déterminer la quantité optimale à fabriquer de chacun de ces 3 produits 21 Formulation : Exercice n°1 22 Contraintes : Heures ouvriers : 2X1+4X2+3X3 <=250 Matières 1ères : 7X1+6X2+5X3 <=100 X1 >=10 X1 >=0 X2 >=0 X3 >=0 • Les variables de décision : X1 : la quantité fabriquée du produit P1 X2 et X3 • Fonction objectif : Max Z = 5X1 + 8X2 + 4X3 Choisir 2 ouvriers parmi 3 les affecter aux 2 machines Ecrire un programme linéaire aboutissant à une affectation optimale des ouvriers 23 Coûts Ouvrier 1 Ouvrier 2 Ouvrier 3 Machine 1 10 5 7 Machine 2 11 12 3 Formulation : Exercice n°2 Problème d’affectation 24  Choisir 2 ouvriers parmi 3  les affecter aux 2 machines  Pgme linéaire aboutissant à une affectation optimale des ouvriers Coûts Ouvr 1 Ouvr 2 Ouvr 3 Machine 1 10 5 7 Machine 2 11 12 3 Contraintes : ∑ Xi1 = 1 pour i=1,2,3 machine 1 ∑ Xi2 = 1 pour i=1,2,3 machine 2 ∑ X1j <= 1 pour j=1,2 ouvrier 1 ∑ X2j <= 1 pour j=1,2 ouvrier 2 ∑ X3j <= 1 pour j=1,2 ouvrier 3 Xij ∈{0,1} Formulation : Exercice n°2 Variables de décision: Xij = { 1 si l’ouvrier i est affecté à la machine j 0 sinon Fonction objectif : Min C = 10 X11 + 5X21 + 7X31 + 11X12 + 12X22 + 3X32 En algorithmique, le problème du sac à dos, noté KP (Knapsack Problem) est un problème d'optimisation combinatoire. Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. 25 Le problème du sac à dos (Knapsack Problem) Input : n objets, un vecteur coûts et un vecteur profits Objectif : sélectionner un sous-ensemble d’objets en maximisant le profit total et en respectant une contrainte donnée 26 Le problème du sac à dos (Knapsack Problem) Exemple : Quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? xj : variable de décision associée à l’objet j (j ∈1..n) : 0 ou 1 n : le nombre d'objets pj : l’utilité ou profit apporté par l'objet j (j ∈1..n) aj : le poids de l'objet j (j ∈1..n) b : la capacité totale du sac 27 Le problème du sac à dos (Knapsack Problem) Modélisation Bin-Packing problem Le problème de bin packing peut s'appliquer à un grand nombre de secteurs industriels ou informatiques : • Pour la version classique en une dimension : • rangement de fichiers sur un support informatique ; • découpe de câbles ; • remplissage de camions ou de containers avec comme seule contrainte le poids ou le volume des articles. • Pour la version en deux dimensions : • découpe de matière première ; • placement de boîtes sur une palette (sans superposition de boîtes) ; • placement dans un entrepôt (sans superposition de boîtes). • Pour la version en trois dimensions : • rangement d'objets physiques dans des boîtes, un entrepôt, des camions, etc. uploads/Science et Technologie/ chapitre-1-introduction-a-loptimisation-combinatoire.pdf