Recherche Opérationnelle

Réalisé par: Prof. M’hamed Segaoui

Cycle Ingénieur : Génie Chimique et Procédés

FST Errachidia, Université Moulay Ismaïl de Meknès, Maroc
E-mail: mhamedsegaoui@[Link]

Année Universitaire: 2024–2025

Prof. M. Segaoui 2024-2025 1 / 164

 Serie 1
Exercice 1
Variable de décision :
x1 le nombre de tables à fabriquer par semaine
x2 le nombre de chaises à fabriquer par semaine
Contraintes :
• 5x1 + 2x2 ≤ 60 pour le bois
• 2x1 + 1x2 ≤ 30 pour le métal
• 3x1 + 1.5x2 ≤ 45 pour le temps de travail
• les variables sont positives x1 , x2 ≥ 0
La fonction objectif :
La fonction objectif est F (x1 , x2 ) = 2000x1 + 1200x2 à maximiser.
Programme linéaire :
Enfin le programme linéaire peut s’écrit sous la forme

maxF = 2000x1 + 1200x2

 5x1 + 2x2 ≤ 60
2x1 + 1x2 ≤ 30
S.C
 3x1 + 1.5x2 ≤ 45
x1 , x2 ≥ 0

Prof. M. Segaoui 2024-2025 40 / 164

Exercice 2
Variable de décision :
x1 Nombre d’avions de type A
x2 Nombre d’avions de type B
Contraintes :
•
•
•
• les variables sont positives x1 , x2 ≥ 0

Prof. M. Segaoui 2024-2025 41 / 164

 Figure: Résolution graphique du problème

Prof. M. Segaoui 2024-2025 42 / 164

Exercice 3 (Problème de découpe) Donner le modèle mathématique
pour que les déchets soient les plus petits possibles.
Correction Il existe cinq façons de découpe possibles pour une plaque de
200 cm de largeur :
F 1: 1 plaque de 75 cm + 2 plaques de 60 cm −→ Déchets : 5 cm
F 2: 1 plaque de 110 cm + 1 plaque de 75 cm −→ Déchets : 15 cm
F 3: 1 plaque de 110 cm + 1 plaque de 60 cm −→ Déchets : 30 cm
F 4: 3 plaques de 60 cm −→ Déchets : 20 cm
F 5: 2 plaques de 75 cm −→ Déchets : 50 cm
Chaque possibilité génère une quantité différente de déchets, qui doit être
minimisée.
Variables de décision : Les variables de décision déterminent le nombre
de plaques à couper en fonction de chaque option de découpe.
xi : nombre de plaques a découper par la façon i.

Prof. M. Segaoui 2024-2025 43 / 164

Fonction objective (minimisation) :

min Z = 5x1 + 15x2 + 30x3 + 20x4 + 50x5

1 Cette fonction optimise la réduction des déchets en fonction de

l’utilisation des différentes options de découpe.
2 Les coefficients (5, 15, 30, 20, 50) représentent les déchets (en cm)
générés par plaque pour chaque option de découpe.
Contraintes :
Les contraintes garantissent que le nombre de plaques requis est produit :
• Répondre à la demande de plaques de 110 cm
Le nombre de plaques de 110 cm des deuxième et troisième options
de coupe doit être d’au moins 30.

x2 + x3 ≥ 30

Prof. M. Segaoui 2024-2025 44 / 164

• Répondre à la demande de plaques de 75 cm
Le nombre total de plaques de 75 cm provenant des première,
deuxième et cinquième options de coupe doit être d’au moins 40.

x1 + x2 + 2x5 ≥ 40

• Répondre à la demande de plaques de 60 cm

Le nombre total de plaques de 60 cm provenant des première,
troisième et quatrième options de coupe doit être d’au moins 15.

2x1 + x3 + 3x4 ≥ 15

• Contrainte de positivité
Le nombre de plaques utilisées pour chaque option de découpe ne
peut pas être négatif.

x1 , x2 , x3 , x4 , x5 ≥ 0.

Prof. M. Segaoui 2024-2025 45 / 164

Alors le problème s’écrit :

min Z = 5x1 + 15x2 + 30x3 + 20x4 + 50x5



 x2 + x3 ≥ 30

 x + x + 2x ≥ 40
1 2 5
S. c



2x 1 + x 3 + 3x 4 ≥ 15

x1 , x2 , x3 , x4 , x5 ≥ 0.

Prof. M. Segaoui 2024-2025 46 / 164

Exercice 4
1 Formuler le problème de la recherche d’un plan de production
maximisant le chiffre d’affaires de l’entreprise sous forme d’un
programme linéaire.
2 Déterminer un plan de production optimal en résolvant
graphiquement le programme linéaire trouvé en 1.
Variables de décision : Soit
x1 : Nombre de boîtes du type 1 fabriquées.
x2 : Nombre de boîtes du type 2 fabriquées.
Fonction objectif : Maximiser le chiffre d’affaires :

max Z = 3x1 + 5x2

où 3USD et 5USD sont les prix de vente des boîtes des types 1 et 2,
respectivement.

Prof. M. Segaoui 2024-2025 47 / 164

Contraintes :
1 Réserve du carton (10 000 m2 )

x1 + 2x2 ≤ 10000

2 Temps d’assemblage (200 heures = 12000 minutes)

2x1 + 3x2 ≤ 12000

3 Stock des agrafes (équivalent à 15000 boîtes du type 1, sachant que

chaque boîte du type 2 consomme 4 fois plus d’agrafes que celle du
type 1)
x1 + 4x2 ≤ 15000
4 Positivité des variables
x1 , x2 ≥ 0

Prof. M. Segaoui 2024-2025 48 / 164

2.

Figure: Résolution graphique du problème

Prof. M. Segaoui 2024-2025 49 / 164

Exercice 5
Variables de décision
x1 Quantité en Tonnes de mélange traitées par la machine A (gelée
d’abricots).
x2 Quantité en tonnes de mélange traitées par la machine B (confiture
et gelée de fraises).
Fonction objectif:
Profit
• La machine A produit 800 kg (0,8 tonne) de gelée d’abricots par
tonne de mélange. Le prix de vente est de 4500 dh/tonne.
• La machine B produit
◦ 600 kg (0,6 tonne) de confiture de fraises par tonne de mélange, vendu
à 4000 dh/tonne.
◦ 300 kg (0,3 tonne) de gelée de fraises par tonne de mélange, vendu à
5000 DH/tonne.
• Profit total est

Pt = 4500 × 0.8 × x1 + 5000 × 0.3 × x2 + 4000 × 0.6 × x2

Prof. M. Segaoui 2024-2025 50 / 164
Cout :
• Machine A : Chaque tonne de mélange contient 0.6 tonne d’abricots
et 0.4 tonne de sucre.
1 Coût des abricots 3000 × 0.6 × x1
2 Coût du sucre 1200 × 0.4 × x1
• Machine B : Chaque tonne de mélange contient 0,8 tonne de fraises
et 0,2 tonne de sucre.
1 Coût des fraises 3500 × 0.8 × x2
2 Coût du sucre 1200 × 0.2 × x2
• Coût total

Ct = 3000×0.6×x1 +1200×0.4×x1 +3500×0.8×x2 +1200×0.2×x2

Alors la fonction objectif est

Z = Pt − Ct = 1320x1 + 860x2

Prof. M. Segaoui 2024-2025 51 / 164

Contraintes :
• La machine A peut traiter au maximum 15 tonnes par jour.

x1 ≤ 15

• La machine B peut traiter au maximum 10 tonnes par jour :

x2 ≤ 10

Contraintes liées à l’élimination des déchets

• La machine A produit 200 kg (0,2 tonne) de déchets par tonne.
• La machine B produit 100 kg (0,1 tonne) de déchets par tonne.
• La machine C peut traiter au maximum 2 tonnes par jour.
la contrainte de déchets

0.2x1 + 0.1x2 ≤ 2

Prof. M. Segaoui 2024-2025 52 / 164

La solution optimale est donnée par :

z ∗ = 15200, x1∗ = 5, et x2∗ = 10

ce qui correspond à fournir 5 tonnes de mélange à la machine A et 10
tonnes de mélange à la machine B pour un bénéfice journalier de 15200.

Prof. M. Segaoui 2024-2025 53 / 164

Exercice 6:
Question 1 :

La région réalisable et la partie en bleu du graphe.

Question 2 : Les points extrêmes sont les sommets de la région réalisable
que sont A, B, C , D et E , obtenus en résolvant les systèmes formés par
l’intersection des droites.
Prof. M. Segaoui 2024-2025 54 / 164
• le point E = (0, 0) c’est l’origine de repère orthogonal.
• le point C est l’intersection de la droite correspondant à la contrainte
2 et de l’axe des abscisses, alors
( (
x2 = 0, x2 = 0,
⇒ , donc C = (3, 0)
x1 − x2 = 3 x1 = 3

• Le point A est l’intersection des droites correspondant aux contraintes

1 et 2, alors
( (
x1 + x2 = 8, x2 = 5/2,
⇒ , donc A = (11/2, 5/2)
x1 − x2 = 3 x1 = 11/2

• Le point B est l’intersection des droites correspondant aux contraintes

1 et 3, alors
( (
x1 + x2 = 8, x2 = 24/5,
⇒ , donc B = (16/5, 24/5)
−x1 + 4x2 = 16 x1 = 16/5

Prof. M. Segaoui 2024-2025 55 / 164

 • le point D est l’intersection de la droite correspondant à la contrainte
3 et de l’axe des ordonnées, alors
( (
x1 = 0, x1 = 0,
⇒ , donc D = (0, 4)
−x1 + 4x2 = 16 x2 = 4

Question 3 :D’après le graphe, le point qui maximise la fonction Z est

B = (16/5, 24/5), alors
Z ∗ = 176/5
Question 4 : Nous allons maintenant vérifier quelles contraintes sont
satisfaites en remplaçant (x1 , x2 ) = (16/5, 24/5) dans chaque contrainte.
• Les contraintes 1 et 3 sont satisfaites et saturées (actives)
• La contrainte 1 est satisfaite mais n’est pas saturée.

Prof. M. Segaoui 2024-2025 56 / 164

Exercice 7:
Question 1 :

Question 2 : L’ensemble des points décrit par le segment [AC ] représente

les solutions optimales du problème linéaire. Alors, la solution n’est pas
unique pour ce problème.
Prof. M. Segaoui 2024-2025 57 / 164
Exercice 8:
Question 1 :

Question 2 : Les points extrêmes sont les sommets de la région réalisable :

A, B et C . Déterminer A, B et C.
Question 3 : Puisque la région est non-bornée et que augmente en se
déplaçant vers le haut, il n’y a pas de solution optimale.
Prof. M. Segaoui 2024-2025 58 / 164
 Série 2:
Exercice 1:
Soit le problème d’optimisation suivant :

max Z = 3x1 + 4x2 + 2x3

(
x1 + x2 − x3 ≤ 10
sous contraintes : x1 − 2x2 + 3x3 ≤ 14
x1 , x2 , x3 ≥ 0

1. Pour construire une solution initiale admissible, nous devons introduire des variables
d’écart pour transformer les inégalités en égalités.
Les contraintes deviennent :

x1 + x2 − x3 + x4 = 10
x1 − 2x2 + 3x3 + x5 = 14

avec x4 ≥ 0 et x5 ≥ 0 sont des variables d’écart.

On choisit une solution basique initiale en posant les variables de décision
x1 = x2 = x3 = 0. Alors, x4 = 10 et x5 = 14.
Donc, la solution initiale admissible est (x1 , x2 , x3 , x4 , x5 ) = (0, 0, 0, 10, 14)

Prof. M. Segaoui 2024-2025 59 / 164

2. Méthode du Simplexe :
Itération 1:
z x1 x2 x3 x4 x5 sol
z -1 3 4 2 0 0 0
x4 0 1 1 -1 1 0 10
x5 0 1 -2 3 0 1 14
La variable qui sort de la base est x4 et celle qui entre est x2 .
Itération 2 :
Lp ← L2 /1, L1 ← L1 − 4Lp , L3 ← L3 − (−2)Lp

z x1 x2 x3 x4 x5 sol
z -1 -1 0 6 -4 0 -40
x2 0 1 1 -1 1 0 10
x5 0 3 0 1 2 1 34
La variable qui sort de la base est x5 et celle qui entre est x3 .
Itération 3 :
Lp ← L3 /1, L1 ← L1 − 6Lp , L2 ← L2 − 1Lp

z x1 x2 x3 x4 x5 sol
z -1 -19 0 0 -16 -6 -244
x2 0 4 1 0 3 1 44
x3 0 3 0 1 2 1 34
Alors la solution optimale est Z = 244

x1 = 0, x2 = 44, x3 = 34

Prof. M. Segaoui 2024-2025 60 / 164

Méthode des dictionnaires :
max Z = 3x1 + 4x2 + 2x3
S.C
x1 + x2 − x3 + e1 = 10
x1 − 2x2 + 3x3 + e2 = 14

⋆ Etape 1
• Solution de base réalisable initiale :
x1 = 0, x2 = 0, x3 = 0, e1 = 10, e2 = 14, avec Z = 0
• Dictionnaire : On exprime les variables de base e1 et e2 en fonction des
variables hors-base x1 , x2 et x3 .
e1 = 10 − x1 − x2 + x3 ≥ 0
e2 = 14 − x1 + 2x2 − 3x3 ≥ 0
Z = 3x1 + 4x2 + 2x3
• Variable entrante xe : max{3, 4, 2} = 4 ⇒ xe = x2
• Variable sortante xs : on maintient les contraintes e1 , e2 ≥ 0
⇒ x2 = 10 ⇒ xs = e1
• Nouvelle solution de base réalisable : x1 = 0, x2 = 10, x3 = 0, e1 = 0,
e2 = 34 alors Z = 40
Prof. M. Segaoui 2024-2025 61 / 164
⋆ Etape 2
• Dictionnaire : On exprime la nouvelle variables de base x2 et e2 en
fonction des variables hors-base x1 , x3 et e1 . On utilise la 1 ère
équation du dictionnaire de l’étape 1 et on substitue x2 dans les autres
relations, ce qui donne le dictionnaire :
x2 = 10 − x1 + x3 − e1 ≥ 0
e2 = 34 − 3x1 − x3 − 2e1 ≥ 0
Z = −x1 + 6x3 − 4e1 + 40
• Variable entrante xe :

max{−1, 6, −4} = 6 ⇒ xe = x3
>0

• Variable sortante xs : on maintient les contraintes x2 , e2 ≥ 0

⇒ x3 = 34 ⇒ xs = e2

• Nouvelle solution de base réalisable : x1 = 0, x2 = 44, x3 = 34, e1 = 0,

e2 = 0 alors Z = 244

Prof. M. Segaoui 2024-2025 62 / 164

⋆ Etape 3
• Dictionnaire : On exprime la nouvelle variables de base x2 et x3 en
fonction des variables hors-base x1 , e1 et e2 . On utilise la 2ème
équation du dictionnaire de l’étape 2 et on substitue x3 dans les autres
relations
x2 = 44 − 4x1 − 3e1 − e2 ≥ 0
x3 = 34 − 3x1 − 2e1 − e2 ≥ 0
Z = −19x1 − 16e1 − 6e2 + 244
Tous les couts réduits sont ≤ 0 donc on ne peut plus augmenter Z :
l’optimum est atteint et la solution optimale est

x1⋆ = 0, x2⋆ = 44, x3⋆ = 34, e1⋆ = 0, e2⋆ = 0

avec
Z ⋆ = 244

Prof. M. Segaoui 2024-2025 63 / 164

Exercice 2:
On considère le programme linéaire (P) suivant :
max Z = 3x1 + 4x2 + 10x3

 x1 + 2x3 ≤ 6

sous contraintes : 2 x +x ≤6
3
 x ,x ,x ≥0

1 2 3

1. Pour montrer que A = (0, 0, 3) est un sommet de la région réalisable,

il faut vérifier que ce point satisfait toutes les contraintes du
problème.
• Contrainte 1 :
• Contrainte 2 :
• conditions de positivité :
Toutes les contraintes sont respectées. Donc, le point A = (0, 0, 3)
appartient bien à la région réalisable.
En plus, un sommet est un point où les contraintes sont actives
• La contrainte x1 + 2x3 ≤ 6 est active.
• Les variables x1 et x2 sont nulles, ce qui correspond aux axes.
Donc le point A est bien un sommet de la région réalisable.
Prof. M. Segaoui 2024-2025 64 / 164
2. Les contraintes deviennent :
x1 + 2x3 + x4 = 6
x2 + x3 + x5 = 6
avec x4 ≥ 0 et x5 ≥ 0 sont des variables d’écart.
En posant les variables de x1 = x2 = 0 et x3 = 3. Alors, x4 = 0 et x5 = 3.
Donc, la solution de base correspondant A est (x1 , x2 , x3 , x4 , x5 ) = (0, 0, 3, 0, 3), alors
Z = 30.
Itération 1:
z x1 x2 x3 x4 x5 sol
z -1 2 4 0 5 0 30
x4 0 1 1 -1 1 0 10
x5 0 2 4 0 5 0 30
La variable qui sort de la base est x4 et celle qui entre est x2 .

Prof. M. Segaoui 2024-2025 65 / 164

Exercice 3 :
On considère le programme linéaire (P) suivant :

max Z = x1 − 7x2 + x3

 2x1 + x2 − x3 ≤ 4
4x1 + 3x2 ≤ 2
sous contraintes :
 −3x1 + 2x2 + x3 ≤ 3
x1 , x2 , x3 ≥ 0

1. Forme Standard

max Z = x1 − 7x2 + x3 + 0x4 + 0x5 + 0x6


 2x1 + x2 − x3 + x4 = 4
4x1 + 3x2 + x5 = 2
sous contraintes :
 −3x1 + 2x2 + x3 + x6 = 3
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

• x1 , x2 , x3 sont les variables de décision.

• x4 , x5 , x6 variables d’écart.
Itération 1 :
• x1 , x2 , x3 variables hors de base.
• x4 , x5 , x6 variables de base
• (x1 , x2 , x3 , x4 , x5 , x6 ) = (0, 0, 0, 4, 2, 3) solution de base admissible.
Prof. M. Segaoui 2024-2025 66 / 164
 z x1 x2 x3 x4 x5 x6 sol
z -1 1 -7 1 0 0 0 0
x4 0 2 1 -1 1 0 0 4
x5 0 4 3 0 0 1 0 2
x6 0 -3 2 1 0 0 1 3
La variable qui sort de la base est x5 et celle qui entre est x1 .
Itération 2 :

Lp ← L3 /4, L1 ← L1 − 1Lp , L2 ← L2 − 2Lp , L4 ← L4 − (−3)Lp

z x1 x2 x3 x4 x5 x6 sol
z -1 0 -25/4 1 0 -1/4 0 -1/2
x4 0 0 5/2 -1 1 -1/2 0 3
x1 0 1 3/4 0 0 1/4 0 1/2
x6 0 0 -1/4 1 0 3/4 1 9/2
La variable qui sort de la base est x6 et celle qui entre est x3 .
Itération 3 :

Lp ← L4 /1, L1 ← L1 − 1Lp , L2 ← L2 − (−1)Lp , L3 ← L3 − 0Lp

z x1 x2 x3 x4 x5 x6 sol
z -1 0 -6 0 0 -1 -1 -5
x4 0 0 9/4 0 1 1/4 0 15/2
x1 0 1 3/4 0 0 1/4 0 1/2
x3 0 0 -1/4 1 0 3/4 1 9/2

Prof. M. Segaoui 2024-2025 67 / 164

D’après le tableau de l’itération 3 on remarque que les coefficients de la
ligne z, sont négatifs ou nuls. Donc on s’arrête. On a trouvé la solution
 T
optimale avec : x ∗ = 12 , 0, 32 , 92 , 0, 0 ,
la base associée est J ∗ = {4, 1, 3} est Z ∗ = 5.
2. la solution optimale est unique puisque les coefficient réduits ci hors
base sont strictement négatifs.
La solution optimale x ∗ n’est pas dégénérée car x1 , x3 et x4 ̸= 0.

Prof. M. Segaoui 2024-2025 68 / 164

Exercice 4 :

 2x1 + x2 ≤ 5
x1 − x2 ≤ 1
(P1 ) ⇒ 3x1 + 2x2 ≤ 8
 x1 + x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
Montrer ((P1) ⇒ 3x1 + 2x2 ≤ 8 revient à montrer que la valeur de la fonction objectif
Z (Max) = 3x1 + 2x2 est inférieur ou égale à 8 dans le programme linéaire suivant :

 3x1 + 2x2 = Z ( max )


(P1)′ 2x1 + x2 ≤5 xj ≥ 0 ∀j = 1, 2
 x1 − x2 ≤1


x1 + x2 ≤3
Pour résoudre (P1)′ nous passons à la forme standard (ajout de variables d’écart x3 , x4 , x5 ).

 3x1 + 2x2 = Z ( max )


(P1)′ 2x1 + x2 + x3 =5 xj ≥ 0 ∀j = 1, . . . , 5
 x1 − x2 + x4 =1


x1 + x2 + x5 =3
!
5
J −1


Soit J = {3, 4, 5} une base de (P1 ) , AJ = I3 et x J = A b=b= 1 .x J est une
3
solution de base réalisable de (P1)′ .J est une base réalisable de (P1)′ . c J = (0, 0, 0). Ainsi nous
pouvons appliquer l’algorithme du simplexe.
Prof. M. Segaoui 2024-2025 69 / 164
Itération 1 :
z x1 x2 x3 x4 x5 sol
z -1 3 2 0 0 0 0
x3 0 2 1 1 0 0 5
x4 0 1 -1 0 1 0 1
x5 0 1 1 0 0 1 3
Itération 2 :
z x1 x2 x3 x4 x5 sol
z -1 0 5 0 -3 0 -3
x3 0 0 3 1 -2 0 3
x1 0 1 -1 0 1 0 1
x5 0 0 2 0 1 1 2
Itération 3 :
z x1 x2 x3 x4 x5 sol
z -1 0 0 -5/3 1/3 0 -8
x2 0 0 1 1/3 -2/3 0 1
x1 0 0 0 1/3 1/3 1 2
x5 0 0 0 -2/3 1/3 1 0
Itération 4 :
z x1 x2 x3 x4 x5 sol
z -1 0 0 -1 0 0 -8
x2 0 0 1 -1 0 0 1
x1 0 1 0 1 0 0 2
x4 0 0 0 -2 1 3 0
Prof. M. Segaoui 2024-2025 70 / 164
L’algorithme du Simplex donne la solution de base optimale
x = (2, 1, 0, 0, 0) (dégénéré). La valeur de la fonction objectif est
Z (max) = 8. On a bien Z (x ) = 3x1 + 2x2 ≤ 8 pour tout x dans le
domaine délimité par le système d’inéquations

2x1 + x2

 ≤5
x −x
1 2 ≤1 xj ≥ 0∀j = 1 . . . 2

≤3

x + x
1 2

Prof. M. Segaoui 2024-2025 71 / 164

 Thank you for your
attention

Prof. M. Segaoui 2024-2025 124 / 164

Série N ◦ 1
Exercice 1 :
Soit (Xn )n∈N une chaine de Markov d’espace d’état E = {0, 1, 2, · · · , k}
avec k ∈ N. On pose

Yn = X2n , pour tout n ≥ 0

P(Yn+1 = j|Yn = in , Yn−1 = in−1 , · · · , Y0 = i0 )

= P(X2n+2 = j|X2n = in , X2n−2 = in−1 , · · · , X2 = i1 , X0 = i0 )
= P(X2n+2 = j|X2n = in ), car (Xn )n≥0 est une chaine de Markov
= P(Yn+1 = j|Yn = in ),
Donc (Yn )n∈N est une chaine de Markov d’espace d’état E .
Soient i, j ∈ E ,
2
P(Yn+1 = j|Yn = i) = P(X2n+2 = j|X2n = i) = qi,j

alors la matrice de transition de chaine de Markov (Yn )n∈N est Q 2

Prof. M. Segaoui 2024-2025 134 / 164
Exercice 2:
1. Puisque le temps du jour suivant dépend uniquement du temps du
jour actuel, et non des jours précédents. Alors on peut modéliser
cette situation par une chaine de Markov.
Nous définissons les états possible:
• ib : Beau temps
• ip : Pluie
• in : Neige
(a) Si aujourd’hui il fait beau (ib ), demain il ne peut pas faire beau. Il peut
neiger ou pleuvoir avec la même probabilité 0.5
(b) Si aujourd’hui il pleut (ip ), il y a une chance sur deux qu’il pleuve
encore demain (0.5). S’il y a un changement , il y a une chance sur
deux que ce soit beau (0.5 × 0.5 = 0.25) et une chance sur deux que ce
soit neige (0.5 × 0.5 = 0.25).
(c) Si aujourd’hui il neige (in ), même raisonnement que pour la pluie.
Alors, la matrice de transition est donnée par :
Pi,j = P(Xn+1 = i/Xn = j)
 
0 0.5 0.5
P =  0.25 0.5 0.25 
 
0.25 0.25 0.5
Prof. M. Segaoui 2024-2025 135 / 164
2. Si un jour il fait beau (ib ), nous voulons savoir quel est l’état le plus
probable deux jours plus tard.
Pour cela, nous allons calculer P(Xn+2 = i/Xn = j) = P 2 .
 
0.25 0.375 0.375
P 2 =  0.1875 0.4375 0.375 
 
0.1875 0.375 0.4375

Lorsque le premier jour il fait beau (ib ), nous lisons la première ligne
de P 2 .
Le temps le plus probable pour le surlendemain est donc soit la neige,
soit la pluie (probabilités égales : 0.375).

Prof. M. Segaoui 2024-2025 136 / 164

 3. Nous définissons les états possible :
• b : beau temps
• m : mauvais temps
Avec Ω = {b, m}.
• La probabilité qu’il fasse beau un jour donné si c’était déjà beau la
veille : P(b/b) = 0.
• La probabilité d’avoir du mauvais temps après un jour de beau temps
: P(m/b) = 1
• Si un jour il fait mauvais, la probabilité qu’il refasse beau :
P(b/m) = 12 × 12
• Si un jour il fait mauvais, la probabilité qu’il reste mauvais :
P(m/m) = 34 = 1 − 14 .
Alors la matrice de transition est :
!
0 1
P= 1 3
4 4

Prof. M. Segaoui 2024-2025 137 / 164

Exercice 3 : Classification des états de P:
 1 2

0 0
 31 3
1
0 0 
P =  21 2
 
1 1
0

 4 4 2 
0 0 0 1

Diagramme de transition d’états :

• {1, 2} : classe Récurrente
• {3} : classe transitoire
• {4} : classe Absorbante
la chaine n’est pas ergodique car n’est pas irréductible. donc on ne peut pas calculer la
probabilité stationnaire.

Prof. M. Segaoui 2024-2025 138 / 164

Classification des états de Q:
1 1
 
0 2 2 0
 1 0 0 2 
 3 3
Q=

 1 0 0 0 


0 0 1 0

Diagramme de transition d’états :

• Tous les états se communique entre eux donc la chaine est irréductible. Alors Irréductible
d’espace d’état fini, Donc la chaine est recurrent positif.

Prof. M. Segaoui 2024-2025 139 / 164

Exercice 4 :
1. Diagramme de transitions :
• État 1 : Attente
• État 2 : Impression
• État 3 : Interruption
• l’imprimante passe de l’état 1 à l’état 2 avec probabilité 0.8.
• l’imprimante reste en état 1 avec probabilité 1 − 0.8 = 0.2
(i) l’imprimante passe de l’état 2 à l’état 1 avec probabilité 0.4.
(ii) l’imprimante reste en état 2 avec probabilité 0.95.
(iii) l’imprimante passe de l’état 2 à l’état 3 avec probabilité 0.01.
(a) l’imprimante passe de l’état 3 à l’état 1 avec probabilité 0.3.
(b) l’imprimante passe de l’état 3 à l’état 2 avec probabilité 0.
(c) l’imprimante reste en état 3 avec probabilité 1 − 0.3 = 0.7.

Prof. M. Segaoui 2024-2025 140 / 164

2. Matrice de transition
 
0.2 0.8 0
P =  0.04 0.95 0.01 
 
0.3 0 0.7

3. Rappel : Pour qu’une chaine de Markov soit ergodique il faut qu’elle

soit irréductible et apériodique.
• La chaine est irréductible car tous les états se communique entre eux.
• La chaine est apériodique
Alors la chaine est ergodique.
4. les équations d’équilibre de al chaine.
Soit π = (π1 , π2 , π3 ) le vecteur ligne des probabilités d’état vérifie

πP = π

et condition de normalisation

π1 + π2 + π3 = 1

Prof. M. Segaoui 2024-2025 141 / 164

Ce qui donne le système d’équations


 0.2π1 + 0.04π2 + 0.3π3 = π1

 0.8π + 0.95π + 0π
1 2 3 = π2

 0π 1 + 0.01π2 + 0.7π3 = π3


π1 + π2 + π3 =1

5. la probabilité stationnaire
15
• Probabilité d’être en attente π1 = 263
• Probabilité d’être en impression π2 = 240
263
8
• Probabilité d’être en interruption π3 = 263

Prof. M. Segaoui 2024-2025 142 / 164

Exercice 5 :
Dans un département, deux sociétés, notée A et B, se partagent le marché
de l’entretien de photocopieurs. Les contrats d’entretien sont renouvelés
chaque année.
En 2010, la société A a possédait 40% du marché.
Depuis, chaque année, la société A perd 2% de ses contrats au profit de la
société B, alors que la société B perd 7% de ses contrats au profit de la
société A.
On considère un photocopieur pris au hasard.
Soit an la probabilité que ce photocopieur soit entretenu par la société A
en l’année 2010 + n.
Soit bn la probabilité que ce photocopieur soit entretenu par la société B
en l’année 2010 + n. 
Soit Pn = an bn l’état probabiliste en l’année 2010 + n.
 
On a donc: P0 = 0.40 0.60 .

Prof. M. Segaoui 2024-2025 143 / 164

On note Xn la société qui entretient ce photocopieur en l’année 2010 + n.
1. La suite ( Xn ) définit une chaîne de Markov. Pourqoui?
2. Donner le diagramme de transition
3. Déterminer la distribution après ces 2 transitions.
4. Déterminer la distribution du système pour l’année 2021.
5. Déterminer la distribution stationnaire du système.

Prof. M. Segaoui 2024-2025 144 / 164

Exercice 5 :
1. La suite (Xn ) est une chaine de Markov car, car à chaque étape n, les
probabilités de transition d’un état à un autre ne dépendent pas de n.
2. Diagramme de transition
• De A àB: 0.02
• De A àA: 1-0.02=0.98
• De B àA: 0.07
• De B àB: 1-0.07=0.93
Alors la matrice de transition
!
0.98 0.02
P=
0.07 0.93

Prof. M. Segaoui 2024-2025 145 / 164

3. la distribution après deux transitions.
Soit l’état initial P0 = (0.4 0.6).
la distribution après 2 transitions est

P2 = (a2 b2 ) = P0 P 2

avec !
2 0... 0...
P =
0... 0...
alors P2 = (0.46494 0.53506)
4. la distribution du système pour l’année 2021 = 2010 + 11
Alors, 2021 correspond à n = 11. Nous devons calculer

P11 = (a11 b11 ) = P0 P 11

on obtient a11 = 0.64 et b11 = 0.36.

Prof. M. Segaoui 2024-2025 146 / 164

5. la distribution stationnaire du système.
Chaine de Markov, irréductible et apériodique donc ergodique.
Alors la suite (Pn ) converge vers P̃ (Probabilités stationnaires de la
chaine), unique solution de l’équation

P̃ = P̃P

Résolvons l’équation P̃ = P̃P.

On pose P̃ = (a b) avec (Condition de normalisation)

a + b = 1.

Ce qui revient à résoudre le système :


 0.98a + 0.07b
 =a
0.02a + 0.93b = b , alors a = 0.7778, b = 0.2222

 a+b =1

Prof. M. Segaoui 2024-2025 147 / 164

Exercice 6 : Dans une région, deux fournisseurs de services Internet,
notés Fibre+ et NetExpress, se partagent le marché. Chaque année :
• Fibre+ perd 5% de ses clients au profit de NetExpress.
• NetExpress perd 10% de ses clients au profit de Fibre+.
En 2020, Fibre+ détenait 30% du marché.
On note :
• an la probabilité qu’un client choisi au hasard soit chez Fibre+ en
l’année 2020 + n
• bn la probabilité qu’il soit chez NetExpress en l’année 2020 + n,
• Pn = (an bn )t l’état probabiliste à l’année 2020 + n.
1. Représenter le graphe de transition associé à cette situation.
2. Écrire la matrice de transition M de cette chaine de Markov.
3. Déterminer le vecteur d’état initial P0 .
4. Calculer l’état probabiliste en 2022.
5. Déterminer la distribution stationnaire π = (π0 π1 ).

Prof. M. Segaoui 2024-2025 148 / 164

Correction On considérer les états:
• État F : Client chez Fibre+
• État N : Client chez NetExpress
La probabilité qu’un client soit chez un fournisseur l’année prochaine
dépend uniquement du fournisseur actuel; elle ne dépend pas des années
précédentes. On modélise la situation par une CMTD à deux états.
1. le graphe de transition

2. la matrice de transition
!
0.95 0.05
M=
0.10 0.90

Prof. M. Segaoui 2024-2025 149 / 164

3. le vecteur d’état initial (en 2020 pour n = 0) P0 .
En 2020, Fibre+ détenait 30% du marché. Alors, NetExpress 70% du
marché. Donc
P0 = (0.3 0.7)
4. État probabiliste en 2022 = 2020 + 2 correspond à n = 2. Alors
P2 = P0 M 2
donc
P2 = (0.403 0.596)t
5. Distribution stationnaire π = (π0 π1 ).
Chaine de Markov, irréductible et apériodique donc ergodique.
Alors la suite (Pn ) converge vers π (Probabilités stationnaires de la
chaine), unique solution de l’équation
π = πM
avec
π0 + π1 = 1
alors π0 = 2/3 et π1 = 1/3
Prof. M. Segaoui 2024-2025 150 / 164
Exercice 7: Un simulateur de jeux est programmé pour le niveau difficile
de la fac¸on suivante :
• La personne a 15% de chance de réussite au premier jeu, puis;
• si la personne a gagné, elle a une chance sur quatre de gagner le jeu
suivant;
• si la personne a perdu, elle a deux chances sur cinq de gagner le jeu
suivant.
Soit Xn la variable aléatoire correspondant à la réussite du joueur au
n-ieme jeu.
1. Justifier que la suite de variables aléatoires Xn est une chaine de
Markov dont on précisera l’espace des états.
2. Donner la distribution initiale π0
3. Représenter le graphe de cette chaine de Markov puis donner la
matrice de transition P de cette chaine.
4. Exprimer la distribution πn au n-ième jeu en fonction de π0 et de P.
5. En déduire la probabilité qu’un joueur gagne le troisième jeu.
6. Déterminer la distribution stationnaire π de cette chaine
Prof. M. Segaoui 2024-2025 151 / 164
Correction : On considère l’espace d’état E = {0, 1} avec
• État 0: le joueur perd le jeu;
• État 1: le joueur gagne le jeu.
Xn la variable aléatoire correspondant à la réussite du joueur au n−ieme
jeu.
1. Xn est une chaîne de Markov car la probabilité de gagner au jeu
suivant dépend uniquement du résultat du jeu précédent.
2. La distribution initiale correspond au premier jeu :
π0 = (P(X1 = 0), P(X1 = 1))
On sait que P(X1 = 1) = 0.15 alors
P(X1 = 0) = 1 − P(X1 = 1) = 0.85, donc
π0 = (0.85 0.15)
3. la matrice de transition
!
3/5 2/5
P=
3/4 1/4

Prof. M. Segaoui 2024-2025 152 / 164

4. la distribution du système est donné par l’équation

πn+1 = πn P

Alors
πn = π0 P n
5. Il suffit de calculer P(X3 = 1)
On a π2 = (P(X3 = 0) P(X3 = 1)) et π2 = π0 P 2 avec
π0 = (0.85 0.15). Alors P(X3 = 1) = 0.34
6. Chaine de Markov est irréductible et apériodique donc ergodique.
Alors la suite (πn ) converge vers π (Probabilités stationnaires de la
chaine).
On chercher π = (π0 π1 ) avec
(
πP = π,
π0 + π1 = 1

Donc
π0 = 15/23, π1 = 8/23
Prof. M. Segaoui 2024-2025 153 / 164
Série N ◦ 2

Exercice 1 : Les premiers modéles de lignes téléphoniques conduisaient à

l’étude de processus aléatoires à valeurs dans {0, 1}. On définit un
procesus Xt par :
(
+1 si la ligne est occupée à l’instant t
Xt =
0 sinon

On suppose que le temps de séjour dans l’état 1 (resp. 0) est distribué

exponentiellement de paramètre µ (resp. λ).
Soit p1 (t) = Pr (Xt = 1), on suppose connu p1 (0).
1 on suppose connu {Xt } est un processus de Markov. Quel est son
générateur infinitésimal.
2 Montrer que p1 (t) converge vers une limite π1 et que (1 − π1 , π1 ) est
la solution stationnaire du processus de Markov.

Prof. M. Segaoui 2024-2025 154 / 164

Correction 1 : Transitions possibles :
• de 0 vers 1 avec taux λ
• de 1 vers 0 avec taux µ
Xt est un processus de Markov car le temps de séjour dans les états du
processus suit une loi exponentielle donc Xt est un processus de Markov à
temps continu d’espace d’état E = {0, 1}.

1. Le générateur infinitésimal Q d’une chaine de Markov continue

contient les taux de transition et la somme des lignes égale à 0. Alors
!
−λ λ
Q=
µ −µ

Prof. M. Segaoui 2024-2025 155 / 164

2. D’après le diagramme de transition, le processus de Markov {Xt } est
irréductible et son espace d’état E = {0, 1} est fini.
Par conséquent, il admet une distribution stationnaire unique π et la
distribution du processus converge vers cette distribution lorsque
t → +∞.
On pose
π = (π0 , π1 ).
La distribution stationnaire vérifie

πQ = 02 et π0 + π1 = 1.

On obtient alors l’équation

−λπ0 + µπ1 = 0.

Donc
λπ0 = µπ1 .

Prof. M. Segaoui 2024-2025 156 / 164

En utilisant la condition π0 + π1 = 1, on obtient
µ λ
π0 = , π1 = .
λ+µ λ+µ
Par conséquent,
λ
lim P(Xt = 1) = π1 = .
t→+∞ λ+µ
Donc p1 (t) converge vers la limite π1 et la distribution stationnaire du
processus est (1 − π1 , π1 ).

Prof. M. Segaoui 2024-2025 157 / 164

Exercice 2 : On considère une population de m individus. Au temps 0 il y
a k individus infectés dans la population, les autres ne l’étant pas. Un
individu infecté guérit après un temps exponentiel de paramètre λ− .
Lorsque n individus sont infectés, le taux de contamination d’un individu
parmi les m − n restants est λ+ (n + 1).
1. Écrire les équations de balance du système.
2. Pour m = 4, λ+ = 1 et λ− = 2, calculer la probabilité stationnaire.
3. Calculer le nombre moyen d’individus infectés sous la probabilité
stationnaire.
4. Calculer la probabilité de l’événement "tout le monde est infecté" sous
la probabilité stationnaire.

Prof. M. Segaoui 2024-2025 158 / 164

Exercice 2 :
1. Soit Xt le nombre d’individus infectés dans la population à l’instant t.
(Xt )t∈R+ a pour espace d’état E = {0, 1, 2, ..., m}.
Xt est un processus de Markov car le temps de séjour de n’importe
quel état suit loi exponentielle.
À chaque état n
• Guérison : Un individu infecté guérit à un taux λ− et provoque une
transition de n à n − 1
• Contamination : Lorsqu’il y a n infectés, chaque des m − n individus
sains peut être infecté à un taux (n + 1)λ+ , et provoque une transition
de n à n + 1
Diagramme de transition :

Prof. M. Segaoui 2024-2025 159 / 164

d’après le diagramme de transition, on remarque que tous les états sont
irréductible de plus l’espace d’état est fini, donc Xt est un processus de
Markov ergodique admet une probabilité stationnaire
λ+ π0 = λ− π1
[(i + 1)λ+ + λ− ]πi = iλ+ πi−1 + λ− πi+1
λ− πm = mλ+ πm−1
m
X
πi = 1
i=0

2. Pour m = 4, λ+ = 1 et λ− = 2
π0 = 2π1 , 4π1 = π0 + 2π3
5π2 = 2π1 + 2π3 , 6π3 = 3π2 + 2π4
4
X
2π4 = 4π3 , πi = 1
i=0
alors
4 2 2 3 6
π0 = , π1 = , π 2 = , π3 = , π4 =
17 17 17 17 17
Prof. M. Segaoui 2024-2025 160 / 164
3. le nombre moyen d’individus infectés sous la probabilité stationnaire.
m
X 39
lim E (Xt ) = E (X ) = iπi =
t→+∞
i=0
17

Prof. M. Segaoui 2024-2025 161 / 164

Exercice 3 : Soient
• Xtc le nombre de camions sur le parking à l’instant t.
• Xtv le nombre de voitures sur le parking à l’instant t.
L’état du parking à l’instant t est décrit par le processus (Xtc , Xtv )t∈R
d’espace d’état

E = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (2, 0)}

• Les voitures arrivent dans le parking selon un processus de Poisson de

paramètre λ1 c-à-d que le temps que se parc 2 voitures
successivement suit une loi exponentielle de paramètre λ1 ;
• Les camions arrivent dans le parking selon un processus de Poisson de
paramètre λ2 c-à-d que le temps que se parc 2 camions
successivement suit une loi exponentielle de paramètre λ2 ;

Prof. M. Segaoui 2024-2025 162 / 164

• La durée de stationnement d’une voiture (resp. camion) suit une loi
exponentielle de paramètre µ1 (resp. µ2 ), de plus la loi est sans
mémoire. Alors, Xtc et Xtv sont des chaine de Markov à temps
continue. Par conséquent (Xtc , Xtv )t∈R est un processus de Markov à
temps continue.
2. Le diagramme de transition de cette chaine.

Prof. M. Segaoui 2024-2025 163 / 164

3. d’après le diagramme de transition (Xtc , Xtv ), tout ses états sont
irréductible, de plus son espace d’état fini donc il est ergodique et
admet probabilité stationnaire. Soit une distribution stationnaire
Π = (π(c, v ))(c,v )∈E , telle que :
(λ1 + λ2 )π(0, 0) = µ2 π(0, 0) + µ1 π(0, 1)
(µ1 + λ1 + λ2 )π(0, 1) = λ1 π(0, 0) + µ1 π(0, 2) + µ2 π(1, 1)
(µ1 + λ1 + λ2 )π(0, 2) = λ1 π(0, 1) + µ1 π(0, 3) + µ2 π(1, 2)
(µ1 + λ1 )π(0, 3) = λ1 π(0, 3) + µ1 π(0, 1)
µ1 π(0, 4) = λ2 π(0, 3)
X
π(c, v ) = 1
(c,v )
4. la valeur moyenne du nombre de camions présents sur le parking à
l’équilibre :
X
E (x ) = cπ(c, v ) = 0 × (π(0, 0) + π(0, 1) + π(0, 2) + π(0, 3) + π(0, 4
(c,v )

+ 1 × (π(1, 0) + π(1, 1) + π(1, 2)) + 2 × π(2, 0)

Prof. M. Segaoui 2024-2025 164 / 164