Vincent Boucheny (a.k.a. Mankalas)

Option SCIA

Recherche opérationnelle � Stochastiques

Promo 2007

Ce document reprend les prises de notes e�ectuées durant le cours de Patrick

Siarry et n'est en aucun cas destiné à être di�usé à l'extérieur du cadre de

l'EPITA.

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

TABLE DES FIGURES

Ing2

EPITA

Table des matières

1 Probabilités 1

1.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Loi de Bernouilli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Probabilités conditionnelles � Théorème de Bayes . . . . . . . . . . . . . . . . . . . . . . . 1

2 Chaînes de Markov 2

2.1 Régime transitoire d'une chaîne de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Régime permanent d'une chaîne de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Processus de Markov 6

4 Généralités 6

4.1 Ergodicité d'un processus de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74.2 Processus de naissance et de mort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 Files d'attentes 9

5.1 Application du service comptable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95.1.1 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105.1.2 Exploitation du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Table des �gures

1 Exemple de la cage d'animal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Graphe de transition de la cage d'animal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Graphe de transisitions du sous-problème de l'animal dans sa cage . . . . . . . . . . . . . . 44 Graphe de transition du problème du garagiste . . . . . . . . . . . . . . . . . . . . . . . . . 55 Schéma du magasin de stockage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Graphe de transition pour l'exemple du magasin . . . . . . . . . . . . . . . . . . . . . . . . 77 Exemple de coupes dans un graphe de transition simpli�é . . . . . . . . . . . . . . . . . . . 88 Processus de naissance et de mort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Organisation de la société de comptabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1010 Graphe de transition du problème de la société de comptabilité . . . . . . . . . . . . . . . . 10

1

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

1. Probabilités

Ing2

EPITA

1 Probabilités

1.1 Rappels

1.1.1 Dénombrement

Exemple :

Soit une main au bridge, soit 13 cartes, extraites parmi 52. Quelle est la probabilité qk d'avoir exactementk as dans la main (0 ≤ k ≤ 4) ? Véri�er que q0 + q1 + q2 + q3 + q4 = 1.On dénombre les probabilités.

qk =Nombre d'événements favorablesNombre d'événement possibles

=Nombre de mains ayant exactement kas

Nombre total de mains possibles

Dénominateur : C1352 =

52!13!(52− 13)!

Nombre de mains de 13 cartes ayant exactement k as. Supposons qu'on ait une main qui réponde auproblème : 13 cartes → k as + (13− k) non-as. Le problème devient :� tirer k cartes parmi un ensemble de 4 cartes (les as) = Ck

4 .� tirer (13− k) carte parmis 48 cartes (les non-as) = C13−k

48 .Finalement,

qk =Ck

4 C13−k48

C1352

,

4∑k=0

qk = 1

� q0 =C0

4C1348

C1352

=48!

13!35!13!39!52!

=39× 38× 37× 3652× 51× 50× 49

≈ 0, 304

� q1 ≈ 0, 439.� q2 ≈ 0, 213.� q3 ≈ 0, 041.� q4 ≈ 0, 003.Exemple :

Quelle est la probabilité d'avoir une main rouge ?

Q =C13

26

C1352

≈ 1, 6.10−5

1.1.2 Loi de Bernouilli

Exemple :

Soit un lot de coton. On suppose qu'il y a dans ce lot de coton� 75% de �bres dont la longueur l ≤ 45mm.� 25% de �bres dont la longueur l > 45mm.On a 3 �bres tirées au hasard. Quelle est la probabilité d'avoir 2 �bres longues et 1 �bre courte ?On a P (C) = 0, 75 = q et P (L) = 0, 25 = p. Loi de Bernouilli (binômiale) : 2 possibilités complémentaires.3 tirages successifs sans remise. Donc P (2L, 1C) = ppq + pqp + qpp = 3p2q.Pour n tirages succesifs, la probabilité d'obtenir m fois l'événement de probabilité p et d'obtenir (n−m)fois l'événement de probabilité q est

Cmn pmqn−m

1.2 Probabilités conditionnelles � Théorème de Bayes

Exemple :

Supposons deux urnes U1 et U2. Dans l'urne U1, on place 4 boules blanches et dans U2, on place une boulenoire et 3 boules blanches. Un individu choisit au hasard une urne et tire successivement 2 boules danscette même urne.

1. On remet la boule après le premier tirage.

1

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

2. Chaînes de Markov

Ing2

EPITA

Fig. 1 � Exemple de la cage d'animal

(a) Quelle est la probabilité de tirer deux boules blanches ?

(b) Sachant que la première boule était blanche, quelle est la probabilité que la deuxième le soit ?

2. Mêmes tirages, mais sans remise.

1. (a) Deux cas de �gure

� Le tirage s'est fait dans l'urne 1 : P (2B) = 1.� Le tirage s'est fait dans l'urne 2 : P (2B) = 3

4 ×34 .

Donc P (2B) = 12 × 1 + 1

2 ×34 ×

34 = 25

32 .

(b) Est-ce plus facile de calculer P (A/B) plutôt que P (B/A) ?. Théorème de Bayes :

P (A/B) =P (B/A)P (A)

P (B)�

P (U1/1B) =P (1B/U1)P (U1)

P (1B)=

1× 12

12 × 1 + 1

234

=47

�

P (U2/1B) =P (1B/U2)P (U2)

P (1B)=

34 ×

12

12 × 1 + 1

234

=37

Au �nal,

P (2emeB/1ereB) =47× 1 +

37

34

=2528

(a) P (2B) = 12 × 1 + 1

2 ×34 × 23 = 3

4 = 2432

(b)

P (2emeB/1ereB) =47× 1 +

37

23

=2428

2 Chaînes de Markov

Processus aléatoire sans mémoire, temps discret.Ingrédients :

1. Un �système� observé

Exemple Un animal de laboratoire enfermé dans une cage à 5 compartiments (Figure 1) :

2. Ce système peut se trouver dans di�érents états. Ce sont les di�érentes observations possibles. Dansl'exemple, on a 5 états A, B, C, D et E qui correspondent à la présence de l'animal dans l'un de cescompartiments. Si l'animal est dans la case C, on dira que le système est dans l'état C.

3. On a fait la liste de tous les états possibles (ces états possibles sont en nombre �ni ou in�ni)

4. À un instant quelconque, le système est dans un état, et un seul. Les états s'excluent mutuellement.

5. On suppose que les instants d'observation du système sont discrets, à intervalles de temps générale-ment réguliers (ex : τ = 1s). τ est choisi assez petit pour que l'on ne �rate� aucune transition.

2

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

2. Chaînes de Markov

Ing2

EPITA

Fig. 2 � Graphe de transition de la cage d'animal

6. Une chaîne formée pas la succession des états observés. (ex : (A,A, B,B,B, . . .), (A,C, C, C, D,D,C, . . .)).

7. Transitions entre les états : changements d'état.

Hypothèse : On suppose que, si le système est dans un état donné Ei à l'instant d'observation kτ , onconnaît la probabilité que le système soit dans chacun des états possibles à l'instant d'observationsuivant. Cette probabilité est une probabilité conditionnelle : P (Ej/Ei)

nb_étatsj=0

Tout le passé du sytème se résume dans l'état présent. On suppose connue la matrice dite �matricede transition� M . C'est une matrice carrée n× n avec n le nombre �ni d'états possibles. M contientdes probabilités de transition que l'on va noter Pi,j = P (etatj/etati)Exemple :

M =

0, 2 0, 5 0, 3 0 00 1 0 0 00 0 0, 3 0, 4 0, 30 0 0, 3 0, 7 00 0 0 0, 4 0, 6

La chaîne des états observés est devenue une chaîne de Markov. À partir de la matrice M , on peut dé�nirun graphe de transition (Figure 2).� sommets ⇐⇒ états.� arc (i, j) ⇐⇒ transition de l'état i à l'instant kτ à l'état j à l'instant (k + 1)τ .� valuation de l'arc (i, j) ⇐⇒ Pi,j .

2.1 Régime transitoire d'une chaîne de Markov

Est-il possible de connaître l'état dans lequel sera le système à l'instant 32τ ? Non, seulement un vecteurΠ32 = (ΠA

32,ΠB32, . . . ,Π

E32). Si l'état d'origine est l'état A, alors Π0 = (1, 0, 0, 0, 0). On a

Πk = Πk−1M, k ≤ 1

Exemple :

ΠC1 = ΠA

0 pA,C + ΠB0 pB,C + . . . + ΠE

0 pE,C

Si l'on désire calculer directement Πk :

3

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

2. Chaînes de Markov

Ing2

EPITA

Fig. 3 � Graphe de transisitions du sous-problème de l'animal dans sa cage

Πk = Π0Mk

2.2 Régime permanent d'une chaîne de Markov

La chaîne de Markov est ergodique (ou fortement ergodique) si et seulement s'il existe une limite auxvecteurs Πk quand k →∞ et si cette limite est indépendante de l'état initial Π0.

Intérêt de l'ergodicité. En régime permanent (k →∞), il y a une sorte de disparition du hasard. Leprocessus devient prévisible. On peut dimensionner le système. On constate deux phénomènes : l'agitationmicroscopique et la stabilisation macroscopique.2 interprétations :

1. Interprétation ponctuelle. Si l'on observe le système à un instant kτ su�samment grand pour que lerégime soit permanent, la probabilité d'observation de chaque état est connu (Π∗). Si l'on fait uneobservation à un instant k′τ avec k′ > k, alors la probabilité de chaque état est la même.

2. Interprétation statistique. Une fois dans le régime permanent, si l'on observe plusieurs fois le systèmependant une certaine durée, la répartition des états est égale. En régime permanent, le système passeune proportion constante de son temps dans chacun des états.

Quand la chaîne de Markov est-elle ergodique ? Il n'y a pas de condition nécessaire et su�sante pourrépondre à cette question, il n'y a qu'un jeu de conditions su�santes qui portent sur le graphe de transition :

1. Graphe �ni (nombre d'états �ni).

2. Graphe fortement connexe.

3. Graphe comporte au moins une boucle (arc qui part d'un sommet et qui rejoint ce même sommet).

Comment calculer le vecteur Π∗ ?

Π∗ = Π∗.M (1)∑i

Π∗i = 1 (2)

Exemple Animal dans sa cage :

La chaîne de Markov n'est pas ergodique car le graphe n'est pas fortement connexe (B est un cul-de-sac).Exemple Sous-problème de l'animal dans sa cage :

On réduit la cage à trois compartiments : C, D et E (voir Figure 3).

M =

0, 3 0, 4 0, 30, 3 0, 7 00, 4 0 0, 6

4

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

2. Chaînes de Markov

Ing2

EPITA

Fig. 4 � Graphe de transition du problème du garagiste

L'ergodicité est assurée ici. Calculons le vecteur Π∗.

Π∗ = (c, d, e) (3)(c, d, e) = (c, d, e)×

0, 3 0, 4 0, 30, 3 0, 7 00, 4 0 0, 6

c + d + e = 1

(4)

Π∗ =(

1237

,1637

,937

)(5)

Exemple Garagiste :

Location de camionnettes, parc de 4 camions, demande > o�re, location minimale au début d'une journéeest de 2 camions. Pour un camion loué, il y a une certaine probabilité de panne p et une probabilité denon-panne q = 1− p ⇒ loi binômiale. Le garagiste répare un seul vehicule en soirée.Étudier le fonctionnement de cette entreprise en la modélisant par une chaîne de Markov.Ici, τ correspond à une journée. Les états sont observés au début de chaque journée. Les états vontcorrespondre au nombre de véhicules en état de marche au début d'une journée. Il n'y a que 4 étatspossibles (le garagiste répare toujours un véhicule le soir) : A, B, C et D (A = 1 véhicule opérationnel,D = 4 véhicules).

M =

0 1 0 0p2 2pq q2 0p3 3p2q 3pq2 q3

p4 4p3q 6p2q2 4pq3 + q4

On suppose qu'en début d'année, tous les véhicules sont en état de marche. On suppose également quep = q = 1

2 .

Π0 = (0, 0, 0, 1) (6)

Π1 =(

116

,416

,616

,516

)(7)

Π2 =(

33256

,104256

,82256

,37256

)(8)

... (9)

Π∗ =(

61361

,196361

,88361

,16361

)(10)

a = 1

4b + 18c + 1

16d

b = a + 24b + 3

8c + 416d

c = 14b + 3

8c + 616d

d = 18c + 5

16d

5

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

4. Généralités

Ing2

EPITA

Fig. 5 � Schéma du magasin de stockage

3 Processus de Markov

4 Généralités

C'est l'extension au cas continu ∀t du modèle des chaînes de Markov. Il n'y a pas d'instant d'observationprivilégié.Éléments nécessaires pour fabriquer un processus de Markov :� Un système observé.� Ce système peut occuper di�érents états possibles. La liste de ces états est connue à l'avance (liste �nieou in�nie).

� Les états s'excluent mutuellement.� Transitions entre les états sont de nature stochastique.� Caractère markovien (absence de mémoire) ? Reconstitution d'une sorte de discrétisation du temps ? ⇒Loi de Poisson : les changements d'état du système sont dûs à des �événements� (ex : arrivée d'usagersdans un bureau de poste, arrivées de travaux à traiter dans un ordinateur, etc.). Ces événements sontrégis par des lois de Poisson.

� Propriété particulière de la loi de Poisson de taux λ. Dé�nition : probabilité de l'occurence de n événe-ments pendant un temps t :

Pn(t) =(λt)n

n!e−λt

λ est une constante connue.Propriété : probabilité d'occurence d'un seul événement pendant un temps �petit� dt : λdt.Conséquence : la probabilité de 2 événements pendant le même temps dt : (λdt)2. On peut donc direque (λdt)2︸ ︷︷ ︸

≈0

<< λdt. Il est impossible d'avoir 2 événements pendant le même temps dt.

Pendant dt, il y a deux possibilités : soit il se produit un événement, soit il ne se passe rien. Cela restevrai avec plusieurs lois.

�Discrétisation� du temps : on considère toutes les transitions entre 2 instants voisins : t et t + dt. 2possibilités seulement : soit il n'y a pas d'événement, soit il y en a un et un seul.Absence de mémoire : on va considérer que la probabilité de transition d'un état Ei à l'instant t à un autreétat Ej à l'instant t + dt ne dépend que de Ei.Exemple Magasin de stockage :

On considère un magasin de stockage de composants électroniques. On suppose que les composants sontstockés dans trois lieux : L1, L2 et L3. On a deux robots qui se déplacent et qui sont chargés de prendredes composants dans des lieux Li. Chaque prélèvement en un lieu donné Li, i ∈ {1, 2, 3} est régi par uneloi de Poisson de taux µi.On suppose que ce sont les prélèvements qui prennent du temps vis-à-vis de la dynamique de déplacementdes robots. Le programme suivi de chaque robot :

1. Prélèvement en L1.

2. Prélèvement en L2 avec la probabilité p ou alors le prélèvement se fait en L3 avec la probabilité q.

3. Retour un L1.

4. Si un robot est déjà présent en Li, le deuxième robot attend son tour.

6

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

4. Généralités

Ing2

EPITA

Fig. 6 � Graphe de transition pour l'exemple du magasin

Modéliser le problème avec un système 3 lieux, 2 robots par un processus de Markov.La modélisation consiste à faire la liste des états possibles : (E1, E2, E3) avec Ei le nombre de robotsprésents en Li. Il y a 6 états possibles : (2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1).On construit le graphe de transition entre t et t + dt. Les sommets vont être les états et les arcs seront lestransitions de t à t + dt.On trace le graphe de transition simpli�é

1. On omet les boucles.

2. On value le graphe par des taux de probabilité

(proba

dt

).

4.1 Ergodicité d'un processus de Markov

t �su�sant� : on a laissé passé le régime transitoire. Existe-t-il un régime permanent, c'est-à-dire est-ce quela probabilité d'observer chacun des états devient-elle indépendante du temps ?On associe à chacun des états un vecteur Π∗ = (Π∗

0,Π∗1, . . .). Π

∗i correspond à la probabilité d'observer l'état

Ei si on examine le système à un instant t quelconque. C'est l'interprétation ponctuelle de l'ergodicité.Comment savoir si le processus de Markov est ergodique ? S'il est ergodique, comment calculer le vecteurΠ∗ ? Les conditions su�santes pour l'ergodicité sont les mêmes que pour les chaînes de Markov.Théorème des coupes : Soit une coupe dé�nie comme étant une ligne fermée entourant un nombre quel-conque de sommets du graphe de transition. En régime permanent (si ergodicité), la probabilité de sortied'une coupe quelconque est égale à la probabilité d'entrée dans cette même coupe pendant le temps dt.On choisit quelques hypothèses pour simpli�er le problème. On prend µ1 = µ2 = µ3 et p = q = 1

2 . Avecces hypothèses, le problème qui comportait 6 inconnues n'en comporte plus que 4. En e�et, il n'y a plusde di�érence entre L2 et L3. Donc Π∗

020 = Π∗002 et Π∗

110 = Π∗101.

On connait déjà une relation : ∑i

Π∗i = 1

Il ne manque plus que 3 relations pour établir un système de 4 équations à 4 inconnues.On prend la coupe C1 (voir Fig. 7) qui isole 002 :

Proba de sortie : Π∗002 × µ3dt

Proba d'entrée : Π∗101 × qµ1dt

}⇒ Π∗

002 × µ3dt = Π∗101 × qµ1dt ⇒ 2Π∗

002 = Π∗101

On prend la coupe C2 qui isole 011 :

Proba de sortie : Π∗011 × µ3dt + Π∗

011 × µ2dt

Proba d'entrée : Π∗110 × qµ1dt + Π∗

101 × pµ1dt

}⇒ 2Π∗

011 = Π∗110

On prend la coupe C3 qui isole 200 :

7

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

4. Généralités

Ing2

EPITA

Fig. 7 � Exemple de coupes dans un graphe de transition simpli�é

Fig. 8 � Processus de naissance et de mort

Proba de sortie : Π∗200 × qµ1dt + Π∗

200 × pµ1dt

Proba d'entrée : Π∗101 × µ3dt + Π∗

110µ2dt

}⇒ 2Π∗

110 = Π∗200

On obtient donc le système :2Π∗

002 = Π∗101

Π∗101 = 2Π∗

011

Π∗200 = 2Π∗

101

Π∗200 + 2Π∗

002 + Π∗011 + 2Π∗

101 = 1

⇒

Π∗

020 = Π∗002 = 1

11

Π∗110 = Π∗

101 = 211

Π∗011 = 1

11

Π∗200 = 4

11

Interprétation : Quel est le nombre moyen de robot se trouvant en L1 ? en L2 ? en L3 ?n1 = 1× 2

11 + 1× 211 + 2× 4

11 = 1211

n2 = n3 = 2× 111 + 1× 2

11 + 1× 211 = 5

11

4.2 Processus de naissance et de mort

C'est un processus de Markov particulier, à la base de la théorie des �les d'attentes. Caractéristiquesspéci�ques :� États E0, E1, . . . , Ek avec Ek l'état associé à la présence de k �usagers� dans l'organisme. Par exemple,le nombre de personnes dans un bureau de poste, le nombre d'appels téléphoniques dans un central, etc.

� Les transitions entre états sont associés à des entrées-sorties d'usagers.� Les entrées / sorties sont régies par des lois de Poisson (caractère markovien).� Graphe de transition formé de boucles. Il ne peut y avoir que des transitions de Ei à Ei+1 (voir Fig. 8).Le graphe est toujours le même, au nombre de boucles prêt.

� C'est un processus ergodique (uniquement si le nombre d'états est �ni). Les conditions sont su�santes(graphe complet �ni, fortement connexe avec au moins une boucle). Donc Π∗ existe en régime permanent.Le calcul du vecteur Π∗ est fait une fois pour toutes :

8

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

5. Files d'attentes

Ing2

EPITA

Π∗ = (Π∗0,Π

∗1, . . . ,Π

∗n) (11)

Π∗1 =

λ0

µ1Π∗

0 (12)

Π∗2 =

λ1

µ2Π∗

1 =λ1λ0

µ2µ1Π∗

0 (13)

... (14)

Π∗n =

∏n−10 λi∏n1 µj

Π∗0 (15)

En rajoutant la relation de normalisation :

n∑i=0

Π∗i = 1 (16)

Cas particulier :

∀i, λi = λ;∀j, µj = µ⇒ ∀Π∗k =

(λ

µ

)k

Π∗0

5 Files d'attentes

Notation de Kendall : A/B/n/m/discipline. Avec� A : Loi des arrivées.� B : Loi des �services� (sorties).� n : Nombre de guichets.� m : Capacité maximale de l'organisme.� discipline : façon dont les usagers sont servis (ex : FIFO).Cas particuliers :� n = 1, guichet unique ⇒∀i, λi = λ et ∀j, µj = µ. Formules connues à l'avance si la capacité maximale m

est donnée : M/M/1/m(/FIFO).� Système ouvert : m non �ni : M/M/1/∞. On utilise les formules du cas précédent en passant à lalimite. Les conditions su�santes d'ergodicité ne sont plus véri�ées. Condition nécessaire et su�santed'ergodicité

λ

µ< 1 ⇒

Π∗0 = 1− λ

µ

Π∗k =

(λµ

)k

Π∗0

Conclusion

� Système fermé ⇒ergodicité ∀λ, µ.� Système ouvert ⇒ergodicité ssi λ

µ < 1.

5.1 Application du service comptable

soient 5 comptables, 2 terminaux. Chaque comptable a besoin d'accéder à un terminal selon une loi dePoisson de taux β = 5 accès par heure.Pour chaque terminal, le service est rendu selon une loi exponentielle de taux α : durée des services de loiexponentielles⇒�n des services = sorties d'usagers de loi de Poisson.Entrées et sorties Poissonieuses.Durée moyenne d'une transaction : 4 minutes⇒taux moyen de �n de service : α = 60

4 = 15 transaction parheure.ATTENTION : β est pour un comptable, α pour un terminal.La société est structurée comme selon la Figure 9.

9

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

5. Files d'attentes

Ing2

EPITA

Fig. 9 � Organisation de la société de comptabilité

Fig. 10 � Graphe de transition du problème de la société de comptabilité

5.1.1 Modélisation

1. Étapes possibles.

Si k = 3, il y a 3 comptables dans la salle info. À l'instant t + dt, quels sont les états possibles ?

� t1 se libère avec une probabilité αdt.� t2 se libère avec une probabilité αdt.� b1 veut accéder à un terminal avec une probabilité de βdt.� b2 veut accéder à un terminal avec une probabilité de βdt.

2. Graphe de transition : voir Figure 10. A pour α, B pour β..

3. Si ergodicité, calculer Π∗. Le processus est bien ergodique. On a

Π∗1 =

5β

αΠ∗

0 ; Π∗2 =

5β × 4β

α× 2αΠ∗

0

Π∗3 =

60β3

4α3Π∗

0 ; Π∗4 =

120β4

8α4Π∗

0

Π∗5 =

120β5

16α5Π∗

0

Et

Π∗0

(1 +

53

+109

+1527

+1581

+15486

)= 1

On obtient donc :

10

Cours SCIA

Promo 2007

Recherche opérationnelle � Stochastiques

5. Files d'attentes

Ing2

EPITA

Π∗0 =

162737

; Π∗1 =

270737

Π∗2 =

180737

; Π∗3 =

90737

Π∗4 =

30737

; Π∗5 =

5737

5.1.2 Exploitation du modèle

Quelle et la probabilité d'une attante nulle ? Ponctuel :

p1 = Π∗0 + Π∗

1 = 0, 6

Quel est le nombre moyen de terminaux utilisés ? Statistique :

p2 = Π∗1 + 2(Π∗

2 + Π∗3 + Π∗

4 + Π∗5) = 1, 19

Quel est le temps moyen total perdu par heure cumulé sur les cinq comptables ? Nombremoyen de comptable en attente :

Π∗3 + 2Π∗

4 + 3Π∗5 =

165737

Or, c'est également le temps d'attente en heure. Temps d'attente = temps perdu = 165737h ≈ 13min.

11