Remerciez-le!

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

METHODES D’OPTIMISATION COMBINATOIRE IRENE CHARON, OLIVIER HUDRY, ANNE GERMA RE

METHODES D’OPTIMISATION COMBINATOIRE IRENE CHARON, OLIVIER HUDRY, ANNE GERMA RESUME Cet ouvrage propose une introduction aux méthodes généralement utilisées dans le domaine de l'optimisation combinatoire. Son objectif est double : proposer un ensemble de modélisations classiques, à l'aide principalement de la théorie des graphes et de la programmation linéaire ; décrire un ensemble de méthodes exactes ou approchées pour résoudre les problèmes d'optimisation ainsi modélisés Composé de trois parties (programmation linéaire, algorithmes dans les graphes, méthodes d'optimisation combinatoire), l'ouvrage propose de nombreux exercices, tous corrigés. Issu d'un cours de première et deuxièmes années de l'Ecole Nationale Supérieure des Télécommunications, il s'adresse aux élèves des écoles d'ingénieurs, aux étudiants de deuxième cycle, ainsi qu'à tous ceux (ingénieurs, chercheurs...) qui souhaitent se familiariser avec les méthodes d'optimisation combinatoire le plus souvent utilisées. TABLE DES MATIERES Introduction 1 I. L'algorithme du simplexe 5 I.1.Introduction 5 I.2.L'algorithme du simplexe appliqué à un exemple 7 I.3.La dégénérescence et le cyclage 10 I.4.Recherche d'un dictionnaire réalisable 13 I.5.Annexe : la forme du pivot 15 I.6.Exercices 16 II. Forme matricielle de la méthode du simplexe 19 II.1 Généralités 19 II.2.Version matricielle d'une itération de la méthode du simplexe 21 II.2.1.Recherche d'une variable entrante 21 II.2.2.Recherche d'une variable sortante 22 II.2.3.Actualisation 22 II.2.4.Résumé 22 II.3.Un exemple d'application de la méthode 23 II.4.Application au problème de découpe 26 II.5.Exercice 31 III. Dualité 33 III.1.Définition du problème dual 33 III.2.Théorème de la dualité 34 III.3.Le théorème des écarts complémentaires : un certificat d'optimalité 37 III.4.La signification économique du dual 38 III.5.Problème dual-réalisable 40 III.6.Exercices 41 IV. Généralités sur les graphes. Arbre couvrant de poids minimum 43 IV.1.Introduction à la théorie des graphes et définitions 43 IV.2.Représentation des graphes en machine 44 IV.2.1.Matrice d'adjacence (sommets-sommets) 45 IV.2.2.Tableau de listes d'adjacence 45 IV.3.Complexité d'un algorithme 46 IV.4.Le problème de l'arbre couvrant de poids minimum 47 IV.4.1.Définition du problème 47 IVA.2.Une application en réseaux 47 IVA.2.Une application en réseaux 47 IV.4.3.Une application en traitement d'images 48 IV.4.4.Algorithme de Kruskal 48 IV.4.5.Algorithme de Prim 50 IV.5.Exercices 52 V. Problèmes de plus courts chemins 55 V.1.Définition des différents problèmes 55 V.1.1.Définitions nécessaires à ce chapitre 55 V.1.2.Problèmes 56 V.2.Plus courts chemins d'un sommet à tous les autres : cas des valuations positives 57 V.2.1.Motivation 57 V.2.2.Algorithme de Dijkstra 58 V.3.Plus courts chemins d'un sommet à tous les autres : cas des graphes sans circuit 60 V.3.1.Motivation 60 V.3.2.Algorithme de Bellman 60 V.4.Plus courts chemins d'un sommet à tous les autres : cas général 62 V.4.1.Motivation 62 V.4.2.Algorithme de Ford 62 V.4.3.Algorithme général de Ford-Dantzig 63 V.5.Plus courts chemins de tout sommet à tout sommet : cas général 64 V.6.Exercices 65 VI. Parcours de graphes 69 VI.1.Définition d'un algorithme de « parcours de graphe » 69 VI.1.1.Cas orienté 69 VI.1.2.Cas non orienté 72 VI.1.3.Complexité 72 VI.2.Les parcours « marquer-examiner » 73 VI.2.1.Généralités 73 VI.2.2.Résultat d'un parcours « marquer-examiner » selon une file le parcours en largeur 74 VI.2.3.Résultat d'un parcours « marquer-examiner » suivant une pile 74 VI.3.Les parcours en profondeur 74 VI.3.1.Le cas orienté 74 VI.3.2.Le cas non orienté 76 VI.4 Applications des parcours en profondeur 78 VI.4.1.Application à la détermination des composantes fortement connexes 78 VI.4.2.Application à la détermination des sommets d'articulation d'un graphe non orienté 80 VI.4.3.Application à la détermination des composantes 2‑connexes d'un graphenon orienté 82 VI.5 Exercices 84 VII. Flot maximum et coupe de capacité minimum 85 VII.I.Introduction, théorème du flot et de la coupe 85 VII.1.1.Introduction 85 VII.1.2.Définitions, notations et problèmes 86 VII.1.3.Résultats théoriques 86 VII.1.4.Lien avec la programmation linéaire 87 VII.2.Algorithme de Ford et Fulkerson 88 VII.2.1.Chaîne augmentante 88 VII.2.2.Description de l'algorithme de Ford et Fulkerson 89 VII.2.3.Un exemple 91 VII.2.4.Preuve, convergence et complexité de l'algorithme 92 VII.3.Compléments : algorithme de Dinic et algorithme de Busacker et Gowen 93 VII.3.1.Graphe d'écart 94 VII.3.2.Algorithme de Dinic 94 VII.3.3.Algorithme de Busacker et Gowen 95 VII.4.Exercice 96 VIII. Applications de la théorie des flots 97 VIII.1.Application à la détermination des connectivités d'un graphe 97 VIII.1.1.Forte arc-connectivité d'un graphe orienté 97 VIII.1.2.Détermination de l'arête connectivité d'un graphe non orienté 99 VIII.1.3.Forte connectivité d'un graphe orienté, connectivité d'un graphe non orienté 100 VIII.2.Couplage maximum dans un graphe biparti 101 VIII.2.1.Un exemple et quelques définitions 101 VIII.2.2.Modélisation d'un problème d'affectation et solution du problème des mariages 102 VIII.3.Exercice 103 IX. Le problème de transport 105 IX.1.Position du problème 105 IX.2.Arbres réalisables 107 IX.3.Recherche d'une solution optimale à partir d'une solution réalisable 108 IX.4.Recherche d'un arbre réalisable 112 IX.4.Recherche d'un arbre réalisable 112 IX.5.Modélisation et résolution à l'aide de la théorie des flots 113 IX.6.Exercices 114 X. Complexité d'un problème 117 X.1.Présentation et premières définitions 117 X.1.1.Problème du voyageur de commerce 117 X.1.2.Taille d'une instance 118 X.1.3.Machine de Turing et complexité d'un algorithme 118 X.1.4.Problème de reconnaissance 121 X.2.Classes P et NP ; problèmes NP-complets 123 X.2.1.La classe P 123 X.2.2.La classe NP 123 X.2.3.Problèmes NP‑complets 124 X.2.4.Problèmes NP‑difficiles 128 X.3.Exercices 129 XI. Méthodes par séparation et évaluation 131 XI.1.Introduction 131 XI.2.Problème du sac à dos : méthodes heuristiques 132 XI.2.1.Première heuristique 133 XI.2.2.Seconde heuristique 133 XI.3.Méthode par séparation et évaluation pour le problème du sac à dos 133 XI.3.1.Principe de séparation 134 XI.3.2.Principe d'évaluation et utilisation de la borne 135 XI.3.3.Stratégie de développement 136 XI.3.4.Application au problème de sac à dos 137 XI4.Application au problème du voyageur de commerce 138 XI.4.1.Forme linéaire en 0‑1 du problème du voyageur de commerce 138 XI.4.2.Définition d'une fonction d'évaluation 139 XI.4.3.Description d'une méthode par séparation et évaluation 139 XI.5.Exercices 140 XII. La programmation dynamique 141 XII.l.Les problèmes de la partition et du sac à dos 141 XII.1.1.Le problème de la partition 141 XII.1.2.Résolution du problème de la partition par la programmation dynamique 142 XII.1.3.Résolution du problème du sac à dos par la programmation dynamique 143 XII.2.Un problème d'entrepôt 144 XII.3.Le problème du voyageur de commerce 146 XII.4.Complexité de la méthode utilisée 148 XII.5.Exercices 149 XIII. Relaxation la grangienne 153 XIII.1.Position du problème 153 XIII.2.Résolution du problème dual 155 XIII.2.1.Principe de la méthode 155 XIII.2.2.Etude du problème de chemin de coût minimum à une contrainte 157 XIII.3.Maximum du minimum d'une famille de fonctions linéaires 161 XIII.4.Exercice 163 XIV. Méthodes approchées définies par un voisinage 165 XIV.1.Introduction 165 XIV.1.1.La fable des randonneurs 165 XIV.1.2.Formulation du problème 167 XIV.2.Principe des méthodes de descente (méthodes d'amélioration itérative) 167 XIV.2.1.Voisinage d'une solution 168 XIV.2.2.Quelques voisinages habituels 168 XIV.2.3.Exemple : le problème du voyageur de commerce 169 XIV.2.4. Schéma général d'une descente 170 XIV.2.5. Algorithmes gloutons 171 XIV.2.6. Méthodes par partitionnement 172 XIV.3. Le recuit simulé 173 XIV.3.1. Une analogie avec la thermodynamique 173 XIV.3.2. Schéma du recuit simulé 174 XIV.3.3. Interprétation de cette méthode, appliquée au problème du voyageur de commerce 176 XIV.3.4. Modèles de recuit 177 XIV.3.5. Exemple d'application : le problème du voyageur de commerce euclidien 180 XIV.4. La méthode Tabou 181 XIV.4.1. Principe de la méthode Tabou 181 XIV.4.2. Amélioration de la méthode Tabou 183 XIV.4.3. Un exemple d'application : le partitionnement de graphes 183 XIV.5. Exercices 185 XIV.5. Exercices 185 XV. Algorithmes génétiques 187 XV.1. Introduction : de la génétique à l'algorithmique 187 XV.2. Principe des algorithmes génétiques 188 XV.2.1. Le codage 189 XV.2.2. La sélection 190 XV.2.3. Le croisement 192 XV.2.4. La mutation 193 XV.2.5. Autres opérateurs 193 XV.3. La théorie des schémas 194 XV.4. Application à un problème d'antennes 195 XV.4.1. Codage 195 XV.4.2. Croisement 195 XV.4.3. Mutation 196 XV.4.4. Résultats 196 XV.5.Exercices 196 Corrigés des exercices 199 1.Chapitre I 199 2.Chapitre II 205 3.Chapitre III 206 4.Chapitre IV 216 5.Chapitre V 218 6.Chapitre VI 223 7.Chapitre VII 227 8.Chapitre VIII 229 9.Chapitre IX 230 10.Chapitre X 238 11.Chapitre XI 241 12.Chapitre XII 246 13.Chapitre XIII 250 14.Chapitre XIV 257 15.Chapitre XV 260 Bibliographie 263 Index 265 TOP uploads/Voyage/ flot-max.pdf