10 4 Exercices La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des questions actuelle, beaucoup plus simple, utilise une modélisation par un graphe (voir Chapitre 2) On voit sur cet modélise, avec A une matrice m × n `a coefficients rationnels, et b ∈ Qm et c ∈ Qn
Previous PDF | Next PDF |
[PDF] Recherche opérationnelle - LMPA
1 2 Modélisation d'un programme linéaire 2 2 6 Exercices récapitulatifs méthodes et techniques rationnelles orientées vers la recherche de la meilleure
[PDF] Recherche opérationnelle - LMPA
1 2 Modélisation d'un programme linéaire 1 3 6 Exercices méthodes et techniques rationnelles orientées vers la recherche de la meilleure façon d' opérer
[PDF] Synthèse de cours exercices corrigés - ACCUEIL
exercices corrigés Éric DOR Économétrie Cours et exercices adaptés aux besoins des économistes Introduction IX Chapitre 1 • Modélisation en économie et gestion de Louvain et a été invité dans plusieurs centres de recherche internationaux, dont le Graduate rationnel de la part des consommateurs Il faut lui
[PDF] Automatique - Systèmes linéaires, non linéaires, temps continu
Cours et exercices corrigés Yves Granjon Professeur à 12 3 3 Première méthode d'étude simple : recherche d'un système à temps continu équivalent 248
[PDF] a la recherche opérationnelle - Educnet
10 4 Exercices La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des questions actuelle, beaucoup plus simple, utilise une modélisation par un graphe (voir Chapitre 2) On voit sur cet modélise, avec A une matrice m × n `a coefficients rationnels, et b ∈ Qm et c ∈ Qn
[PDF] Exercice 1 :
Soit la base de l'extension suivante de la relation Personne : Que valent les expressions suivantes ? Correction de l'exercice 2 1 Numero Nom Prenom 2
[PDF] Examen corrigé de recherche opérationnelle pdf - f-static
s5 Exercices corrigés recherche opérationnelle S5 Economie rationnelles visant à trouver le meilleur choix dans la façon de travailler pour obtenir le résultat (logique, probabilité, analyse des données) et la modélisation des processus
[PDF] Optimisation
1 2 Exercices corrigés D'autres exemples sont dans la séance d'exercices d'optimisation (cf chapitre 3) à la recherche du minimum de la fonction F(x) un contexte élémentaire, est un outil général de modélisation mathématique, aussi rationnels) en un temps polynômial par rapport à la longueur des données
[PDF] Modélisation et analyse des systèmes
Ce manuel d'exercices complète le cours de Modélisation et Analyse des Systèmes Unité de Recherches en Modélisation et Systèmes Un système LTI dont la fonction de transfert est une fraction rationnelle ne peut être BIBO stable et
[PDF] formulation variationnelle exercices corrigés pdf
[PDF] pecheur d'islande film
[PDF] madame chrysanthème
[PDF] pecheur d'islande film 1996
[PDF] ramuntcho
[PDF] aziyadé
[PDF] cours modélisation et simulation des systèmes pdf
[PDF] différence entre modélisation et simulation
[PDF] modélisation et simulation cours
[PDF] modélisation et simulation cours informatique
[PDF] modélisation et simulation pdf
[PDF] pierre et jean résumé court
[PDF] pierre et jean personnages
[PDF] pierre et jean chapitre 1
![[PDF] a la recherche opérationnelle - Educnet [PDF] a la recherche opérationnelle - Educnet](https://pdfprof.com/Listes/18/9694-18CoursROPonts.pdf.pdf.jpg)
Frederic Meunier
Introduction a la recherche
operationnelle13 juillet 2017 iiTable des matieres
1 Generalites 1
I Fondements 7
2 Bases9
2.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92.2 Retour sur les ponts et sur le voyageur . . . . . . . . . . . . . . . . . . . . .
142.3 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
162.4 Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
192.5 Algorithme et complexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
202.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
253 Plus courts chemins et programmation dynamique 29
3.1 Cas du graphe oriente et programmation dynamique . . . . . . . . . . . . . .
293.2 Cas du graphe non-oriente . . . . . . . . . . . . . . . . . . . . . . . . . . . .
383.3 Resume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
393.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
394 Programmation lineaire 47
4.1 Denition et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
474.2 Quelques elements theoriques . . . . . . . . . . . . . . . . . . . . . . . . . .
504.3 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
544.4 Dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
584.5 Une application de la dualite : jeux matriciels a somme nulle . . . . . . . . .
614.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
625 Flots et Coupes 65
5.1 Flots et coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
655.2 Flot de co^ut minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
715.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74TABLE DES MATI
ERESiv
6 Graphes bipartis : probleme d'aectation, probleme de transport, mariages
stables816.1 L'objet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
816.2 Probleme du couplage optimal . . . . . . . . . . . . . . . . . . . . . . . . . .
816.3 Couplages generalises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
836.4 Probleme de l'aectation optimale . . . . . . . . . . . . . . . . . . . . . . . .
846.5 Mariages stables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
856.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
867 Que faire face a un probleme dicile? 89
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
897.2 Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
907.3 Metaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
957.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98II Problematiques 103
8 Remplissage de conteneurs 105
8.1 Sac-a-dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1058.2 Bin-packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1078.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1129 Positionnement d'entrep^ots 115
9.1 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1159.2 Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1169.3 Recherche locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1189.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11910 Ordonnancement industriel 125
10.1 Preliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12510.2 Management de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12610.3 Ordonnancement d'atelier . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12810.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13811 Tournees 143
11.1 Probleme du voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . .
14311.2 Probleme du postier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15211.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15412 Conception de reseaux 159
12.1 Quelques rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15912.2 Arbre couvrant de poids minimal . . . . . . . . . . . . . . . . . . . . . . . .
16012.3 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
163vTABLE DES MATIERES
12.4 Quelques remarques pour nir . . . . . . . . . . . . . . . . . . . . . . . . . .
16712.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16813 Ouverture 175
13.1 Quelques outils absents de ce livre . . . . . . . . . . . . . . . . . . . . . . . .
17513.2 Trois domaines a la frontiere de la recherche operationnelle . . . . . . . . . .
177TABLE DES MATI
ERESvi
CHAPITRE1Generalites
Presentation
La recherche operationnelle (RO) est la discipline des mathematiques appliquees qui traite des questions d'utilisation optimale des ressources dans l'industrie et dans le secteur public. Depuis une dizaine d'annees, le champ d'application de la RO s'est elargi a des domaines comme l'economie, la nance, le marketing et la planication d'entreprise. Plus recemment, la RO a ete utilisee pour la gestion des systemes de sante et d'education, pour la resolution de problemes environnementaux et dans d'autres domaines d'inter^et public.Exemples d'application
Planier la tournee d'un vehicule de livraison qui doit passer par des points xes a l'avance puis revenir a son point de depart en cherchant a minimiser la distance parcourue est un probleme typique de recherche operationnelle. On appelle ce probleme leprobleme du voyageur de commerce(etudie plus en detail au Chapitre 11). Remplir un conteneur avec des objets de tailles et de valeurs variables. Si le conteneur a une capacite nie, on va chercher a maximiser la valeur placee dans le conteneur. On appelle ce probleme leprobleme du sac-a-dos(etudie plus en detail au Chapitre 8). Ordonnancer les t^aches sur un chantier. Pour chaque t^acheT, on conna^t sa duree. De plus, on conna^t les autres t^aches dontTdepend directement et combien de temps avant ou apres le debut de chacune d'ellesTdoit demarrer. On desire minimiser la duree totale du chantier. On dit que ce probleme est unprobleme d'ordonnancement(etudie plus en detail au Chapitre 10). Chacun de ces problemes peut bien s^ur ^etre complique a l'envie. Dans ce cours, on restera relativement simple { quelques contraintes de plus susent en eet a faire de ces problemes de veritables sujets de these (par exemple pour le remplissage de conteneur un sujet de these peut consister en : plusieurs types de conteneurs, plusieurs produits a stocker, des incompatibilites).Histoire
La recherche operationnelle est nee pendant la Seconde Guerre mondiale des eorts conjugues d'eminents mathematiciens (dont von Neumann, Dantzig, Blackett) a qui il avaitCHAPITRE 1. G
ENERALITES2
ete demande de fournir des techniques d'optimisation des ressources militaires. Le premier succes de cette approche a ete obtenue en 1940 par le Prix Nobel de physique Patrick Blackett qui resolut un probleme d'implantation optimale de radars de surveillance. Le qualicatif operationnellevient du fait que les premieres applications de cette disci- pline avait trait aux operations militaires. La denomination est restee par la suite, m^eme si le domaine militaire n'est plus le principal champ d'application de cette discipline, le mot operationnelleprenant alors plut^ot le sens d'eectif. Ce sont donc ces mathematiciens qui ont cree une nouvelle methodologie caracterisee par les mots-clesmodelisationetopti- misation. A partir des annees 50, la recherche operationnelle fait son entree dans les entreprises. En France, des entreprises comme EDF, Air France, la SNCF creent a cette epoque des services de recherche operationnelle (qui existent toujours). La discipline commence a ^etre enseignee dans les universites et les grandes ecoles. Puis, au milieu des annees 70, sans doute a cause d'un exces d'enthousiasme au depart et a l'inadequation des moyens informatiques a l'application des methodes de la RO, la discipline s'essoue. A partir du milieu des annees 90, on assiste a un retour en force la RO, les outils informatiques etant maintenant a la hauteur des methodes proposees par la recherche operationnelle. On assiste depuis a une explosion du nombre de logiciels commerciaux et l'apparition de nombreuses bo^tes de conseil. Pour la France, notons Ilog (65 millions d'euros de CA), Eurodecision (2,8 millions d'euros de CA), Artelys (1,6 millions d'euros de CA) a l'etranger Dash-Optimization (rachete debut 2008 pour 32 millions de dollars par Fair Isaac), IBM Optimization et beaucoup d'autres (le site de INFORMS Institute of Operations Research and Management Science en liste pres de 240).Les racines
Si l'on cherche a trouver des precurseurs a la Recherche Operationnelle, on peut penser a Alcuin ou a Euler qui se sont tous deux interesses a des problemes du type RO, bien qu'aucune application n'ait motive leur travail. Alcuin est le moine irlandais charge par Charlemagne de construire l'ecole palatine et qui inventa le probleme du loup, de la chevre et du chou devant traverser une riviere dans une barque ou au plus un element peut prendre place.Un homme devait transporter de l'autre c^ote d'un
euve un loup, une chevre et un panier de choux. Or le seul bateau qu'il put trouver ne permettait de transporter que deux d'entre eux. Il lui a donc fallu trouver le moyen de tout transporter de l'autre c^ote sans aucun dommage. Dise qui peut comment il a reussi a traverser en conservant intacts le loup, la chevre et les choux 1. Euler est le mathematicien allemand a qui les notables de Konigsberg demanderent s'iletait possible de parcourir les ponts de la ville en passant sur chacun des 7 ponts exactement1. Homo quidam debebat ultra
uvium transferre lupum, capram, et fasciculum cauli. Et non potuitaliam navem invenire nisi quae duos tantum ex ipsis ferre valebat. Praeceptum itaque ei fuerat ut omnia
haec ultra illaesa omnino transferret. Dicat, qui potest, quomodo eis illaesis transire potuit.