[PDF] Images a?n d’assurer que

View - Download Images

Previous PDF

Next PDF

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

quotesdbs_dbs4.pdfusesText_7

[PDF] Méthodes d 'analyse de sensibilité de modèles pour entrées - INRA

[PDF] la distance professionnelle en ehpad

[PDF] L 'analyse de la pratique - IFSI DIJON

[PDF] Présentation de la situation - Infirmierscom

[PDF] réflexion autour de la fiche d analyse de la pratique - Infirmierscom

[PDF] Analyses de sol et interprétation des résultats

[PDF] 30 fiches pour réussir les épreuves sur textes

[PDF] l 'analyse des textes littéraires : vingt méthodes - Revue Texto

[PDF] METHODOLOGIE D 'ANALYSE D 'UN TEXTE : I/ Avant la lecture : II

[PDF] Pour un définition de l 'analyse littéraire - Lettresorg

[PDF] Demain dès l 'aube » de Victor Hugo Fiche du professeur - Xtec

[PDF] Cours de Démographie- Hassen MATHLOUTHI - essai

[PDF] Cours analyse coûts-1 - IUT de Bayonne

[PDF] Thème 1 Le contrôle de gestion et le calcul des coûts - Moodle UM

[PDF] Traitement des données avec Microsoft EXCEL 2016 - Université de