Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



SED Chap 3 (étudiants) .pdf



Nom original: SED Chap 3 (étudiants).pdf
Titre: (Microsoft PowerPoint - SED Chap 3 \(\351tudiants\))
Auteur: DELL

Ce document au format PDF 1.4 a été généré par PScript5.dll Version 5.2.2 / GPL Ghostscript 8.15, et a été envoyé sur fichier-pdf.fr le 10/11/2013 à 20:04, depuis l'adresse IP 197.1.x.x. La présente page de téléchargement du fichier a été vue 925 fois.
Taille du document: 1.8 Mo (46 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


26/09/2013

Chapitre 3
Les réseaux de Petri
Étude comportementale – Aspect
dynamique
Année Universitaire 2013 / 2014

1

Chapitre III

Formalisation
• L'un des intérêts de ce formalisme, c'est la possibilité de
vérifier formellement des propriétés
• Nécessite le recours à la formalisation (matrice d'incidence,
séquence de franchissement, vecteur caractéristique, équation
d'état)
• Propriétés structurelles (structure du
comportementales (évolution du réseau)

M. F. Karoui

réseau)

et/ou

2

1

26/09/2013

Chapitre III

Formalisation
Réseau de Petri: R = {P, T, Pre, Post}
• P = ensemble de places (P = {P1, P2, .., Pm} )
• T = ensemble de transitions (T= {T1, T2, .., Tn})
• Pre = PxT → N

places précédentes

Pre(p, t) = nombre de jeton nécessaire dans la place p pour le franchissement
de la transition t

• Post = PxT → N places suivantes

Post(p, t) = nombre de jeton produits dans la place p lors du franchissement
de la transition t

⇒ C = Post (Pi, Tj) – Pré (Pi, Tj)
(W+) –
(W-)
+
W : matrice d’incidence arrière
W- : Matrice d’incidence avant

matrice d'incidence

3

M. F. Karoui

Chapitre III

Formalisation

2
P0
T0

M. F. Karoui

4

2

26/09/2013

Chapitre III

Formalisation
• Exercice

T1

– P?
– T?
– Pré (Pi, Tj) ?
– Post (Pi, Tj) ?

2

7
5

T2
3

1

P1

P2

6
T3

1

4

5

M. F. Karoui

Chapitre III

Formalisation
Réseau de Petri: R = {P, T, Pre, Post}
=> Représentation matricielle

T1

2

7
5

T2
3

1

P1

P2

6
1

M. F. Karoui

T3

4

6

3

26/09/2013

Chapitre III

Formalisation
Réseau marqué: N = {R,M}
Le marquage d'un RdP R=(P, T, Pre, Post) est son état.
Formellement, un marquage est une application
M:P→N
donnant pour chaque place le nombre de jetons qu'elle contient.
Le marquage initial est généralement noté M0.
M0= {1,0}

Notation matricielle:
– Transitions en colonnes
– Places en lignes
– Marquage = vecteur colonne

7

M. F. Karoui

Chapitre III

Formalisation
• Exercice
Notation matricielle
Pré?
Post?
C?
M0?

M. F. Karoui

8

4

26/09/2013

Chapitre III

Formalisation

9

M. F. Karoui

Chapitre III

Formalisation

M. F. Karoui

10

5

26/09/2013

Chapitre III

Formalisation

C=

C=

11

M. F. Karoui

Chapitre III

Formalisation

C=

Une colonne de cette matrice correspond à la modification du
marquage apportée par le franchissement de la transition
correspondante.
Par exemple la première colonne indique que le franchissement
de de la transition T1 consiste à retirer un jeton dans la place P1
et ajouter un jeton ans P2
M. F. Karoui

12

6

26/09/2013

Chapitre III

Formalisation : Propriétés dynamique
Dynamique (sémantique) d'un RdP
– Transition T franchissable
• une transition T est franchissable ssi, pour toute place p,
M(p) > Pre(p, t)

– Franchissement d'une transition t
• Si une transition T est franchissable à partir du marquage M,
alors le nouveau marquage de toute place p est
M'(p) = M(p) - Pre(p, t) + Post(p, t)
= M(p) + C(p, t)
avec C = Post - Pre (matrice d'incidence)
13

M. F. Karoui

Chapitre III

Formalisation : Propriétés dynamique
Dynamique (sémantique) d'un RdP
– Exemple
• T1 est franchissable car
Pré (P1, t1) < M0

• Après le franchissement de T1
M = M0 - Pré(., T1) + Post(., t1)
2

= 3 =

M. F. Karoui

2
0

1
6

0
4

1
0 +
0

5
7

0
3

1
0

1
0
0

2
2
5
5
+
=
3
0
7
10

14

7

26/09/2013

Chapitre III

Formalisation : Propriétés dynamique
Dynamique (sémantique) d'un RdP
– Exemple
• calcul direct avec la matrice d'incidence
M = M0 + C(., t1)
2

= 3 +

3
7

-1
-3

1
-4

1
0 = 5
10
0

donne (heureusement) le même résultat

15

M. F. Karoui

Chapitre III

Formalisation
• Exercice
– A partir du
marquage initiale ,
calculez les
marquage suivant:
M1 après tir de T1 ,
puis M2 après tir de
T3 puis M3 après tir
de T3 puis M5 après
tir de T2 puis M6
après tir de T1
M. F. Karoui

16

8

26/09/2013

Chapitre III

Formalisation
T1

T2

T3

T3

T1 T2 T3 T4
est une séquence de
transitions
franchissables

T2

17

M. F. Karoui

Chapitre III

Formalisation :propriétés dynamiques
Dynamique (sémantique) d'un RdP : séquence de transitions
Soit un RdP R=(P, T, Pre, Post) de marquage initial M0
Soit t1 t2 ... tn des transitions de T telles que

M0 /t1→ M1 /t2→ M2 … /tn→ Mn

alors, t1 t2 ... tn est appelée séquence de transitions franchissables
(successivement)
De plus

Mn = M + C . VsT
où Vs est le vecteur caractéristique de la séquence de transitions

s = t1 t2 ... tn

tel que Vs(t) donne le nombre d'occurrences de la transition t dans s
On note :

M /s→ Mn
M. F. Karoui

18

9

26/09/2013

Chapitre III

Formalisation :propriétés dynamiques
Equation d'état

Mf = M + C . VsT

Remarque :
s = s1 . s2
Vs1 = Vs2

=>
=>

Vs = Vs1 + Vs2
M + C . Vs1T = M + C . Vs2T même si s1≠s2
19

M. F. Karoui

Chapitre III

Formalisation :propriétés dynamiques
Dynamique (sémantique) d'un RdP : séquence
de transitions
Exemple :

T = {T1, T2, T3, T4}
VT2T3T4T1T3 = (1, 1, 2, 1)
M. F. Karoui

20

10

26/09/2013

Chapitre III

Formalisation :propriétés dynamiques
Remarques importantes :
– ATTENTION ! Le vecteur caractéristique ne fait que compter le
nombre d'apparition des transitions. Il ne donne pas, comme la
séquence, l'ordre
ordre dans lequel celles-ci ont lieu.
T = {T1, T2, T3}

V = (1, 2, 1)

Le vecteur V ci-dessus est le vecteur de comptage de toutes les
séquences de franchissement suivantes :
<T1, T2, T3, T2>, <T3, T1, T2, T2>, <T3, T2, T2, T1>, <T1, T3, T2, T2>,
<T1, T2, T2, T3>, …

21

M. F. Karoui

Chapitre III

Formalisation :propriétés dynamiques
Remarques importantes :
– ATTENTION ! L'équation d'état permet de calculer le marquage atteint
après franchissement d'une séquence de transitions. Elle ne permet pas de
dire que la séquence est franchissable !!
T1
P1

T2
P2

T3
P3

T4
P4

P5

La séquence <T1, T2, T3> est franchissable,
Les séquences <T2, T1, T3>, <T3, T2, T1>, <T2, T3, T1> ne le sont pas !
Elles ont pourtant même vecteur de comptage. L'équation d'état donnera
donc le même résultat pour les quatre.
M. F. Karoui

22

11

26/09/2013

Chapitre III

Formalisation :propriétés dynamiques
Aperçu (incomplet et approximatif) des raisonnements faisables sur un RdP
– Le rôle de l'équation d'état est de matérialiser, en termes de jetons, l'évolution du RdP.
Elle représente l'outil qui va permettre de calculer le résultat du franchissement de
transitions. En tant que tel, elle est nécessaire. Il faut toutefois l'utiliser correctement, en
pas à pas
pas.

M0

Eq.
Etat

M1

Pb

Eq.
Etat

M2

Pb

Eq.
Etat

M3

Pb

L'équation d'état peut signaler un non-franchissement. Une transition est franchissable
s'il y a suffisamment de jetons dans chacune de ses places en entrée. La matrice
d'incidence fournit le nombre de jetons produits par le déclenchement de chaque
transition.

M. F. Karoui

L'équation d'état appliquée à une séquence réduite à une transition fournit le nombre de
jetons qui restent après « exécution » de cette transition.
=> Si ce nombre est négatif, alors la transition n'est pas franchissable.
(Attention : réciproque fausse)
23

Chapitre III

Formalisation :propriétés dynamiques
Aperçu… des raisonnements faisables…
– L'équation d'état peut également servir à autre chose. Il est possible de calculer
le marquage initial nécessaire pour franchir une séquence donnée et arriver à
un marquage donné. Le travail se fait, dans ce cas-là, « à l'envers ».
M0 = Mf - C . VsT

P1
P2

M0

Eq.
Etat

M1

Eq.
Etat

M2

Eq.
Etat

Mf

2
T1

Pb

Pb

Pb

P3
P4

– Exemple :
Quel marquage initial pour le marquage final
Mf= [2, 5, 1, 4, 0] et la séquence <T1, T2, T2>

M. F. Karoui

T2
2
P5

24

12

26/09/2013

Chapitre III

Formalisation :propriétés dynamiques
– Exemple :

Quel marquage initial pour le marquage final
Mf= [2, 5, 1, 4, 0] et la séquence <T1, T2, T2>
=> calcul de M2

P1
P2
2
T1

x
0
2
y
-2
5
M2 = z = 1 - 1
t
0
4
u
0
0

-1
0
0
-1
1
-1
2

3
5
=> M2= 2
5
-2

P3
P4

T2
2
P5

Impossible :Mf inaccessible par T2

25

M. F. Karoui

Chapitre III

Formalisation :propriétés dynamiques
Aperçu… des raisonnements faisables…
– Autre Exemple :

Quel marquage initial pour le marquage final
P1
Mf= [2, 5, 1, 4, 5]
la séquence <T1, T2, T2>

P2
2
T1
P3
P4

T2
2
P5

M. F. Karoui

26

13

26/09/2013

Chapitre III

Formalisation :propriétés dynamiques
=> calcul de M2

=> calcul de M1

=> calcul de M0

0
2
-2
5
M2 = 1 - 1
0
4
0
5

3
-1
5
0
0
-1
= 2
1
5
-1
3
2

0
3
-2
5
M1 = 2 - 1
0
5
0
3

4
-1
5
0
0
-1
= 3
1
6
-1
1
2

0
4
-2
5
M0 = 3 - 1
0
6
0
1

4
-1
7
0
1
-1
= 2
0
6
-1
1
2

Mf= [2, 5, 1, 4, 5]
la séquence <T1, T2, T2>
P1
P2
2
T1
P3
P4

2

T2

P5

27

M. F. Karoui

Chapitre III

Formalisation :propriétés dynamiques
Aperçu… des raisonnements faisables…
– L'équation d'état peut également déterminer le marquage initial
minimal pour franchir une séquence donnée, sans se préoccuper du
marquage final.
M 0 + C . Vs T > 0
M0

Eq.
Etat
Pb

M. F. Karoui

M1

Eq.
Etat
Pb

M2

Eq.
Etat

Mf > 0

Pb

28

14

26/09/2013

Chapitre III

Formalisation :propriétés dynamiques
Aperçu… des raisonnements faisables…
– Exemple :

Quel marquage initial minimal permettant le franchissement
de la séquence <T1, T2, T2>
P1
P2
2
T1
P3
P4

2

T2

P5

29

M. F. Karoui

Chapitre III

Formalisation :propriétés dynamiques
=> calcul des contraintes sur M1

Mf =

0
x
-2
y
z + 1
0
t
0
u

0
-1
0
0
0
-1
> 0
1
0
-1
0
2

=>

x
1
y
0
z > 1
t
1
u
0

séquence <T1, T2, T2>

P1
P2

=> calcul des contraintes sur M2
0
x
-2
y
M2 = z + 1
0
t
0
u

1
-1
0
0
0
-1
> 1
1
1
-1
0
2

2

=>

x
2
y
0
z > 2
t
2
u
0

T1
P3
P4

T2
2

=> calcul des contraintes sur M0
0
x
-2
y
M1 = z + 1
0
t
0
u
M. F. Karoui

-1
2
0
0
1
-1
> 2
0
-1
2
2
0

=>

x
2
y
2
z > 1
t
2
u
0

P5

30

15

26/09/2013

Chapitre III

Validation
• Types d'analyse formelle pour les RdP:
– Analyse par énumération
– Analyse structurelle
– Analyse par réduction

• Enumération de tous les états possibles du
système.

31

M. F. Karoui

Chapitre III

Graphe des marquages
Marquage accessible et graphe de marquage
– Marquages accessibles (ou successeurs)

• Un marquage M' est un marquage accessible (successeur de M) s'il
existe une séquence de transitions s tel que
M / s → M'

• L'ensemble des marquages accessibles depuis M est noté A(R,M)

– Graphe des marquages accessibles

• Le graphe des marquages accessibles, noté GA(R,M), est le graphe
ayant comme sommets les marquages de A(R,M) et tel qu'il existe
un arc entre deux sommets M1 et M2 si et seulement si
M1 / t → M2
où t est une transition du RdP

M. F. Karoui

32

16

26/09/2013

Chapitre III

Graphe des marquages
Algorithme de construction du graphe des
marquages : (en français)
• Stocker le premier état issu du marquage initial
• Pour tout état stocké et non traité :
– Pour toute transition sensibilisée : construire l’état
successeur et le stocker s’il est nouveau.
– Si plus de transition tirable: marquer l’état comme
traité.

• Si plus d’état à traiter : fin.
33

M. F. Karoui

Chapitre III

Validation
Exemple : Marquage accessible et graphe de marquage

M. F. Karoui

34

17

26/09/2013

Chapitre III

Graphe des marquages
Exemple

⇒ Graphe de marquage :

Idle1

Idle2

1 (Idle1
0

d1

d2
Res

Busy1

Busy2

f1

0

f1, d2, f2)

0
1

Idle1

-1

1

0

0

Busy1

1

-1

0

0

0

(Busy1)

0

0

-1

1

0

Busy2

0

0

1

-1

01

Res

-1

1

-1

1

Idle2

C=

f2

1 Res)

f2

T= (d1,

P=

1 Idle2

f1

d1

0

d2

0
0
(Busy2)

1
01

35

M. F. Karoui

Chapitre III

Graphe des marquages
• Commande de va-et-vient d'un vérin

M. F. Karoui

36

18

26/09/2013

Chapitre III

Graphe des marquages
• Commande de va-et-vient d'un vérin

37

M. F. Karoui

Chapitre III

Graphe des marquages
• Exemple pour un RdP généralisé.

M. F. Karoui

38

19

26/09/2013

Chapitre III

Graphe des marquages
• Exemple pour un graphe non cyclique.
• Rmq: s'il n'y a pas de cycle dans le graphe des marquages,
c'est qu'il y a une "fin", un blocage (deadlock)
P0

T0
P1
T1

39

M. F. Karoui

Chapitre III

Graphe des marquages
Marquage accessible et graphe de marquage
Remarque importante : le graphe des marquage peut être infini
=> dans ce cas, le RdP est non borné
Exemple :
2

M. F. Karoui

(1) —t→ (2) —t→ (3) —t→ (4) —t→ …
t

40

20

26/09/2013

Chapitre III

Graphe des marquages
• Exemple pour un graphe borné.

41

M. F. Karoui

Chapitre III

Graphe des marquages
• Exemple pour un graphe non borné

M. F. Karoui

42

21

26/09/2013

Chapitre III

Graphe des marquages
• Exemple pour un graphe non borné (2)
P1

Ta
P3

P2
Tb
P4

Te

Tc
P5

Td

43

M. F. Karoui

Chapitre III

Graphe de couverture
• Comment traiter les graphes non bornés ?
• Le problème : une augmentation infinie du nb de
jetons dans certaines places.
• Notion de marquage supérieur. Mb > Ma si :

– pour chaque place Pi : ∀i, Mb(Pi) ≥Ma(Pi)
– Il existe une place Pj tel que : ∃j / Mb(Pj) > Ma(Pj)
– Il existe une séquence de transitions allant de Ma à Mb

• Si un GM contient deux marquages dont l'un est
supérieur à l'autre, alors ce graphe est non borné.

M. F. Karoui

44

22

26/09/2013

Chapitre III

Graphe de couverture
• Algorithme de construction du graphe de
couverture(GC) :
– début : idem que GM
– À chaque nouveau marquage trouvé, on vérifie qu'il
n'est pas supérieur à l'un des marquages existant.
– si c'est le cas, on transforme ce marquage en
remplaçant le marquage des places non bornées par ∞.
– on ne cherchera pas les successeurs de ces marquages.
– etc.

• Le graphe de couverture remplace le graphe de
marquage pour les RdP non bornés.

45

M. F. Karoui

Chapitre III

Graphe de couverture

Graphe de couverture ?

M. F. Karoui

46

23

26/09/2013

Chapitre III

Graphe de couverture

47

M. F. Karoui

Chapitre III

Graphe de couverture
P1

Ta
Graphe de couverture ?
P3

P2
Tb
P4

Te

M. F. Karoui

Tc
P5

Td

48

24

26/09/2013

Chapitre III

Graphe de couverture

P1

Ta
P3

P2
Tb
P4

Tc
P5

Td

Te

49

M. F. Karoui

Chapitre III

Validation : vérification de propriétés
• Vérification formelle de la structure du réseau: vérification de
propriétés comportementales (générales) indépendantes de la
"signification" du RdP
• Principales propriétés comportementales:






Bornage des marquages : réseau borné ou sauf(borne=1)
Utilité des transitions : réseau vivant, ou quasi-vivant
Sans blocage : pas de verrou mortel (deadlock)
Possibilité de réinitialisation : réseau réinitialisable ou propre
Déterminisme

• Vérification formelle de la conformité du réseau: vérification
d'un certain nombre de propriétés spécifiques, dépendantes du
cahier des charges.
M. F. Karoui

50

25

26/09/2013

Chapitre III

Analyse par énumération
• L'analyse par énumération permet la vérification de propriétés
sur l'ensemble des états possibles du système :
– Construction du graphe (GM ou GC)
– Parcours du graphe
– Vérification pour chacun des marquages si la propriété est
vérifiée
• Rmq1: le GM permet la vérification de toutes les propriétés
comportementales des RdP.
• Rmq2: Le GC ne permet que de vérifier le bornage et la
quasi-vivacité.
51

M. F. Karoui

Chapitre III

Vérification de propriétés
Pour un marquage initial donné:
• réseau borné: toutes ses places sont bornées
• place bornée: nombre de jetons toujous inférieur à une borne k.
∀M, ∀p : M(p) ≤k
• réseau sauf (binaire) : k=1.
• Exemple : modélisation d'un stock à capacité limitée.
• Exemple réseau sauf : modélisation d'un fonctionnement de
type automatisme logique (MEF).

M. F. Karoui

52

26

26/09/2013

Chapitre III

Vérification de propriétés
• Exemple de réseaux borné et sauf

53

M. F. Karoui

Chapitre III

Vérification de propriétés



Réseau vivant: chacune de ses transitions est vivante.
Transition Ti vivante: pour tout marquage M, il existe une séquence de
franchissement (transitions) qui permettra de franchir Ti.

séquence de franchissement
permettant le tir de Ta à
partir de M3

M. F. Karoui

54

27

26/09/2013

Chapitre III

Vérification de propriétés
• Le RDP suivant est il vivant ?

55

M. F. Karoui

Chapitre III

Vérification de propriétés




Réseaux non vivant : transition T3 non vivante
Rmq: visible dans le GM : cycle infini entre M1 et M2 qui ne contient pas T3

M. F. Karoui

56

28

26/09/2013

Chapitre III

Vérification de propriétés
• Une transition Tj est quasi-vivante si il existe au moins une
séquence de franchissement contenant Tj à partir de M0
Ex : dans l'exemple précédent, T3 est quasi-vivante.
• Un blocage (deadlock) est un marquage à partir duquel plus
aucune transition n'est tirable
• Remarque :
– Vivant ⊂ Quasi vivant
– Blocage⊂ Non vivant

57

M. F. Karoui

Chapitre III

Vérification de propriétés
• Réseau réinitialisable ou propre: pour chaque marquage, il
existe une séquence de franchissement permettant de revenir
dans l'état initial

M. F. Karoui

58

29

26/09/2013

Chapitre III

Vérification de propriétés
• Exemple de réseau non réinitialisable:

59

M. F. Karoui

Chapitre III

Vérification de propriétés
• "Un système déterministe est un système dans lequel chaque
état n'a qu'un seul successeur possible".
• Application aux RdP: un RdP est déterministe s'il n'existe pas
de conflit effectif.
• Conflit structurel: le jeton d'une place est partagé entre deux
transitions. (indépendant du marquage)
• Conflit effectif: conflit structurel ET le marquage ne permet
pas le tir des deux transitions.

M. F. Karoui

60

30

26/09/2013

Chapitre III

Exercice: producteur/consommateur
Quand sa "production" est finie (production d'une seule pièce à la
fois), un producteur dépose la pièce produite dans un stock, s'il
y a de la place libre dans ce stock dont la capacité est de 3
unités. Dès qu'il a pu faire le dépôt, il commence à produire
une autre pièce. Un consommateur, dès qu'il a fini de
"consommer" (une seule pièce à la fois), prélève une pièce
dans le stock s'il n'est pas vide.
Représenter le fonctionnement de ce système par un RdP avec un
marquage initial correspondant à la figure.
Quels sont les invariants de marquage de ce système, et quelles
sont leurs significations ?

M. F. Karoui

61

Chapitre III

Correction: producteur/consommateur

M. F. Karoui

62

31

26/09/2013

Chapitre III

Exercice: Gestion de cabine
1) On considère le protocole suivant de gestion des 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 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. Modéliser
ce protocole avec Nc = 3 et Np = 5. Le nombre de clients à la baignade
(c'est-à-dire après déshabillage et avant rhabillage) est-il borné ? Le RdP
est-il borné ? Montrer qu'il y a un état de blocage. Y-a-t-il blocage pour
toutes valeurs de Nc et de Np ?
2) Définir un protocole tel qu'il n'y ait pas de blocage, et donner le RdP
correspondant.
3) Modifier le RdP du 2) pour modéliser le nombre des clients qui attendent
une cabine pour entrer à la piscine.

63

M. F. Karoui

Chapitre III

Exercice: Boules de billard
On considère deux boules de billard, A et B qui se déplacent sur une même
ligne parallèle à une des bandes. Chaque boule peut avoir trois états : en
mouvement vers la gauche, vers la droite, ou arrêtée. On demande de
modéliser le comportement de ces boules par un RdP en supposant que :
a) une boule qui heurte une bande repart dans l'autre sens à la même vitesse,
b) si les deux boules sont en mouvement (elles sont supposées avoir la même
vitesse) elles repartent chacune en sens inverse quand elles se heurtent.
c) si une boule est arrêtée et heurtée par l'autre, la première se met en
mouvement et l'autre s'arrête (on suppose qu'il n'y a pas de ralentissement et
arrêt par frottement). On commentera plusieurs états initiaux possibles.
Boule A

M. F. Karoui

Boule B

64

32

26/09/2013

Chapitre III

Analyse structurelle
• L'analyse par énumération n'est pas toujours possible
à cause de sa complexité, même après réductions.
• L'analyse structurelle est indépendante du marquage
initial et dépend directement de la structure du RdP:
pas de construction du GM.
• Algèbre linéaire

65

M. F. Karoui

Chapitre III

Composantes répétitives
• Equation fondamentale : Mf = M + C . VsT
• S’il existe C . VsT=0 alors Mf = M
(L'ensemble des transitions franchissables de Vs
ramène au vecteur initial).
• Définition : on appelle composante stationnaire
(=invariant de transitions) l'ensemble des transitions de
S telles que : C . VsT=0
• Propriété: S’il existe toujours une transition de cet
ensemble tirable alors le RDP est vivant.
M. F. Karoui

66

33

26/09/2013

Chapitre III

Composantes répétitives
2 invariants de transitions:
• 1er invariant :
• CommandeX
• Xfabriqué
• Xvendu
• 2ème invariant :
• CommandeY
• Yfabriqué
• Yvendu

• Toutes
les
transitions
appartiennent à un invariant.
⇒ Le réseau est vivant !
67

M. F. Karoui

Chapitre III

Composantes non stationnaires
• Equation fondamentale : Mf = M + C . VsT
• S’il existe C . VsT>0 alors Mf > M
⇒Réseau non borné
• Définition : on appelle composante non
stationnaire l'ensemble des transitions de S
telles que : C . VsT>0

M. F. Karoui

68

34

26/09/2013

Chapitre III

Composantes non stationnaires
S={T0,T1}
Vs=[1 1]
C. VsT>0
S est une
composante non
stationnaire
• Le RDP est non
borné





69

M. F. Karoui

Chapitre III

Composantes conservatives
• Définition : Vp= Vecteur colonne de pondération des places
• K=VpT.Mi représente une combinaison linéaire des places
• Equation d’état : VpT.Mf = VpT.M + VpT.C . VsT
• S’il existe Vp tel que: VpT.C =0 alors : VpT.Mf = VpT.M
⇒ L'ensemble des places contient toujours le même nb de jetons.
• Définition : on appelle composantes conservatives ( invariants de
places) les solutions en Vp de l'équation :
VpT.C =0
M. F. Karoui

70

35

26/09/2013

Chapitre III

Composantes conservatives
1 invariant de places:






Attente
FabricationX
FabricationY
XAVendre
YAVendre

Toutes les places sont couvertes
par des p-invariants.
⇒Le réseau est borné
71

M. F. Karoui

Chapitre III

Composantes conservatives
Exemples d'interprétations:
• Si une composante conservative est telle que K0 = 0 :
– aucune de ces places n’est marquée dans M0.
– elles restent vides quelque soit le marquage.
⇒C'est anormal

• Si une composante conservative est telle que K0 = 1 :

– il y a toujours une de ces places marquées d’un jeton, et pas plus
d'un jeton.
⇒L'interprétation de ces places doit donc être booléenne

• Si un RdP est tel que toutes ses places appartiennent à des
invariants de place de constantes = 1, il est sauf !
⇒L'interprétation du réseau doit donc être complètement
booléenne
M. F. Karoui

72

36

26/09/2013

Chapitre III

Composantes conservatives
Exemple
P1

P=

P3

d1

d2

P5

P2

P1

-1

1

0

0

P2

1

-1

0

0

0

0

-1

1

P4

0

0

1

-1

P5

-1

1

-1

1

P3

C=

T= (d1,

f1, d2, f2)

P4

f1

f2

⇒Composantes conservatrices positives ?
73

M. F. Karoui

Chapitre III

Composantes conservatives
VpT.C =>

VpT.C =0

M2 – M1 – M5 = 0
M1 – M2 + M5 = 0

VpT = (M1, M2, M3, M4, M5)

M4 – M3 – M5 = 0
M3 – M4 + M5 =0

C=

-1

1

0

0

1

-1

0

0

0

0

-1

1

(1 , 1 , 0 , 0 , 0 )

VpT = (M1, M2, M3, M4, M5)

0

0

1

-1

(0 , 1 , 0 , 0 , 1 )

-1

1

-1

1

(0 , 0 , 1 , 1 , 0 )
(0 , 0 , 0 , 1 , 1 )
(0 , 1 , 0 , 1 , 1 )

M. F. Karoui

74

37

26/09/2013

Chapitre III

Composantes conservatives
P1

P3

d1
P5

P2

P4

f1

1

0

0

1

-1

0

0

0

0

-1

1

0

0

1

-1

-1

1

-1

1

1

M0=

f2

1
1

V1=

C=

d2

-1

(P1
+ P2)

V2=

0

0

0

0

1

1

0

1

0

0

V3=

(P3
+ P4)

1

1
0
1

(P2

0
1

0

+ P4
+ P5)

•V1’.M0=1 et V1’.C= 0 =>V1’.Mi=1 => Mi(P1)+Mi(P2)=1
•V2’.M0=1 et V2’.C= 0 =>V2’.Mi=1 => Mi(P3)+Mi(P4)=1
•V3’.M0=1 et V3’.C= 0 =>V3’.Mi=1 => Mi(P2)+Mi(P4)+Mi(P5)=1

Il est toujours
possible de
trouver
d’autres
invariant s en
additionnant
les invariants
minimaux
75

M. F. Karoui

Chapitre III

Composantes conservatives
P3
c2
P1
c1

P4
f2

P6

P2

P5

f1
P7

t2

• Invariants de marquage minimaux?
M. F. Karoui

76

38

26/09/2013

Chapitre III

Composantes conservatives
P3
P1
c1
P2

m1 + m2 = 1

P4

P’’ = {P3, P4, P5} ⇒

m3 + m4 + m5 = 1

f2

P ’’’ = {P6, P7}

m6 + m7 = 1



P5
P7




P’ = {P1, P2 } ⇒

P6

f1



c2

t2

Les ensembles P’, P’’, P ’’’, sont des composantes conservatives. A partir de cet
ensemble de relations, nous pouvons construite l’invariant suivant: m1 + m2 + m3+
m 4 + m 5+ m 6 + m 7 = 3
Dans cet invariant nous pouvons trouver toutes les places du RdP
RDP conservatif
77

M. F. Karoui

Chapitre III

Analyse Globale
•RDP A non bloqué
•RDP B non bloqué
•RDP A et RDP B bloqués

• L'analyse des "sous-RdP" pris séparément est correcte.
• Mais leur interaction est bloquantes !!
• ⇒Nécessité d'une analyse globale

M. F. Karoui

78

39

26/09/2013

Chapitre III

Transformation des RDP
• Graphe des marquages : vérification de propriétés de façon
exhaustive.
• Problème = complexité du GM pour les systèmes complexes.
• Solution : réduction du RdP grâce à des transformations
conservant les propriétés comportementales.
• Inconvénient : pas de conservation de la signification physique
du RdP=> difficile de remonter à la cause de l'erreur lorsqu'il y
en a.
⇒C'est l'Analyse par réduction
79

M. F. Karoui

Chapitre III

Transformation de Boussin: R1
• Suppression d'une transition isolée.

M. F. Karoui

80

40

26/09/2013

Chapitre III

Transformation de Boussin: R2
• Suppression d'une place isolée.

81

M. F. Karoui

Chapitre III

Transformation de Boussin: R3
• Suppression d'une transition isolée bouclée.

M. F. Karoui

82

41

26/09/2013

Chapitre III

Transformation de Boussin: R4
• Suppression d'une place isolée bouclée.

83

M. F. Karoui

Chapitre III

Transformation de Boussin: R5
• Fusion de plusieurs transitions isolées

M. F. Karoui

84

42

26/09/2013

Chapitre III

Transformation de Boussin: R6
• Fusion de plusieurs places isolées

85

M. F. Karoui

Chapitre III

Transformations simples
Notion de résidu :
• RESIDU = RdP sur lequel on ne peut plus appliquer de
transformation.
• Il n’est pas unique. Il dépend de l’ordre des transformations.

M. F. Karoui

86

43

26/09/2013

Chapitre III

Transformations simples

87

M. F. Karoui

Chapitre III

Exercice
Après Réduction

M. F. Karoui

88

44

26/09/2013

Chapitre III

Exercice
Après Réduction

89

M. F. Karoui

Chapitre III

Exercice
Après Réduction

M. F. Karoui

90

45

26/09/2013

Chapitre III

Exercice
Après Réduction

91

M. F. Karoui

Chapitre III

Exercice
Après Réduction

M. F. Karoui

92

46


Documents similaires


Fichier PDF sed chap 3 etudiants
Fichier PDF chapitre 3 graphes ponderes et probabilistes
Fichier PDF vousappliquezdesrevetementsdemarquageroutier
Fichier PDF description de systemes automatises sequentiels par grafcet
Fichier PDF 3 le grafcet
Fichier PDF sfc diffusion sac de lestage


Sur le même sujet..