[PDF] Introduction a la recherche op erationnelle



Previous PDF Next PDF







Recherche op erationnelle - Université du Littoral Côte dOpale

La recherche op´erationnelle trouve son origine au d´ebut du XXe si`ecle dans l’´etude de la gestion de stock avec la formule du lot ´economique (dite formule de Wilson) propos´ee par Harris en 1913 Mais ce n’est qu’avec la seconde guerre mondiale que la pratique va s’organiser pour la premi`ere fois et acqu´erir son nom En 1940,



Recherche opérationnelle et applications

Recherche opérationnelle et applications Bernard Fortz 2012-2013 Table des matières I Introduction à la recherche opérationnelle 3 1 Quelques exemples de modèles mathématiques 3 2 Tour d’horizon des techniques de recherche opérationnelle 4 II Applications de la programmation linéaire 6 3 Définition, exemples et méthode de résolution 6



Précis de recherche opérationnelle - Dunod

de recherche opérationnelle Méthodes et exercices d’application Robert Faure était professeur de la chaire de recherche opérationnelle au CNAM Bernard Lemaire est professeur émérite de la chaire de recherche opérationnelle au CNAM Christophe Picouleau est professeur des universités au CNAM 7e édition







Recherche oprationnelle exercices corrigs pdf

recherche opérationnelle cours exercices corrigés pdf 3 Les méthodes de recherche arborescente par séparation et évaluation 64 1 Le graphe de la figure 2 7 correspond à des parcours possibles pour aller dun point s à un 3 annales de Recherche opérationnelle Ingénierie et Management de Process pour



Mod´elisation - Université libre de Bruxelles

MATH-F-306 – 0 Mod´elisation Exercice 0 1 Exercice 0 1 cf : Recherche op´erationnelle pour ing´enieurs I (de Werra, Liebling, Hˆeche) ; page 33



Introduction a la recherche op erationnelle

A partir des ann ees 50, la recherche op erationnelle fait son entr ee dans les entreprises En France, des entreprises comme EDF, Air France, la SNCF cr eent a cette epoque des services de recherche op erationnelle (qui existent toujours) La discipline commence a ^etre enseign ee dans les universit es et les grandes ecoles



Problème de flot, d’affectation et de transport

notamment la recherche opérationnelle, à cause de leur niveau de complexité particulièrement élevé et à cause des coûts supplémentaires qu’ils génèrent s’ils sont mal gérés Ce qui souligne l’importance qu’occupe ce type de problème dans la gestion quotidienne de l’entreprise

[PDF] cours de recherche operationnelle gratuit pdf

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomie

[PDF] fonction de cobb douglas pdf

Frederic Meunier

Introduction a la recherche

operationnelle13 juillet 2017 ii

Table des matieres

1 Generalites 1

I Fondements 7

2 Bases9

2.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2 Retour sur les ponts et sur le voyageur . . . . . . . . . . . . . . . . . . . . .

14

2.3 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.4 Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.5 Algorithme et complexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3 Plus courts chemins et programmation dynamique 29

3.1 Cas du graphe oriente et programmation dynamique . . . . . . . . . . . . . .

29

3.2 Cas du graphe non-oriente . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.3 Resume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

3.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4 Programmation lineaire 47

4.1 Denition et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.2 Quelques elements theoriques . . . . . . . . . . . . . . . . . . . . . . . . . .

50

4.3 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

4.4 Dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

4.5 Une application de la dualite : jeux matriciels a somme nulle . . . . . . . . .

61

4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

5 Flots et Coupes 65

5.1 Flots et coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

5.2 Flot de co^ut minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

TABLE DES MATI

ERESiv

6 Graphes bipartis : probleme d'aectation, probleme de transport, mariages

stables81

6.1 L'objet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

6.2 Probleme du couplage optimal . . . . . . . . . . . . . . . . . . . . . . . . . .

81

6.3 Couplages generalises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

6.4 Probleme de l'aectation optimale . . . . . . . . . . . . . . . . . . . . . . . .

84

6.5 Mariages stables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

6.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

7 Que faire face a un probleme dicile? 89

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89

7.2 Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

7.3 Metaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

7.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

II Problematiques 103

8 Remplissage de conteneurs 105

8.1 Sac-a-dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

105

8.2 Bin-packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

107

8.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

112

9 Positionnement d'entrep^ots 115

9.1 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

115

9.2 Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

116

9.3 Recherche locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

118

9.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

119

10 Ordonnancement industriel 125

10.1 Preliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

125

10.2 Management de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

126

10.3 Ordonnancement d'atelier . . . . . . . . . . . . . . . . . . . . . . . . . . . .

128

10.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

138

11 Tournees 143

11.1 Probleme du voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . .

143

11.2 Probleme du postier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

152

11.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

154

12 Conception de reseaux 159

12.1 Quelques rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

159

12.2 Arbre couvrant de poids minimal . . . . . . . . . . . . . . . . . . . . . . . .

160

12.3 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

163
vTABLE DES MATIERES

12.4 Quelques remarques pour nir . . . . . . . . . . . . . . . . . . . . . . . . . .

167

12.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

168

13 Ouverture 175

13.1 Quelques outils absents de ce livre . . . . . . . . . . . . . . . . . . . . . . . .

175

13.2 Trois domaines a la frontiere de la recherche operationnelle . . . . . . . . . .

177

TABLE 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 avait

CHAPITRE 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 dequotesdbs_dbs3.pdfusesText_6