Remerciez-le!

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

Chap 3 1 Partie Introduction a l ? optimisation combinatoire Qu'est-ce que l'Optimisation Combinatoire L'Optimisation Combinatoire consiste à trouver un meilleur choix parmi un ensemble fini souvent très grand de possibilités Exploiter et explorer les pro

Partie Introduction a l ? optimisation combinatoire Qu'est-ce que l'Optimisation Combinatoire L'Optimisation Combinatoire consiste à trouver un meilleur choix parmi un ensemble fini souvent très grand de possibilités Exploiter et explorer les propriétés structurelles des problèmes bonnes caractérisations décompositions ? etc qui permettent de concevoir des algorithmes efficaces exacts ou approchés ou alors montrent que de tels algorithmes n'existent pas Quelques problèmes d ? optimisation Développement des robots au service du monde industriel Trajectoire du meilleur itinéraire GPS Recalage médical Exemples de problèmes réseaux On souhaite approvisionner une région en eau potable différents consommateurs différents points de pompage contraintes de pression Objectif minimiser le nombre points de pompage et la longueur du réseau Notions et terminologies d ? optimisation combinatoire Définition Un problème d ? optimisation noté nn nn nn se définit comme la recherche du minimum ou du maximum d ? une fonction donnée tout en respectant un ensemble de définitions et de contraintes nn est l'ensemble non vide des solutions réalisables et nn nn une fonction objectif qui associe à chaque nn ? nn un réel appartenant à n ensemble des nombres réels qui sera utilisé comme critère pour comparer l'optimalité entre les différentes solutions réalisables Il est possible de passer d ? un problème de maximisation à un problème de minimisation gr? ce à la propriété suivante nnnnnn nn nn nnnnnn - nn nn Généralement une solution nn ? nn est un vecteur d ? un espace à nn dimensions Notions et terminologies d ? optimisation combinatoire Les problèmes d'optimisation continue versus discrète n Problème d'optimisation discret les variables de décision sont discrètes sous la forme d'entiers ou de binaires n Problèmes d'optimisation continue les variables peuvent prendre n'importe quelle valeur ce sont des réels n Les problèmes d'optimisation continue sont généralement plus simples à résoudre n Un problème d'optimisation mêlant variables continues et variables discrètes est dit mixte Notions et terminologies d ? optimisation combinatoire n Problèmes d'optimisation mono-objectif ou multi-objectif Les problèmes mono-objectif sont définis par une unique fonction objectif Les problèmes multi-objectifs existent quand un compromis est à rechercher entre plusieurs objectifs n Problèmes d'optimisation avec et sans contrainte Distinguer les problèmes o? des contraintes existent sur les variables de décision Ces contraintes peuvent être simplement des bornes et aller jusqu'à un ensemble d'équations de type égalité et de type inégalité Notions et terminologies d ? optimisation combinatoire Définition Une contrainte d ? un problème est une restriction imposée par la nature et les caractéristiques du problème sur les solutions proposées Chaque problème d'optimisation peut contenir plus d'une contrainte c'est ce qui fait la grande variété des problèmes Définition L ? espace de recherche nn d ? un problème est composé de l ? ensemble de valeurs pouvant être prises par les variables nnnn nnnn nnnn ? nnnn qui construisent la solution nn réalisable Définition Le voisinage nn nn d ? une solution nn est un sous ensemble de nn dont les membres sont des solutions proches voisines de la solution nn Une solution