Questão 1) Uma rede de Petri na qual não há malhas fechadas (circuitos direcionados) é chamada de acíclica. Para esta classe de redes de Petri, uma condição necessária e suficiente para que o estado \mathbf{x} seja alcançável a partir do estado inicial \mathbf{x}_{0} é que exista uma solução inteira não negativa \mathbf{z} para a equação:
\mathbf{x}=\mathbf{x}_{0}+\mathbf{z A},
em que A é a matriz de incidência.
Use este resultado para mostrar que \mathbf{x}=[0,0,1,2] é um estado alcançável desde o estado \mathbf{x} \mathbf{0}=[3,1, 0,0] para a rede de Petri descrita a seguir: P=\left\{p_{1}, p_{2}, p_{3}, p_{4}\right\} T=\left\{t_{1}, t_{2}\right\} A=\left\{\left(p_{1}, t_{1}\right),\left(p_{2}, t_{2}\right),\left(p_{3}, t_{2}\right),\left(t_{1}, p_{2}\right),\left(t_{1}, p_{3}\right),\left(t_{2}, p_{4}\right)\right\},
em que todos os pesos dos arcos de A são 1 , exceto para w\left(p_{2}, t_{2}\right)=2.
Nota: Lembrar que A é o conjunto de arcos da rede.
Qual é a interpretação do vetor z?
Passo 1
O que o enunciado pede e os dados fornecidos:
Pede para mostrar que o estado \mathbf{x}=[0,0,1,2] é alcançável a partir do estado inicial \mathbf{x}_{0}=[3,1,0,0] usando a condição de existência de uma solução inteira não negativa \mathbf{z} da equação
\mathbf{x}=\mathbf{x}_{0}+\mathbf{zA},
em que A é a matriz de incidência.
Dados da rede (ordeno os lugares como p_{1},p_{2},p_{3},p_{4} e as transições como t_{1},t_{2}):
Arcos (com pesos): (p_{1},t_{1}) com peso 1; (p_{2},t_{2}) com peso 2; (p_{3},t_{2}) com peso 1; (t_{1},p_{2}) com peso 1; (t_{1},p_{3}) com peso 1; (t_{2},p_{4}) com peso 1.
Pergunta adicional: qual é a interpretação do vetor \mathbf{z}.
Passo 2
Definição/princípio usado (explicado de forma didática): matriz de incidência.
A matriz de incidência que vamos usar tem uma linha para cada lugar e uma coluna para cada transição. O elemento da linha do lugar p_{i} e da coluna da transição t_{j} mede a variação de tokens em p_{i} quando t_{j} dispara:
A_{i,j} = w(t_{j},p_{i}) - w(p_{i},t_{j}),
onde w(\cdot,\cdot) é o peso do arco (se o arco não existe, o peso é 0).
Interpretação dessa fórmula: se a transição tem um arco de consumo de p_{i} para ela (isto é, p_{i}\to t_{j}), esse termo entra com sinal negativo (consome tokens); se a transição produz em p_{i} (isto é, t_{j}\to p_{i}), entra com sinal positivo (produz tokens).
Passo 3
Construção da matriz de incidência A a partir dos arcos (faço linha por linha para os lugares p_{1},p_{2},p_{3},p_{4} e colunas para t_{1},t_{2}):
Para t_{1}:
w(t_{1},p_{1})=0 e w(p_{1},t_{1})=1\Rightarrow entrada em p_{1},t_{1} é 0-1=-1.
w(t_{1},p_{2})=1 e w(p_{2},t_{1})=0\Rightarrow entrada em p_{2},t_{1} é 1-0=1.
w(t_{1},p_{3})=1 e w(p_{3},t_{1})=0\Rightarrow entrada em p_{3},t_{1} é 1-0=1.
w(t_{1},p_{4})=0 e w(p_{4},t_{1})=0\Rightarrow entrada em p_{4},t_{1} é 0.
Para t_{2}:
w(t_{2},p_{1})=0 e w(p_{1},t_{2})=0\Rightarrow entrada em p_{1},t_{2} é 0.
w(t_{2},p_{2})=0 e w(p_{2},t_{2})=2\Rightarrow entrada em p_{2},t_{2} é 0-2=-2.
w(t_{2},p_{3})=0 e w(p_{3},t_{2})=1\Rightarrow entrada em p_{3},t_{2} é 0-1=-1.
w(t_{2},p_{4})=1 e w(p_{4},t_{2})=0\Rightarrow entrada em p_{4},t_{2} é 1.
Portanto a matriz de incidência (linhas = p_{1},p_{2},p_{3},p_{4}; colunas = t_{1},t_{2}) é
Escrevo a equação a resolver explicando dimensões:
Vou tomar \mathbf{z}=\begin{pmatrix}z_{1}\\[2pt] z_{2}\end{pmatrix} como vetor coluna onde z_{1} é o número de disparos de t_{1} e z_{2} é o número de disparos de t_{2}.
A equação a satisfazer é então
\mathbf{x}=\mathbf{x}_{0}+A\mathbf{z},
com \mathbf{x}_{0}=\begin{pmatrix}3\\[2pt]1\\[2pt]0\\[2pt]0\end{pmatrix} e \mathbf{x}=\begin{pmatrix}0\\[2pt]0\\[2pt]1\\[2pt]2\end{pmatrix}.]
Passo 5
Escrevo o sistema de equações componente a componente (cada linha corresponde a um lugar):
Logo \mathbf{z}=\begin{pmatrix}3\\[2pt]2\end{pmatrix} é uma solução inteira e não negativa.]
Passo 7
Concluo e dou uma interpretação concreta (aqui mostro também uma sequência de disparos real que produz \mathbf{x}):
Como a rede é acíclica, a existência desta solução inteira não negativa é condição suficiente para garantirmos que \mathbf{x} é alcançável a partir de \mathbf{x}_{0}. Portanto \mathbf{x} é alcançável.
Interpretação prática de \mathbf{z}: z_{1}=3 significa que t_{1} dispara 3 vezes; z_{2}=2 significa que t_{2} dispara 2 vezes. Isso não dá a ordem obrigatória dos disparos, apenas quantas vezes cada transição dispara. Um exemplo de ordem válida aqui é disparar t_{1} três vezes (isso é possível porque p_{1} começa com 3 tokens), ficando após isso com marcação (0,4,3,0), e então disparar t_{2} duas vezes (cada disparo consome 2 tokens de p_{2} e 1 de p_{3}, produzindo em p_{4}), o que leva à marcação final (0,0,1,2).
Resposta
\mathbf{x}=[0,0,1,2] é alcançável a partir de \mathbf{x}_{0}=[3,1,0,0] com \mathbf{z}=\begin{pmatrix}3\\[2pt]2\end{pmatrix}.
Interpretação: \mathbf{z} indica que t_{1} dispara 3 vezes e t_{2} dispara 2 vezes (ou seja, os elementos de \mathbf{z} são os números de disparos de cada transição).]