CORRIGES DES EXERCICES DU POLYCOPIE DE TD

Génie Electrique

EXERCICE I :

1 2 3 4

5 6 7 8 9 10

question 1 :
- les réseaux 1, 2, 3, 4 et 5 sont des réseaux de Petri.
- les réseaux 6, 9 et 10 ne sont pas des réseaux de Petri car il manque un noeud (transition) alors qu'il y a un arc
orienté.
- les réseaux 7 et 8 ne sont pas des réseaux de Petri car il n'y a aucune transition ou aucune place.

question 2 :
- toutes les transitions des réseaux de 1 à 5 sont validées. Le réseau 4 possède une transition source.
- évolution des réseaux après franchissement de la transition

1 2 3

4 5
- les réseaux 4 et 5 sont encore validés. Le réseau 5 est composé d'une transition puits.

1
EXERCICE II
P1

2 2
T4 T1 T5
3
P2

2
P3 P4

T2 T3

question 1 : transitions validées ?

- les transitions validées sont T1 et T5.

question 2 : marquage atteint après franchissement

- franchissement de T1 : (2, 0, 0, 1) ® (0, 3, 0, 2)
- franchissement de T5 : (2, 0, 0, 1) ® (4, 0, 0, 0)

Remarque :
Si on cherche l'arbre des marquages, on rencontre un arbre avec une explosion d'états (plus de 1000 noeuds).
Le marquage maximum atteint par les places est (w, w, w, w). Le réseau de Petri est donc non borné, il est sans
blocage mais n'est pas réinitialisable.

2
EXERCICE III :
On considère le RdP donné par la figure suivante et son marquage initial M0=[1,1,2,1].
P1

1 1
t1 P2 t2 P3 t3
1
2 1 1

1 P4 t4

1) Quel est le marquage de ce réseau après franchissement de la séquence s=<t1,t2,t3,t4> ?

p1 p2 p3 p4
marquage initial 1 1 2 1
franchissement de t1 -1 2
franchissement de t2 -1 1 1
franchissement de t3 1 -1
franchissement de t4 1 -2
Bilan 1 3 2 0

M0=(1, 1, 2, 1) ® (1, 3, 2, 0)
Il faut remarquer que les sommes partielles conduisent toujours à des marquages à composantes positives, sinon
il y aurait blocage.

2) On pose sn = soso....os. Partant de M0, est-il possible de franchir sn pour tout n? Si oui, quel est en fonction
de n le marquage auquel on aboutit? Si non, quelle est la valeur maximale pour laquelle le franchissement est
posssible ?

p1 p2 p3 p4
marquage initial 1 1 2 1
franchissement de t1 -1 2
marquage après franchissement 0 3 2 1
franchissement de t2 -1 1 1
marquage après franchissement 0 2 3 2
franchissement de t3 1 -1
marquage après franchissement 1 2 2 2
franchissement de t4 1 -2
marquage après franchissement 1 3 2 0
franchissement de t1 -1 2
marquage après franchissement 0 5 2 0
franchissement de t2 -1 1 1
marquage après franchissement 0 4 3 1
franchissement de t3 1 -1
marquage après franchissement 1 4 2 1
franchissement de t4 1 -2
marquage après franchissement 1 5 2 -1

s1 = s représente la seule possibilité. Le second franchissement de s est bloqué après le franchissement de t3 ;

p4 ne contient qu'un jeton, ce qui est insuffisant pour franchir t4.

3
EXERCICE IV: REPRESENTATION MATRICIELLE DES RdP
Soit C le réseau défini par P ={P1,P2,P3,P4} et T={T1,T2,T3,T4}.
°T1 = {P1} T1° = {2P2, P3}
°T2 = {2P2} T2° = {P4}
°T3 = {P3} T3° = {P4}
°T4 = {P4} T4° = {P1}
1) Donner la représentation de la matrice d’incidence avant, la matrice d’incidence arrière et la matrice
d’incidence.
La matrice d'incidence avant (matrice d'entrée) est la matrice W- = [w-ij] avec w-ij= Pré(Pi,Tj).
La matrice d'incidence arrière (matrice de sortie) est la matrice W+ = [w+ij] avec w+ij= Post(Pi,Tj).
La matrice d'incidence W est donnée par : W = W+ - W- = [wij].

t1 t2 t3 t4 t1 t2 t3 t4
1 0 0 0 p1 0 0 0 1 p1
W-= 0 2 0 0 p2 W+= 2 0 0 0 p2
0 0 1 0 p3 1 0 0 0 p3
0 0 0 1 p4 0 1 1 0 p4

t1 t2 t3 t4
-1 0 0 1 p1
W= 2 -2 0 0 p2
1 0 -1 0 p3
0 1 1 -1 p4

2) Donner la représentation graphique de l’arbre.

P1

t1
P2 P3
2

2
t2 t3
P4

t4

3) Soit le marquage initial M0=[1 0 0 0], donner l’évolution des marquages.

Mkt = Mit + W . St
Une transition Tj est validée pour un marquage M si et seulement si : " Pi Î P, M(Pi) ³ Pré(Pi,Tj).

t1 validée ? oui car (1000) ³ (1000)= Pré(Pi,T1), on trouve donc pour le marquage suivant avec l'équation d'état
:

1 -1 0 0 1 1
0 2 -2 0 0 0
t
Mk = 0 + 1 0 -1 0 * 0
0 0 1 1 -1 0
soit M1 = (0 2 1 0)

On regarde ensuite les transitions qui sont validées.

t1 validée ? non car (0210) < (1000)
t2 validée ? oui car (0210) ³ (0200), on obtient le marquage M2 = (0011)
t3 validée ? oui car (0210) ³ (0010), on obtient le marquage M3 = (0201)
t4 validée ? non car (0210) < (0001)
L'arbre comporte 158 noeuds.

4
EXERCICE V : REPRESENTATION MATRICIELLE DES RdP
On considère le RdP suivant :
P1 P2 P3

T1 T2

P4 P5

T3 T4

1) Donner les différentes matrices.

t1 t2 t3 t4 t1 t2 t3 t4
1 0 0 0 p1 0 0 1 0 p1
W-= 1 1 0 0 p2 W+= 1 1 0 0 p2
0 1 0 0 p3 0 0 0 1 p3
0 0 1 0 p4 1 0 0 0 p4
0 0 0 1 p5 0 1 0 0 p5

t1 t2 t3 t4
-1 0 1 0 p1
W= 0 0 0 0 p2
0 -1 0 1 p3
1 0 -1 0 p4
0 1 0 -1 p5

2) Donner l’évolution des marquages avec M0=[1 1 1 0 0].

A partir du marquage M0, deux transitions sont franchissables : t1 (11100) ³ (11000) et t2 (11100) ³ (01100).
0
t3 1 t4
1
1 1
0 0
1 t1 t2
1
1 0
0 t4 t3 1
0 1
1
1
0 t1
t2 0
1

3) Donner les propriétés de ce réseau.

C'est un réseau 1_borné donc sauf, réinitialisable et vivant.

5
EXERCICE VI : ANALYSE
P1
1 T1 0 T2 1
0 1 0 marquage initial
0 0 0

T1 T4 *borné.
*sans blocage.
*non vivant, t3 et t4 non validées
P2 P3 *conservatif.

T3
T2

P1
2 T1 1 T2 2
2 0 1 0 marquage initial *borné.
0 0 0 *sans blocage.
*vivant
T1 T4 *réinitialisable.
0 T2 1
2 1 marquage identique
P2 P3 T1 0 0
T3
T2 0 T4 2
0 0 marquage initial
T3 1 0

P1

T1 T4 *non borné.
*vivant.

P2 P3
T3
T2

2 T1 1 T1 0 T2 1
0 1 2 1 marquage identique
0 0 0 0

T2 2
0 marquage initial
0

T3 0 T4 w T1 w T1 w
0 0 w w marquage identique
1 0 0 0

T2
w
w marquage identique
0

T3 w T1 w
w w marquage identique
w w

T2
w
w marquage identique
w

T3
w marquage identique
w
w

T4
w marquage identique
w
w

6
 P2 T2 T3
1 0 0
0 1 0 blocage
0 1 1

T1 T1
1 1
w w marquage identique
T1 T3
0 0

P1
T2 T3
0 0 marquage identique
w w
T2 P3
7) 1 1

*réseau non borné.

*réseau non conservatif
*blocage après franchissement de la séquence S=t1t2 à partir du marquage initial.

w indique que le nombre de marques tend vers l'infini.

P2 1 T1 0 T2 1
0 1 0
0 1 0
marquage identique
T3
1 T1 0 T2 1
P1 0 1 0
w w w
T3
T1 T2
P3
1
0
w
T3
T1
*pas de blocage
1 T1 0 T3 1 0 *non borné marquage identique
0 1 0 1 *vivant
0 1 w T2 w
T2
T3

P1 P2
T1
nombre de marquages de l'arbre = 18
P1 (marquage maximum (w w w )
T1 non borné
aucun blocage T4 T2
t1, t2, t3 quasi vivantes
P2 P3 non réinitialisable

T2 T3 T3
P4 P3

1 T1 0 T2 1 T1 0 T2 1 1 T1 0 T2 0 T3 0 T4 1
0 1 0 1 0 0 1 0 0 0
0 1 w w w 0 0 1 0 0
0 0 0 1 0

w T1 w T1 w
1 w w borné, sauf (1_borné)
w w w aucun blocage
T3
réinitialisable
vivant
conservatif (nombre de jetons constant)
T2 w
w
w

T3 w
w
w

7
EXERCICE VII : ANALYSE DE RESEAU DE PETRI (Partiel 1993-1994)
P1

T4 T1

P4 P2

T5 T2 T7

P3
P5

T6 T3

P6

1) Calculer l’arbre des marquages.

1 t1 0 t2 0 t3 1
0 1 0 0
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0

t4 t5 t6 t7
0 1 1 1
0 0 0 0
0 0 0 0
1 0 0 0
0 1 0 0
0 0 1 0

2) Donner les propriétés.

C'est un réseau 1_borné donc sauf, réinitialisable et vivant.

3) Etablir les matrices d’incidence avant, d’incidence arrière et la matrice d’incidence.

t1 t2 t3 t4 t5 t6 t7 t1 t2 t3 t4 t5 t6 t7
1 0 0 1 0 0 0 p1 0 0 1 0 0 0 1 p1
W-= 0 1 0 0 0 0 0 p2 W+= 1 0 0 0 0 0 0 p2
0 0 1 0 0 0 0 p3 0 1 0 0 0 0 0 p3
0 0 0 0 1 0 0 p4 0 0 0 1 0 0 0 p4
0 0 0 0 0 1 0 p5 0 0 0 0 1 0 0 p5
0 0 0 0 0 0 1 p6 0 0 0 0 0 1 0 p6

t1 t2 t3 t4 t5 t6 t7
-1 0 1 -1 0 0 1 p1
W= 1 -1 0 0 0 0 0 p2
0 1 -1 0 0 0 0 p3
0 0 0 1 -1 0 0 p4
0 0 0 0 1 -1 0 p5
0 0 0 0 0 1 -1 p6

8
EXERCICE VIII : ANALYSE
Ce réseau représente une machine soumise à pannes. Le franchissement de t1 représente l'arrivée d'un produit
dans la machine.
p1

p2 p3
t1 t2
t3

t4 t5
p4

1) Expliquer le fonctionnement du système ainsi modélisé.

Le franchissement de t1 qui n'est possible que si p1 contient un jeton, représente l'arrivée d'un produit dans la
machine. Si la machine est en panne, le jeton qui se trouve dans p2 est utilisé pour franchir t5, puis t4, puis à
nouveau t5, et ainsi de suite tant que la machine est en panne. Si la machine est en état de fonctionner, le jeton
qui se trouve dans p2 est utilisé pour franchir t2. Ce franchissement représente l'opération exécutée sur la
machine. Le franchissement de t3 représente le départ de la pièce de la machine, ce qui se traduit par le retour
d'un jeton dans p1. La présence de ce jeton dans p1 indique que la machine est libre, et qu'une nouvelle pièce
peut être lancée en production.

2) Donner la matrice d'incidence.

t1 t2 t3 t4 t5 t1 t2 t3 t4 t5
1 0 0 0 0 p1 0 0 1 0 0 p1
W-= 0 1 0 0 1 p2 W+= 1 0 0 1 0 p2
0 0 1 0 0 p3 0 1 0 0 0 p3
0 0 0 1 0 p4 0 0 0 0 1 p4

t1 t2 t3 t4 t5
-1 0 1 0 0 p1
W= 1 -1 0 1 -1 p2
0 1 -1 0 0 p3
0 0 0 -1 1 p4

3) Construire l'arbre des marquages.

t1 t2 t3
1 0 0 1
0 1 0 0
0 0 1 0
0 0 0 0

t4
0 0
0 1
0 0
t5 1 0

4) Trouver les p-invariants.

Un vecteur de dimension n (n est le nombre de places du RdP considéré) et dont les composante sont entières et
non négatives est un p_invariant si : Z.W=0
ici Z=[z1, z2, z3, z4] ce qui donne comme systèmes d'équations :
-z1 + z2 = 0
-z2 + z3 = 0
z1 - z3 = 0
z2 - z4 = 0
-z2 + z4 = 0
La seule solution est Z=[1, 1, 1, 1] (ainsi que tous les multiples entiers). Z.Mt=Z.Mt0 quelque soit les marquages
M rencontrés dans l'arbre. Ce résultat indique qu'il y a toujours exactement un jeton dans le réseau ou en terme
de système de production, soit qu'il y a une pièce en attente ou en cours de fabrication, soit que la machine est
libre.

9
EXERCICE IX :
Prenons comme convention que, dans un RdP, une transition représente une opération et une place iun
lieu de stockage dans un système de fabrication. Dire ce que représentent les différents RdP de la figure suivante.
Donnez en particulier la signification des jetons et les types d'opérations représentées.
p1

2
p3 p1 t p2
1
p2

Réseau de Petri 1 Réseau de Petri 2

t1 p2
p1 p2 p1 t 1

1 p3
t2 2

Réseau de Petri 3 Réseau de Petri 4

Le RdP 1 correspond à une opération d'assemblage. Les jetons situés dans la place p1 représentent des
composants de type C1, et les jetons situés dans la place p2 représentent des composants de type C2. La
transition t représente l'opération d'assemblage. Les jetons situés dans p3 figurent les produits assemblés. Il faut
deux composants de type C1 et un composant de type C2 pour obtenir une unité de produit fini.

Le RdP 2 modélise une opération de transformation. Les jetons situés dans p1 figurent les produits avant
transformation, alors que p2 contient les jetons qui représentent les produits après transformation.

Le RdP 3 modélise deux opérations qui se déroulent en parallèle. Les jetons qui se trouvent dans la place p1
figurent les produits en attente. Ils vont ensuite soit subir l'opération représentée par t1, soit subir l'opération par
t2. Ces deux opérations sont, par exemple, deux opérations identiques effectuées sur deux machines différentes.
Les jetons qui se trouvent dans p2 représentent les produits finis.

Le RdP 4 représente une opération de désassemblage (démontage, découpe, etc..).

10
EXERCICE X : MODELISATION
Soit un système producteur consommateur. Quand la production est terminée (production d’une seule
pièce à la fois), le producteur dépose la pièce réalisée dans un stock, s’il y a de la place libre (capacité du stock :
3 pièces). Dès qu’il a pu déposer sa pièce, le producteur recommence une nouvelle pièce. Le consommateur
prélève une seule pièce à la fois à l’intérieur du stock, à condition que ce stock ne soit pas vide.
1) Représenter le fonctionnement de ce système par un RdP avec un marquage initial correspondant à la figure
suivante.

producteur stock (capacité 3) consommateur

Le producteur : *il produit

*il est prêt à déposer la pièce

Le consommateur : *il consomme

*il est prêt à consommer

Le stock : *il y a des places libres

*il y a des pièces en stock

PRET ADEPOSER
LAPIECE PLACES LIBRES CONSOMMATION
p1 p3 p5

DEPOT FIN DE
FIN DE t1 t2 t3 t4
RETRAIT CONSOMMATION
PRODUCTION

p2 p4 p6

PRODUCTION PIECES EN STOCK PRET ACONSOMMER

2) Quels sont les invariants de ce système ?

3 invariants : m1 + m2 = 1 : 2 états possibles (état prêt, état production)
m5 + m6 = 1 : 2 états possibles pour le consommateur
m3 + m4 = 3 : capacité du stock

11
EXERCICE XI : MODELISATION
Deux calculateurs utilisent une mémoire commune. On suppose que chaque calculateur peut avoir trois
états : soit il n’a pas besoin de la mémoire, soit il la demande mais ne l’utilise pas encore, soit il l’utilise.
Modéliser le fonctionnement de ce système par une RdP.

MEMOIRE
LIBRE
P1 P7 P4

CALCULATEUR 1 CALCULATEUR 2
DEMANDE DEMANDE
T1 T4

T3 CAL.1 P5 CAL.2 T6
P2
UTILISE UTILISE

T2 T5

CALCULATEUR 1 CALCULATEUR 2
N'A PAS BESOIN N'A PAS BESOIN
P3 P6

m1+m2+m3=1 invariant relatif au calculateur 1

m4+m5+m6=1 invariant relatif au calculateur 2
m7+m2+m5=1 invariant relatif à la mémoire (3 états : libre, mémoire occupée par cal.1, mémoire occupée par
cal.2)
La somme des 3 invariants : m1+2m2+m3+m4+2m5+m6+m7=3
Le RdP est donc conservatif

12
EXERCICE XII : MODELISATION
Une banque fait entrer des clients puis ferme la porte d’entrée avant de commencer à servir. Au fur et à
mesure qu’ils sont servis, les clients sortent par une autre porte. La porte d’entrée ne sera rouverte que lorsque
tous les clients qui étaient entrés seront sortis.
1) Décrire le fonctionnement par un RdP à arcs inhibiteurs.
On ajoute une contrainte supplémentaire : la banque ne fait entrer qu’un seul client à la fois.
2) Décrire le fonctionnement par un RdP à arcs inhibiteurs.
3) Décrire le fonctionnement par un RdP ordinaire.

CORRECTION

• porte d'entrée ouverte P1 Tant que P2 est occupée

• porte d'entrée fermée P3 T4 ne peut être tirée P1
• nombre de clients en attente ou en cours de
service P2
T1
T1 correspond à l'arrivée d'un client :
* ajoute une marque dans P2
* P1 ne change pas P'2 P2 T4 T3

Quand la banque sert Þ T3 est tirée Þ la porte est

fermée (P3) T2

P3

Pour entrer un client à la fois, il faut ajouter une place P'2, complémentaire de P2.
La place P'2 est marquée quand et seulement quand P1
P2 est vide, donc on peut supprimer l'arc inhibiteur
et lui substituer la lecture de P'2
T1

P'2 P2 T3
T4

T2

P3

13
EXERCICE XIII :
On considère le protocole suivant de gestion de cabines et des paniers d’une piscine. A l’entrée, un
client qui a trouvé une cabine libre y entre et se change en posant ses vêtements dans la cabine. Il demande
ensuite un panier qu’il remplit pour libérer la cabine. Après la baignade, le client rentre dans une cabine avec son
panier, le vide et le libère. Ensuite, il se rhabille et libère la cabine. Soit Nc le nombre de cabines et Np le
nombre de paniers.
1) Modéliser le protocole précédent avec Nc=3 et Np=5.
2) Le nombre de clients à la baignade, c’est à dire après déshabillage et avant rhabillage, est-il borné?
3) Le réseau de Petri est-il borné?
4) Monter qu’il y a un état de blocage. Ce blocage existe-t-il quelques soient les valeurs de Nc et de Np?
5) Définir un protocole tel qu’il n’y ait pas de blocage et donner le modèle RdP correspondant.
6) Modifier le RdP précédent pour modéliser le nombre de clients qui attendent une cabine pour entrer à
la piscine.

CORRECTION
6) arrivée
T0
d'un client
P0 clients en attente
1) Modélisation : Np = 5
Nc = 3
entrée d'un client T1 entrée T1
d'un client
P1 déshabillage P1 déshabillage

T2 T2

remplissage remplissage
P2 panier P2 panier

T3 T3
à la à la
P6 P3 P7 P6 P3 baignade P7
baignade
paniers cabines paniers cabines
libres T4 libres libres T4 libres

P4 vidage panier P4 vidage panier

T5 T5

P5 rhabillage P5 rhabillage

sortie d'un client T6 sortie d'un client T6

2) Le nombre de clients à la baignade correspond au nombre de marques dans la place P3.

Il y a un invariant correspondant au nombre de paniers vides soit 5. Þ m7+m2+m3+m4=5 Þ m3 £ 5 le nombre
de clients est borné.

3) Il y a un invariant correspondant au nombre de cabines soit 3. m6+m1+m2+m4+m5=3

Chaque place appartient à un invariant au moins donc le RdP est borné.

4)Blocage ?
Si on effectue la séquence de franchissement (T1T2T3)5(T1)3, on aboutit au marquage (3,0,5,0,0,0,0) qui est un
blocage. 3 personnes en phase de déshabillage, 5 personnes à la baignade et plus de cabines ni de paniers libres.

5) Le client a besoin de 2 ressources : une cabine et un panier. Quand le client arrive, il doit prendre les deux.

6) T0, transition source qui ajoute un jeton dans la plce P0, place des clients en attente.

14
EXERCICE XIV :
Soit un système ayant 2 tâches à exécuter et se partagent la même unité centrale. Une exécution à tour
de rôle consiste à exécuter une partie (par exemple, une instruction) de la tâche 1 puis une partie de la tâche 2,
puis ensuite une autre partie de la tâche 1 puis une autre partie de la tâche 2 et ainsi de suite.
1) Modéliser par un RdP l’exécution à tour de rôle de 4 tâches avec exécution d’une instruction de chaque
tâche à chaque fois.
2) Modéliser par un RdP généralisé l’exécution à tour de rôle de 2 tâches avec les paramètres suivants : 3
instructions de la tâche 1 puis 5 instructions de la tâche 2.

CORRECTION

1) une tache a plusieurs A4

états, elle est :
• autorisée à l'éxécution P1 P4
• en attente
• en cours d'éxécution
T8 EX4 T7
T1 T6
Marquage initial : seule la
tâche 1 est autorisée à EX1 EX3
l'éxécution ; les autres tâches
2, 3, 4 et ainsi que la tâche 1 A1 T3 T4 T5
A3
T2 EX2
sont en attente Þ T1 est
franchissable.
P2 P3
Quand T1 est franchie, la
Pi : tâche i autorisée
place EX1 est marquée. A la Ai : tâche i en attente
fin de l'éxécution de A2
EXi : tâche i en cours d'exécution
l'instruction, T2 est franchie
Þ Tâche 1 en attente et tâche 2 autorisée. T3 étant validée, on la franchit Þ tâche 2 en exécution et ainsi de
suite.

2) L'introduction des RdP généralisés permet P1 P'2

d'introduire les poids des arcs. 3 5

Le marquage initial est tel que l'on peut T1 T6 T5

éxécuter 3 instruction de la tâche 1.
EX1 EX2
Il faut réaliser 3 fois successivement la
T3
séquence T1T2 avavt d'avoir une autre A1 T2 T4
A2
transition validée. 3 5

P'1 P2

(T1T2)3 Þ P1 vide, P'1 contient 3 marques Þ T3 validée

T3 franchie Þ 5 marques dans P2
Þ il faut 5 marques dans P'2 pour valider T6

invariants relatifs aux tâches 1 et 2 : M(A1)+M(EX1) = 1

M(A2)+M(EX2) = 1

15
16