---
tags: fiche
---

# Fiche - Recherche Operationnelle Stochastique

## Rappels de probabilités (p111)

### Exercice 1

:::success
Une main au bridge : 13 carte tirées d'un jeu de 52 cartes
:::

:::spoiler 1. Probabilité d'avoir dans la main exactement k as ?
$$q_k = \frac{\binom{4}{k}*\binom{48}{13-k}}{\binom{52}{13}}$$
:::

:::spoiler 2. Probabilité d'avoir au moins 1 as ?
$$p = 1 - q_0$$
:::

:::spoiler 3. Probabilité d'avoir une main rouge (13 cartes rouges) ?
$$p = \frac{\binom{26}{13}}{\binom{52}{13}}$$
:::

### Exercice 2

:::success
Un lot contient 12 pièces
- 4 pièces defectueuses
- 8 pièces bonnes

On tire 3 pièces, l'une après l'autre, sens remise après tirage.
:::

1) Probabilité d'avoir aucune pièce défectueuse

:::spoiler Méthode 1 : On tire les 3 pièces d'un coup
\
Nombre de manière de tirer 3 pièces bonnes : $\binom{8}{3}$
$$\frac{{\binom{8}{3}}}{{\binom{12}{3}}} = 0,255$$
:::

:::spoiler Méthode 2 : On tire les pièces l'une après l'autre
\
1er tirage : 4 défect - 8 bonnes -> $\frac{8}{12}$
2e tirage : 4 défects - 7 bonnes -> $\frac{7}{11}$
3e tirage : 4 défects - 6 bonnes -> $\frac{6}{10}$
$$\frac{8}{12} * \frac{7}{11} * \frac{6}{10}$$
:::

### Exercice 3 (Loi binomiale)

:::success
75% des fibres sont courtes.
25% des fibres sont longues.
On tire au hasard 3 fibres.
:::

:::spoiler Probabilité de tirer deux fibres longues et une fibre courte ?
*Tirage d'une fibre*

Proba (1L) = 0,25 = p
Proba (1C) = 0,75 = q

*Tirage de trois fibres*

Loi binomiale = loi de Bernouilli

$3 * p * p * q$

Proba(LLC) = p * p * q
Proba(LCL) = p * q * p
Proba(CLL) = q * p * p

Somme = 3 * p * p * q

Evenement de probabilité p = Pile
Evenement contraire de propabilité q = face

Proba (m fois PILE, (n - m) fois FACE) = $\binom{n}{m} * p^m * q^{n-m}$
:::

### Exercice 4 (Probas conditionnelles, théorème de BAYES)

:::success
Il y a 2 urnes :
- Urne 1 : 4 boules blanches
- Urne 2 : 3 boules blanches et 1 boules noires

Un individu choisi une urne et tire deux boules sucessivement dans cette même urne.
:::

1. Sachant qu'il remet la boule après le premier tirage

:::spoiler a) La probabilité de tirer deux boules blanches
\
Lorsqu'on est dans U1 : $p1(2bb) = 1$
Lorsqu'on est dans U2 : $p2(2bb) = {(\frac{3}{4})}^2$
$$ p(2bb) = \frac{1}{2} * p1(2bb) + \frac{1}{2} * p2(2bb) $$
$$ p(2bb) = \frac{1}{2} * 1 + \frac{1}{2} * {(\frac{3}{4})}^2 $$
$$ p(2bb) = \frac{25}{32} $$

:::

:::spoiler b) Sachant que la première boule était blanche, quelle est la probabilité que la deuxième boule soit blanche ?
\
$$ p = \frac{4}{7} * 1 + \frac{3}{7} * \frac{3}{4}$$
$$ p = \frac{25}{28} $$
:::

\
2. Même question pour un tirage sans remise

:::spoiler a)
\
Lorsqu'on est dans U1 : $p1(2bb) = 1$
Lorsqu'on est dans U2 : $p2(2bb) = \frac{3}{4} * \frac{2}{3}$
$$ p(2bb) = \frac{1}{2} * p1(2bb) + \frac{1}{2} * p2(2bb) $$
$$ p(2bb) = \frac{3}{4} $$
:::

:::spoiler b)
\
$$ p = \frac{4}{7} * 1 + \frac{3}{7} * \frac{2}{3}$$
$$ p = \frac{6}{7} $$
:::

### Exercice 5 (de BAYES)

:::success
Dans une usine de boulons, on a 3 urnes :
* La machine A produit 25% des boulons, dont 5% défectueux
* B -> 35%, 4% défectueux
* C -> 40%, 2% défectueux
On tire un boulon au hasard et il est défectueux.
:::

:::spoiler Quelle est la probabilité qu'il vienne de A ?
$P(A) = 0,25$ ; $P(B) = 0,35$ ; $P(C) = 0,40$
$P(d/A) = 0,05$ ; $P(d/B) = 0,04$ ; $P(d/C) = 0,02$

Théorème de BAYES:
$P(A/d) = \frac{P(d/A)*P(A)}{P(d)}$
Théorème des probabilités totales:
$P(d) = P(A)*P(d/A) + P(B)*P(d/B) + P(C)*P(d/C)$
:::

## Chaîne de Markov

### Cours

**Chaîne de Markov :**

:::info
++Définition :++
Une chaîne de Markov est un modèle pour un **processus aléatoire**, **discret** et **sans mémoire**.
:::

On décompose cette chaîne en une mutlitude de vecteurs.
On notera $\pi_k$ le vecteur correspondant à la $k^{ème}$ itération.

**Ergodicité :**

:::info
++Définition :++
La chaîne de Markov est ergodique s'il existe une limite au vecteur $\pi_k$ lorsque $k \to +\infty$, et si cette limite est indépendante de l'état initial.
$$\pi_\infty = (\pi_\infty^A \quad \pi_\infty^B \quad \dots \quad \pi_\infty^E)$$
avec A, B, ..., E des états possibles
:::

*Rq :* Une chaîne de Markov est ergodique si le **graphe de transition** est **fini**, **fortement connexe** et possède au **minimum une boucle** (condition suffisante mais pas nécessaire)

++Interprétation ponctuelle :++

++Interprétation statistique :++

**Graphe de transition :**

Les sommets du graphes correspondent aux états et les arcs aux transitions.

**Matrice de transition :**

On représente le système grâce à une matrice de transition. Les lignes et les colonnes correspondent au différents états du système. On la complète avec les probabilités de chaque transition.
Ex: La case en ligne A, colonne B correspond à la proba de passer de l'état A à l'état B.

**Prévision :**

On calcule les transitions avec la formule suivante

:::danger
$$ \pi_k = (\pi_{k-1}) * M_t $$
$$ \text{ou encore} $$
$$ \pi_k = (\pi_0) * M_t^k $$
:::

### Exemple 1

:::success
Un garagiste dispose d'un parc de 4 voitures louées à la journée. Chaque véhicule loué peut tomber en panne.
Le garage ne peut ouvrir que s'il y a au minimum 2 voiture en état de marche en début de journée.
Chaque soir, le garagiste ne peut réparer qu'une seule voiture.
La demande de location est supérieure à l'offre : touts les véhicules disponible à la location sont systématiquement loués.

On considère le système au début de chaque journée. $\tau= 1$ jour.

La probabilité qu'un véhicule tombe en panne est $p$ ( et $q = 1 - p$)
:::

:::spoiler Modélisation
Les états possibles correspondent au nombres de véhicules en états de marche
- Etat A = 1 véhicule
- Etat B = 2 véhicules
- Etat C = 3 véhicules
- Etat D = 4 véhicules

*Rq :* L'état avec 0 véhicule qui marche n'est pas possible
:::

:::spoiler Matrice de transition
$$
M_t =
\begin{array}{c|cccc}
{} & {A} & {B} & {C} & {D} \\
\hline
{A} & {0} & {1} & {0} & {0} \\
{B} & {p^2} & {2pq} & {q^2} & {0} \\
{C} & {p^3} & {3p^2q} & {3pq^2} & {q^3} \\
{D} & {p^4} & {4p^3q} & {6p^2q^2} & {4pq^3 + q^4}
\end{array}
$$

++Pour remplir la 1ere ligne :++

A $t = k\tau$, le système est dans l'état A, il y a donc un véhicule en état de marche.
Le garagiste pourra réparer un véhicule le soir.

A $t = (k+1)\tau$, il y a maintenant deux véhicules qui marchent. Nous sommes dans l'état B

++Pour remplir la 2eme ligne :++

A $t = k\tau$, le système est dans l'état B, il y a donc deux véhicules qui marchent, et qui sont loués dans la journée.

A $t = (k+1)\tau$
- Si les deux véhicules sont en pannes, on est dans l'état A.
$$ \Rightarrow p^2 $$
- Si un véhicule est en panne, on est dans l'état B.
$$ \Rightarrow 2pq $$
- Si aucun véhicule n'est en panne, on est dans l'état C.
$$ \Rightarrow q^2 $$

++Pour remplir la 3eme ligne :++

A $t = k\tau$, le système est dans l'état C, il y a donc trois véhicules qui marchent, et qui sont loués dans la journée.

A $t = (k+1)\tau$
- Si les trois véhicules sont en pannes, on est dans l'état A.
$$ \Rightarrow p^3 $$
- Si deux véhicules sont en pannes, on est dans l'état B.
$$ \Rightarrow \binom{2}{3}p^2q=3p^2q $$
- Si un véhicule est en panne, on est dans l'état C.
$$ \Rightarrow \binom{1}{3}pq^2=3pq^2 $$
- Si aucun véhicule n'est en panne, on est dans l'état D.
$$ \Rightarrow q^3 $$

++Pour remplir la 4eme ligne :++

A $t = k\tau$, le système est dans l'état D, il y a donc quatres véhicules qui marchent, et qui sont loués dans la journée.

A $t = (k+1)\tau$
- Si les quatres véhicules sont en pannes, on est dans l'état A.
$$ \Rightarrow p^4 $$
- Si trois véhicules sont en pannes, on est dans l'état B.
$$ \Rightarrow \binom{4}{3}p^3q = 4p^3q $$
- Si deux véhicules sont en pannes, on est dans l'état C.
$$ \Rightarrow \binom{4}{2}p^2q^2 = 6p^2q^2 $$
- Si un véhicule est en pannes, on est dans l'état D.
$$ \Rightarrow \binom{4}{1}pq^3 = 4pq^3 $$
- Si aucun véhicule n'est en panne, on est dans l'état D.
$$ \Rightarrow q^4 $$

Pour l'état D ici on a
$$ P(D) = P(1) + P(0) = 4pq^3 + q^4 $$
:::

:::spoiler Graphe de transition
:::

:::spoiler Chaîne de Markov ergodique ?
Le graphe est de transition est fini, fortement connexe et possède au minimum une boucle, donc la chaîne de Markov est ergodique
:::

On étudie maintenant la limite pour $p=q=1/2$, avec toutes les voitures qui marchent à $t=0$

:::spoiler Calcul de pi
Si toutes les voitures marchent, nous sommes dans l'état D.
$$ \Rightarrow \pi_0 = (0\ 0\ 0\ 1) $$

On calcule ensuite $\pi_1$ et $\pi_2$
$$ \pi_1 = \pi_0 * M = (\frac{1}{16}, \frac{4}{16},\frac{6}{16}, \frac{5}{16}) \\
\pi_2 = \pi_1 * M = (\frac{33}{256}, \frac{104}{256},\frac{82}{256}, \frac{37}{256}) $$

On calcule $\pi_{\infty}$
$$ \pi_{\infty} = (a\ b\ c\ d)*M $$
$$
\pi_{\infty} = (a\ b\ c\ d) *
\begin{pmatrix}
{0} & {1} & {0} & {0} \\
{1/4} & {2/4} & {1/4} & {0} \\
{1/8} & {3/8} & {3/8} & {1/8} \\
{1/16} & {4/16} & {6/16} & {5/16} \\
\end{pmatrix}
$$
$$
\left\{
\begin{array}{ll}
a = 1/4b + 1/8c + 1/16d \\
b = a + 2/4b + 3/8c + 4/16d \\
c = 1/4b + 3/8c + 6/16d \\
d = 1/8c + 5/16d \\
1 = a + b + c + d
\end{array}
\right.
$$
$$ \pi_\infty = (\frac{61}{361}, \frac{196}{361}, \frac{88}{361}, \frac{16}{361}) $$
:::

:::spoiler Interprétation statistique
On laisse le garage fonctionner pendant 1 an, et on arrive en régime permanent.

On trouve
- Etat A = 61/361 (envrion 2 mois = pas d'argent)
- Etat B = 196/361 (environ 6,5 mois)
- Etat C = 88 / 361 (environ 3 mois)
- Etat D = 16 / 361 (environ 0,5 mois = beaucoup d'argent)

On peut ainsi calculer la recette annuelle (quelle que soit l'année considérée) => Stabilisation macroscopique
:::

:::spoiler Reprendre la modélisation si p=0
Système déterministe

$$ M =
\begin{pmatrix}
{0} & {1} & {0} & {0} \\
{0} & {0} & {1} & {0} \\
{0} & {0} & {0} & {1} \\
{0} & {0} & {0} & {1} \\
\end{pmatrix}
$$

Au bout de maximum 3 jours le système arrive dans l'état D et y reste indéfiniment.
:::

## Processus de Markov

Généralisation du modèle markovien précédent au cas où le **temps est continu**. On suppose alors que les évènement aléatoires qui provoquent les changements d'état obéissent à une **loi de Poisson**.

++Loi de Poisson++
On suppose que les occurrences des évènements sont :
- Indépendantes entre elles
- A flux stationnaire
- Ce qui se produit entre t et t+h ne dépend que de h
- Non groupés
- La probabilité d'un évènement entre t et t+h est très faisible si h est petit

++Exemple++
Les évènements sont des arrivées de clients. Par définition, ils suivent une loi de Poisson de taux $\lambda$ lorsque la probabilité d'observer n arrivées pendant un temps t est donné par :
$$ P_n(t) = \frac{(\lambda t)^n}{n!}.e^{-\lambda t} $$

Parfois l'occurence d'un évènement marque la fin d'un évènement (départ d'un client d'un guichet est l'achèvement d'un service). Dans ce cas, on s'intéresse à la variable aléatoire "durée de vie du service".

Lorsque l'occurence d'évènement de fin est régi par une loi de Poisson de taux $\lambda$, la durée de vie associé suit une **loi exponentielle** de même taux. Les deux modes de raisonnement sont dont rigouresement équivalent.

Pour la suite, la loi de Poisson ou la loi exponnetielle, de taux $\lambda$ se traduit de la manière suivante :
- La probabilité d'occurence d'un évènement, pendant le temps $dt$ est égale à $\lambda.dt$
- La probabilité d'occurence de n évènements, pendant le même temps $dt$, de la forme $(\lambda.dt)^n$, est supposé négligeable devant la probabilité d'occurence d'un seul évènement, quel que soit $n > 1$.

### Graphe de transition

:::danger
Si le système est dans l'état $E_i$ à l'instant $t$, il n'y a que deux possibilité pour l'instant $t+dt$ :
- Le système est encore dans l'état $E_i$
- Le système est passé dans l'un des autres états, mais il y **un seul** changement d'état entre $t$ et $t+dt$.
:::

#### Exemple

:::success
Dans un magasin de stockage, des composants sont stockés en trois lieux : L1, L2, L3. Deux robots identiques permettent de prélever des composants en chacun de ces lieux, selon des programmes pré-mémorisés.

La durée aléatoire nécessaire pour un prélèvement en $L_i (i=1,2,3)$ est régie par une loi exponentielle de taux $\mu_i$. LOrsque les deux robots se trouvent au même lieu, le dernier arrivé doit attendre la fin de l'opération du premier.

Pour chaque robot, chaque programme commence par un prélèvement en $L_1$. Puis le robot se dirige vers $L_2$ à $t +dt$.

:::