Remerciez-le!

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

Université A.MIRA de Béjaia Faculté des Sciences Exactes Département d’Informat

Université A.MIRA de Béjaia Faculté des Sciences Exactes Département d’Informatique Module : Techniques d’Optimisation Dr TARI Abdelkamel Maître de Conférences Habilité Directeur du Laboratoire de Recherche LIMED Février 2014 Programme du module • Introduction à l’Optimisation Combinatoire • Problème de flôt maximum • Programmation linéaire en nombres entiers • Programmation Booléenne • Parcours Hamiltonien et Eulerien dans un graphe Février 2013 Quelques informations utiles • Pré requis du module: – Théorie des graphes – Programmation Linéaire • Ouvrages recommandés: – Cote: 511.5/12- Claude Berge. Graphes et Hypergraphes – Cote: 003/23-Roseaux. Exercices corrigés – Cote: 003/19-Roseaux. Exercices corrigés • Site du groupe: e-learning de l’université (à construire): master1oc2014@gmail.com • Mot de passe: bejaia2014 Techniques d'Optimisation Février 2014 Définition de la RO • Operations Research (OR) is a discipline that deals with application of advanced analytical methods to help make better decisions. (Wikipédia). • Advanced analytical methods include mathematical logic, graph, network analysis, Petri net, queuing theory, simulation etc. • Concevoir et implémenter des approches pour résoudre des problématiques liées à des domaines diverses (informatique, médecine, économie, finance, militaire etc.) jusqu’à satisfaction du (des) décideur (s). 4 Techniques d'Optimisation Méthodologie d’approche 1- Analyse du système dans lequel le problème est posé (Approche CATWOE) 2- Identifier les facteurs (Contrôlables et non contrôlables) et les objectifs 3- Construire le modèle (Graphe, Réseaux de Pétri, Mathématiques, Simulation etc.) 4) Elaborer une approche de résolution (exacte ou approchée) 5- Concevoir et implémenter les algorithmes de l’approche de résolution 5 Techniques d'Optimisation Formulation d’un problème • Objectifs du système (minimisation de coût, minimisation de l’énergie dans les réseaux de capteurs, etc.) • Facteurs contrôlables: Variables de décisions • Facteurs non contrôlables: Contraintes et ceux imposés par l’environnement • Exemple voyageur de commerce: Objectif: Minimiser la longueur totale parcourue Contraintes: Cycle Hamiltonien (pas de cycles parasites), les distances entre les sommets. 6 Techniques d'Optimisation F Modélisation d’un problème • Un modèle est une représentation d’une réalité. • Forme d’un modèle: Mathématique (linéaire et non linéaire), graphe (toutes ses topologies: arbre, arborescence, biparti etc.), réseau (toutes ses formes: Transport, Pétri, Automate à états finis etc.), simulation, théorie des jeux etc. • Traduire les objectifs et contraintes en termes de variables de décision 7 Techniques d'Optimisation Exemple de Modélisation On associe au problème un réseau R=(X, U, l) Où: X: l’ensemble des villes, U les liens entre ces villes et l: la longueur entre ces villes • Variables de décision: xij = 1 si l’arc (i, j) est emprunté et 0 sinon ) 0 , 1 ( ,..., 1 1 ,..., 1 1 1 1 1 1              ij n i ij n j ij n i n j ij ij x n j x n i x x l Z Min 8 Techniques d'Optimisation Problème d’Optimisation Combinatoire • Un (POC) consiste à chercher le minimum S* d’une application  le plus souvent à valeurs entières ou réelles sur un ensemble fini S • Un problème d’existence (PE ) consiste à chercher sS • PE équivalent à un POC Techniques d'Optimisation 9        S s s f Min s f S s Trouver ) ( ) ( * * Approches de résolution (1/2) • Méthodes exactes: – Programmation linéaire (Simplexe et ses variantes) – Programmation non linéaire avec ou sans contraintes (relaxation de Lagrange, Khun Tecker – Programmation en nombres entiers et bivalentes (Branch and Bound) – Arbre recouvrant (Algorithme Glouton: Kruskal) – Cheminement (Algorithme Glouton:Djikstra, Bellman, Ford) – Flôt (Ford et Fulkerson) – Etc… 10 Techniques d'Optimisation Approches de résolution (2/2) • Méthodes approchées – Heuristiques (recherche locale) • Algorithmes de construction (plus proche voisin, plus proche insertion, meilleure insertion) - Métaheuristiques (recherche globale) - Algorithmes génétiques - Recherche Taboo - Recuit simulé - Colonies de fournies etc. 11 Techniques d'Optimisation Classification naïve de problèmes - Problème facile ou problème difficile • Si le problème est "facile": Trouver un algorithme efficace. • Si le problème est « difficile» et de "grande taille": Chercher une solution approchée et garantir l’efficacité de cette solution. 12 Techniques d'Optimisation Quelques Applications(1/3) • Parcours d’un graphe (existence de chaîne, chemin, cycle et circuit) • Programmation linéaire (recherche d’une solution de base réalisable optimale parmi toutes les solutions de bases réalisables) • Problèmes de routage dans les réseaux (ad-hoc, capteurs, DTN etc.): entre deux noeuds particuliers (facile), entre n’importe quel couple de nœud du réseau (difficile). • Découverte sémantique de services web: Pour une requête d’un utilisateur, il s’agit de trouver un service (atomique ou virtuel) parmi un nombre important de services celui qui satisfait cette requête . 13 Techniques d'Optimisation Quelques applications (2/3) • Emplois du temps : Planifier n cours en un minimum de temps, certains cours ne pouvant avoir lieu en parallèle (partage des ressources: classe ou prof). • Localisation d’entrepôts: Combien faut-il créer d'entrepôts et où faut-il les installer de façon à satisfaire tous les clients avec un coût total minimal? Application réelle: Algérie Télecom où les entrepôts sont les stations de téléphonie • Etc. 14 Techniques d'Optimisation Quelques Applications (3/3) • Optimisation des tournées de véhicules dans les problèmes de distribution, organisation des centres logistiques. • Bin packing: Comment mettre les objets dans les Boîtes en utilisant le moins possible de Boîtes? Problèmes de chargement en conteneurs des bateaux, problème de stockage de l’information sur des supports • Voyageur de commerce, postier chinois • Ordonnancement d’ateliers : Ordonnancer les passages sur les machines(Facile: Aspect temporel, difficile: aspect ressources • Etc. 15 Techniques d'Optimisation La théorie des Graphes (TG)  TG(Vocabulaire, théorèmes, algorithmes,…) a été développée depuis le 20ème siècle par Claude Berge  TG est un outil puissant de modélisation conduisant à des solutions efficaces. Modéliser une situation à l'aide d'un graphe revient à identifier l’ensemble X des sommets (nœuds) et à caractériser l’ensemble U des arêtes (arcs). 16 Techniques d'Optimisation Claude BERGE Définitions et terminologies • L’ordre d’un graphe est égal au nombre de ses sommets. L’ordre du graphe G est égal à 4. • On dit que deux sommets sont adjacents s’ils sont reliés par une arête (arcs). • Une arête (arc) est incidente à un sommet si ce dernier est une de ses deux extrémités. • Deux arêtes (arcs) sont adjacentes si au moins une de leurs extrémités est commune. • Un graphe est dit simple si chaque couple de sommets est relié par au plus une arête (arc). • Un graphe est complet si chaque sommet est adjacent à tous les autres, c'est a dire si toutes les arêtes possibles existent (sauf les boucles). 17 Techniques d'Optimisation Concepts et résultats • Un sommet est isolé s’il n’est adjacent à aucun autre sommet. Un graphe est nul s’il n’a aucune arête, c’est un ensemble de sommets isolés. • Le degré d’un sommet x, dG(x), est le nombre d’arêtes (arcs) qui lui sont incidentes (intérieurement et extérieurement dans le cas orienté). • La somme des degrés des sommets est paire. • Le nombre d’arêtes d’un graphe est égal à la somme des degrés des sommets divisée par deux. • Le nombre de sommets de degré impair d’un graphe non orienté est donc toujours pair. • Dans un graphe simple d’ordre n on a: dG(x)≤(n-1) xX • Le diamètre d’un graphe est la plus grande distance entre deux sommets 18 Techniques d'Optimisation Quelques structures d’un graphe (1/3) • Sous graphe, graphe partiel et sous graphe partiel • Parcours (chaîne, cycle, chemin, circuit) Hamiltonien (élémentaire) et Eulerien (simple) d’un graphe • Cycle et cocycle engendré par une partie A de X • Arbre et co-arbre – Construction d’un arbre recouvrant – Problème de l’arbre de poids minimum (Algorithme de Kruskal) (problème Facile) – Problème de la recherche arborescente (Problème difficile) – Problèmes de cheminiment (facile et difficile) Techniques d'Optimisation 19 Quelques structures d’un graphe (2/3) • Une clique est un sous-ensemble de sommets qui induit un sous graphe complet et symétrique. • Une clique d’ordre n sommets possède n(n-1)/2 arêtes • On note Kn l’ensemble des cliques d’ordre n d’un graphe G. • Une clique C est dite maximale s’il n’existe pas une autre clique C’ qui la contient. On note G l’ensemble des cliques maximales de G • Le problème de la recherche d’une clique maximale de cardinalité maximale est un POC difficile. • Applications: • Réseaux sociaux: Rechercher une communauté d’individus tous en relation • Biologie l’interaction entre gènes, métabolites ou protéines Techniques d'Optimisation 20 Quelques structures d’un graphe (3/3) • Un couplage C est un ensemble d’arêtes 2 à 2 non adjacentes. – Recherche d’un couplage de cardinalité maximale • Un stable S est un ensemble de sommets 2 à 2 non adjacents. – Recherche d’un stable de cardinalitémaximale • Un transversal T est un ensemble de sommets tel que chaque arête de G a au moins une extrémité dans T. – Recherche d’un Transversal de cardinalité minimale Techniques d'Optimisation 21 Exemple • Soit le graphe non orienté suivant: 2 7 1 3 6 8 4 5 Déterminer un uploads/Science et Technologie/ chapitre-1 14 .pdf