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}) é
A=\begin{pmatrix} -1 & 0\\[4pt] 1 & -2\\[4pt] 1 & -1\\[4pt] 0 & 1 \end{pmatrix}.]

Passo 4

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):
  • Para p_{1}:
0 = 3 + (-1)z_{1} + 0\cdot z_{2} \quad\Rightarrow\quad 3 - z_{1} = 0.
  • Para p_{2}:
0 = 1 + 1\cdot z_{1} + (-2)z_{2} \quad\Rightarrow\quad 1 + z_{1} - 2 z_{2} = 0.
  • Para p_{3}:
1 = 0 + 1\cdot z_{1} + (-1)z_{2} \quad\Rightarrow\quad z_{1} - z_{2} = 1.
  • Para p_{4}:
2 = 0 + 0\cdot z_{1} + 1\cdot z_{2} \quad\Rightarrow\quad z_{2} = 2.

Passo 6

Resolve o sistema passo a passo:
  • Da última equação obtemos imediatamente \;z_{2}=2.
  • Da primeira equação obtemos \;z_{1}=3.
  • Verifico as equações do meio com esses valores:
    • Para p_{2}: 1 + z_{1} - 2 z_{2} = 1 + 3 - 2\cdot 2 = 1 + 3 -4 =0 (ok).
    • Para p_{3}: z_{1} - z_{2} = 3 - 2 = 1 (ok).
  • 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).]

Exercícios relacionados