[PDF] Modèles de Recherche Opérationnelle



Previous PDF Next PDF







Cours : Recherche opérationnelle

décisionnelles et d'optimisation de la recherche opérationnelle Les exemples qui accompagnent ce cours permettent aux étudiants de modéliser des problèmes simples en utilisant les techniques de la Recherche Opérationnelle L’importance de l’optimisation est la nécessité d’un outil simple pour modéliser



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



COURS DE RECHERCHE OPERATIONNELLE

2 Nature de la recherche opérationnelle La recherche opérationnelle implique la recherche dans les différentes opérations et activités des organisations Ainsi, ses méthodes sont appliquées aux problèmes qui portent sur la conduite et la coordination des opérations (activités) au sein d’une organisation La nature de l’organisation



Modèles de Recherche Opérationnelle

Modèles de Recherche Opérationnelle Fabian Bastin Un modèle, telle que considéré dans ce cours, est une construction mathématique utilisée pour représenter



Recherche opérationnelle Master 1 - Esa

Recherche opérationnelle Master 1 - Esa Si vous souhaitez prendre connaissance des questions traitées dans le cours de recherche opérationnelle du Master 1 ESA, je vous recommande cet ouvrage F S Hillier & G T Lierberman Introduction to Operations Research McGraw-Hill, 2004



RECHERCHE OPÉRATIONNELLE : Optimisation Combinatoire

a) Le caractère pratique de la Recherche Opérationnelle : Définition "La recherche opérationnelle a été, reste et demeurera l'art d'intervenir rapidement au profit d'une entité économique déterminée (agent ou collectivité) dans une situation difficile afin de tenter d'en améliorer l'issue" b) Heuristique et traitement interactif :







Informatique / Recherche operationnelle / Presentation (French)

PLAN DU COURS Dans ce cours, nous verrons différents outils de recherche opérationnelle sans apporter de justifications mathématiques très détaillées et rigoureuses Après quelques exemples qui permettront de mieux cerner le domaine de la recherche opérationnelle, nous introduirons un outil à la fois graphique et théorique: les graphes



Cours de Programmation linéaire et Recherche Opérationnelle

Université Abdelmalek Essaadi aculFté Polydisciplinaire de Larache A U : 2017-2018 Cours de Programmation linéaire et Recherche Opérationnelle

[PDF] recherche opérationnelle simplexe exercices corrigés

[PDF] livre recherche opérationnelle pdf

[PDF] cours et exercices corrigés de recherche opérationnelle+pdf

[PDF] recherche opérationnelle cours maroc

[PDF] inpes

[PDF] methode boscher pdf download

[PDF] méthode boscher cahier de lecture pdf

[PDF] methode boscher en ligne

[PDF] méthode boscher gratuit

[PDF] méthode boscher cahier des sons pdf

[PDF] adjectif pour acrostiche

[PDF] recherche qualitative définition

[PDF] méthode qualitative et quantitative

[PDF] méthode qualitative mémoire

[PDF] méthode quantitative

Modèles de Recherche Opérationnelle

Fabian Bastin

bastin@iro.umontreal.ca Département d"Informatique et de Recherche Opérationnelle

Université de Montréal

IFT-1575

Hiver 2010

http://www.iro.umontreal.ca/~bastin

La présente version du syllabus s"inspire des notes de Patrice Marcotte, Bernard Gendron, ainsi que des livres

Introduction to Operational Research[1] etThe Basics of Practical Optimization[3].Le présent document peut être modifié et redistribué à des fins non commerciales, sous conditions d"être diffusé

sous les même conditions. Photographie de couverture: viaduc de Millau, France. c

Fabian Bastin, 2006

Table des matières

1 Introduction1

1.1 Les origines de la recherche opérationnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 La nature de la recherche opérationnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.4 Algorithmes et logiciels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4.1 Un exemple avec GAMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2 Programmation linéaire7

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2 Modèle général de programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3 Terminologie de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.4 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.5 La méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.5.1 Solution de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.5.2 Interprétations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.5.3 Critère d"optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.5.4 Adaptation à d"autres formes de modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.5.5 Obtention d"une base admissible initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.5.6 Variables à valeurs quelconques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.6 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.6.2 Analyse de sensibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3 Programmation non linéaire31

3.1 Fonctions convexes et concaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.1.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.2 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

3.2.1 L"algorithme du simplexe dans le cas non-linéaire . . . . . . . . . . . . . . . . . . . . . . . . .

35

3.2.2 Optimisation sans contrainte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.2.3 Méthode de la bissection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.2.4 Méthode du gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.2.5 Optimisation sous contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.2.6 Conditions d"optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4 Programmation mixte entière 41

4.1 Présentation générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.2 Contraintes mutuellement exclusives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.2.1 Deux contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.2.2Kcontraintes parmiN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45

4.2.3 Fonction ayantNvaleurs possibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45

iii ivTABLE DES MATIÈRES

4.2.4 Objectif avec coûts fixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.2.5 Variables entières en variables 0-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.2.6 Problème de recouvrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4.3 Stratégies de résolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

4.3.1 Relaxation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

4.3.2 Approche par énumération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

4.3.3 Les hyperplans coupants (méthode de coupe) . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4.4 Modélisation avec GAMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

4.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

5 Réseaux63

5.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

5.1.1 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

5.1.2 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

5.1.3 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

5.1.4 Chemins et circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

5.1.5 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

5.2 Problème du chemin le plus court - algorithmes de corrections d"étiquettes . . . . . . . . . . . . . . .

65

5.2.1 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

5.3 Flot dans un réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.3.1 Réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.3.2 Modèle de flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.3.3 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

5.3.4 Modèle du chemin critique (PERT/CPM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

5.4 Problème de l"arbre partiel minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.4.1 Algorithme de Prim (1957) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

5.5 Problème du flot maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

5.5.1 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

5.5.2 Flot maximum - Coupe minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

5.6 Problème de flot minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

5.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

6 Modèles stochastiques77

6.1 Concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

6.2 Variable aléatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

6.2.1 Variables aléatoires discrètes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6.2.2 Variables aléatoires continues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6.2.3 Espérance mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6.2.4 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

6.3 Loi de probabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

6.3.1 Loi de Bernouilli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

6.3.2 Loi uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

6.3.3 Loi de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

6.3.4 Loi exponentielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

6.4 Modèles stochastiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

6.4.1 Processus stochastiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

6.4.2 Chaînes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

6.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

TABLE DES MATIÈRESv

7 Programmation dynamique85

7.1 Principe d"optimalité de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

7.2 Affectation de ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

7.3 Programmation dynamique déterministe et plus court chemin . . . . . . . . . . . . . . . . . . . . . .

90

7.4 Cas probabiliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

7.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

8 Simulation93

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

8.2 Files d"attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

8.2.1 Concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

8.2.2 ModèleM=M=1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94

8.3 Simulation à événements discrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

8.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

Annexe99

8.5 Logiciels d"optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

8.5.1 IOR Tutorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

8.5.2 GAMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

8.5.3 Autres logiciels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

105

8.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

105

Bibliographie105

viTABLE DES MATIÈRES

Chapitre 1

Introduction

1.1 Les origines de la recherche opérationnelle

Si la recherche opérationnelle, en abrégé RO, est aujourd"hui présente dans la plupart des domaines civils, ses

racines sont habituellement attribués aux services militaires. La seconde guerre mondiale, de part son envergure,

créa une besoin urgent d"allouer de manière efficace des ressources limitées aux différentes opérations militaires

et aux activités au sein de chaque opération. En particulier, l"organisation militaire britannique, puis américaine,

mis à contribution un grand nombre de scientifiques pour gérer ces allocations, et s"occuper d"autres problèmes

stratégiques et tactiques. Ce faisant, ils furent appelés à poursuivre des recherches sur des opérations (militaires),

et constituèrent les premières équipes de RO. Leurs efforts furent signifactifs dans la marche vers la victoire, par

exemple en ce qui touche l"utilisation du radar, nouvellement développé. Ces succès encouragèrent la poursuite de

l"utilisation de la RO dans d"autres domaines. La croissance importante de l"industrie d"après-guerre entraîna des

problèmes, causés par la complexité croissante et la spécialisation dans les organisations, problèmes en fait proches

de ceux présent lors du conflit. Au début des années 1950"s, la RO avait pénétré une multitude d"organisations

commerciales, industrielles, et gouvernementales. Et ce n"était que le début.

Au moins deux autres facteurs ont joué un rôle clé dans la croissance rapide de la RO. Tout d"abord, des

progrès substantiels ont été obtenus très tôt afin d"améliorer les techniques de RO. Ces techniques, dans leur mise

en pratique, furent soutenues par l"essor des outils informatiques.

1.2 La nature de la recherche opérationnelle

"Rechercher sur des opérations" touche tous les problèmes reliés à la conduite et à la coordination des opérations

(activítés) au sein d"une organisation. Cette organisation peut représenter des domaines très divers: l"industrie

quotesdbs_dbs11.pdfusesText_17