---
title: RO stochastique
tags: OPERA, romain.baguet
---

# Recherche Opérationnelle Stochastique

[toc]

## Rappels / probabilites

**Exo 1** : (p.111)

1 main : 13 cartes / 52

++Q1++: Proba q~k~ d'avooir exactement k as dans la main ?

Proba = Nb elements favorables / Nb elements possibles
= Nb mains ayant 4 as / Nb total de mains

Nb total de main ? C^13^~52~ -> nb de manieres d'extrare 13 elements de 52 elements.

C^p^~n~ = n! / p!(n-p)! -> Nb de mains ayant exactement k as (0 <= k <= 4)

Et on a :
- 4 as : k cartes C^k^~4~
- 48 non as : (13-k) / 13 => C^13-k^~48~

q~0~ = C^0^~4~ * C^13^~48~ / C^13^~52~ = 48! / 13!35! = 39! / 52!
q~0~ ~= 0,304
q~1~ ~= 0,439
q~2~ ~= 0,2013
q~3~ ~= 0,041
q~4~ ~= 0,003

++Q2++: Proba d'avoir 1 as ?

1 - q~0~ = 0,696

++Q3++: Proba d'avoir une main rouge ?

On a 13 cartes rouges (vu qu'on en tire 13 max).
=> Nb de mains rouge / Nb total de mains

Nb total de main = C^13^~52~
26 rouges <- 13 cartes = C^13^~26~

Proba(1 main rouge) = C^13^~26~ / C^13^~52~

**Exo 2** :

Un lot de 12 pieces contient :
- 4 pieces deffectueuses
- 8 pieces bonnes

On tire 3 pieces, l'une apres l'autre sans remise apres tirage.

++Proba (aucune piece defectueuse) ? :++

*Methode 1* : On raisonne (1 seul tirage des 3 pieces d'un seul coup)

=> nb de jeux de 3 pieces bonnes / Nb de jeux de 3 pieces = C^3^~8~ / C^3^~12~
= 8 * 7 * 6 / 12 * 11 * 10 ~= 0,255

*Methode 2* : On tire les pieces l'une apres l'autre

1^er^ tirage : 4 pieces def, 8 pieces bonnes => 8 / 12
2^nd^ tirage : 4 pieces def, 7 pieces bonnes => 7 / 11
3^ieme^ tirage : 4, 6 => 6 / 10

PROBA => (8 / 12) * () 7 / 11* (6 / 10) ~= 0,255

**Exo 3** : Loi de bernouilli

On tire au hasard 3 fibres

L: longue C: Courte

++Proba (2L, 1C) ?++

-> Tirage d'1 fibre :
- Proba(1C) = 0,75 = q
- Proba(1L) = 0,25 = p

LLC = ppq = p^2^q
LCL = pqp
CLL = qpp

Loi binomiale sur loi de bernouilli

Proba (m fois pile sur les n tirages)

C^m^~n~ = p^m^q^n-m^

Ici: C^m^~n~ = C^1^~3~ = 3 = C^2^~3~

**Exo 4**

On considere 2 urnes :
- Une avec 4 boules blanches
- Une avec 3 boules blanches et 1 noire

On selectionne 1 urne et on tire 2 boules successivement dans cette meme urne.

++1)a) Sachant qu'on remet la boule apres le premier tirage, proba d'avoir tire 2 boules blanches ?++

Proba(2 boule blanches) =
- dans U1 : (1 / 2) * 1
- dans u2 : (1 / 2) * (3 / 4)^4^

=> u1 + u2

++1)b) Sachant que la premiere boule etait blanche, proba que la deuxieme soit blanche ?++

P(U1 | 1^ere^ boule etait blanche) -> Proba conditionelle
P(U2 | 1^ere^ boule etait blanche)

Le "Proba que x sachant y" : le "sachant y" est la stochastique.

Test => P(A | B)
Est-il plus facile de calculer P(B | A) ?

++Theoreme de BAYES++

P(A | B) = (P(B | A) * P(A)) / P(B)

P(U1 | 1^ere^ b'b') = (P(1^ere^ b'b' | U1) * P(U1)) / P(1^ere^ b'b')
= (1 * 1/2) / (1/2 * 1 + 1/2 * 3/4) = 4 / 7

P(U2 | 1^ere^ b'b') = (3/4 * 1/2) / (1/2 * 1 + 1/2 * 3/4) = 3 / 7

Resultats logiques car on a : 7 boules blanches et 4 dans U1, et 3 dans U2.

= 25 / 28

++2)a) Meme question que 1)a) mais sans remise++

=> ((1 / 2) * 1) + ((1 / 2) * (3 / 4) * (2 / 3)) = 24 / 32

++2)b) Meme question que 1)b) mais sans remise++

=> (4/7 * 1) + (3/7 * 2/3) = 24 / 28

**Exo 5**

3 machines qui produisent des boulons : A(25% des boulons), B(35%), C(40%)
Machine A : 5% boulons defectueux
Machine B : 4%
Machine C : 2%

On tire un boulon au hasard -> ce boulon est defectueux :
- Proba produit par A ?
- // par B ?
- // par C ?
(La somme donne 1)

On tire 1 boulon :
- P(A) = 0,25
- P(B) = 0,35
- P(C\) = 0,40
d = defectueux
- P(d|A) = 0,05
- P(d|B) = 0,04
- P(d|C) = 0,02

++P(A|d) ? P(B|d) ? P(C|d) ?++ (On remarque qu'il y a le meme univers (d) donc la somme vaut 1

$P(A|d) = \frac{P(d|A) * P(A)}{P(d)} = \frac{0,05 * 0,25}{(0,25 * 0,05) + (0,35 * 0,04) + (0,40 * 0,02)} = \frac{25}{69}$

## Chaines de MARKOV

Modelisation par processus a 3 proprietes :
- aleatoire
- discret
- sans memoire

++Un systeme++ : On considere un "systeme" qui est observe a des instants distincts

++Exemple++ : Animal enferme dans une cage.
A -> B
|
\\/
C
/\\/\\
||
\\/\\/
D E

++Etat++ : a un instany d'observation $t = k\tau$ (k=entier) le systeme se trouve dans un etat et un seul (parmi une liste d'etats possibles)

++Ici++ : 5 etats A,B,C,D,E -> l'animal est en C = le systeme est a l'etat C

Rq: pas d'etat intermediaire

++Chaine++ : On s'interesse a la succession des etats observes a $t=0, t=\tau, t=2\tau, etc$
Ex: AAABB, ABB

++Mecanismes de "Transition"++ (changement d'etat)
Si le systeme est dans l'etat i a $t=k\tau$. On connait p~ij~ = proba d'etre dans l'etat j a $t=(k+1)\tau$.
On connait la matrice de transition M: n * n avec n le nombre d'etats possibles.

$\begin{bmatrix}&A&B&C&D&E\\A&0,2&0,5&0,3&0&0\\B&&1\\C&&&0,3&0,4&0,3\\D&&&0,3&0,7\\E&&&0,4&&0,6\end{bmatrix}$

++Hypothese++ $\tau$ assez petit pour que entre $k\tau$ et $(k+1)\tau$, l'animal n'a pas changer plusieurs fois d'etat.

++1^er^ travail++ : determiner M
La chaine des etats successifs observes est alors une Chaine de Markov.
Processus
- Aleatoire : p~ij~
- Discret : $t=k\tau$
- sans memoire

La connaissance de l'etat present suffit pour calculer les etats ulterieurs.

++Rq++ : tous les processus aleatoires et discret ne peuvent pas etre modelises par une Chaine de Markov

++Regime transitoire d'une chaine de Markov++

On suppose :
- L'etat connu t=0
- On connait la matrice M

++Ex++ : a t=o, animal en A

Peut on calculer dans quel etat se trouvera le systeme a $t=32\tau$ ?

On peut calculer 5 probabilites a $\prod_{32}$

$\prod_{32} = \prod_{32}^{A},\prod_{32}^{B},\prod_{32}^{C}, etc = 1$

- a t=0, $\prod_{0}=(1\ 0\ 0\ 0)$
- a $t=\tau, \prod_{1}=(?\ voir\ suite)$
- a $t=32\tau, \prod_{32}=(?\ voir\ suite)$

Formule : $\prod_{k}=\prod_{k-1}*M \ pour\ k=1,2,...$

$\prod_{1}^{C}=\prod_{0}^{A}*0,3 + \prod_{0}^{B}*0 + \prod_{0}^{C}*0,3 + \prod_{0}^{D}*0,3 + \prod_{0}^{E}*0,4$ (coef de la colonne C de la matrice)

Peut-on calculer $\prod_{32}$ sans calculer tous ceux qui le precedent ?

$\prod_{k} = \prod_{0}*M^k$

Donc on a :
- $\prod_{1}=\prod_{0}*M = (0,2\ \ 0,5\ \ 0,3\ \ 0\ \ 0)$
- $\prod_{2}=\prod_{1}*M = (0,2\ \ 0,5\ \ 0,3\ \ 0\ \ 0)*M = (0,04\ \ 0,6\ \ 0,15\ \ 0,12\ \ 0,09)$
- $\prod_{32}=\prod_{0}*M^{32}$

++Regime permanant d'une chaine de Markov++

On s'interesse a la limite (si elle existe) du vecteur $\prod_{k}$ lorsque k -> +$\infty$
Definition : La chaine de M. est ergodique ssi il existe une limite $\prod_{\infty}$ (vecteur) au vecteur $\prod_{k}$ alors que k -> +$\infty$ et si cette limite est independante de l'etat initiale

||Animal en A| Animal en B|...| Animal en E|
|:-----------------------------|:--------------:|:------------:|:-------------:|:--------:|:---------:|
|a $t=0$|$\prod_{0}=(1\ 0\ 0\ 0\ 0)$|$\prod_{0}=(0\ 1\ 0\ 0\ 0)$||$\prod_0=(00001)$
|a $t=\tau$|$\prod_{1}$ = (0,2 0,5 0,3 0 0)|$\prod_{0}=(0\ 1\ 0\ 0\ 0)$|
|a $t=2\tau$|$\prod_{2}$ = (0,04 0,6 ...)||

La chaine de M n'est pas ergodique car :
- la chaine 2 converge vers (0 1 0 0 0)
- la chaine 5 ne peut pas converger vers (0 1 0 0 0)

++Conditions suffisantes d'ergodicité++
3 conditions concernant le graphe de transition:
- Graphe fini
- // fortement connexe
- // au moins une boucle

++Graphe de transition++
- Sommets -> etats
- Arcs -> transitions i->j (kt)->((k+1)t)
- valuations -> p~ij~


- Ici, les 3 conditions suffisantes d'ergodicité ne sont pas vérifiées (regle 2 non verifiés) => on ne peut pas conclure.
- On a conclue en examinant les cas particulier de la 2^ieme^ colonne

++Application plus simple++ -> 3 compartiments


Les 3 conditions suffisantes d'ergodicité sont verifiés.
=> $\prod_{infini}$ existe

Calcul du vecteur $\prod_{infini}$ (lorsque la chaine de Markov est ergodique)


++Interpretation++
++1) Interpretation PONCTUELLE++
La probabilité d'observer l'animal en c ne varie plus. Elle est constante (egale a 12/37), a tout instant de l'observation.
-> "Sorte de disparition du hasard"
-> STABILISATION MACROSCOPIQUE

++2) Interpretation statistique++

##### 2^ieme^ application : Pb du garagiste (p.114)
- 4 véhicules loués a la journée
- Chaque véhicule loué -> Proba de panne = p (proba de non panne q = 1 - p)
- Le garagiste peut faire une seule réparation en soirée
- 
- Demande en location > offre
- Le garagiste ne loue des vehicules que si il y a au moins 2 vehicules en etats de marche au debut de la journee.

++1) Modeliser le fonctionnement du garage avec une chaine de Markov++
*Modelisation* :
- Systeme consideré ?
- $\tau$ ?
- etats possible a $t=k\tau$
- Matrice de transition M ?
- Graphe de transition ?

Etats <=> Nb de véhicules qui marchent au debuts d'une journée.
++AN++ : p=(1/2)=q
++2) Regime transitoire++
Initialement les 4 vehicules sont en etat de marche.
- Quelles sont les probabilités des 4 états possibles au bout d'une journée ?
- // au bout de deux journéses
++3) Regime permanant++
Au bout d'un grand nombre de jours de location, existe-t-il une limite aux probabilités des etats du parc de véhicules ? (limite indépendante de l'etat initial)
Ici, les 3 conditions suffisante d'ergodicité sont verifies
- graphe fini
- // fortement connexe
- au moins 1 boucle (ici, 3 boucles)

=> $\prod_{infini}$ existe et il est independant de $\prod_0$
Interpretation statistique de l'ergodicité
- le garagiste peut calculer a l'avance sa recette annuelle
- Cette recette sera la meme chaque année

361 ~= 365 jours

- 2 mois etat A (1 vehicule marche) recette 0
- 6,5 mois B (2 vehicules) => recette
- 3 mois C (3 vehicules) => //
- 0.5 mois D (4 vehicules) => //

p = 1/2
Il achete des vehicules neufs: p=0,01

++4) Reprendre la modelisation si p=0++
++Reprendre la modelisation si p=1++

p=0 => Comportement deterministe q=1
++Etat D++ -> etat permanent absorbant
Au bout d'au plus 3 jours, le systeme sera dans l'etat D indéfiniment.

p=1, q=0
Cycle permanent absorbant A-B-A-B-etc
Au bout d'une journée au plus, le systeme est piégé dans le cycle ABABAB...
Processus deterministe.

## Processus de MARKOV

Généralisation du modèle de la chaine de Markov dans le cas du ++temps continue++
=> On introduit la notion d'instant voisin (le voisin est infiniment proche de t)
++Loi de POISSON++
-> Frequement utilisée pour décrire des phenomenes aleatoires tels que les arrivés d'usagers dans un bureau de Poste, ou encore les sorties des usagés
++Propriété fondamentale de la loi de Poisson++
La probabilité d'une arrivé pendant 'dt' vaut : $\lambda.dt$
++Conséquence++:
Pendant $dt$, il n'y a que 2 possibilités
- 1 arrivé se produit -> Proba $\lambda.dt$
- 0 arrivé se produit -> Proba $1-\lambda.dt$ (le plus probable)
- $\sum = 1$

++Remarque++ : Il est considéré comme impossible d'avoir 2 arrivés observés entre $t$ et $(t + dt)$ -> la probabilité est de $(\lambda.dt)*(\lambda.dt)=\lambda^2(dt)^2$ négligeable
++Remarque++ : s'il y a plusieurs sources d'aléas, on observera entre $t$ et $(t+dt)$ au plus 1 seul évènement (de l'une sur l'autre des differentes sources d'aléas)
Il est exclu d'avoir pendant le meme dt :
- a la fois 1 arrivé $\lambda dt$
- et une sortie venant de G1 $\mu_1 dt$
$(\lambda \mu_1)(dt)^2$ ~= 0

##### Application
Magasin de stockage de composants éléctroniques
- Une fois le prevelevement en L1 fait, le robot se deplace instantanement vers L2 avec la proba $p$ OU L3 avec la proba $q=1-p$
- Arrivé en L2, le robot stationne jusqu'a ce qu'il fasse 1 prélevement, selon une loi de Poisson de taux $\mu_2$
- Une fois le prélèvement fait en L2 (ou L3), le robot retourne instatanement en L1
- Si les 2 robots sont present en un meme lieux a un instant donnée, seul le premier arrivé peut faire un prelevement.

On peut décrire le fonctionnement du systeme {3 lieux, 2 robots} à l'aide d'un PROCESSUS DE MARKOV.
car les sources d'aleas sont toutes regis par les lois de Poisson.

## Processus NAISSANCE et de MORT

## Files d'attentes