[PDF] Mathématiques – Recherche Opérationnelle

View - Download Mathématiques – Recherche Opérationnelle

Previous PDF

Next PDF

Mathématiques - Recherche Opérationnelle

Alain Billionnet

Notes de cours

2010-2011

2

Avertissement

Ce document ne prétend pas à l"exhaustivité d"un cours. Il se peut que des erreurs ou des fautes de frappe s"y soient également glissées par mégarde, auquel cas je vous invite à envoyer vos corrections à l"adressemarc.vanderwal@ensiie.fr. J"espère que ces notes vous seront néanmoins utiles pour vos révisions.

Marc 'x0r" van der Wal

Ce document est distribué sous la licence CreativeCommons Pater- nité - Pas d"Utilisation Commerciale - Partage des Conditions Ini- tiales à l"Identique version 2.0. Pour plus d"informations : 3 4

Table des matières0 Introduction9

Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Types de problèmes étudiés . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 10 Programmation linéaire en nombre entiers . . . . . . . . . . . . . 10 Aléatoire/Stochastique . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1 Programmation dynamique11

1.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Exemple : Tracé optimal d"une autoroute . . . . . . . . . . . . . . 11

1.3 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.1 Formules d"optimisation séquentielle . . . . . . . . . . . . . 13

1.4 Deuxième exemple d"application . . . . . . . . . . . . . . . . . . . . 13

1.4.1 Représentation du problème en tant que graphe . . . . . 15

2 Chemins optimaux dans les graphes 17

2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1 Exemple d"application . . . . . . . . . . . . . . . . . . . . . . 19

2.2.2 Preuve de l"algorithme . . . . . . . . . . . . . . . . . . . . . 19

2.3 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . 20

2.3.1 Exemple d"application . . . . . . . . . . . . . . . . . . . . . . 20

2.4 Algorithme de Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . 21

3 Flots dans les graphes23

3.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Problème du flot maximal . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2.2 Condition nécessaire et suffisante d"optimalité . . . . . . . 27

3.3 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . 27

3.3.1 L"algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5

6TABLE DES MATIÈRES

3.3.2 Exemple d"application . . . . . . . . . . . . . . . . . . . . . . 29

4 Ordonnancement31

4.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2 La méthode PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2.1 Exemple de diagramme . . . . . . . . . . . . . . . . . . . . . 32

4.2.2 Exemple avec des tâches fictives . . . . . . . . . . . . . . . 33

4.2.3 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2.4 Marges relatives aux tâches . . . . . . . . . . . . . . . . . . 35

4.2.5 Exemple d"ordonnancement d"atelier . . . . . . . . . . . . 35

5 Méthodes d"énumération implicite 37

5.1 Idée sur un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.2 Schéma général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.3 Application au problème du voyageur . . . . . . . . . . . . . . . . 40

5.3.1 Calcul du regret . . . . . . . . . . . . . . . . . . . . . . . . . 41

6 Programmation linéaire43

6.1 Problèmes de production . . . . . . . . . . . . . . . . . . . . . . . . 43

6.1.1 Optimisation fractionnaire . . . . . . . . . . . . . . . . . . . 44

6.1.2 Interprétation géométrique d"un programme linéaire . . . 45

6.1.3 Forme générale d"un programme linéaire . . . . . . . . . . 45

6.1.4 Base et solution de base . . . . . . . . . . . . . . . . . . . . 46

6.2 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 48

6.2.1 Caractérisation des solutions optimales . . . . . . . . . . . 48

6.2.2 Algorithme du simplexe pour la minimisation . . . . . . . 52

6.2.3 Méthode des tableaux . . . . . . . . . . . . . . . . . . . . . . 52

6.3 Initialisation de l"algorithme du simplexe . . . . . . . . . . . . . .54

6.3.1 Problème auxiliaire : Méthode des 2 phases . . . . . . . . 55

6.3.2 Exemples d"application . . . . . . . . . . . . . . . . . . . . . 56

6.3.3 Méthode des pénalités . . . . . . . . . . . . . . . . . . . . . 59

7 Processus aléatoires61

7.1 Processus de Markov (sans mémoire) . . . . . . . . . . . . . . . . . 61

7.1.1 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . 61

7.1.2 Processus de naissance . . . . . . . . . . . . . . . . . . . . . 63

7.1.3 Processus de naissance et de mort . . . . . . . . . . . . . . 65

7.2 Chaînes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.2.1 Matrice associée . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.2.2 Graphe associé à une chaîne . . . . . . . . . . . . . . . . . . 69

7.2.3 Classification des états . . . . . . . . . . . . . . . . . . . . . 70

TABLE DES MATIÈRES7

7.2.4 Distribution limite d"une chaîne de Markov finie . . . . . 72

8 Phénomènes d"attente75

8.1 Système à un guichet . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

8.1.1 Nombre moyen de clients dans le système . . . . . . . . . 76

8.1.2 Nombre moyen de clients dans la file . . . . . . . . . . . . 77

8.2 Système à plusieurs guichets identiques . . . . . . . . . . . . . . . 77

9 Fiabilité des équipements79

9.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

9.2 Formes analytiques de la fiabilité et du taux d"avarie . . . . . . .80

9.3 Généralisation de la loi exponentielle : loi Erlang-k . . . . .. . . 80

9.4 Matériel d"usure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

9.5 Fiabilité des systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

9.5.1 Système en série . . . . . . . . . . . . . . . . . . . . . . . . . 81

9.5.2 Système en parallèle . . . . . . . . . . . . . . . . . . . . . . . 82

9.6 Probabilité de consommation . . . . . . . . . . . . . . . . . . . . . . 83

9.7 Entretien préventif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

9.7.1 Calcul du coût moyen . . . . . . . . . . . . . . . . . . . . . . 84

9.7.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

A Transformée de Laplace87

8TABLE DES MATIÈRES

- Faure, Lemaire, Picouleau,Précis de Recherche Opérationnelle, Dunod. - Roseaux,Exercices et problèmes résolus de RO(3 tomes), Dunod.

But du cours

- Savoir prendre les “meilleures" décisions (critère d"optimalité à définir) - Démarche scientifique - Aperçu des grands domaines de la RO

Historique

- Pascal, Fermat, Bernoulli - Monge : problème des déblais et des remblais - Fourier : systèmes d"équations linéaires (programmation linéaire) - Borel, Von Neumann : théorie des jeux - Sainte-Lague, Konig : théorie des graphes - 1956 : Recherche opérationnelle civile (les militaires s"en étaient appro- priés en premier), sorte d"“aide à la décision"

Domaines

1. Combinatoire

2. Aléatoire

3. Concurrentiel

Exemple 1.Problème d"affectation : on anpersonnes etnpostes. Chaque personne inscrit sa préférence pour un certain poste dans une grille. Comment trouver l"affectation qui maximise la somme des préférences? Il y an! solutions; pourn=4 cela en fait 24; pourn=20, on atteint

81010solutions.

9

10INTRODUCTION

Un problèmefacileest un problème dont le nombre d"opérations est borné par un polynôme. Un problèmedifficileest un problème pour lequel il n"y a pas d"algorithme polynomial connu; on conjecture qu"il n"en existe pas.

Exemple 2.Rotation d"avions, d"équipages...

Exemple 3.Problème duvoyageur de commerce: traverser les villes d"un pays et retourner à son point de départ en minimisant le coût (trouveruncircuit hamiltonien de valeur minimale). Problème NP-difficile; pournvilles il y a (n1)! chemins différents.

Types de problèmes étudiés

Programmation linéaire

Il s"agit d"optimiser une fonction linéaire :

mincx Ax=b x0min n j=1c jxj n j=1a ijxj=bii1,m x i0i1,m

Programmation linéaire en nombre entiers

On remplace la contraintex0 pari1,m,xiN, voirexi 0,1 (dnas le cas de prises de décisions).

Aléatoire/Stochastique

Problèmes de files d"attente, de fiabilité et de gestion des stocks. Par exem- ple, on souhaite étudier le temps moyen d"attente à une file d"attente, et savoir combien de guichets supplémentaires on doit ouvrir pour ramenerce temps moyen à une certaine valeur. Chapitre 1Programmation dynamique1.1 Généralités Principe d"optimalité de Bellman : Toute sous-politique d"une politique op- timale est optimale. Par exemple, lorsqu"on a trouvé un chemin optimal d"un sommetAvers un sommetB, et que les sommetsCetDsont sur ce même chemin, le chemin optimal deCversDest le sous-chemin qui emprunte une partie de celui deA versB.

1.2 Exemple : Tracé optimal d"une autoroute

On se donne le graphe en figure 1.1. On veut déterminer le tracé de coût minimal; tracé qui s"exprime par coût d"un tracé= coûts des tronçons

Algorithme possible :

1. Chemin optimal depuisAjusqu"à chaque ville de la phase 2 :

x 2 chemin optimalcoût

EACE,ADE10

F ACF9 G ADG9 H ACH9

2. Chemin optimal depuisAjusqu"à chaque ville de la phase 3 :

11

12CHAPITRE 1. PROGRAMMATION DYNAMIQUE

A B C D 8 5 7 E F G H 3 45
4 6 4 3 2 3 I J 4 5 4 4 3 2 4 K 5 7

FIGURE1.1 - Tracé d"une autoroute.

x 3 chemin optimalcoût

IAGI12

J AGJ11

3. Chemin optimal depuisAjusqu"à chaque ville de la phase 4 :

x 4 chemin optimalcoût

KAIK17

4. En considérant chaque possibilité de la fin vers le début, on endéduit

que le chemin optimal estADGIKde coût 17.

1.3 Formalisation

SoitFune fonction deN+1 variables à optimiser :

F(x0,x1,...,xN) =v1(x0,x1)+v2(x1,x2)++vN(xN1,xN)

Pour toutn0,N1,xndépend dex0et dexn+1.

Dans notre exemple précédent, nous avions :

F(x0,x1,...,xn) =4

i=1v i(xi1,xi)

1.4. DEUXIÈME EXEMPLE D"APPLICATION13

oùvi(xi1,xi)est le coût du tronçon reliant la villexi1de la phasei1 à la villexide la phasei.

1.3.1 Formules d"optimisation séquentielle

On cherchef2(x0,x2), la valeur optimale dev1(x0,x1)+v2(x1+x2), c"est-

à-dire

f

2(x0,x2) =min

x

1X1(x0,x2)v1(x0,x1)+v2(x1+x2)

Ensuite, on cherche la valeur optimale def3(x0,x3), i.e. f

3(x0,x3) =minx2f2(x0,x2)+v3(x2,x3)

On continue ensuite jusqu"à trouverfN(x0,xN). Ainsi, l"optimum recherché est obtenu avec la formule minF(x0,x1,...,xN) =minx0,xNfN(x0,xN)(1.1)

Dans notre exemple :

f

2(x0,E) =min

x

1B,C,Dv1(A,x1)+v2(x1,E)=10

f

3(A,I) =min

x

2E,F,Gf2(A,x2)+v3(x2,I)=12

f

4(A,K) =min

x

3I,Jf3(x0,x3)+v(x3,K)=17

1.4 Deuxième exemple d"application

On se propose de faire une campagne de publicité dans quatre régions. On possède un budget deBunités. On investit un certain nombre d"unités dans chaque région; le rendement étant donné dans le tableau suivant:

I II III IV

00 0 0 0

1

0,28 0,25 0,15 0,20

2

0,45 0,41 0,25 0,35

3

0,65 0,55 0,40 0,42

4

0,78 0,65 0,50 0,48

5

0,90 0,75 0,62 0,53

Déterminer la stratégie optimale d"investissement.

Exemple de stratégie d"investissement :

I II III IV

1 0 2 2

0,28 0 0,25 0,35

14CHAPITRE 1. PROGRAMMATION DYNAMIQUE

ce qui donne un rendement de 0,88. Si on tente de rechercher maxF(x1,x2,x3,x4)oùxiest la somme investie dans la régioni, ça ne marchera pas. Il faut rechercher maxF(x1,x2,x3,x4)où x iest lesous-totaldes sommes investies dans les régions 1,2,...,i. On pose alorsvi(xi1,xi)le rendement obtenu en investissantxixi1dans la région i. On a f

2(x2) =max

x

10,x2v1(x0,x1)+v2(x1,x2)

le rendement maximal que l"on peut obtenir en investissantx2unités au to- tal dans les deux premières régions. Il faut faire les calculs pour tous les cas possibles pourx2: x 2 f2(x2)x1 000 1 0,281 2 0,531 3 0,702 4 0,903 5 1,063

Au rang 3, on a :

f

3(x3) =rendement max en investissantx3dans I, II et III

=maxx1,x2v1(x0,x1)+v2(x1,x2)+v3(x2,x3) =max x

20,x3f2(x2)+v3(x2,x3)

d"où (I, II)III 000 1

0,280,15

2

0,530,25

3

0,700,40

4

0,900,50

5

1,060,62x

3 f3(x3)x2 00

10,281

2 0,532 3 0,703 4 0,904 5 1,065 L"optimum est atteint lorsquex3=0; cette région n"est pas suffisamment intéressante pour investir dedans. Passons ensuite au rang 4: x 4 f4(x4)x3

51,104

L"optimum est atteint lorsquex4=4.

La solution est donc la suivante :

1.4. DEUXIÈME EXEMPLE D"APPLICATION15

I II III IV Total

Investissement cumulé3 4 4 5 5

Investissement

3 1 0 1 5

Rendement

0,65 0,25 0 0,20 1,10

1.4.1 Représentation du problème en tant que graphe

Le problème peut également être représenté selon un graphe (fig. 1.2). E

012345

012345

012345

012345

F Chaque arc a pour valeur le rendement de l"investissement envisagé.

FIGURE1.2 - Graphe des investissements

Ici, il faut trouver le chemin de valeurmaximaledeEàF.

16CHAPITRE 1. PROGRAMMATION DYNAMIQUE

Chapitre 2Chemins optimaux dans lesgraphes2.1 Position du problème SoitG= (X,U)un graphe. Pour toutuU, on notev(u)la valeur de l"arc u. Cette valeur peut représenter une distance, un temps, ou de façon générale un coût. Soient(A,B)X2. La valeur du cheminest simplement : uv(u) Problème : déterminer un chemin de valeur minimal deAàB. Exemple 4.Réseau de télécommunications : chaque couple(A,B)de stations est reliée par un nombre donné de stations intermédiaires. Chaque arc a alors pour valeurpi,j, qui est la probabilité de fonctionnement correct de la liaison entreietj.

Trouver le chemindeAàBconsiste à trouver :

max (i,j)p i,j ou encore min (i,j)log(pi,j) 17

18CHAPITRE 2. CHEMINS OPTIMAUX DANS LES GRAPHES

2.2 Algorithme de Dijkstra

SoitG= (X,U)quelconque, tel queuU,v(u)0.sest une racine. On attribue pour chaquexXla valeur(x). La valeur(x)peut être : -Définitive: valeur du chemin optimal desàx. -Provisoires: borne supérieure de la valeur du chemin optimal desàx. On notec(s,x)la valeur de l"arc(s,x)s"il existe,+sinon.

Algorithme 1Algorithme de Dijkstra

{Initialisation} (s) =0 pour chaquex=sfaire (x) =c(s,x)

A(x) =s

fin pour D=s P=Xs

A(s) =

tant queP=faire {Attribution d"une valeur définitive à un sommet deP}

Soitx0Pt.q.(x0) =minxP(x)

D=D+x0

P=Px0 {Révision éventuelle des valeurs attribuées au sommet deP} pour chaquexPfaire si(x) (x0)+c(x0,x)alors (x) =(x0)+c(x0,x)

A(x) =x0

fin si fin pour fin tant que

La complexité de l"algorithme estO(n2).

quotesdbs_dbs50.pdfusesText_50

[PDF] cours de relativité restreinte pdf

[PDF] cours de sage saari comptabilité 100 pdf

[PDF] cours de schema electrique batiment pdf

[PDF] cours de science administrative gratuit

[PDF] cours de science d'ingenieur 1 stm

[PDF] cours de science d'ingenieur 2 stm

[PDF] cours de science islamique gratuit

[PDF] cours de science politique pdf

[PDF] cours de sciences politiques l1 droit

[PDF] cours de seconde bac pro gestion administration

[PDF] cours de secrétariat de direction gratuit pdf

[PDF] cours de secrétariat gratuit pdf

[PDF] cours de sécurité informatique - cryptographie (en pdf )

[PDF] cours de sig gratuit

[PDF] cours de sociologie politique droit