Remerciez-le!

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

Cours ro ponts Frédéric Meunier IONPTÉRROADTUIOCNTNIOENLLÀE LA RECHERCHE CFrédéric Meunier Université Paris Est CERMICS Ecole des Ponts Paristech - avenue Blaise Pascal Marne-la-Vallée Cedex E-mail frederic meunier cermics enpc fr CINTRODUCTION À LA RECHE

Frédéric Meunier IONPTÉRROADTUIOCNTNIOENLLÀE LA RECHERCHE CFrédéric Meunier Université Paris Est CERMICS Ecole des Ponts Paristech - avenue Blaise Pascal Marne-la-Vallée Cedex E-mail frederic meunier cermics enpc fr CINTRODUCTION À LA RECHERCHE OPÉRATIONNELLE Frédéric Meunier C CTABLE DES MATIÈRES Généralités Présentation Histoire Modélisation et optimisation Objectif de ce cours partie I Fondements Bases Graphes Retour sur les ponts et sur le voyageur Programmation mathématique Problème Algorithme et complexité Exercices Plus courts chemins et programmation dynamique Cas du graphe orienté et programmation dynamique Cas du graphe non-orienté Résumé Exercices Programmation linéaire C Dé nition et exemples Quelques éléments théoriques Algorithmes Dualité Une application de la dualité jeux matriciels à somme nulle Exercices Flots et Coupes Flots et coupes D Multi ots Exercices B Graphes bipartis problème d'a ectation problème de transport mariages stables L'objet Problème du couplage optimal C Couplages généralisés B Problème de l'a ectation optimale Mariages stables Exercices E Que faire face à un problème di cile Introduction Séparation et évaluation ou branch-and-bound Métaheuristiques Exercices partie II Problématiques Remplissage de conteneurs Sac-à-dos Bin-packing Exercices Positionnement d'entrepôts Formalisation Branch-and-bound Recherche locale Exercices Ordonnancement industriel Préliminaires Management de projet Ordonnancement d'atelier Exercices Tournées Problème du voyageur de commerce Problème du postier Exercices Conception de réseaux Quelques rappels Arbre couvrant de poids minimal Arbre de Steiner C Quelques remarques pour nir Exercices Ouverture Quelques outils absents de ce livre Trois domaines à la frontière de la recherche opérationnelle Eléments de correction Bibliographie Annexe Quelques outils de R O Quelques sociétés Ressources en ligne vi CQuelques SSII spécialisées dans la RO Quelques sociétés éditrices de logiciels de RO Entreprises françaises ayant des départements avec compétences en RO Quelques solveurs de programmation linéaire Quelques langages de modélisation vii C CCHAPITRE GÉNÉRALITÉS Présentation La recherche opérationnelle RO est la discipline des mathématiques appliquées qui traite des questions d'utilisation optimale des ressources dans l'industrie et dans le secteur public Depuis une dizaine d'années le champ d'application de la RO s'est élargi à C C des domaines comme l'économie la nance le marketing et la plani cation d'entreprise Plus récemment la RO a été utilisée pour la gestion des systèmes de santé et d'éducation pour la résolution de problèmes environnementaux et dans d'autres domaines d'intérêt public Exemples C d'application Plani er la tournée d'un véhicule de livraison qui doit passer C par des points xés à l'avance puis revenir à son point de départ en cherchant à minimiser la distance parcourue est un problème typique de recherche opérationnelle On appelle ce problème le problème du voyageur de commerce étudié plus en détail au Chapitre Remplir un conteneur avec des objets de tailles et de valeurs variables Si le conteneur a une C capacité nie on va chercher à maximiser la valeur placée dans le conteneur On appelle ce problème le problème du sac-à-dos étudié plus en détail au Chapitre Ordonnancer les t? ches sur un chantier Pour chaque t? che T on conna? t sa durée De plus on conna? t les autres t? ches dont T dépend