Questão 5: Ache os tempos toleráveis no segundo e quarto ciclos usando \boldsymbol{x}(r+1)=\boldsymbol{A} \otimes \boldsymbol{x}(r),
\boldsymbol{A}=\left(\begin{array}{cccc} 10 & 7 & 3 & 4 \\\ c_{1}+c_{2} & -\infty & 1 & 2 \\\\ 6 & c_{3}+c_{4} & 0 & 1 \\\\ 5 & b+2 & 1 & 0 \end{array}\right)
e \boldsymbol{x}(0)=\left(c_{1}+c_{2}, a_{1}+a_{2}, b, c_{3}+c_{4}\right)^{T} e supondo que as tarefas são encerradas no quinto ciclo. O que significa -\infty neste contexto?

Passo 1

O que o enunciado dá e pede (lista clara):
  • É dada a dinâmica em álgebra max-plus \boldsymbol{x}(r+1)=\boldsymbol{A}\otimes\boldsymbol{x}(r),com a matriz \boldsymbol{A}=\begin{pmatrix} 10 & 7 & 3 & 4 \\\ c_{1}+c_{2} & -\infty & 1 & 2 \\\\ 6 & c_{3}+c_{4} & 0 & 1 \\\\ 5 & b+2 & 1 & 0 \end{pmatrix}e o estado inicial \boldsymbol{x}(0)=\bigl(c_{1}+c_{2},\; a_{1}+a_{2},\; b,\; c_{3}+c_{4}\bigr)^{T}.
  • O enunciado pede: “Ache os tempos toleráveis no segundo e quarto ciclos” e diz que as tarefas são encerradas no quinto ciclo.
  • Também pergunta: “O que significa -\infty neste contexto?”
Observação importante (não resolvo ainda): vou interpretar “tempos toleráveis no r-ésimo ciclo” como os tempos de início/ativação dos eventos (os componentes de \boldsymbol{x}(r)) calculados pela dinâmica max-plus. Ou seja, vou encontrar \boldsymbol{x}(2) e \boldsymbol{x}(4). Se “tempos toleráveis” tivesse outro significado técnico (por exemplo folgas máximas), precisaríamos de mais informação; aqui vou entender como os instantes que o sistema permite/fornece em cada ciclo, conforme a recorrência dada.

Passo 2

Breve aula prática sobre álgebra max-plus (o que é preciso saber para usar a fórmula):
  • Em álgebra max-plus definimos duas operações:
    • “adição” é o máximo: para quaisquer u,v usamos u\oplus v=\max(u,v).
    • “multiplicação” é a soma usual: para quaisquer u,v usamos u\otimes v=u+v.
  • Produto matriz-vetor em max-plus: \boldsymbol{y}=\boldsymbol{A}\otimes\boldsymbol{x} significa, para cada componente i, y_i=\bigoplus_{j} (A_{ij}\otimes x_j)=\max_{j}\bigl(A_{ij}+x_j\bigr).Isso é análogo a multiplicação convencional, trocando + por max e × por +.
  • O símbolo -\infty é o elemento neutro da operação \oplus (máximo): ele representa “ausência de caminho” ou “entrada impossível”. Em prática, um termo A_{ij}=-\infty significa que o índice j não influencia i naquela equação (o termo A_{ij}+x_j=-\infty não contribui ao máximo).
  • Regra prática: para calcular \boldsymbol{x}(r) faça multiplicações sucessivas: \boldsymbol{x}(1)=\boldsymbol{A}\otimes\boldsymbol{x}(0), \boldsymbol{x}(2)=\boldsymbol{A}\otimes\boldsymbol{x}(1)=\boldsymbol{A}^2\otimes\boldsymbol{x}(0), etc., onde \boldsymbol{A}^2 em max-plus tem entradas (\boldsymbol{A}^2)_{ij}=\max_k\bigl(A_{ik}+A_{kj}\bigr).
Vou usar essa regra para obter \boldsymbol{x}(2) explicitamente; para \boldsymbol{x}(4) usarei a notação \boldsymbol{x}(4)=\boldsymbol{A}^4\otimes\boldsymbol{x}(0) e indicarei como se obtém computacionalmente.

Passo 3

Convenções de notação (para simplificar a escrita):
  • Defino c_{12}:=c_1+c_2,\qquad a_{12}:=a_1+a_2,\qquad c_{34}:=c_3+c_4.Assim \boldsymbol{x}(0)=(c_{12},\,a_{12},\,b,\,c_{34})^{T}.
  • Vou escrever somas repetidas como, por exemplo, 2c_{12} para c_{12}+c_{12}.

Passo 4

Calcular \boldsymbol{x}(1)=\boldsymbol{A}\otimes\boldsymbol{x}(0) (passo intermédio para checar entendimento):
  • Pelo produto linha-por-coluna (max-plus), cada componente é \begin{aligned} x_1(1)&=\max\bigl(10+c_{12},\;7+a_{12},\;3+b,\;4+c_{34}\bigr),\\[4pt] x_2(1)&=\max\bigl(c_{12}+c_{12},\;-\infty+a_{12},\;1+b,\;2+c_{34}\bigr) =\max\bigl(2c_{12},\;1+b,\;2+c_{34}\bigr),\\[4pt] x_3(1)&=\max\bigl(6+c_{12},\;c_{34}+a_{12},\;0+b,\;1+c_{34}\bigr),\\[4pt] x_4(1)&=\max\bigl(5+c_{12},\;b+2+a_{12},\;1+b,\;0+c_{34}\bigr). \end{aligned}
  • Observação: o termo com -\infty no segundo elemento da segunda linha desapareceu pois -\infty+a_{12}=-\infty e não afeta o máximo.]

Passo 5

Calcular \boldsymbol{A}^2 (necessário para escrever \boldsymbol{x}(2)=\boldsymbol{A}^2\otimes\boldsymbol{x}(0)). Vou calcular cada entrada (\boldsymbol{A}^2)_{ij}=\max_k(A_{ik}+A_{kj}).
Resultados (mostrando as máximos explícitos):
\begin{aligned} (\boldsymbol{A}^2)_{11}&=\max\bigl(20,\;7+c_{12},\;9,\;9\bigr)=\max\bigl(20,\;7+c_{12}\bigr),\\[4pt] (\boldsymbol{A}^2)_{12}&=\max\bigl(17,\;3+c_{34},\;b+6\bigr),\\[4pt] (\boldsymbol{A}^2)_{13}&=\max\bigl(13,\;8,\;3,\;5\bigr)=13,\\[4pt] (\boldsymbol{A}^2)_{14}&=\max\bigl(14,\;9,\;4,\;4\bigr)=14,\\[6pt] (\boldsymbol{A}^2)_{21}&=\max\bigl(10+c_{12},\;-\infty,\;7,\;7\bigr)=\max\bigl(10+c_{12},\;7\bigr),\\[4pt] (\boldsymbol{A}^2)_{22}&=\max\bigl(7+c_{12},\;1+c_{34},\;b+4\bigr),\\[4pt] (\boldsymbol{A}^2)_{23}&=\max\bigl(3+c_{12},\;-\infty,\;1,\;3\bigr)=\max\bigl(3+c_{12},\;3\bigr),\\[4pt] (\boldsymbol{A}^2)_{24}&=\max\bigl(4+c_{12},\;-\infty,\;2,\;2\bigr)=\max\bigl(4+c_{12},\;2\bigr),\\[6pt] (\boldsymbol{A}^2)_{31}&=\max\bigl(16,\;c_{34}+c_{12},\;6,\;6\bigr)=\max\bigl(16,\;c_{12}+c_{34}\bigr),\\[4pt] (\boldsymbol{A}^2)_{32}&=\max\bigl(13,\;c_{34},\;b+3\bigr),\\[4pt] (\boldsymbol{A}^2)_{33}&=\max\bigl(9,\;c_{34}+1,\;0,\;2\bigr)=\max\bigl(9,\;c_{34}+1\bigr),\\[4pt] (\boldsymbol{A}^2)_{34}&=\max\bigl(10,\;c_{34}+2,\;1,\;1\bigr)=\max\bigl(10,\;c_{34}+2\bigr),\\[6pt] (\boldsymbol{A}^2)_{41}&=\max\bigl(15,\;b+2+c_{12},\;7,\;5\bigr)=\max\bigl(15,\;b+2+c_{12}\bigr),\\[4pt] (\boldsymbol{A}^2)_{42}&=\max\bigl(12,\;1+c_{34},\;b+2\bigr),\\[4pt] (\boldsymbol{A}^2)_{43}&=\max\bigl(8,\;b+3,\;1,\;1\bigr)=\max\bigl(8,\;b+3\bigr),\\[4pt] (\boldsymbol{A}^2)_{44}&=\max\bigl(9,\;b+4,\;2,\;0\bigr)=\max\bigl(9,\;b+4\bigr). \end{aligned}]

Passo 6

Agora \boldsymbol{x}(2)=\boldsymbol{A}^2\otimes\boldsymbol{x}(0). Vou escrever cada componente como máximo das combinações obtidas (expandindo os \max internos em termos de soma com as componentes iniciais). Isso dá os “tempos toleráveis” no segundo ciclo (isto é, os instantes permitidos no ciclo 2):
\begin{aligned} x_1(2)&=\max\bigl(\;20+c_{12},\;7+2c_{12},\;17+a_{12},\;3+c_{34}+a_{12},\;b+6+a_{12},\;13+b,\;14+c_{34}\;\bigr),\\[6pt] x_2(2)&=\max\bigl(\;10+2c_{12},\;7+c_{12},\;7+c_{12}+a_{12},\;1+c_{34}+a_{12},\;b+4+a_{12},\;3+c_{12}+b,\;3+b,\;4+c_{12}+c_{34},\;2+c_{34}\;\bigr),\\[6pt] x_3(2)&=\max\bigl(\;16+c_{12},\;2c_{12}+c_{34},\;13+a_{12},\;c_{34}+a_{12},\;b+3+a_{12},\;9+b,\;c_{34}+1+b,\;10+c_{34},\;2c_{34}+2\;\bigr),\\[6pt] x_4(2)&=\max\bigl(\;15+c_{12},\;b+2+2c_{12},\;12+a_{12},\;1+c_{34}+a_{12},\;b+2+a_{12},\;8+b,\;2b+3,\;9+c_{34},\;b+4+c_{34}\;\bigr). \end{aligned}
Explicando um pouco cada termo (para não te deixar assustado): cada termo do tipo, por exemplo, 20+c_{12} corresponde a um caminho de duração (soma de pesos) que leva à componente considerada após dois saltos; os termos com somas como 7+2c_{12} vêm de escolher a alternativa máxima interna em (\boldsymbol{A}^2)_{11} e somar com x_1(0)=c_{12}, etc. No exame, basta saber montar \boldsymbol{A}^2 pelo máximo de somas A_{ik}+A_{kj} e depois somar com a componente inicial correspondente.]

Passo 7

Como obter \boldsymbol{x}(4) (quarto ciclo) na prática:
  • Por definição \boldsymbol{x}(4)=\boldsymbol{A}^4\otimes\boldsymbol{x}(0)=\boldsymbol{A}^2\otimes\boldsymbol{A}^2\otimes\boldsymbol{x}(0).
  • Procedimento prático (o que você faria passo a passo na prova):
    1. Já computamos \boldsymbol{A}^2 (Passo 5). Calcule \boldsymbol{A}^4=(\boldsymbol{A}^2)^2 em max-plus usando (\boldsymbol{A}^2)^2_{ij}=\max_k\bigl((\boldsymbol{A}^2)_{ik}+(\boldsymbol{A}^2)_{kj}\bigr).
    2. Em seguida aplique \boldsymbol{x}(4)=\boldsymbol{A}^4\otimes\boldsymbol{x}(0) ou alternativamente calcule sequencialmente \boldsymbol{x}(3)=\boldsymbol{A}\otimes\boldsymbol{x}(2) e depois \boldsymbol{x}(4)=\boldsymbol{A}\otimes\boldsymbol{x}(3).
  • Escrever explicitamente todos os termos de \boldsymbol{x}(4) em função de a_{12},b,c_{12},c_{34} é possível mas gera muitas combinações (cada entrada de \boldsymbol{A}^4 é um máximo sobre somas de quatro entradas de \boldsymbol{A}) — o procedimento algébrico é exatamente o mesmo que usei para \boldsymbol{A}^2, só com mais termos.
Para ser claro e prático: o resultado exato é
\boldsymbol{x}(4)=\boldsymbol{A}^4\otimes\boldsymbol{x}(0),
onde \boldsymbol{A}^4 é obtida por (\boldsymbol{A}^2)^2 com a fórmula (\boldsymbol{A}^2)^2_{ij}=\max_k\bigl((\boldsymbol{A}^2)_{ik}+(\boldsymbol{A}^2)_{kj}\bigr). Se quiser, eu posso expandir cada componente de \boldsymbol{x}(4) termo a termo (vai dar uma lista grande); aqui te mostrei o método e o cálculo completo de \boldsymbol{x}(2) para que repitas a mesma técnica até \boldsymbol{x}(4) sem dificuldade.

Passo 8

  • Como as tarefas são encerradas no quinto ciclo, faz sentido calcular até \boldsymbol{x}(4) (os instantes no quarto ciclo) porque a evolução até o ciclo 5 é governada por \boldsymbol{x}(5)=\boldsymbol{A}\otimes\boldsymbol{x}(4). Se o exame ou a questão pedirem folgas máximas relativas a um deadline no ciclo 5, usaríamos também uma recursão “para trás” (min-plus) com data de término conhecida; mas isso não foi solicitado explicitamente aqui.
  • Resumindo: eu te dei as fórmulas explícitas para \boldsymbol{x}(1) e \boldsymbol{x}(2) e o procedimento direto para \boldsymbol{x}(4). Se você quiser, eu agora expando totalmente \boldsymbol{x}(4) em termos de a_{12},b,c_{12},c_{34} (leva tempo e produz uma expressão grande) — digo isso porque às vezes em prova é suficiente indicar \boldsymbol{x}(4)=\boldsymbol{A}^4\otimes\boldsymbol{x}(0) e explicar como calcular \boldsymbol{A}^4.

Resposta

Segundo ciclo: \boldsymbol{x}(2)=\begin{pmatrix} \max\bigl(20+c_{12},\;7+2c_{12},\;17+a_{12},\;3+c_{34}+a_{12},\;b+6+a_{12},\;13+b,\;14+c_{34}\bigr)\\[6pt] \max\bigl(10+2c_{12},\;7+c_{12},\;7+c_{12}+a_{12},\;1+c_{34}+a_{12},\;b+4+a_{12},\\[2pt]\qquad\;3+c_{12}+b,\;3+b,\;4+c_{12}+c_{34},\;2+c_{34}\bigr)\\[6pt] \max\bigl(16+c_{12},\;2c_{12}+c_{34},\;13+a_{12},\;c_{34}+a_{12},\;b+3+a_{12},\;9+b,\;c_{34}+1+b,\;10+c_{34},\;2c_{34}+2\bigr)\\[6pt] \max\bigl(15+c_{12},\;b+2+2c_{12},\;12+a_{12},\;1+c_{34}+a_{12},\;b+2+a_{12},\;8+b,\;2b+3,\;9+c_{34},\;b+4+c_{34}\bigr) \end{pmatrix}
Quarto ciclo: \displaystyle \boldsymbol{x}(4)=\boldsymbol{A}^4\otimes\boldsymbol{x}(0) (obtenha \boldsymbol{A}^4 por \boldsymbol{A}^4=(\boldsymbol{A}^2)^2 com (\boldsymbol{A}^2)^2_{ij}=\max_k\bigl((\boldsymbol{A}^2)_{ik}+(\boldsymbol{A}^2)_{kj}\bigr); em seguida \boldsymbol{x}(4)=\boldsymbol{A}^4\otimes\boldsymbol{x}(0)).
Significado de -\infty: representa “ausência de ligação” ou “termo proibido” na álgebra max-plus; numericamente é o elemento neutro do máximo, ou seja, um valor que não contribui ao máximo (equivalente a ignorar aquela opção).]

Exercícios relacionados