A. T. Baraviera e Flávia M. Branco
Introdução à Álgebra Max-Plus
III Colóquio de Matemática da Região
Sul
Florianópolis, SC
2014
A. T. Baraviera e Flávia M. Branco
Introdução à Álgebra Max-Plus
III Colóquio de Matemática da Região Sul
Minicurso apresentado no III
Colóquio de Matemática da Região Sul, realizado na Universidade Federal de Santa Catarina,
em maio de 2014.
Florianópolis, SC
2014
". . . e a vida o que é?
diga lá meu irmão
ela é a batida
de um coração . . . "
(Luiz Gonzaga Júnior)
Ao Pedro
Resumo
Nesse texto introduzimos a álgebra max-plus, motivando brevemente a teoria e apresentando seus aspectos mais elementares;
os conceitos de autovetor e autovalor são apresentados nesse contexto bem como a ideia de polinômios, seus gráficos e interseções.
Fazemos também um breve desenvolvimento de formas quadráticas e conjuntos convexos no sentido max-plus.
Palavras-chaves: max-plus. autovalor. autovetor. polinômio.
Lista de ilustrações
Figura 1 – Gráfico de p(x) = 2 ⊕ (3 ⊗ x) . . . . . . . . .
37
Figura 2 – Gráfico de q(x) = −2 ⊕ (1 ⊗ x) ⊕ (−1 ⊗ x ⊗ x ⊗ x) 38
Figura 3 – Gráfico de r(x) = (−1 ⊗ x) ⊕ (x ⊗ x) . . . . .
39
Figura 4 – Região max-plus (x ⊗ x) ⊕ (y ⊗ y) = 1 . . . .
48
Figura 5 – Região max-plus x ⊕ y ⊕ 1 = 0 . . . . . . . .
51
Sumário
Introdução . . . . . . . . . . . . . . . . . . .
11
1
Motivação . . . . . . . . . . . . . . . . . . .
13
1.1
Tempo de Tarefas Combinadas . . . . . . . . .
13
1.2
Ganho com Tarefas Repetidas . . . . . . . . .
14
1.3
Crescimento Exponencial de Funções Reais . .
15
2
Conceitos Básicos . . . . . . . . . . . . . . .
19
2.1
Semianel . . . . . . . . . . . . . . . . . . . . .
19
2.2
Álgebra Max-Plus . . . . . . . . . . . . . . . .
20
3
Álgebra Linear Max-Plus . . . . . . . . . . .
23
3.1
Vetores . . . . . . . . . . . . . . . . . . . . . .
23
3.2
Funções Lineares . . . . . . . . . . . . . . . .
24
3.3
Matrizes . . . . . . . . . . . . . . . . . . . . .
25
4
Autovalores e Autovetores Max-Plus . . . .
31
5
Polinômios Max-Plus . . . . . . . . . . . . .
37
5.1
Raízes . . . . . . . . . . . . . . . . . . . . . .
40
5.2
Interseção de Polinômios . . . . . . . . . . . .
41
5.3
Polinômios Min-Plus . . . . . . . . . . . . . .
44
6
Formas Quadráticas Max-Plus . . . . . . . .
47
6.1
Definindo Regiões . . . . . . . . . . . . . . . .
47
6.2
Forma Quadrática . . . . . . . . . . . . . . . .
48
n
6.3
Forma Quadrática em R̄ . . . . . . . . . . . .
49
6.4
Outra Forma de Definir Regiões . . . . . . . .
50
7
Conjuntos Convexos . . . . . . . . . . . . . .
55
7.1
Convexidade em R2 . . . . . . . . . . . . . . .
55
7.2
Convexidade Max-Plus . . . . . . . . . . . . .
56
Referências . . . . . . . . . . . . . . . . . . .
61
11
Introdução
Estas notas têm o objetivo de servir de apoio ao minicurso Introdução à Álgebra Max-Plus ministrado no III Colóquio
de Matemática da Região Sul realizado na Universidade Federal
de Santa Catarina - UFSC, em Florianópolis. Não sendo especialistas no assunto (no qual chegamos por um caminho indireto)
desejamos apenas fazer um texto de caráter bastante elementar,
que sirva de motivação e de primeiro passo para que os leitores procurem depois bibliografia mais especializada e possam se
aprofundar nesse rico assunto se sua curiosidade for despertada
por essas poucas linhas. Um texto básico interessante é [3]; para
algumas aplicações o leitor pode consultar, por exemplo, [1] e [4].
Por fim, uma outra sugestão é visitar a página maxplus.org que
apresenta uma série de referências sobre o assunto, em diversos
níveis de complexidade.
Agradecemos aos organizadores do evento, em especial
a Artur Lopes, pela oportunidade de apresentar esse mini-curso.
Todo texto está longe de ser perfeito e esse não é uma
exceção; o leitor que quiser nos comunicar erros, fazer comentários ou apenas discutir um pouco dos assuntos aqui apresentados
pode entrar em contato por meio de nossos endereços eletrônicos
[email protected]
A. T. Baraviera
[email protected].
Flávia M. Branco
13
1 Motivação
A álgebra max-plus é basicamente a álgebra dos números reais (com uma extensão, que será feita no momento certo)
munidos de duas operações binárias, a saber a ⊕ b = max(a, b)
e a ⊗ b = a + b; existem algumas motivações distintas para a
introdução desse objeto matemático, algumas vindo da área de
pesquisa operacional, como veremos a seguir.
1.1 Tempo de Tarefas Combinadas
Vamos imaginar, por exemplo, que em uma fábrica um
determinado trabalhador i precisa esperar a conclusão das tarefas de dois de seus colegas, j e k, de forma a poder realizar
sua parte do trabalho. Imagine que j leva um tempo Tij para
concluir e entregar sua tarefa a i e k leva um tempo Tik para
também concluir e entregar sua tarefa a i. Já i, para realizar sua
própria tarefa, gasta um tempo ai . Qual é o tempo total envolvido no trabalho? Como i precisa esperar pelo trabalho de j e k
para só então executar sua tarefa temos que o tempo total nesse
caso será ai + max {Tij , Tik }. Na notação introduzida acima isso
pode ser reescrito como ai ⊗ (Tij ⊕ Tik ). Se agora consideramos
um conjunto maior de trabalhadores, é possível utilizar o mesmo
formalismo para determinar o tempo total de execução de um
trabalho e isso permite, entre outras coisas, estudar melhor o
processo de forma a torná-lo, por exemplo, mais eficiente como
um todo.
14
Capítulo 1. Motivação
1.2 Ganho com Tarefas Repetidas
Imaginemos que numa dada situação certas tarefas sejam executadas em sequência e o ganho depende da ordem em
que isso é feito. A informação do ganho pode então ser traduzida
numa matriz A onde cada entrada Aij significa exatamente o ganho quando uma certa tarefa inicial i é seguida de outra tarefa
j, ambas escolhidas em uma lista com d opções.
Nesse caso, sabendo que devemos começar com uma tarefa i, executar alguma tarefa k e terminar com a execução de
j, qual é o ganho total? Claramente é dado por
Aik + Akj = Aik ⊗ Akj
E de que forma podemos escolher a tarefa intermediária
k de forma a maximizar o ganho? Nesse caso queremos
M
max {Aik + Akj } = max {Aik ⊗ Akj } =
Aik ⊗ Akj
k
k
k
Como o leitor verá no capítulo sobre a álgebra linear max-plus,
isso corresponde exatamente a entrada ij do produto matricial
AA (no sentido max-plus).
Naturalmente podemos fazer a mesma pergunta com q
tarefas intermediárias k1 , k2 , . . . , kq :
max
k1 ,k2 ,...,kq
{Aik1 + Ak1 k2 + · · · + Akq j } =
=
=
max
M
k1 ,k2 ,...,kq
k1 ,k2 ,...,kq
{Aik1 ⊗ Ak1 k2 ⊗ · · · ⊗ Akq j }
Aik1 ⊗ Ak1 k2 ⊗ · · · ⊗ Akq j
1.3. Crescimento Exponencial de Funções Reais
15
E esse termo corresponde exatamente a entrada ij de Aq+1 .
Desta forma, o formalismo de álgebra linear max-plus
corresponde ao problema de se maximizar o ganho num processo
como o descrito acima.
1.3 Crescimento Exponencial de Funções Reais
De um ponto de vista puramente matemático, podemos
ver essa álgebra como, por exemplo, a estrutura básica que descreve o crescimento exponencial de funções reais. Mais precisamente: dada uma função h : R → R, tal que h(x) > 0, definimos
o crescimento exponencial de h como sendo o limite (claro, na
situação em que o referido limite existe)
e(h) = lim
x→+∞
1
log h(x).
x
Para fixar ideias, considere o caso simples
f (x) = eax
e
g(x) = ebx .
Da definição é imediato que e(f ) = a e e(g) = b. Convidamos o
leitor a obter e(x2 eax ). Já para uma função como h(x) = x não é
difícil ver que e(x) = 0 e de fato isso seria verdade também para
qualquer potência de x, o que é uma tradução precisa do fato
que muitas vezes é lembrado na afirmação (nada incomum num
curso de cálculo) de que uma potência cresce mais lentamente
em função de x do que uma função exponencial.
Exemplo 1.1. Qual é o crescimento exponencial da função real
f (x) = exsen x ? Nesse caso
1
1
log f (x) = xsen x = sen x
x
x
16
Capítulo 1. Motivação
Bem, a função sen x não tem um limite quando x → +∞ (pois
fica sempre oscilando entre −1 e +1). Portanto nesse caso não
faz sentido falar em e(f ).
Então podemos agora, supondo f e g funções para as
quais e(f ) e e(g) estão bem definidos, indagar qual é o crescimento exponencial de f g ou f + g? Voltando aos nossos exemplos, note que (f g)(x) = eax ebx = e(a+b)x e assim temos que a
função f g cresce exponencialmente com uma taxa a + b, ou seja,
e(f )+e(g). Portanto e(f g) = e(f )+e(g) = e(f )⊗e(g). Para f +g,
temos que (f + g)(x) = eax + ebx = emax {a,b}x (1 + ekx ), onde k =
min {a, b} − max {a, b} < 0. Logo, e(f + g) = max {e(f ), e(g)} =
e(f ) ⊕ e(g).
De fato isso não é válido apenas nesses exemplos, mas
sim em geral:
Lema 1.1. Dadas duas funções reais f e g tais que e(f ) e e(g)
estão bem definidos, então
e(f.g) = e(f ) + e(g) = e(f ) ⊗ e(g)
e
e(f + g) = max {e(f ), e(g)} = e(f ) ⊕ e(g)
Demonstração. Para a primeira igualdade, note que
e(f.g) = e (f (x)g(x)) = lim
x→∞
1
log f (x)g(x)
x
1
1
log f (x) + log g(x)
x
x
1
1
= lim log f (x) + lim log g(x)
x→∞ x
x→∞ x
= e(f ) + e(g) = e(f ) ⊗ e(g)
= lim
x→∞
1.3. Crescimento Exponencial de Funções Reais
17
Para a segunda igualdade, vamos esboçar as principais
ideias da prova. Como e(f ) e e(g) estão bem definidos, podemos
pensar que, para valores suficientemente grandes de x, f (x) =
Cf ee(f )x e g(x) = Cg ee(g)x onde Cf e Cg são tais que
lim
x→∞
1
log (Cf (x)) = 0
x
e
lim
x→∞
1
log (Cg (x)) = 0
x
Vamos assumir, sem perda de generalidade que e(f ) ≥ e(g).
Então:
1
log (f (x) + g(x))
x
1
= lim log (Cf ee(f )x + Cg ee(g)x )
x→∞ x
1
e(f )x
(e(g)−e(f ))x
= lim log Cf e
1 + (Cg /Cf )e
x→∞ x
1
= lim log ee(f )x = e(f ) = max {e(f ), e(g)}
x→∞ x
= e(f ) ⊕ e(g)
e(f + g) = lim
x→∞
como afirmamos.
Exercícios
1) Obtenha o crescimento exponencial e(f ) (se este estiver
definido) para as seguintes funções:
a) f (x) = e5x+sen (x)
b) f (x) = 3x2 5x
c) f (x) = 4x + (1/10)x
19
2 Conceitos Básicos
Neste capítulo lembramos algumas definições básicas da
álgebra e enunciamos as principais propriedades das operações
⊕ e ⊗ que foram brevemente mencionadas no capítulo anterior.
2.1 Semianel
Um semianel é um conjunto S dotado de duas operações
binárias + e · tais que:
1 - (S, +) é um monóide comutativo com elemento identidade 0, ou seja:
i) (a + b) + c = a + (b + c)
ii) 0 + a = a + 0 = a
iii) a + b = b + a
2 - (S, ·) é um monóide com elemento identidade 1, ou
seja:
i) (a · b) · c = a · (b · c)
ii) 1 · a = a · 1 = a
3 - A multiplicação é distributiva à direita e à esquerda:
i) a · (b + c) = (a · b) + (a · c)
20
Capítulo 2. Conceitos Básicos
ii) (a + b) · c = (a · c) + (b · c)
4 - A multiplicação por 0 anula S, ou seja, resulta no
próprio elemento identidade de +:
i) 0 · a = a · 0 = 0
Se o leitor deseja ver um exemplo de semianel então podemos exibir um velho familiar, o conjunto R munido das operações usuais de adição e subtração. No entanto há uma diferença:
dado um número real qualquer x então temos que existe o oposto
−x, que também é real, e tal que x + (−x) = 0. Isso faz de R
um conjunto ainda mais especial, uma estrutura que é chamada
de anel. Portanto, ainda que esse seja um exemplo de semianel,
podemos dar um exemplo mais genuíno, no sentido que em que
não é um anel (ou seja, basicamente não tem a propriedade do
oposto), mas deixamos isso para a próxima seção.
2.2 Álgebra Max-Plus
Neste texto usaremos a notação
R̄ = R ∪ {−∞}
para o conjunto R estendido (com a inclusão de −∞), com a
convenção x + (−∞) = −∞ para todo ponto x ∈ R̄.
Esse conjunto será dotado de duas operações:
a ⊕ b = max(a, b)
a ⊗ b = a + b.
2.2. Álgebra Max-Plus
21
Com essa notação, temos que a ⊕ (−∞) = a, mostrando
que −∞ é o elemento neutro para a operação binária ⊕. Além
disso, podemos reescrever a convenção acima como a ⊗ (−∞) =
−∞, o que verifica a condição (4) da definição de semianel.
Para a operação ⊗ temos que a⊗0 = a+0 = a para todo
a ∈ R̄, mostrando que 0 é o elemento neutro da mesma. Deixamos como exercício para o leitor verificar as demais propriedades
das operações ⊕ e ⊗.
Desta forma, definimos a álgebra max-plus como sendo
o semianel munido das operações ⊕ e ⊗ sobre o conjunto de reais
estendidos R̄.
Algumas das principais propriedades dessa álgebra estão
resumidas no resultado abaixo:
Lema 2.1. Dados a, b e c em R̄, temos
1 - Associatividade: a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c e a ⊗ (b ⊗ c) =
(a ⊗ b) ⊗ c
2 - Comutatividade: a ⊕ b = b ⊕ a e a ⊗ b = b ⊗ a
3 - Distributividade: a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c)
4 - Identidade aditiva: a ⊕ (−∞) = (−∞) ⊕ a = a
5 - Identidade multiplicativa: a ⊗ 0 = 0 ⊗ a = a
6 - Inverso multiplicativo: se a 6= −∞ então existe um único
b tal que a ⊗ b = 0
7 - Elemento absorvente: a ⊗ −∞ = −∞ ⊗ a = −∞
8 - Idempotência da adição: a ⊕ a = a.
22
Capítulo 2. Conceitos Básicos
Demonstração. Mostraremos aqui algumas das propriedades acima,
deixando as demais como exercício para o leitor.
A distributividade, por exemplo, segue naturalmente de
a ⊗ (b ⊕ c) = a + max(b, c) = max(a + b, a + c) = (a ⊗ b) ⊕ (a ⊗ c).
Para o inverso multiplicativo, basta notar que para cada
a real podemos tomar b = −a (o que ocorreria se a = −∞?) e
então
a ⊗ b = a + (−a) = 0.
Note que o elemento −∞ não tem oposto; exatamente
por isso esse conjunto, dotado dessas operações, não é um anel
(e assim temos um exemplo mais legítimo, que é semianel mas
que não é anel).
Exercícios
1) Obtenha o resultado das seguintes operações:
a) (34 ⊕ π) ⊗ −π
√
b) (−∞ ⊕ 2 ⊗ −4
c) (7 ⊗ 8) ⊕ (−∞ ⊗ −4) ⊕ (−63 ⊗ 3)
d) (4 ⊗ x) ⊕ 3 = 9
23
3 Álgebra Linear Max-Plus
Nesse capítulo desenvolveremos o formalismo da álgebra
linear quando produto e adição usuais são trocados por suas
versões max-plus.
3.1 Vetores
Um vetor d-dimensional v é um elemento de R̄d , que
é denotado por v = (v1 , v2 , . . . , vd ), ou, como também é usual,
representado como um vetor coluna


v1


 v2 

v= . 
.
 .. 
vd
Dados dois vetores u e v em R̄d e um escalar λ ∈ R̄d ,
podemos definir a soma vetorial como sendo
u ⊕ v := (u1 ⊕ v1 , u2 ⊕ v2 , . . . , ud ⊕ vd ),
e o produto por escalar como
λ ⊗ u := (λ ⊗ u1 , λ ⊗ u2 , . . . , λ ⊗ ud ).
Não é difícil ver que o vetor (x1 , x2 ) pode ser escrito
como
(x1 , x2 ) = x1 ⊗ (0, −∞) ⊕ x2 ⊗ (−∞, 0)
24
Capítulo 3. Álgebra Linear Max-Plus
3.2 Funções Lineares
Definição 3.1. Dizemos que uma função f : R̄d → R̄D é linear
se
1) f (λ ⊗ v) = λ ⊗ f (v)
2) f (u ⊕ v) = f (u) ⊕ f (v)
Exemplo 3.1. Considere f (x1 , x2 ) = (a1 ⊗x1 )⊕(a2 ⊗x2 ), então
não é difícil verificar que f é linear.
O exemplo acima, na verdade, é a forma geral de uma
função linear do espaço R̄2 em R̄, como mostramos no lema
abaixo.
Lema 3.1. Uma função f : R̄2 → R̄ é linear se e somente se
f (x1 , x2 ) = (a1 ⊗ x1 ) ⊕ (a2 ⊗ x2 )
Demonstração. Dada uma função f : R̄2 → R̄ linear então, como
(x1 , x2 ) = x1 ⊗ (0, −∞) ⊕ x2 ⊗ (−∞, 0)
temos que
f (x1 , x2 )
= f
=
x1 ⊗ (0, −∞) ⊕ x2 ⊗ (−∞, 0)
x1 ⊗ f (0, −∞)
⊕ x2 ⊗ f (−∞, 0)
= (a1 ⊗ x1 ) ⊕ (a2 ⊗ x2 )
onde a1 = f (0, −∞) e a2 = f (−∞, 0) .
A recíproca é deixada ao leitor como exercício.
3.3. Matrizes
25
3.3 Matrizes
Uma matriz m × n A é definida como no caso usual, um
arranjo de m colunas e n linhas.
Dadas duas matrizes m × n A e B, definimos a soma
matricial A ⊕ B como sendo a matriz m × n cujas entradas são
(A ⊕ B)ij := Aij ⊕ Bij = max {Aij , Bij }.
Dado λ ∈ R̄, podemos também definir a matriz λ ⊗ A
como sendo a matriz m × n cujas entradas são
(λ ⊗ A)ij = λ ⊗ Aij = λ + Aij .
Das propriedades básicas das operações ⊕ and ⊗, não
é difícil verificar que as operações com matrizes satisfazem as
seguintes propriedades:
Lema 3.2. Dadas A, B e C matrizes m × n e dado um λ ∈ R̄
então temos:
1 - Existe uma matriz m × n [−∞] tal que A ⊕ [−∞] = A;
2 - A ⊕ B = B ⊕ A;
3 - A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C;
4 - λ ⊗ A = A ⊗ λ;
5 - λ ⊗ (A ⊕ B) = (λ ⊗ A) ⊕ (λ ⊗ B).
Demonstração. Vamos provar as propriedades 1, 4 e 5. As demais são deixadas como exercício para o leitor.
26
Capítulo 3. Álgebra Linear Max-Plus
Para mostrar a propriedade 1, basta observar que, para
qualquer elemento Aij da matriz A, max(Aij , −∞) = Aij .
A propriedade 4 é verdadeira pois

A11
A12
···
A1n


 A21
λ ⊗ 
 ..
 .
A22
..
.
···
..
.
A2n
..
.


=


Am1
Am2
...
Amn
λ + A11
λ + A12
···
λ + A1n


 λ + A21
= 
..


.
λ + A22
..
.
···
..
.
λ + A2n
..
.





λ + Am1
λ + Am2
...
λ + Amn

A11
A12
···
A1n


 A21
= 
 ..
 .
A22
..
.
···
..
.
A2n
..
.


⊗λ


Am1
Am2
...
Amn

Mostramos a propriedade 5 observando que:
λ ⊗ (A ⊕ B) =

λ + max(A11 , B11 )
···
λ + max(A1n , B1n )


 λ + max(A21 , B21 )
=
..


.
···
..
.
λ + max(A2n , B2n )
..
.





λ + max(Am1 , Bm1 ) · · ·
λ + max(Amn , Bmn )
3.3. Matrizes

27
max(λ + A11 , λ + B11 )
···
max(λ + A1n , λ + B1n )


 max(λ + A21 , λ + B21 )
=
..


.
···
..
.
max(λ + A2n , λ + B2n )
..
.





max(λ + Am1 , λ + Bm1 ) · · ·
max(λ + Amn , λ + Bmn )
= (λ ⊗ A) ⊕ (λ ⊗ B)
Dadas uma matriz m × n denotada por A e uma matriz
n × l denotada por B definimos o produto matricial A ⊗ B como
sendo a matriz m × l cujas entradas são
(A ⊗ B)ij =
M
(Aik ⊗ Bkj ) = max (Aik + Bkj ) .
k
k
Algumas propriedades básicas do produto matricial estão listadas no resultado abaixo.
Lema 3.3. Sejam A uma matriz m × n, B uma matriz n × p e
C uma matriz p × q. Então temos que:
1 - (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C)
2 - λ ⊗ (A ⊗ B) = A(λ ⊗ B) = (A ⊗ B) ⊗ λ
3 - Se B e C são matrizes de mesma ordem então
A ⊗ (B ⊕ C) = (A ⊗ B) ⊕ (A ⊗ C)
Demonstração. Para provar a propriedade 1, vamos considerar
as matrizes m × q dadas por D = (A ⊗ B) ⊗ C e E = A ⊗ (B ⊗ C)
28
Capítulo 3. Álgebra Linear Max-Plus
e mostrar que (D)ij = (E)ij . De fato,
(D)ij
=
p M
(A ⊗ B)il ⊗ Clj =
l=1
=
max
max
l∈{1,··· ,p}
k∈{1,··· ,n}
=
max
max
l∈{1,··· ,p}
k∈{1,··· ,n}
=
=
max
max
l∈{1,··· ,p}
max
k∈{1,··· ,n}
=
n M
Aik +
l∈{1,··· ,p}
(A ⊗ B)il + Clj
Aik + Bkl + Clj
Aik + Bkl + Clj
k∈{1,··· ,n}
max
Aik + Bkl + Clj
max
l∈{1,··· ,p}
Bkl + Ckl
Aik ⊗ (B ⊗ C)kj = (E)ij
k=1
Pelo lema 3.2 temos que λ⊗(A⊗B) = (A⊗B)⊗λ então,
para provarmos 2, basta mostrarmos que λ⊗(A⊗B) = A(λ⊗B).
λ ⊗ (A ⊗ B)
= λ + (A ⊗ B)ij = λ + max Aik + Bkj
k
ij
= max Aik + λ + Bkj
k
= A(λ ⊗ B)
ij
Para mostrar 3, vamos verificar que:
A ⊗ (B ⊕ C)
= max Aik + max(Bkj , Ckj )
ij
k
= max (Aik + Bkj , Aik + Ckj )
k
= (A ⊗ B) ⊕ (A ⊗ C)
ij
3.3. Matrizes
29
Se m = n dizemos que a matriz A é uma matriz quadrada de ordem n. Considere a matriz

0
−∞ −∞ . . .

0
−∞ . . .
 −∞
In = 
..
..
..
 ..
 .
.
.
.
−∞
−∞
...
−∞

−∞
..
.


.


−∞
0
Então podemos mostrar que
A ⊗ In = In ⊗ A = A,
para qualquer matriz A de ordem n.
Exercícios
1) Efetue as operações indicadas:
"
# "
#
1 3
0
a)
⊗
4 2
4
"
# " #
0
3
b)
⊕
4
2
"
#
"
# "
#!
−1 −∞
0
1
4
2
c)
⊗
⊕
2
−4
−1 −∞
−∞ 1

 

−∞
0
0
0
−∞

 

d)  1
1 
−∞
0 ⊗ 0
1
1
−∞
−∞
2
31
4 Autovalores
e
Autovetores
Max-Plus
Vamos considerar uma matriz quadrada A de ordem n
cujas entradas são elementos de R̄ e um vetor coluna v (que nada
mais é do que uma matriz n × 1).
Da definição de produto matricial temos que a matriz
A ⊗ v, de ordem n × 1, assume a forma:
M
(A ⊗ v)i =
(Aij ⊗ vj ) = max (Aij + vj ).
j
j
Dado λ ∈ R̄ temos também que
λ ⊗ v = (λ ⊗ v1 , . . . , λ ⊗ vn ) = (λ + v1 , . . . , λ + vn ).
Nesse contexto uma questão totalmente natural é a procura de autovalores e autovetores de A no sentido max-plus, ou
seja, soluções da equação A ⊗ v = λ ⊗ v. Essa equação pode ser
traduzida, em termos das operações usuais, como sendo
max (Aij + vj ) = λ + vi para todo i = 1, . . . , n.
j
Exemplo 4.1.
"
# "
# "
# "
#
"
#
1 0
0
max (1, −1)
1
0
⊗
=
=
= 1⊗
.
0 1
−1
max (0, 0)
0
−1
Temos também
"
# "
# "
# "
#
"
#
1 0
−1
max (0, 0)
0
−1
⊗
=
=
= 1⊗
.
0 1
0
max (−1, 1)
1
0
32
Capítulo 4. Autovalores e Autovetores Max-Plus
Nesse caso vemos que 1 é um autovalor da matriz associado a dois autovetores distintos.
Exemplo 4.2. Considere a matriz
"
−∞
a
b
−∞
#
,
que tem autovalor λ = (a + b)/2 e autovetor
"
x
x + (b − a)/2
#
"
=x⊗
0
#
(b − a)/2
(onde qualquer escolha de x é permitida).
O resultado mais interessante sobre esse tópico, dentro
de nossos objetivos, é que matrizes com entradas reais tem um
único autovalor no sentido max-plus. Para provar isso usaremos
uma ferramenta muito importante, o Teorema do Ponto Fixo de
Brower, que recordamos a seguir. Para uma demonstração deste
resultado, consulte por exemplo [5].
Teorema 4.1. Seja C um subconjunto fechado de Rn e f : Rn →
Rn uma função contínua. Então, se f (C) ⊂ C, existe ao menos
um ponto p ∈ C tal que f (p) = p.
De posse desse resultado podemos então provar nosso
principal teorema nesse capítulo:
Teorema 4.2. Seja A uma matriz d × d com todas as entradas
Aij ∈ R; então existe um número real λ e um vetor v, tal que,
A ⊗ v = λ ⊗ v. Além disso, o autovalor λ é único.
33
Demonstração. Antes de mais nada, note que se M ⊗ v = µ ⊗ v,
então (α ⊗ M ) ⊗ v = α ⊗ (M ⊗ v) = α ⊗ (µ ⊗ v) = (α + µ) ⊗ v.
Mas sabemos que

α + M11
α + M12
···
α + M1d


 α + M21
α⊗M =
..


.
α + M22
..
.
···
..
.
α + M2d
..
.





···
α + Md1
· · · α + Mdd
Portanto, não perdemos em generalidade ao supor que todas as
entradas da matriz A são maiores ou iguais a zero. Assim, temos
que
0 ≤ Aij ≤ L.
Agora vamos introduzir uma função T : Rd → Rd definida de
forma que
(T x)i = max (Aij + xj ) − min max (Akj + xj ).
j
j
k
Não é difícil verificar que esta expressão depende continuamente
do vetor x. Também segue diretamente da definição que (T x)i ≥
0. Por outro lado, temos
(T x)i ≤ max (L + xj ) − min max (0 + xj )
j
k
j
≤ max (L + xj ) − max (xj ) = L.
j
j
Em particular, isso mostra que a região do espaço {x =
(x1 , x2 , · · · , xd ) ∈ Rd : 0 ≤ xj ≤ L para todo j} tem como
imagem pela função T um subconjunto dela mesma; como T é
uma função contínua isso implica (como consequência direta do
teorema de ponto fixo de Brower) que T tem ao menos um ponto
fixo v. Portanto
v = T (v) ⇒ vi = (T v)i = max (Aij + vj ) − min max (Akj + vj ).
j
k
j
34
Capítulo 4. Autovalores e Autovetores Max-Plus
Se denotamos
λ = min max (Akj + vj ),
k
j
então a expressão acima implica que
v = A ⊗ v − λ ⇒ λ + v = A ⊗ v ⇒ λ ⊗ v = A ⊗ v,
no sentido max-plus, como afirmamos.
Para provar a unicidade desse autovalor vamos supor,
por absurdo, que temos dois autovalores distintos λ e µ. Em
outras palavras, existem vetores v e u, tais que,
A⊗v =λ⊗v
e
A ⊗ u = µ ⊗ u.
Sem perda de generalidade podemos supor que λ < µ.
Antes de prosseguirmos, observamos que, denotando por
2
A o produto max-plus A ⊗ A, temos:
A2 ⊗v = A⊗(A⊗v) = A⊗(λ⊗v) = λ⊗(A⊗v) = λ⊗λ⊗v = (λ+λ)⊗v
ou, mais geralmente, An ⊗ v = (nλ) ⊗ v.
Podemos então considerar um valor suficientemente grande
de t, tal que, t ⊗ v ≥ u (no sentido de que t ⊗ vi ≥ ui , para cada
i ∈ {1, . . . , d}). Então
(t ⊗ v) ⊕ u = t ⊗ v.
Portanto,
An ⊗ (t ⊗ v) = An ⊗ (t ⊗ v) ⊕ u = An ⊗ (t ⊗ v) ⊕ An ⊗ (u)
⇒t ⊗ (An ⊗ v) = t ⊗ (An ⊗ v) ⊕ An ⊗ (u)
⇒t ⊗ (nλ) ⊗ v = t ⊗ (nλ) ⊗ v ⊕ (nµ) ⊗ u
35
o que é equivalente a dizer que, para todo inteiro n, temos t ⊗
(nλ) ⊗ v ≥ (nµ) ⊗ u. Ou ainda:
t + v − u ≥ n(µ − λ)
Mas isso é uma contradição pois observamos que ambos os lados
desta desigualdade são valores positivos e, portanto, existirá um
n suficientemente grande para o qual a desigualdade não será
verificada. Então temos que λ = µ e o autovalor max-plus é
único, conforme queríamos mostrar.
Se removemos a hipótese de que as entradas da matriz
são todas reais (ou seja, se permitimos que ao menos uma delas seja −∞) então a situação é bem diferente. Considere, por
exemplo,

1

 1
A=
 −∞

−∞

1
−∞
−∞
1
−∞
−∞
2
−∞
2

−∞ 
.
2 

2
Então não é muito difícil ver que
 




−∞
−∞
−∞
 




 −∞   −∞ 
 −∞ 






A⊗
=
 = 2 ⊗  1 ,
 1   3 


1
3
1
e que

1


2


1


 



 1   2 


=
 = 1 ⊗  1 .
A⊗
 −∞   −∞ 
 −∞ 

 



−∞
−∞
−∞
36
Capítulo 4. Autovalores e Autovetores Max-Plus
Logo, 1 and 2 são autovalores max-plus de A, mostrando que
a unicidade dos autovalores não vale mais quando admitimos
matrizes com entradas −∞.
Exercícios
1) Obtenha o autovalor max-plus (e respectivos autovetores)
das seguintes matrizes:
"
#
−3 −∞
a)
−∞
1
"
#
4 0
b)
0 2
37
5 Polinômios Max-Plus
Nesse capítulo faremos um breve estudo de polinômios
no mundo max-plus.
Um polinômio max-plus p : R̄ → R̄ de grau d é uma
função do tipo
p(x) = a0 ⊕ (a1 ⊗ x) ⊕ (a2 ⊗ x ⊗ x) ⊕ . . . ⊕ (ad ⊗ x · · · ⊗ x)
= max {a0 , a1 + x, a2 + 2x, . . . , ad + dx}
com os coeficientes ai ∈ R̄ e ad 6= −∞.
Exemplo 5.1. Considere o polinômio max-plus p(x) = 2 ⊕ (3 ⊗
x) de grau 1. Usando as operações usuais, podemos escrevê-lo da
seguinte forma p(x) = max{2, 3 + x}. Destacamos o gráfico de
p(x) na figura 1.
y
6
5
4
3
2
1
0
-4
-3
-2
-1
0
1
2
3
x
Figura 1. Gráfico de p(x) = 2 ⊕ (3 ⊗ x)
38
Capítulo 5. Polinômios Max-Plus
Exemplo 5.2. Seja q(x) = −2 ⊕ (1 ⊗ x) ⊕ (−1 ⊗ x ⊗ x ⊗ x).
Ou ainda q(x) = max{−2, x + 1, 3x − 1}. Observe que q(x) é
um polinômio de grau 3 e que não possui o termo de grau 2.
Cabe ressaltar que, como a identidade para ⊕ é o elemento −∞,
consideramos aqui que a2 = −∞. O gráfico de q(x) está na figura
2.
y
6
5
4
3
2
1
0
-5
-4
-3
-2
-1
0
1
2
3
x
-1
-2
-3
Figura 2. Gráfico de q(x) = −2 ⊕ (1 ⊗ x) ⊕ (−1 ⊗ x ⊗ x ⊗ x)
Exemplo 5.3. O polinômio r(x) = (−∞) ⊕ (−1 ⊗ x) ⊕ (x ⊗
x) é de grau 2. Observe que o coeficiente do termo de maior
grau não está escrito mas é zero, o elemento identidade para a
operação ⊗ e não o 1, como na operação multiplicação usual. Da
mesma forma, como −∞ é o elemento identidade da operação
⊕, também podemos escrever
r(x) = (−1 ⊗ x) ⊕ (x ⊗ x) = max{−1 + x, 2x}.
Seu gráfico está na figura 3.
39
y
4
3
2
1
0
-4
-3
-2
-1
0
1
2
3
x
-1
-2
-3
-4
Figura 3. Gráfico de r(x) = (−1 ⊗ x) ⊕ (x ⊗ x)
Um primeiro fato simples sobre uma função dessa forma
é que elas são não-decrescentes.
Teorema 5.1. Dado um polinômio max-plus p(x) de grau maior
ou igual a 1 temos:
1 - p(x) é contínua
2 - p(x) é não-decrescente
3 - existe x0 tal que p(x) é estritamente crescente quando x ≥
x0 .
4-
lim p(x) = a0
x→−∞
5 - lim p(x) = +∞
x→∞
40
Capítulo 5. Polinômios Max-Plus
Demonstração. Seja d o grau do polinômio max-plus p(x). Cada
uma das funções a0 , a1 + x, a2 + 2x, . . . , ad + dx presentes na
definição de p(x) é contínua (de fato diferenciável). Desta forma
p(x) é uma função contínua, por ser o máximo entre funções
contínuas, e também é não-decrescente por ser o máximo entre
funções não-decrescentes.
Para mostrarmos o item 3 basta observarmos que, se
a0 6= −∞, o polinômio p(x) passa a ser estritamente crescente
quando o máximo entre as funções deixa de ser o termo constante
a0 . Sendo assim, seja ai + ix a função com menor i ∈ {1, · · · , d}
tal que ai 6= −∞, então se escolhemos x0 = (a0 − ai )/i temos
que:
x ≥ x0 ⇒ ai + ix ≥ a0 e p(x) ≥ ai + ix
que é uma função estritamente crescente. Se a0 = −∞, este
termo será sempre menor que qualquer outro termo ai + ix e
este polinômio será estritamente crescente para todo x ∈ R.
Quando consideramos valores de x muito pequenos (ou
seja, próximos de −∞) então todos os termos com x se tornam
muito pequenos e assim o máximo entre eles acaba sendo o termo
constante a0 , o que mostra o item 4.
Quando escolhemos valores de x suficientemente grandes, os termos com x claramente se tornam maiores do que a0 ;
de fato cada um deles vai a +∞ e portanto seu máximo também
vai a +∞, o que mostra o item 5.
5.1. Raízes
41
5.1 Raízes
Dado um polinômio max plus de grau d
p(x) = a0 ⊕ (a1 ⊗ x) ⊕ (a2 ⊗ x ⊗ x) ⊕ · · · ⊕ (ad ⊗ x ⊗ x . . . ⊗ x)
= max {a0 , a1 + x, a2 + 2x, . . . , ad + dx}
queremos encontrar as soluções da equação p(x) = 0.
Observando os gráficos de alguns polinômios podemos
imaginar que, de fato, só temos três casos possíveis: nenhuma
raiz, uma única raiz ou infinitas raízes. Isso é deixado claro no
próximo resultado.
Teorema 5.2. Seja p(x) um polinômio max-plus. Então o número de soluções da equação p(x) = 0 é zero, uma ou infinitas.
Demonstração. Suponhamos, primeiramente, que a0 = −∞. Então, p(x) é estritamente crescente e, além disso, limx→−∞ p(x) =
−∞ e limx→+∞ p(x) = +∞. Podemos concluir assim que p(x)
possui uma única raiz. Caso tenhamos a0 6= −∞, então o gráfico de p(x) possui uma reta paralela ao eixo x; se essa reta está
exatamente sobre o eixo (a0 = 0) então p(x) tem infinitas raízes.
Se esta reta está acima do eixo (a0 > 0), e considerando que
p(x) é uma função não-decrescente, então não existe raiz. Se,
por outro lado, esta reta está abaixo do eixo (a0 < 0) então, se
o grau de p(x) é maior ou igual a 1, estamos na situação em que
há exatamente uma raiz pois, pelos itens 3 e 5 do teorema 5.1,
p(x) é estritamente crescente a partir de um ponto x0 e tende
a +∞ quando x tende a +∞. Entretanto, se o grau de p(x) for
zero, isto é, se p(x) = a0 < 0, então este polinômio não possui
raiz.
42
Capítulo 5. Polinômios Max-Plus
5.2 Interseção de Polinômios
Dados dois polinômios max-plus p(x) e q(x) queremos
saber em que pontos temos p(x) = q(x).
Uma observação básica é que podemos, em princípio, ter
um número infinito de interseções. Considere, por exemplo, os
polinômios p(x) = 1 ⊕ x e q(x) = 1 ⊕ (x ⊗ x). Nesse caso, quando
x < 1/2 ambos valem 1, e então todo ponto x < 1/2 é um
ponto de interseção desses dois polinômios. Porém é muito fácil
modificar completamente essa situação: bastaria, por exemplo,
considerar o polinômio r(x) = 0, 99999 ⊕ (x ⊗ x) no lugar de
q(x). Ou seja, uma pequena perturbação em um dos coeficientes
faz com que as infinitas interseções desapareçam. De uma certa
forma o caso p(x) e q(x) é um tipo de caso degenerado, que
não pretendemos abordar, mas uma pequena perturbação de um
caso desses nos leva a p(x) e r(x), que é a situação mais geral e
interessante, para a qual é possível estabelecer uma cota para o
número de interseções.
Teorema 5.3. Sejam p e q dois polinômios max-plus de graus,
respectivamente, P e Q. Então o número de soluções da equação
p(x) = q(x) é um elemento do conjunto {0, 1, . . . , P ⊕ Q}.
Demonstração. Por simplicidade, vamos considerar que os coeficientes dos polinômios p e q não assumem o valor −∞. Considere o polinômio p. Vamos definir uma divisão da reta em pontos
p1 , p2 , . . . , pP de forma que, no intervalo [−∞, p1 ], p(x) tem inclinação zero, no intervalo [p1 , p2 ], p(x) tem inclinação 1 e assim
sucessivamente, até que em [pP , +∞) p(x) tem inclinação P . De
forma similar definimos uma divisão em pontos q1 , . . . , qQ , de
5.2. Interseção de Polinômios
43
forma que em cada subintervalo determinado temos que q(x)
tem inclinação constante.
Vamos então denotar os intervalos definidos acima como
I0 = [−∞, p1 ], I1 = [p1 , p2 ], . . . , IP = [pP , +∞)
e
J0 = [−∞, q1 ], J1 = [q1 , q2 ], . . . , JQ = [qQ , +∞)
De acordo com o que já estudamos sobre polinômios
max-plus, temos que a primeira interseção entre os polinômios
não pode ocorrer em um ponto em [−∞, p1 ) e [−∞, q1 ), ou seja,
pontos de I0 ∩ J0 , pois se isso ocorresse, como ambos são constantes nessas regiões, então teríamos uma infinidade de pontos
em comum nos gráficos. De fato o mesmo argumento mostra que
não podemos ter interseção dos gráficos em nenhum ponto que
pertença a um conjunto do tipo Ii ∩ Ji .
Consideremos então os intervalos na forma Ii ∩ Jj ; variando os índices i e j podemos ver que todos os pontos da reta
estão em algum desses conjuntos. O intervalo que está mais a
esquerda é, claro, I0 ∩ J0 . Um intervalo do tipo Ii ∩ Jj pode ser
seguido por Ii+1 ∩ Jj (se o extremo de Ii está dentro de Jj ), ou
Ii ∩ Jj+1 (se o extremo de Jj está dentro de Ii ) ou Ii+1 ∩ Jj+1
(se Ii e Jj têm o mesmo extremo). Toda essa informação pode
ser resumida na seguinte notação: vamos identificar o conjunto
Ii ∩ Jj com o par ordenado (i, j). Então o par (i, j) só pode ser
seguido por um dos três pares seguintes: (i + 1, j), (i, j + 1) ou
(i + 1, j + 1). Portanto a sequência dos intervalos Ii ∩ Jj na reta
começa com (0, 0) (correspondente a I0 ∩ J0 e continua seguindo
a regra acima até chegar ao intervalo (P, Q).
44
Capítulo 5. Polinômios Max-Plus
Dentre esses intervalos, onde podemos ter as interseções
dos gráficos? Já sabemos que isso não pode ocorrer em nenhum
dos intervalos do tipo (i, i). Imagine que temos a primeira interseção no intervalo (i0 , j0 ); se i0 é maior do que j0 então o polinômio p(x) cresce mais rápido do que q(x) nessa região. Para que
voltem a se cruzar é preciso que q comece a crescer mais rápido
do que p, o que significa que o novo cruzamento só pode ocorrer
quando tivermos um novo par (i1 , j1 ) com j1 maior que i1 . De
forma similar, se i0 é menor do que j0 então o proximo possível
cruzamento só poderá ocorrer num novo par (i1 , j1 ) tal que i1 é
maior do que j1 .
Portanto é preciso haver uma certa inversão na ordem
dos pares para que possamos ter cruzamentos dos gráficos. Inverter a ordem (ou seja, trocar um par (maior, menor) por outro
(menor, maior), ou vice-versa) envolve cruzar a diagonal (i, i).
A maneira de fazer isso maximizando o número de cruzamentos
(e portanto permitindo o máximo de interseções dos gráficos) é
com algo do tipo
(0, 0)
(1, 0)
→
(0, 1)
(0, 2)
...
(0, Q)
(1, 1)
→ (1, 2)
...
(1, Q)
...
(2, Q)
(3, 2) → . . .
..
..
.
.
(3, Q)
..
.
↓
(2, 0)
(2, 1)
(2, 2)
↓
(3, 0)
..
.
(3, 1)
..
.
(P, 0)
(P, 1)
...
...
(P, Q)
ou seja, um caminho que serpenteia em torno da diagonal. Suponha que P > Q; nesse caso o número máximo de pares que
5.3. Polinômios Min-Plus
45
podem corresponder a cruzamentos do gráfico é de Q + 1 ≤
max{P, Q}.
Quando P = Q podemos, de forma similar, ver que o
número de pares que podem corresponder a cruzamentos é de
Q = max{P, Q}, o que conclui a prova.
5.3 Polinômios Min-Plus
Existem algumas variações da álgebra max-plus, uma
delas sendo a álgebra min-plus onde consideramos a operação
⊕ dada por a ⊕ b = min{a, b}. Nesta álgebra, consideramos o
conjunto R com a inclusão de +∞. Esta álgebra também é conhecida como álgebra tropical. Neste contexto, é interessante,
por exemplo, estudar o comportamento de polinômios como:
p(x) = a0 ⊕ (a1 ⊗ x) ⊕ (a2 ⊗ x ⊗ x) = min {a0 , a1 + x, a2 + 2x}.
Observe que os gráficos desses polinômios são, em um
certo sentido, parecidos com os estudados na álgebra max-plus
mas com a diferença que as inclinações dos segmentos de reta
que o compõem vão diminuindo, ao contrário do que acontece
quando consideramos o máximo. A investigação geométrica desses objetos é conhecida como geometria tropical; o leitor interessado pode consultar o bonito texto expositório [2].
Exercícios
1) Esboce o gráfico do polinômio m(x) = 3 ⊕ (2 ⊕ x) ⊕ (x ⊗ x)
2) Determine um polinômio s(x) cuja única solução para a
equação s(x) = 0 ocorra em x = −2.
46
Capítulo 5. Polinômios Max-Plus
3) Determine os intervalos onde ocorrem as interseções de
p(x) e m(x) e p(x) e s(x) onde p(x) é o primeiro exemplo de polinômio max-plus dado no capítulo e m(x) e s(x)
são os polinômios definidos nos exercícios acima.
47
6 Formas Quadráticas Max-Plus
Um outro problema clássico dentro da álgebra linear é
o de se maximizar (ou, eventualmente, o de se minimizar) uma
forma quadrática sobre uma determinada região, por exemplo
um círculo, o que é um exemplo de problema de maximização
com vínculos. Neste capítulo desejamos apresentar o equivalente
max-plus desse problema.
6.1 Definindo Regiões
Vamos considerar o equivalente max-plus de uma equação como x2 + y 2 = 1, que define um círculo de raio unitário no
plano xy. Esta expressão na verdade é a forma curta de
x.x + y.y = 1
Trocando então as operações · e + por ⊗ e ⊕ temos
(x ⊗ x) ⊕ (y ⊗ y) = 1
ou seja,
max {2x, 2y} = 1
Esta é então a equação do vínculo max-plus. A região acima é
formada por duas semi-retas no plano que podem ser escritas
como
R = {x = 1/2, y ≤ 1/2} ∪ {y = 1/2, x ≤ 1/2}
e podem ser conferidas na figura 4.
(6.1)
48
Capítulo 6. Formas Quadráticas Max-Plus
y
2
1
b
0
-2
-1
0
1
2
x
-1
-2
Figura 4. Região max-plus (x ⊗ x) ⊕ (y ⊗ y) = 1
6.2 Forma Quadrática
Uma forma quadrática em R2 é uma função q : R2 → R
definida a partir de uma transformação linear A : R2 → R2 da
seguinte forma:
"
q(x1 , x2 ) = [x1 x2 ]A
x1
x2
#
= a11 x21 + (a12 + a21 )x1 x2 + a22 x22
Inspirados por isso, podemos definir uma forma quadrática max-plus como sendo a função Q : R̄2 → R̄ dada por:
Q(x1 , x2 ) =
=(a11 ⊗ x1 ⊗ x1 ) ⊕ (a12 ⊕ a21 ) ⊗ x1 ⊗ x2 ⊕ (a22 ⊗ x2 ⊗ x2 )
= max {a11 + 2x1 , max {a12 , a21 } + x1 + x2 , a22 + 2x2 }
= max {a11 + 2x1 , a12 + x1 + x2 , a21 + x2 + x1 , a22 + 2x2 }
Então agora queremos maximizar a função Q no conjunto R e de fato podemos mostrar o resultado seguinte.
6.3. Forma Quadrática em R̄n
49
Lema 6.1. Seja Q uma forma quadrática max-plus e R a região
definida em 6.1 então
max {Q(x)} = 1 + max {aij }
x∈R
1≤i,j≤2
Demonstração. Temos que o ponto (1/2, 1/2) ∈ R e Q(1/2, 1/2) =
1 + max {aij }. Naturalmente, max {Q(x)} ≥ Q(1/2, 1/2).
x∈R
1≤i,j≤2
Mas para um ponto x = (x1 , x2 ) qualquer na região R
temos que
Q(x) = max {a11 + 2x1 , a12 + x1 + x2 , a21 + x2 + x1 , a22 + 2x2 }
≤ max {a11 + 1, a12 + 1/2 + 1/2, a21 + 1/2 + 1/2, a22 + 1}
= Q(1/2, 1/2)
Assim, o máximo é, de fato, realizado em (1/2, 1/2) e
portanto temos o lema.
6.3 Forma Quadrática em R̄n
Vamos agora definir a forma quadrática Q : R̄n → R̄
dada por
Q(x) = xT Ax = max {aij + xi + xj }
i,j∈I
onde I = {1, · · · , n}.
Consideremos a região R definida por
max {kxi } = 1
i∈I
onde k é uma constante tal que k ∈ N e k > 1.
Observe que, se k = 2, temos uma generalização natural
da região definida em 6.1.
50
Capítulo 6. Formas Quadráticas Max-Plus
Então podemos mostrar o seguinte resultado:
Lema 6.2. Seja Q(x) uma forma quadrática definida em R̄n e
a R a região definida acima então
max {Q(x)} =
x∈R
2
+ max {aij }
k i,j∈I
Demonstração. O ponto (1/k, 1/k, . . . , 1/k) ∈ R e
1 1
1
2
Q
, ,...,
= + max {aij },
k k
k
k i,j∈I
portanto
max {Q(x)} ≥
x∈R
2
+ max {aij }
k i,j∈I
Por outro lado, dado um x qualquer em R temos
Q(x) = max {aij + xi + xj }
i,j∈I
1
1
2
≤ max aij + +
= + max {aij }
i,j∈I
k k
k i,j∈I
2
=⇒ max {Q(x)} ≤ + max {aij }
x∈R
k i,j∈I
e o lema esta provado.
6.4 Outra Forma de Definir Regiões
Agora apresentaremos uma outra forma de definir curvas; embora pareça menos natural que a anterior, de fato essa
forma é a mais usada no contexto max-plus.
Começamos com um exemplo: queremos saber qual é a
região em R̄2 definida pela equação x+y+1 = 0, ou x⊕y⊕1 = 0,
usando a soma max-plus. Vamos definir essa região como sendo
6.4. Outra Forma de Definir Regiões
51
o conjunto de pares (x, y) para os quais a expressão max {x, y, 1}
é realizada em ao menos dois pontos (o que inclui o 1). Então a
região definida consiste em três semirretas, a saber
{(x, 1) : x ≤ 1}
{(1, y) : y ≤ 1}
{(x, x) : x ≥ 1}
Esta região de R̄2 pode ser observada na figura 5.
y
2
1
b
0
-2
-1
0
1
2
3
x
-1
Figura 5. Região max-plus x ⊕ y ⊕ 1 = 0
Definição 6.1. Dizemos que a equação max-plus
(a ⊗ x) ⊕ (b ⊗ y) ⊕ c = 0,
com a, b, c ∈ R̄, define a região de R̄2 onde o máximo
max {a + x, b + y, c}
é realizado simultaneamente em pelo menos dois pontos.
52
Capítulo 6. Formas Quadráticas Max-Plus
Observe que se tivermos duas das constantes a, b, c assumindo o valor −∞ então esta equação não determina uma região
pois não teremos o máximo atingido em dois pontos. No entanto,
se a = b = c = −∞ então o máximo é atingido sempre, para
quaisquer valores de x e y determinando o próprio R̄2 . Sendo assim, excetuando o caso particular onde a = b = c = −∞, temos
que a região R consiste em três semirretas definidas por
{(c − a, y) : y ≤ c − b}
{(x, c − b) : x ≤ c − a}
{(x, x + a − b) : x > c − a}
Podemos, de forma análoga, definir uma região em R̄n .
Definição 6.2. Dizemos que a equação max-plus
(a ⊗ xn ) ⊕ (b ⊗ y m ) ⊕ c = 0,
com a, b, c ∈ R̄, define a região de R̄n onde o máximo
max {a + nx, b + my, c}
é realizado em pelo menos dois pontos.
Podemos agora perguntar qual região de R̄2 a equação
do círculo de raio 1 no plano xy determina nesta nova acepção.
Observe que x2 + y 2 − 1 = 0 é a região onde
max {2x, 2y, −1}
ocorre em ao menos dois pontos. Então esta região consiste em
6.4. Outra Forma de Definir Regiões
53
três semirretas, a saber
{(x, −1) : x ≤ −1/2}
{(−1, y) : y ≤ −1/2}
{(x, x) : x ≥ −1/2}
O leitor pode notar que agora temos valores de x e de
y ficando arbitrariamente pequenos (isto é, próximos de −∞) e
também muito grandes (ou seja, próximos de +∞. Desta forma
maximizar ou minimzar expressões nessa região é algo que tipicamente não será tão interessante quanto nos casos anteriores.
Exercícios
1) Encontre a região definida pela expressão dada:
a) (x ⊗ x) ⊕ (y ⊗ y ⊗ y) = 1
b) (5 ⊗ x ⊗ x) ⊕ (3 ⊗ y ⊗ y) = 15
2) Considere a região R definida pela expressão
max {2 + 10x, 2 + 4x} = 1
a) Reescreva-a na notação max-plus.
b) Considere a função definida em R pela expressão
Q(x, y) = max {20 + 2x, x + y, x + y, 2y}
Verifique que o máximo da função acima ocorre em qualquer ponto de R na forma (−5, y).
55
7 Conjuntos Convexos
Vamos aqui rapidamente recordar o importante conceito
de conjunto convexo; como estamos mais interessados nas ideias
principais e não em fazer uma teoria absolutamente geral, vamos
nos limitar a subconjuntos do plano R2 .
7.1 Convexidade em R2
Dados dois pontos x e y em R2 , definimos o segmento
[x, y] como sendo o conjunto
[x, y] := {(1 − t)x + ty : para t ∈ [0, 1] }
(ou seja, geometricamente esse é exatamente o segmento de reta
cujas extremidades são os pontos x e y). Note que a definição é
simétrica, isto é, [x, y] = [y, x].
Observação 1. Podemos pensar em (1 − t) e t como sendo
α = 1 − t e β = t reais não negativos tais que α + β = 1.
Definição 7.1. Um subconjunto C ⊂ R2 é dito convexo se para
todo par de pontos x e y pertencentes a C temos que o segmento
[x, y] está contido em C.
Alguns exemplos simples são o próprio R2 , R2+ e um
disco de raio r e centro p, Dr (p) = {x ∈ R2 : |x − p| ≤ r}.
Uma propriedade que pode ser provada sem muito esforço é a seguinte:
56
Capítulo 7. Conjuntos Convexos
Lema 7.1. Se C1 e C2 são conjuntos convexos então C1 ∩ C2
também é um conjunto convexo.
Demonstração. De fato, sejam p1 e p2 pontos pertencentes a
C1 ∩ C2 . Então o segmento [p1 , p2 ] está contido em C1 e também
está contido em C2 , pois ambos são convexos,mostrando que
[p1 , p2 ] está contido em C1 ∩ C2 . Isso nos leva à conclusão de que
C1 ∩ C2 é convexo, como afirmado.
7.2 Convexidade Max-Plus
Vamos agora estender o conceito de convexidade para
o conjunto R̄2 . Em primeiro lugar, é preciso redefinir o conceito
de segmento no contexto max-plus.
Vamos considerar α e β elementos de R̄ tais que
α⊕β =0
ou seja, max{α, β} = 0. Estes elementos estão no conjunto R1 ∪
R2 , e essas regiões são dadas por:
R1 = {(α, β) ∈ R̄2 : α = 0, β ≤ 0}
R2 = {(α, β) ∈ R̄2 : β = 0, α ≤ 0}
Definimos também
max {(x1 , x2 ), (y1 , y2 )} =
max {(x1 , y1 )}, max {(x2 , y2 )}
(ou seja, o máximo é feito coordenada a coordenada).
Então a definição de segmento é feita da seguinte forma:
[x, y] := {(α ⊗ x) ⊕ (β ⊗ y) : α e β em R1 ∪ R2 }
7.2. Convexidade Max-Plus
57
onde
(α ⊗ x) ⊕ (β ⊗ y) = (α + x1 , α + x2 ) ⊕ (β + y1 , β + y2 )
= max {(α + x1 , α + x2 ), (β + y1 , β + y2 )}
= max {α + x1 , β + y1 }, max {α + x2 , β + y2 }
Exemplo 7.1. Vamos encontrar o segmento max-plus que liga
os pontos (0, 0) e (1, 1). De acordo com a definição acima temos
que os pontos do segmento satisfazem
max {α, β + 1}, max {α, β + 1}
Na região R2 temos α ≤ 0 e β = 0, donde
max {α, β + 1}, max {α, β + 1} = max {α, 1}, max {α, 1}
= (1, 1)
Na região R1 temos α = 0 e β ≤ 0, donde
max {0, β + 1}, max {0, β + 1}
Se β < −1 o par acima é igual a (0, 0); para β ∈ [−1, 0] temos
que o par é (β + 1, β + 1), o corresponde ao segmento de reta
usual que liga (0, 0) a (1, 1).
Exemplo 7.2. Vamos determinar o segmento max-plus que liga
(0, 0) e (1, 0). Da definição temos
max {α, β}, max {α + 1, β}
Em R1 temos
(0, 1)
58
Capítulo 7. Conjuntos Convexos
Já em R2 temos
max {α, 0}, max {α + 1, 0} = 0, max {α + 1, 0}
Se α < −1 a expressão acima nos dá (0, 0); se α ∈ [−1, 0] temos
(0, α + 1), o que nos dá o segmento de reta usual que liga (0, 0)
a (1, 0).
Esses dois exemplos parecem sugerir que o segmento
max-plus é de fato o mesmo que um segmento usual, mas isso
não está correto.
Exemplo 7.3. Vamos encontrar o segmento max-plus [x, y] quando
x = (1, 0) e y = (0, 1). Da definição queremos os pontos nos
quais
max {α + 1, β}, max {α, β + 1}
Em R1 temos
max {1, β}, max {0, β + 1} = 1, max {0, β + 1}
Para β < −1 temos (1, 0); para β ∈ [−1, 0] temos (1, β + 1) que
é o segmento de reta usual que liga (1, 0) a (1, 1).
Na região R2 temos
max {α + 1, 0}, max {α, 1} = max {α + 1, 0}, 1
Para α < −1 temos (0, 1); para α ∈ [−1, 0] temos (α + 1, 1), que
é o segmento de reta usual que liga (0, 1) ao ponto (1, 1).
Portanto nesse caso o segmento max-plus é na verdade
a união de dois segmentos de reta.
Os exemplos acima nos sugerem que os segmentos maxplus são de fato formados por segmentos de reta de inclinação 0,
7.2. Convexidade Max-Plus
59
1 ou +∞ (ou seja, um segmento vertical); efetivamente é isso o
que ocorre, mas não provaremos esta afirmação.
Definição 7.2. Um conjunto C é dito convexo se para todo par
de elementos x e y pertencentes a C temos que o segmento maxplus [x, y] está contido em C.
Abaixo temos alguns exemplos de conjuntos convexos
no sentido max-plus.
Exemplo 7.4. O conjunto
A = {(x, y) : 0 ≤ x ≤ y}
De fato, se x e y estão na mesma vertical então o segmento [x, y] é o segmento de reta vertical que os liga, que está
em A. Se não estão na mesma vertical então imagine, sem perda
de generalidade, que x1 < y1 . Se x2 = y2 então o segmento que
os liga é um segmento de reta horizontal, que está contido em
A. Se x2 < y2 o segmento max-plus que os liga é uma união de
dois segmentos de reta, um horizontal e outro de inclinação 1,
estando assim contido em A. Por fim, se x2 > y2 o segmento
max-plus que os liga é uma união de um segmento de reta horizontal com outro vertical, ambos então contidos em A. Assim os
segmentos que unem dois pontos do conjunto estão no conjunto,
mostrando que o mesmo é efetivamente convexo.
De forma similar podemos mostrar que também é convexo o conjunto seguinte:
Exemplo 7.5.
Ba = {(x, y) : 0 ≤ x ≤ a, 0 ≤ y}
60
Capítulo 7. Conjuntos Convexos
(onde a é um número real positivo)
Um fato cuja prova é simples (e é, com pequenas adaptações, exatamente a prova já apresentada no caso anterior) é o
seguinte:
Lema 7.2. A interseção de dois conjuntos convexos é também
um convexo.
Desta forma podemos dar mais um exemplo de conjunto
convexo, a saber:
Exemplo 7.6.
C = A ∩ Ba
que corresponde à região delimitada pelo triângulo de vértices
(0, 0), (a, 0) e (a, a).
Exercícios
1) Obtenha o segmento max-plus que conecta os pontos (0, 0)
e (1, 2). Faça o mesmo com os pontos (0, 0) e (2, 1).
2) Prove que a interseção de dois conjuntos convexos maxplus é também um convexo max-plus.
3) Considere os pontos (x1 , x2 ) e (y1 , y2 ), com x1 < y2 . Vamos
considerar dois casos:
a) x2 > y2 : nessa situação, mostre que o segmento que liga
esses pontos é uma união de um segmento horizontal com
um segmento vertical.
b) x2 = y2 : nesse caso, mostre que o segmento que liga
esses pontos é um segmento de reta horizontal.
61
Referências
[1]
A. T. BARAVIERA, R. LEPLAIDEUR e A. LOPES, Ergodic optmization, zero temperature limits and the maxplus algebra, 29 Colóquio Brasileiro de Matemática - IMPA,
2013.
[2]
E. BRUGALLÉ, Um pouco de geometria tropical, Revista
Matemática Universitária, 46 (2009)27-40.
[3]
K. FARLOW, Max-Plus Algebra, Dissertação de Mestrado,
Virginia Polytechnic Institute and State University, 2009.
[4]
E. GARIBALDI e J. T. A. GOMES, Otimização de médias
sobre grafos orientados, 29 Colóquio Brasileiro de Matemática - IMPA, 2013.
[5]
C. S. HONIG, Aplicações da topologia à análise, Projeto
Euclides - IMPA, 1976