Embed Size (px)
Citation preview
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-PlusIII Colóquio de Matemática da Região Sul
Minicurso apresentado no IIIColóquio de Matemática da Re-gião Sul, realizado na Universi-dade Federal de Santa Catarina,em maio de 2014.
Florianópolis, SC
2014
". . . e a vida o que é?diga lá meu irmão
ela é a batidade um coração . . . "
(Luiz Gonzaga Júnior)
Ao Pedro
Resumo
Nesse texto introduzimos a álgebra max-plus, motivando breve-mente a teoria e apresentando seus aspectos mais elementares;os conceitos de autovetor e autovalor são apresentados nesse con-texto 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) . . . . . . . . . 37Figura 2 – Gráfico de q(x) = −2⊕(1⊗x)⊕(−1⊗x⊗x⊗x) 38Figura 3 – Gráfico de r(x) = (−1⊗ x)⊕ (x⊗ x) . . . . . 39Figura 4 – Região max-plus (x⊗ x)⊕ (y ⊗ y) = 1 . . . . 48Figura 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
6.3 Forma Quadrática em R̄n . . . . . . . . . . . . 49
6.4 Outra Forma de Definir Regiões . . . . . . . . 50
7 Conjuntos Convexos . . . . . . . . . . . . . . 55
7.1 Convexidade em R2 . . . . . . . . . . . . . . . 557.2 Convexidade Max-Plus . . . . . . . . . . . . . 56
Referências . . . . . . . . . . . . . . . . . . . 61
11
Introdução
Estas notas têm o objetivo de servir de apoio ao mini-curso Introdução à Álgebra Max-Plus ministrado no III Colóquiode Matemática da Região Sul realizado na Universidade Federalde Santa Catarina - UFSC, em Florianópolis. Não sendo especi-alistas 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 leito-res procurem depois bibliografia mais especializada e possam seaprofundar nesse rico assunto se sua curiosidade for despertadapor essas poucas linhas. Um texto básico interessante é [3]; paraalgumas aplicações o leitor pode consultar, por exemplo, [1] e [4].Por fim, uma outra sugestão é visitar a página maxplus.org queapresenta uma série de referências sobre o assunto, em diversosníveis de complexidade.
Agradecemos aos organizadores do evento, em especiala Artur Lopes, pela oportunidade de apresentar esse mini-curso.
Todo texto está longe de ser perfeito e esse não é umaexceção; o leitor que quiser nos comunicar erros, fazer comentá-rios ou apenas discutir um pouco dos assuntos aqui apresentadospode entrar em contato por meio de nossos endereços eletrônicos
[email protected] [email protected].
A. T. Baraviera Flávia M. Branco
13
1 Motivação
A álgebra max-plus é basicamente a álgebra dos núme-ros 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 aintrodução desse objeto matemático, algumas vindo da área depesquisa operacional, como veremos a seguir.
1.1 Tempo de Tarefas Combinadas
Vamos imaginar, por exemplo, que em uma fábrica umdeterminado trabalhador i precisa esperar a conclusão das ta-refas de dois de seus colegas, j e k, de forma a poder realizarsua parte do trabalho. Imagine que j leva um tempo Tij paraconcluir e entregar sua tarefa a i e k leva um tempo Tik paratambém concluir e entregar sua tarefa a i. Já i, para realizar suaprópria tarefa, gasta um tempo ai. Qual é o tempo total envol-vido no trabalho? Como i precisa esperar pelo trabalho de j e kpara só então executar sua tarefa temos que o tempo total nessecaso será ai + max {Tij , Tik}. Na notação introduzida acima issopode ser reescrito como ai ⊗ (Tij ⊕ Tik). Se agora consideramosum conjunto maior de trabalhadores, é possível utilizar o mesmoformalismo para determinar o tempo total de execução de umtrabalho e isso permite, entre outras coisas, estudar melhor oprocesso de forma a torná-lo, por exemplo, mais eficiente comoum todo.
14 Capítulo 1. Motivação
1.2 Ganho com Tarefas Repetidas
Imaginemos que numa dada situação certas tarefas se-jam executadas em sequência e o ganho depende da ordem emque isso é feito. A informação do ganho pode então ser traduzidanuma matriz A onde cada entrada Aij significa exatamente o ga-nho quando uma certa tarefa inicial i é seguida de outra tarefaj, ambas escolhidas em uma lista com d opções.
Nesse caso, sabendo que devemos começar com uma ta-refa i, executar alguma tarefa k e terminar com a execução dej, qual é o ganho total? Claramente é dado por
Aik +Akj = Aik ⊗Akj
E de que forma podemos escolher a tarefa intermediáriak de forma a maximizar o ganho? Nesse caso queremos
maxk{Aik +Akj} = max
k{Aik ⊗Akj} =
⊕k
Aik ⊗Akj
Como o leitor verá no capítulo sobre a álgebra linear max-plus,isso corresponde exatamente a entrada ij do produto matricialAA (no sentido max-plus).
Naturalmente podemos fazer a mesma pergunta com q
tarefas intermediárias k1, k2, . . . , kq:
maxk1,k2,...,kq
{Aik1+Ak1k2
+ · · ·+Akqj} =
= maxk1,k2,...,kq
{Aik1⊗Ak1k2
⊗ · · · ⊗Akqj}
=⊕
k1,k2,...,kq
Aik1 ⊗Ak1k2 ⊗ · · · ⊗Akqj
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-pluscorresponde ao problema de se maximizar o ganho num processocomo o descrito acima.
1.3 Crescimento Exponencial de Funções Reais
De um ponto de vista puramente matemático, podemosver essa álgebra como, por exemplo, a estrutura básica que des-creve o crescimento exponencial de funções reais. Mais precisa-mente: dada uma função h : R→ R, tal que h(x) > 0, definimoso crescimento exponencial de h como sendo o limite (claro, nasituação em que o referido limite existe)
e(h) = limx→+∞
1
xlog h(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 oleitor a obter e(x2eax). 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 paraqualquer potência de x, o que é uma tradução precisa do fatoque muitas vezes é lembrado na afirmação (nada incomum numcurso de cálculo) de que uma potência cresce mais lentamenteem função de x do que uma função exponencial.
Exemplo 1.1. Qual é o crescimento exponencial da função realf(x) = exsen x? Nesse caso
1
xlog f(x) =
1
xxsenx = senx
16 Capítulo 1. Motivação
Bem, a função senx não tem um limite quando x → +∞ (poisfica sempre oscilando entre −1 e +1). Portanto nesse caso nãofaz sentido falar em e(f).
Então podemos agora, supondo f e g funções para asquais e(f) e e(g) estão bem definidos, indagar qual é o cresci-mento exponencial de fg ou f + g? Voltando aos nossos exem-plos, note que (fg)(x) = eaxebx = e(a+b)x e assim temos que afunção fg cresce exponencialmente com uma taxa a+ b, ou seja,e(f)+e(g). Portanto e(fg) = 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, massim 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)
ee(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)) = limx→∞
1
xlog f(x)g(x)
= limx→∞
1
xlog f(x) +
1
xlog g(x)
= limx→∞
1
xlog f(x) + lim
x→∞
1
xlog g(x)
= e(f) + e(g) = e(f)⊗ e(g)
1.3. Crescimento Exponencial de Funções Reais 17
Para a segunda igualdade, vamos esboçar as principaisideias da prova. Como e(f) e e(g) estão bem definidos, podemospensar que, para valores suficientemente grandes de x, f(x) =
Cfee(f)x e g(x) = Cge
e(g)x onde Cf e Cg são tais que
limx→∞
1
xlog (Cf (x)) = 0 e lim
x→∞
1
xlog (Cg(x)) = 0
Vamos assumir, sem perda de generalidade que e(f) ≥ e(g).Então:
e(f + g) = limx→∞
1
xlog (f(x) + g(x))
= limx→∞
1
xlog (Cfe
e(f)x + Cgee(g)x)
= limx→∞
1
xlog
(Cfe
e(f)x(
1 + (Cg/Cf )e(e(g)−e(f))x))
= limx→∞
1
xlog ee(f)x = e(f) = max {e(f), e(g)}
= e(f)⊕ e(g)
como afirmamos.
Exercícios
1) Obtenha o crescimento exponencial e(f) (se este estiverdefinido) para as seguintes funções:
a) f(x) = e5x+sen (x)
b) f(x) = 3x25x
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çõesbinárias + e · tais que:
1 - (S,+) é um monóide comutativo com elemento iden-tidade 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, ouseja:
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 nopróprio elemento identidade de +:
i) 0 · a = a · 0 = 0
Se o leitor deseja ver um exemplo de semianel então po-demos 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 Rum conjunto ainda mais especial, uma estrutura que é chamadade anel. Portanto, ainda que esse seja um exemplo de semianel,podemos dar um exemplo mais genuíno, no sentido que em quenão é um anel (ou seja, basicamente não tem a propriedade dooposto), 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 aconvençã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, mostrandoque −∞ é o elemento neutro para a operação binária ⊕. Alémdisso, 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 todoa ∈ R̄, mostrando que 0 é o elemento neutro da mesma. Deixa-mos como exercício para o leitor verificar as demais propriedadesdas operações ⊕ e ⊗.
Desta forma, definimos a álgebra max-plus como sendoo semianel munido das operações ⊕ e ⊗ sobre o conjunto de reaisestendidos R̄.
Algumas das principais propriedades dessa álgebra estãoresumidas 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 únicob 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 cadaa real podemos tomar b = −a (o que ocorreria se a = −∞?) eentão
a⊗ b = a+ (−a) = 0.
Note que o elemento −∞ não tem oposto; exatamentepor isso esse conjunto, dotado dessas operações, não é um anel(e assim temos um exemplo mais legítimo, que é semianel masque 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 álgebralinear quando produto e adição usuais são trocados por suasversõ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
v =
v1
v2...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 escritocomo
(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 é linearse
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ãonão é difícil verificar que f é linear.
O exemplo acima, na verdade, é a forma geral de umafunção linear do espaço R̄2 em R̄, como mostramos no lemaabaixo.
Lema 3.1. Uma função f : R̄2 → R̄ é linear se e somente sef(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, umarranjo de m colunas e n linhas.
Dadas duas matrizes m × n A e B, definimos a somamatricial 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 λ ⊗ Acomo 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 asseguintes 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 de-mais 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, paraqualquer 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 matrizn× l denotada por B definimos o produto matricial A⊗B comosendo a matriz m× l cujas entradas são
(A⊗B)ij =⊕k
(Aik ⊗Bkj) = maxk
(Aik +Bkj) .
Algumas propriedades básicas do produto matricial es-tão listadas no resultado abaixo.
Lema 3.3. Sejam A uma matriz m× n, B uma matriz n× p eC 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 consideraras 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⊕l=1
((A⊗B)il ⊗ Clj
)= max
l∈{1,··· ,p}
((A⊗B)il + Clj
)
= maxl∈{1,··· ,p}
(max
k∈{1,··· ,n}
(Aik +Bkl
)+ Clj
)
= maxl∈{1,··· ,p}
(max
k∈{1,··· ,n}
(Aik +Bkl + Clj
))
= maxk∈{1,··· ,n}
(max
l∈{1,··· ,p}
(Aik +Bkl + Clj
))
= maxk∈{1,··· ,n}
(Aik + max
l∈{1,··· ,p}
(Bkl + Ckl
))
=
n⊕k=1
(Aik ⊗ (B ⊗ C)kj
)= (E)ij
Pelo lema 3.2 temos que λ⊗(A⊗B) = (A⊗B)⊗λ então,para provarmos 2, basta mostrarmos que λ⊗(A⊗B) = A(λ⊗B).(
λ⊗ (A⊗B))ij
= λ+ (A⊗B)ij = λ+ maxk
(Aik +Bkj
)= max
k
(Aik + λ+Bkj
)=(A(λ⊗B)
)ij
Para mostrar 3, vamos verificar que:(A⊗ (B ⊕ C)
)ij
= maxk
(Aik + max(Bkj , Ckj)
)= max
k(Aik +Bkj , Aik + Ckj)
=(
(A⊗B)⊕ (A⊗ C))ij
3.3. Matrizes 29
Se m = n dizemos que a matriz A é uma matriz qua-drada de ordem n. Considere a matriz
In =
0 −∞ −∞ . . . −∞−∞ 0 −∞ . . . −∞...
......
......
−∞ −∞ . . . −∞ 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:
a)
[1 3
4 2
]⊗
[0
4
]
b)
[0
4
]⊕
[3
2
]
c)
[−1 −∞2 −4
]⊗
([0 1
−1 −∞
]⊕
[4 2
−∞ 1
])
d)
−∞ 0 0
1 −∞ 0
1 1 −∞
⊗ 0 −∞
0 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 nadamais é do que uma matriz n× 1).
Da definição de produto matricial temos que a matrizA⊗ v, de ordem n× 1, assume a forma:
(A⊗ v)i =⊕j
(Aij ⊗ vj) = maxj
(Aij + vj).
Dado λ ∈ R̄ temos também que
λ⊗ v = (λ⊗ v1, . . . , λ⊗ vn) = (λ+ v1, . . . , λ+ vn).
Nesse contexto uma questão totalmente natural é a pro-cura de autovalores e autovetores de A no sentido max-plus, ouseja, soluções da equação A⊗ v = λ⊗ v. Essa equação pode sertraduzida, em termos das operações usuais, como sendo
maxj
(Aij + vj) = λ+ vi para todo i = 1, . . . , n.
Exemplo 4.1.[1 0
0 1
]⊗
[0
−1
]=
[max (1,−1)
max (0, 0)
]=
[1
0
]= 1⊗
[0
−1
].
Temos também[1 0
0 1
]⊗
[−1
0
]=
[max (0, 0)
max (−1, 1)
]=
[0
1
]= 1⊗
[−1
0
].
32 Capítulo 4. Autovalores e Autovetores Max-Plus
Nesse caso vemos que 1 é um autovalor da matriz asso-ciado 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, dentrode nossos objetivos, é que matrizes com entradas reais tem umúnico autovalor no sentido max-plus. Para provar isso usaremosuma ferramenta muito importante, o Teorema do Ponto Fixo deBrower, que recordamos a seguir. Para uma demonstração desteresultado, 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 menosum ponto p ∈ C tal que f(p) = p.
De posse desse resultado podemos então provar nossoprincipal teorema nesse capítulo:
Teorema 4.2. Seja A uma matriz d× d com todas as entradasAij ∈ 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
α⊗M =
α+M11 α+M12 · · · α+M1d
α+M21 α+M22 · · · α+M2d
......
......
α+Md1 · · · · · · α+Mdd
Portanto, não perdemos em generalidade ao supor que todas asentradas da matriz A são maiores ou iguais a zero. Assim, temosque
0 ≤ Aij ≤ L.
Agora vamos introduzir uma função T : Rd → Rd definida deforma que
(Tx)i = maxj
(Aij + xj)−mink
maxj
(Akj + xj).
Não é difícil verificar que esta expressão depende continuamentedo vetor x. Também segue diretamente da definição que (Tx)i ≥0. Por outro lado, temos
(Tx)i ≤ maxj
(L+ xj)−mink
maxj
(0 + xj)
≤ maxj
(L+ xj)−maxj
(xj) = L.
Em particular, isso mostra que a região do espaço {x =
(x1, x2, · · · , xd) ∈ Rd : 0 ≤ xj ≤ L para todo j} tem comoimagem pela função T um subconjunto dela mesma; como T éuma função contínua isso implica (como consequência direta doteorema de ponto fixo de Brower) que T tem ao menos um pontofixo v. Portanto
v = T (v)⇒ vi = (Tv)i = maxj
(Aij + vj)−mink
maxj
(Akj + vj).
34 Capítulo 4. Autovalores e Autovetores Max-Plus
Se denotamosλ = min
kmax
j(Akj + vj),
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 µ. Emoutras 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 porA2 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 grandede t, tal que, t⊗ v ≥ u (no sentido de que t⊗ vi ≥ ui, para cadai ∈ {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 ladosdesta desigualdade são valores positivos e, portanto, existirá umn 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 matrizsão todas reais (ou seja, se permitimos que ao menos uma de-las seja −∞) então a situação é bem diferente. Considere, porexemplo,
A =
1 1 −∞ −∞1 1 −∞ −∞−∞ −∞ 2 2
−∞ −∞ 2 2
.
Então não é muito difícil ver que
A⊗
−∞−∞
1
1
=
−∞−∞
3
3
= 2⊗
−∞−∞
1
1
,e que
A⊗
1
1
−∞−∞
=
2
2
−∞−∞
= 1⊗
1
1
−∞−∞
.
36 Capítulo 4. Autovalores e Autovetores Max-Plus
Logo, 1 and 2 são autovalores max-plus de A, mostrando quea unicidade dos autovalores não vale mais quando admitimosmatrizes com entradas −∞.
Exercícios
1) Obtenha o autovalor max-plus (e respectivos autovetores)das seguintes matrizes:
a)
[−3 −∞−∞ 1
]
b)
[4 0
0 2
]
37
5 Polinômios Max-Plus
Nesse capítulo faremos um breve estudo de polinômiosno mundo max-plus.
Um polinômio max-plus p : R̄ → R̄ de grau d é umafunçã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 daseguinte forma p(x) = max{2, 3 + x}. Destacamos o gráfico dep(x) na figura 1.
-4 -3 -2 -1 0 1 2 30
1
2
3
4
5
6 y
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 figura2.
-5 -4 -3 -2 -1 0 1 2 3
-3
-2
-1
0
1
2
3
4
5
6 y
x
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 maiorgrau não está escrito mas é zero, o elemento identidade para aoperação ⊗ e não o 1, como na operação multiplicação usual. Damesma 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
-4 -3 -2 -1 0 1 2 3
-4
-3
-2
-1
0
1
2
3
4 y
x
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 maiorou 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 - limx→−∞
p(x) = a0
5 - limx→∞
p(x) = +∞
40 Capítulo 5. Polinômios Max-Plus
Demonstração. Seja d o grau do polinômio max-plus p(x). Cadauma das funções a0, a1 + x, a2 + 2x, . . . , ad + dx presentes nadefinição de p(x) é contínua (de fato diferenciável). Desta formap(x) é uma função contínua, por ser o máximo entre funçõescontínuas, e também é não-decrescente por ser o máximo entrefunções não-decrescentes.
Para mostrarmos o item 3 basta observarmos que, sea0 6= −∞, o polinômio p(x) passa a ser estritamente crescentequando o máximo entre as funções deixa de ser o termo constantea0. 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 temosque:
x ≥ x0 ⇒ ai + ix ≥ a0 e p(x) ≥ ai + ix
que é uma função estritamente crescente. Se a0 = −∞, estetermo será sempre menor que qualquer outro termo ai + ix eeste polinômio será estritamente crescente para todo x ∈ R.
Quando consideramos valores de x muito pequenos (ouseja, próximos de −∞) então todos os termos com x se tornammuito pequenos e assim o máximo entre eles acaba sendo o termoconstante a0, o que mostra o item 4.
Quando escolhemos valores de x suficientemente gran-des, os termos com x claramente se tornam maiores do que a0;de fato cada um deles vai a +∞ e portanto seu máximo tambémvai 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 podemosimaginar que, de fato, só temos três casos possíveis: nenhumaraiz, uma única raiz ou infinitas raízes. Isso é deixado claro nopró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 = −∞. En-tã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 quep(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, seo grau de p(x) é maior ou igual a 1, estamos na situação em quehá exatamente uma raiz pois, pelos itens 3 e 5 do teorema 5.1,p(x) é estritamente crescente a partir de um ponto x0 e tendea +∞ quando x tende a +∞. Entretanto, se o grau de p(x) forzero, isto é, se p(x) = a0 < 0, então este polinômio não possuiraiz.
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) queremossaber em que pontos temos p(x) = q(x).
Uma observação básica é que podemos, em princípio, terum número infinito de interseções. Considere, por exemplo, ospolinômios p(x) = 1⊕x e q(x) = 1⊕ (x⊗x). Nesse caso, quandox < 1/2 ambos valem 1, e então todo ponto x < 1/2 é umponto de interseção desses dois polinômios. Porém é muito fácilmodificar completamente essa situação: bastaria, por exemplo,considerar o polinômio r(x) = 0, 99999 ⊕ (x ⊗ x) no lugar deq(x). Ou seja, uma pequena perturbação em um dos coeficientesfaz com que as infinitas interseções desapareçam. De uma certaforma o caso p(x) e q(x) é um tipo de caso degenerado, quenão pretendemos abordar, mas uma pequena perturbação de umcaso desses nos leva a p(x) e r(x), que é a situação mais geral einteressante, para a qual é possível estabelecer uma cota para onú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çãop(x) = q(x) é um elemento do conjunto {0, 1, . . . , P ⊕Q}.
Demonstração. Por simplicidade, vamos considerar que os coe-ficientes dos polinômios p e q não assumem o valor −∞. Consi-dere o polinômio p. Vamos definir uma divisão da reta em pontosp1, p2, . . . , pP de forma que, no intervalo [−∞, p1], p(x) tem in-clinação zero, no intervalo [p1, p2], p(x) tem inclinação 1 e assimsucessivamente, até que em [pP ,+∞) p(x) tem inclinação P . Deforma 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ômiosmax-plus, temos que a primeira interseção entre os polinômiosnão pode ocorrer em um ponto em [−∞, p1) e [−∞, q1), ou seja,pontos de I0 ∩ J0, pois se isso ocorresse, como ambos são cons-tantes nessas regiões, então teríamos uma infinidade de pontosem comum nos gráficos. De fato o mesmo argumento mostra quenão podemos ter interseção dos gráficos em nenhum ponto quepertença a um conjunto do tipo Ii ∩ Ji.
Consideremos então os intervalos na forma Ii ∩ Jj ; va-riando os índices i e j podemos ver que todos os pontos da retaestão em algum desses conjuntos. O intervalo que está mais aesquerda é, claro, I0 ∩ J0. Um intervalo do tipo Ii ∩ Jj pode serseguido por Ii+1 ∩ Jj (se o extremo de Ii está dentro de Jj ), ouIi ∩ 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 podeser resumida na seguinte notação: vamos identificar o conjuntoIi ∩ Jj com o par ordenado (i, j). Então o par (i, j) só pode serseguido 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 retacomeça com (0, 0) (correspondente a I0∩J0 e continua seguindoa regra acima até chegar ao intervalo (P,Q).
44 Capítulo 5. Polinômios Max-Plus
Dentre esses intervalos, onde podemos ter as interseçõesdos gráficos? Já sabemos que isso não pode ocorrer em nenhumdos intervalos do tipo (i, i). Imagine que temos a primeira inter-seçã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 quevoltem a se cruzar é preciso que q comece a crescer mais rápidodo que p, o que significa que o novo cruzamento só pode ocorrerquando tivermos um novo par (i1, j1) com j1 maior que i1. Deforma similar, se i0 é menor do que j0 então o proximo possívelcruzamento só poderá ocorrer num novo par (i1, j1) tal que i1 émaior do que j1.
Portanto é preciso haver uma certa inversão na ordemdos pares para que possamos ter cruzamentos dos gráficos. In-verter 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) (0, 1) (0, 2) . . . (0, Q)
(1, 0) → (1, 1) → (1, 2) . . . (1, Q)
↓(2, 0) (2, 1) (2, 2) . . . (2, Q)
↓(3, 0) (3, 1) (3, 2) → . . . (3, Q)...
......
......
(P, 0) (P, 1) . . . . . . (P,Q)
ou seja, um caminho que serpenteia em torno da diagonal. Su-ponha 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 onúmero de pares que podem corresponder a cruzamentos é deQ = max{P,Q}, o que conclui a prova.
5.3 Polinômios Min-Plus
Existem algumas variações da álgebra max-plus, umadelas sendo a álgebra min-plus onde consideramos a operação⊕ dada por a ⊕ b = min{a, b}. Nesta álgebra, consideramos oconjunto R com a inclusão de +∞. Esta álgebra também é co-nhecida 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 umcerto sentido, parecidos com os estudados na álgebra max-plusmas com a diferença que as inclinações dos segmentos de retaque o compõem vão diminuindo, ao contrário do que acontecequando consideramos o máximo. A investigação geométrica des-ses objetos é conhecida como geometria tropical; o leitor interes-sado 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 aequaçã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 dep(x) e m(x) e p(x) e s(x) onde p(x) é o primeiro exem-plo 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) umaforma quadrática sobre uma determinada região, por exemploum círculo, o que é um exemplo de problema de maximizaçãocom vínculos. Neste capítulo desejamos apresentar o equivalentemax-plus desse problema.
6.1 Definindo Regiões
Vamos considerar o equivalente max-plus de uma equa-ção como x2 + y2 = 1, que define um círculo de raio unitário noplano 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 escritascomo
R = {x = 1/2, y ≤ 1/2} ∪ {y = 1/2, x ≤ 1/2} (6.1)
e podem ser conferidas na figura 4.
48 Capítulo 6. Formas Quadráticas Max-Plus
-2 -1 0 1 2
-2
-1
0
1
2 y
x
b
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 → Rdefinida a partir de uma transformação linear A : R2 → R2 daseguinte forma:
q(x1, x2) = [x1x2]A
[x1
x2
]= a11x
21 + (a12 + a21)x1x2 + a22x
22
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 con-junto 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ãodefinida em 6.1 então
maxx∈R{Q(x)} = 1 + max
1≤i,j≤2{aij}
Demonstração. Temos que o ponto (1/2, 1/2) ∈ R eQ(1/2, 1/2) =
1 + max1≤i,j≤2
{aij}. Naturalmente, maxx∈R{Q(x)} ≥ Q(1/2, 1/2).
Mas para um ponto x = (x1, x2) qualquer na região Rtemos 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) eportanto 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) = xTAx = maxi,j∈I
{aij + xi + xj}
onde I = {1, · · · , n}.
Consideremos a região R definida por
maxi∈I{kxi} = 1
onde k é uma constante tal que k ∈ N e k > 1.
Observe que, se k = 2, temos uma generalização naturalda 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 ea R a região definida acima então
maxx∈R{Q(x)} =
2
k+ max
i,j∈I{aij}
Demonstração. O ponto (1/k, 1/k, . . . , 1/k) ∈ R e
Q
(1
k,
1
k, . . . ,
1
k
)=
2
k+ max
i,j∈I{aij},
portanto
maxx∈R{Q(x)} ≥ 2
k+ max
i,j∈I{aij}
Por outro lado, dado um x qualquer em R temos
Q(x) = maxi,j∈I
{aij + xi + xj}
≤ maxi,j∈I
{aij +
1
k+
1
k
}=
2
k+ max
i,j∈I{aij}
=⇒ maxx∈R{Q(x)} ≤ 2
k+ max
i,j∈I{aij}
e o lema esta provado.
6.4 Outra Forma de Definir Regiões
Agora apresentaremos uma outra forma de definir cur-vas; embora pareça menos natural que a anterior, de fato essaforma é a mais usada no contexto max-plus.
Começamos com um exemplo: queremos saber qual é aregiã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 aregiã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.
-2 -1 0 1 2 3
-1
0
1
2
y
x
b
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 assu-mindo o valor −∞ então esta equação não determina uma regiãopois não teremos o máximo atingido em dois pontos. No entanto,se a = b = c = −∞ então o máximo é atingido sempre, paraquaisquer valores de x e y determinando o próprio R̄2. Sendo as-sim, excetuando o caso particular onde a = b = c = −∞, temosque 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⊗ ym)⊕ 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çãodo círculo de raio 1 no plano xy determina nesta nova acepção.Observe que x2 + y2 − 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 dey ficando arbitrariamente pequenos (isto é, próximos de −∞) etambém muito grandes (ou seja, próximos de +∞. Desta formamaximizar ou minimzar expressões nessa região é algo que tipi-camente 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 qual-quer ponto de R na forma (−5, y).
55
7 Conjuntos Convexos
Vamos aqui rapidamente recordar o importante conceitode conjunto convexo; como estamos mais interessados nas ideiasprincipais e não em fazer uma teoria absolutamente geral, vamosnos 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 retacujas 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 paratodo 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 es-forç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 aC1∩C2. Então o segmento [p1, p2] está contido em C1 e tambémestá contido em C2, pois ambos são convexos,mostrando que[p1, p2] está contido em C1∩C2. Isso nos leva à conclusão de queC1 ∩ C2 é convexo, como afirmado.
7.2 Convexidade Max-Plus
Vamos agora estender o conceito de convexidade parao conjunto R̄2. Em primeiro lugar, é preciso redefinir o conceitode 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 ligaos pontos (0, 0) e (1, 1). De acordo com a definição acima temosque 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] temosque o par é (β + 1, β + 1), o corresponde ao segmento de retausual 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 segmentomax-plus é de fato o mesmo que um segmento usual, mas issonão está correto.
Exemplo 7.3. Vamos encontrar o segmento max-plus [x, y] quandox = (1, 0) e y = (0, 1). Da definição queremos os pontos nosquais (
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 verdadea união de dois segmentos de reta.
Os exemplos acima nos sugerem que os segmentos max-plus 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 oque ocorre, mas não provaremos esta afirmação.
Definição 7.2. Um conjunto C é dito convexo se para todo parde elementos x e y pertencentes a C temos que o segmento max-plus [x, y] está contido em C.
Abaixo temos alguns exemplos de conjuntos convexosno 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 seg-mento [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 perdade generalidade, que x1 < y1. Se x2 = y2 então o segmento queos liga é um segmento de reta horizontal, que está contido emA. Se x2 < y2 o segmento max-plus que os liga é uma união dedois segmentos de reta, um horizontal e outro de inclinação 1,estando assim contido em A. Por fim, se x2 > y2 o segmentomax-plus que os liga é uma união de um segmento de reta hori-zontal com outro vertical, ambos então contidos em A. Assim ossegmentos que unem dois pontos do conjunto estão no conjunto,mostrando que o mesmo é efetivamente convexo.
De forma similar podemos mostrar que também é con-vexo 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 adap-tações, exatamente a prova já apresentada no caso anterior) é oseguinte:
Lema 7.2. A interseção de dois conjuntos convexos é tambémum convexo.
Desta forma podemos dar mais um exemplo de conjuntoconvexo, 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 max-plus é também um convexo max-plus.
3) Considere os pontos (x1, x2) e (y1, y2), com x1 < y2. Vamosconsiderar dois casos:
a) x2 > y2: nessa situação, mostre que o segmento que ligaesses pontos é uma união de um segmento horizontal comum segmento vertical.
b) x2 = y2: nesse caso, mostre que o segmento que ligaesses pontos é um segmento de reta horizontal.
61
Referências
[1] A. T. BARAVIERA, R. LEPLAIDEUR e A. LOPES, Er-godic optmization, zero temperature limits and the max-plus algebra, 29 Colóquio Brasileiro de Matemática - IMPA,2013.
[2] E. BRUGALLÉ, Um pouco de geometria tropical, RevistaMatemá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édiassobre grafos orientados, 29 Colóquio Brasileiro de Matemá-tica - IMPA, 2013.
[5] C. S. HONIG, Aplicações da topologia à análise, ProjetoEuclides - IMPA, 1976
