Soutenance mémoire
Les problèmes d’optimisation occupent actuellement une place grandissante dans la communauté scientifique. Ces problèmes peuvent être combinatoires (discrets) ou à variables continues, avec un seul ou plusieurs objectifs (optimisation mono ou multi-objectifs), statiques ou dynamiques, avec ou sans contraintes. L’optimisation combinatoire est une branche de l’optimisation en mathématiques appliquées et en informatique, elle est également située au carrefour des différentes sciences et technologies liées à la recherche opérationnelle, la théorie des graphes et l’algorithme. C’est plutôt incontournable dans tous les domaines car dans la plupart des cas, on l’appelle souvent : ‘‘Aide à la décision’’.
PROBLEME D’OPTIMISATION ET THEORIE DES GRAPHES
Un problème d’optimisation consiste à chercher la meilleure solution optimisant un critère ou une fonction donnée. Il occupe une place très importante dans plusieurs domaines scientifiques, surtout en RO (Recherche Opérationnelle), en Economie, Mathématique et Informatique ; on l’appelle souvent aussi POC (Problème d’Optimisation Combinatoire). Dans la plupart des cas, même les problèmes extrêmement complexes et de tout type peuvent être ramenés à un POC pour qu’on puisse les résoudre. Cependant on étend la notion de complexité aux problèmes d’optimisation. Le contexte actuel défini que l’optimisation cherche à trouver une solution optimale à un problème donné. Sans perte de généralités, un problème d’optimisation sous contraintes contient deux aspects, à savoir ‘’l’aspect contraintes’’ et ‘’l’aspect optimisation’’. La plupart du temps, l’optimisation d’un modèle mathématique doit respecter le sens d’un critère de contrainte donné. Parmi les principaux outils de modélisation utilisée pour la résolution des problèmes d’optimisation combinatoire, nous trouvons la théorie des graphes. En effet, la modélisation par les graphes est naturelle dans certains problèmes, par exemple la recherche du plus court chemin,…. Dans ce chapitre nous présentons deux outils mathématiques utilisés dans la résolution de problèmes d’optimisation en considération des contraintes et à la recherche d’extremum. La première étape consiste à définir la classification et les outils des méthodes d’optimisation. Ensuite, la deuxième modélise la résolution de problèmes combinatoire concrets, à l’aide de l’ensemble des techniques et outils mathématiques mis au point par la Théorie des Graphes.
Principes de l’optimisation
L’optimisation permet de minimiser ou maximiser des fonctions des systèmes dans lesquels peut intervenir un grand nombre de paramètres. On peut déterminer aisément ces objectifs grâce à l’application des outils mathématiques. Ces outils nous permettent de trouver les extremums des fonctions mono ou plusieurs variables, incluant les minimums ou les maximums. Les méthodes que nous allons étudier sont considérées comme des principes généraux pour comprendre les problèmes de l’optimisation. Les principes sont les mêmes mais l’objectif principal converge vers la recherche d’une solution adéquate. Dans la suite, nous allons présenter quelques outils mathématiques utilisés dans la résolution de problèmes d’optimisation (recherche d’extremum, ajustements etc.). Ils sont formulés dans le cas où la variable à optimiser est à valeurs réelles ; toutefois la plupart de ces outils se généralisent sans difficulté dans le cas d’une variable prenant la forme d’un vecteur à composantes réelles.
Pour la résolution mathématiques, on trouve toujours la présence d’une ou des contraintes. On distingue deux types de contraintes : les contraintes d’égalité et les contraintes en inégalité. L’ensemble des solutions satisfaisant toutes les contraintes est appelé l’ensemble admissible.
Outils mathématiques pour l’Optimisation
Notations
– On note de manière générale dans ce cours ?, ?, ? des espaces vectoriels normés, ? un point quelconque de ?, ? une fonction de ? dans ?, ?∗ une fonction de ? ???? ℝ.
– On note 〈?, ?〉 un produit scalaire quelconque.
– Si ? = ℝ? , un vecteur ? a pour composantes ? = (?1, ?2 . . . , ??), une fonction ?∗ (?) est donc une fonction de ? variables notées aussi ?∗ (?1, ?2 . . . , ??). On note dans ce cas 〈?, ?〉 = ∑ ????? le produit scalaire canonique de deux vecteurs ? ?? ?.
Soit ? un espace de dimension finie et un produit scalaire noté 〈?, ?〉 et soit ?∗ une fonction de V dans ℝ différentiable en ?. Il existe alors un vecteur ‘’gradient’’, noté : ∇?∗ (?), tel que :
??∗ (?). ℎ = 〈∇?∗(?), ℎ 〉 (1.01)
Systèmes non linéaires et optimisation
Considérons un système non linéaire de n équations à n inconnues : ?(?) = 0 défini par une application ?(?) de ℝ? dans lui-même. L’étude générale de l’existence et du nombre des solutions d’un tel système est un problème difficile, il n’existe pas, comme pour les systèmes linéaires, de critère d’existence. Mais s’il existe une fonction “potentielle” ?∗ (?) telle que :?(?) = ∇ ?∗ (?). [1.01] Les solutions du système sont les points stationnaires de ?∗ (?). Or l’étude de la fonction ?∗ (?) permet sous certaines conditions d’affirmer l’existence d’au moins une solution, son éventuel unicité ou la présence d’un nombre minimal de solutions. Pour l’existence on utilisera la proposition. Si ?∗(?) tend vers +∞ quand ||?|| tend vers l’infini alors ?∗(?) admet au moins un minimum et le système ?(?) = 0 admet donc au moins une solution.
Systèmes linéaires et fonction convexe
La forme générale d’un système linéaire est ?? = ?. Pour le résoudre on peut utiliser:
– des méthodes directes qui sont pour la plupart des variantes de la méthode classique d’élimination des inconnues de Gauss ;
– des méthodes itératives où l’on construit une suite qui converge vers la solution du système.
On note ? ⊂ ? un ensemble convexe.
Définition 1.01 : Fonctions convexes
Les fonctions convexes sont définies comme suit : [1.01] [1.02]
∀?, ? ∈ ?, ∀? ∈ [0, 1] ???? ??? ?∗(?? + (1 − ?)? ≤ ??∗(?) + (1 − ?)?∗ (?) (1.06)
De plus
Si ?∗(?) est convexe l’ensemble {? / ?∗(?) ≤ ?} est convexe, mais la réciproque est fausse. La fonction?∗(?) est dite strictement convexe si :
∀?, ? ∈ ?, (? ≠ ?) et ∀? ∈ ]0,1[ ??????????
?∗(?? + (1 − ?)? < ??∗(?) + (1 − ?)?∗(?)(1.06) .
|
Table des matières
INTRODUCTION
CHAPITRE 1. PROBLEME D’OPTIMISATION ET THEORIE DES GRAPHES
1.1 Introduction
1.2 Principes de l’optimisation
Outils mathématiques pour l’Optimisation
Systèmes non linéaires et optimisation
Systèmes linéaires et fonction convexe
1.3 Optimisation sans et avec contrainte
Optimisation sous contraintes d’égalité
Optimisation sous contraintes d’inégalité
Programmation convexe et le Théorème de Kuhn – Tucker
Définition et terminologie d’un POC
1.4 Complexité des problèmes d’optimisation
Les systèmes complexes
Optimisation multi-objectif
Méthodes d’optimisation multi-objectif
Classification des méthodes d’optimisation multi-objectif
1.5 Théorie des graphes
Notations de théorie des graphes
Notions de base sur les graphes
Problèmes de chemins Eulérien
Complexité des problèmes d’optimisation
Relations Mathématique (théories des graphes) et informatique (Algorithme)
1.6 Relation entre ‘’Optimisation’’ et ‘’Graphe’’
1.7 Conclusion
CHAPITRE 2. RESOLUTION DES VRP ET SES INSTANCES
2.1 Introduction
2.2 Un problème de plus court chemin
Les tournées de véhicules
Les problèmes de transport
PVC (Le problème du voyageur de commerce) ou TSP (Travelling Salesman Problem)
Le VRP instancié du TSP
Les différentes variantes principales du VRP
Complexité
Modélisation de la théorie des graphes
2.3 Méthodes et techniques de résolution du VRP
Problème de tournées de véhicules sur nœuds
Les tournées sur arcs
Problème de tournées de véhicules sur arcs
Transformation des problèmes de tournées sur arcs en problèmes de tournées sur nœuds
Autres problèmes sur arcs sans capacité
CARP – Le problème de tournées sur arcs avec contrainte de capacité
Applications et extensions du CARP
2.4 Conclusion
CHAPITRE 3. METHODE DE RESOLUTION DES POC A L’AIDE D’UNE HYBRIDATION DES ALGORITHMES COUPLES AVEC SIG & SMA
3.1 Introduction
3.2 Méthodes de résolution
Méthodes exactes
Heuristiques
Métaheuristiques
Méthodes hybrides
3.3 Coopérations entre méthodes de résolutions
Etat de l’art des coopérations Méta/Exacte
Classification de l’hybridation de méthodes exactes et de métaheuristiques
Coopération métaheuristiques-métaheuristiques
3.4 Proposition d’une heuristique hybride
Les méthodes hybrides
Les métaheuristiques hybrides
Evaluation des hybrides
3.5 Une nouvelle architecture SMA (Système Multi-Agent) – SIG (Système
d’Information Géographique)
Le SIG (Système d’Information Géographique)
Les Systèmes Multi-Agents SMA
3.6 Une approche hybride originale entre SIG et SMA
Avantages d’une approche hybride SMA – SIG
Contraintes d’un couplage SMA-SIG
Cas réel pour le couplage SMA- SIG
3.7 Conclusion
CHAPITRE 4. LA RÉSOLUTION ET DETERMINATION DES TOURNEES OPTIMISEES PROCHE DE LA REALITE
4.1 Introduction
4.2 Affectation du trafic basée sur les activités
Notion de plus court chemin
Calcul de plus courts chemins
Algorithme de Résolution
Le plus court chemin élémentaire
Construction de deux chemins (u, v), (v, u) et d’un réseau Cs
Flots maximum
Voisinage k-Opt
Modèle d’écoulement de trafic
Modèles stochastiques & Modèle de file d’attente
4.3 Processus stochastique et simulation (File d’attente markovienne)
Processus de Markov à états discrets et à temps continu
Equations de Chapman-Kolmogorov
Particularités des Processus de Markov utilisés en Réseau routier
Processus de Markov particuliers pour Réseau routier
Processus de naissance et de mort
4.4 Trouver des solutions par approche multi-objectif à un problème monoobjectif
incertain
Problème de tournée de véhicule avec domaine incertaine (SVRP)
Résoudre un problème stochastique multi-objectif
Algorithmes d’optimisation adaptés aux problèmes de grande dimension
4.5 Coopération méta/exacte en optimisation multi-objectif
4.6 Hybridation proposée
4.7 Conclusion
CONCLUSION
