Remerciez-le!

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

Flot max 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 ensemb

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 I L'algorithme du simplexe I Introduction I L'algorithme du simplexe appliqué à un exemple I La dégénérescence et le cyclage I Recherche d'un dictionnaire réalisable I Annexe la forme du pivot I Exercices II Forme matricielle de la méthode du simplexe II Généralités II Version matricielle d'une itération de la méthode du simplexe II Recherche d'une variable entrante II Recherche d'une variable sortante II Actualisation II Résumé II Un exemple d'application de la méthode II Application au problème de découpe II Exercice III Dualité III Définition du problème dual III Théorème de la dualité III Le théorème des écarts complémentaires un certificat d'optimalité III La signification économique du dual III Problème dual-réalisable III Exercices IV Généralités sur les graphes Arbre couvrant de poids minimum IV Introduction à la théorie des graphes et définitions IV Représentation des graphes en machine IV Matrice d'adjacence sommets-sommets IV Tableau de listes d'adjacence IV Complexité d'un algorithme IV Le problème de l'arbre couvrant de poids minimum IV Définition du problème IVA Une application en réseaux IVA Une application en réseaux IV Une application en traitement d'images IV Algorithme de Kruskal IV Algorithme de Prim IV Exercices V Problèmes de plus courts chemins V Définition des différents problèmes V Définitions nécessaires à ce chapitre V Problèmes V Plus courts chemins d'un sommet à tous les autres cas des valuations positives V Motivation V Algorithme de Dijkstra V Plus courts chemins d'un sommet à tous les autres cas des graphes sans circuit V Motivation V Algorithme de Bellman V Plus courts chemins d'un sommet à tous les autres cas général V Motivation V Algorithme de Ford V Algorithme général de Ford-Dantzig V Plus courts chemins de tout sommet à tout sommet cas général V Exercices VI Parcours de graphes VI Définition d'un algorithme de parcours de graphe ? VI Cas orienté VI Cas non orienté VI Complexité VI Les parcours marquer-examiner ? VI Généralités VI Résultat d'un parcours marquer-examiner ? selon une file le parcours en largeur VI Résultat d'un parcours marquer-examiner ? suivant une pile VI Les parcours en profondeur VI Le cas orienté VI Le cas non orienté VI Applications des parcours en profondeur VI Application à la détermination des composantes