Chapitre 8 sur 10. Prouver la conservation des ressources et comprendre les limites de l’équation de marquage.
1. Construire la matrice d’incidence
La matrice C = Post − Pre décrit le bilan net de chaque transition. Pour le réseau agent, les lignes suivent Attente, Libre, En cours, Terminé ; les colonnes suivent Commencer, Terminer.
| Place | Commencer | Terminer |
|---|---|---|
| Attente | −1 | 0 |
| Libre | −1 | +1 |
| En cours | +1 | −1 |
| Terminé | 0 | +1 |
Après une séquence, son vecteur de comptage σ indique combien de fois chaque transition a été franchie. On obtient M = M₀ + Cσ. Ce vecteur compte les occurrences mais ne mémorise pas leur ordre.
2. Conserver l’agent et les demandes
Un P-invariant est un vecteur y tel que yᵀC = 0. La somme pondérée yᵀM reste alors égale à yᵀM₀ pour chaque marquage accessible. Dans notre réseau, y = (0,1,1,0) donne Libre + En cours = 1.
Un second vecteur (1,0,1,1) donne Attente + En cours + Terminé = 1. Le premier suit l’agent ; le second suit la demande. Le jeton En cours participe aux deux relations, car une demande en traitement mobilise un agent.
Les deux relations et la non-négativité bornent ici toutes les places par 1. Une relation portant seulement sur certaines places ne bornerait pas les places qu’elle ignore. Un invariant ne suffit pas non plus à démontrer l’absence de blocage.
3. Ne pas confondre bilan et séquence réalisable
L’équation M = M₀ + Cσ est nécessaire pour une séquence réalisable ; en général elle n’en prouve pas l’existence. Une transition ayant une boucle de poids 1 sur une place vide possède C = 0. L’équation accepte σ = 1 et M = M₀ = 0, mais aucun premier franchissement n’est possible.
De même, les invariants permettent d’écarter un état qui viole une conservation. Un état qui respecte toutes les conservations n’est pas automatiquement accessible. Il reste à vérifier les préconditions et l’ordre des événements.
4. Reconnaître un T-invariant
Un vecteur entier non négatif x tel que Cx = 0 décrit un bilan cyclique : si une séquence avec ces occurrences est réalisable, elle ramène au même marquage. Dans le cycle Repos/Actif, x = (1,1) signifie un Démarrer et un Revenir.
Ce vecteur existe aussi si le marquage initial du cycle est (0,0), mais aucune transition ne peut alors partir. Il faut donc distinguer un calcul structurel et une séquence exécutable. Dans les exemples fournis, le script vérifie à la fois les égalités matricielles et les sommes sur tous les marquages énumérés.
Trois exercices corrigés
Exercice 1 : Calculer avec C
Depuis (1,1,0,0), appliquer le vecteur de comptage σ = (1,1).
Voir la correction de l’exercice 1
Cσ = (−1,0,0,+1). En ajoutant M₀, on obtient (0,1,0,1). La séquence Commencer, Terminer réalise effectivement ce bilan ; l’ordre inverse ne serait pas possible depuis M₀.
Exercice 2 : Écarter un état
Le marquage (0,1,1,0) est-il accessible dans le réseau agent initial ?
Voir la correction de l’exercice 2
Non : Libre + En cours = 2 alors que l’invariant doit valoir 1. Cette contradiction suffit à prouver la non-accessibilité, sans parcourir tous les chemins.
Exercice 3 : Trouver une conservation pondérée
Dans le réseau Grouper, pourquoi Demandes + 2 × Lots reste-t-il constant ?
Voir la correction de l’exercice 3
Chaque franchissement retire 2 à Demandes et ajoute 1 à Lots. La variation pondérée est −2 + 2 × 1 = 0. Avec trois demandes initiales, les états (3,0) et (1,1) donnent tous deux la somme 3.
Références pour approfondir
Javier Esparza : notes universitaires sur les réseaux de Pétri, Jörg Desel : référence sur les méthodes algébriques. Cours, cas et figures rédigés pour PandaCodeur ; aucune figure universitaire reproduite. Les exemples NKILItech sont fictifs.