|
République Algérienne Démocratique et
Populaire
Ministère de l'Enseignement Supérieur et de la
Recherche Scientifique
UniversitéA. Mira de
Béja·ýa
Facultédes Sciences Exactes
Département de Recherche Opérationnelle
M'emoire de fin d''etudes
Pour l'obtention du Diplôme Master
En
Recherche
Opérationnelle
Th`eme
???????????????????????????????????????????
Estimation de l'erreur de troncature de
? l'espace d'etats du système d'attente
M/M/1 :
? Méthode de StabilitéForte
?
???????????????????????????????????????????
Présentépar :
Melle Haoua LARAB
Devant le jury composéde :
Présidente Mme O. LEKADIR M C B
Encadreurs
Mr K. ABBAS M C B
Mr D. A·ISSANI Professeur
Examinateurs
Mme K. ADEL C C
Melle S. HAKMI M A
Année Universitaire 2010 - 2011
Table des matières
|
Introduction générale
1 Généralités sur les chaàýnes
de Markov
|
2
5
|
|
1.1
|
Processus stochastiques
|
5
|
|
|
1.1.1 Définitions
|
6
|
|
|
1.1.2 Processus Markoviens
|
6
|
|
1.2
|
Chaàýnes de Markov a` temps discret
|
7
|
|
|
1.2.1 Définitions et propriétés
|
7
|
|
1.3
|
Exemples
|
7
|
|
|
1.3.1 File d'attente en temps discret
|
7
|
|
|
1.3.2 La Gestion des stocks
|
8
|
|
1.4
|
Chaàýnes de Markov discrètes
|
8
|
|
|
1.4.1 Classification des états d'une chaàýne
de Markov
|
8
|
|
1.5
|
Classification des chaàýnes de Markov
discrètes
|
10
|
|
|
1.5.1 Chaàýnes de Markov homogènes
|
10
|
|
|
1.5.2 Chaàýnes de Markov irréductibles
|
10
|
|
|
1.5.3 Chaàýnes de Markov absorbantes
|
13
|
|
1.6
|
Distribution initiale et comportement transitoire
|
13
|
|
|
1.6.1 Distribution initiale
|
13
|
|
1.7
|
Comportement asymptotique des chaàýnes
irréductibles
|
13
|
|
|
1.7.1 Comportement asymptotique
|
13
|
|
|
1.7.2 Distribution limite
|
14
|
|
|
1.7.3 Distribution invariante
|
14
|
|
|
1.7.4 Comportement asymptotique des chaàýnes
irréductibles et apériodiques 15
|
|
|
1.7.5 Chaàýnes de Markov ergodiques
|
16
|
|
1.8
|
Conclusion
|
17
|
|
2
|
Systémes de files d'attente
|
18
|
|
2.1
|
Introduction et structure d'un système d'attente
|
18
|
|
|
2.1.1 Classification et formalisation d'un système de
files d'attente . . . .
|
19
|
|
|
2.1.2 Analyse mathématique d'un système de files
d'attente
|
21
|
|
2.2
|
Files d'attente markoviennes
|
21
|
|
|
2.2.1 La file d'attente M/M/1
|
21
|
2.2.2 La file d'attente M/M/m 23
2.2.3 La file d'attente M/M/1/N 25
2.3 Files d'attente non Markoviennes 28
2.3.1 Système de files d'attente M/G/1 28
2.3.2 Système de files d'attente G/ M/ l 31
2.4 Conclusion 33
3 Chaàýnes de Markov tronquées 34
3.1 Chaàýnes de Markov tronquées 34
3.1.1 Principe de troncature 35
3.1.2 Définitions 35
3.2 Différentes techniques de la troncature des
chaàýnes de Markov 36
3.2.1 Augmentation linéaire 37
3.2.2 Renormalisation 37
3.2.3 Distance entre les distributions stationnaires 39
3.3 Exemple de la troncature sur un réseau de files
d'attente en tandem avec
blockage 39 3.4 Exemple illustratif sur les techniques de
troncature par l'augmentation linéaire 41 3.5 Conclusion 46
4 Calcul de la borne de stabilitéforte pour le cas de
troncature de la capacitéd'attente de la file M/M/1 47
4.1 Préliminaires et notations 47
4.1.1 Borne de la stabilitéforte 48
4.2 Troncature de la capacitéd'attente de la file M/M/1
49
4.2.1 Description du modèle et position du problème
49
4.3 L'augmentation de la première colonne 50
4.3.1 Calcul de la borne de stabilitéforte
:Augmentation de la premi`ere
colonne 51
4.4 L'augmentation uniforme 57
4.4.1 Calcul de la borne de stabilitéforte : Augmentation
uniforme . . 58
4.4.2 Calcul de la borne réelle 62
4.4.3 Bornes de déviation du nombre moyen de clients
62
4.5 Conclusion 62
5 Comparaison des techniques de troncature 63
5.1 Applications numériques 63
5.1.1 Environnement MATLAB 63
5.1.2 Approche algorithmique 64
5.1.3 Algorithme de StabilitéForte 64
5.1.4 Organigramme de stabilitéforte 65
5.1.5 Variation de l'erreur en fonction de 66
5.1.6 Variation de l'erreur en fonction de N 67
5.1.7 Variation de l'erreur en fonction 3 75
5.2 Conclusion 75
Conclusion générale 76
Bibliographie 78
| 
