Polígonos, Poliedros e Polítopos
Teorema de Yannakakis
João Gouveia
CMUC - Universidade de Coimbra
17 de Março de 2012 - Oráculo Delfos - Coimbra
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
1 / 29
1. Geometria Convexa
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
2 / 29
Convexidade
Um conjunto S ⊆ Rn é convexo se dados quaisquer dois pontos de S
o segmento que os une estiver contido em S.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
3 / 29
Convexidade
Um conjunto S ⊆ Rn é convexo se dados quaisquer dois pontos de S
o segmento que os une estiver contido em S.
Conjunto Convexo
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
3 / 29
Convexidade
Um conjunto S ⊆ Rn é convexo se dados quaisquer dois pontos de S
o segmento que os une estiver contido em S.
Conjunto Convexo
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
3 / 29
Convexidade
Um conjunto S ⊆ Rn é convexo se dados quaisquer dois pontos de S
o segmento que os une estiver contido em S.
Conjunto Convexo
João Gouveia (UC)
Conjunto Não Convexo
Teorema de Yannakakis
Oráculo Delfos
3 / 29
Polígonos Convexos
Como definir Polígono Convexo?
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
4 / 29
Polígonos Convexos
Como definir Polígono Convexo?
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
4 / 29
Definição por Vértices
Dado um número finito de pontos S no plano, um polígono convexo é
o mais pequeno conjunto convexo que os contém.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
5 / 29
Definição por Vértices
Dado um número finito de pontos S no plano, um polígono convexo é
o mais pequeno conjunto convexo que os contém.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
5 / 29
Definição por Vértices
Dado um número finito de pontos S no plano, um polígono convexo é
o mais pequeno conjunto convexo que os contém.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
5 / 29
Definição por Vértices
Dado um número finito de pontos S no plano, um polígono convexo é
o mais pequeno conjunto convexo que os contém.
O polígono designa-se por invólucro convexo de S, conv(S).
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
5 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Definição por Semiplanos
Um polígono convexo é um conjunto limitado obtido por intersecção
de semiplanos.
As duas definições são equivalentes.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
6 / 29
Exemplo: Quadrado
Consideremos o quadrado unitário.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
7 / 29
Exemplo: Quadrado
Consideremos o quadrado unitário.
Vértices:
É o invólucro convexo dos
pontos
(0, 0), (1, 0), (0, 1) e (1, 1).
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
7 / 29
Exemplo: Quadrado
Consideremos o quadrado unitário.
Vértices:
Semiplanos:
É o invólucro convexo dos
pontos
(0, 0), (1, 0), (0, 1) e (1, 1).
É a intersecção dos
semiplanos dados por
x ≥ 0, y ≥ 0, 1 − x ≥ 0 e
1 − y ≥ 0.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
7 / 29
Poliedros Convexos
E para definir Poliedros Convexos?
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
8 / 29
Poliedros Convexos
E para definir Poliedros Convexos?
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
8 / 29
Poliedros Convexos
E para definir Poliedros Convexos?
As mesmas ideias funcionam, trocando pontos no plano por pontos no
espaço e semiplanos por semi-espaços.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
8 / 29
Exemplo: Tetraedro
Consideremos o tetraedro unitário.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
9 / 29
Exemplo: Tetraedro
Consideremos o tetraedro unitário.
Vértices:
É o invólucro convexo dos
pontos
(0, 0, 0), (1, 0, 0), (0, 1, 0) e
(0, 0, 1).
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
9 / 29
Exemplo: Tetraedro
Consideremos o tetraedro unitário.
Vértices:
Semiplanos:
É o invólucro convexo dos
pontos
(0, 0, 0), (1, 0, 0), (0, 1, 0) e
(0, 0, 1).
É a intersecção dos
semiplanos dados por
x ≥ 0, y ≥ 0, z ≥ 0 e
1 − x − y − z ≥ 0.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
9 / 29
E em Rn ?
Tudo o que dissemos funciona em qualquer dimensão. Assim
podemos definir polítopo convexo:
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
10 / 29
E em Rn ?
Tudo o que dissemos funciona em qualquer dimensão. Assim
podemos definir polítopo convexo:
Definição por vértices
Um polítopo convexo P ⊆ Rn é o invólucro convexo de um número
finito de pontos em Rn .
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
10 / 29
E em Rn ?
Tudo o que dissemos funciona em qualquer dimensão. Assim
podemos definir polítopo convexo:
Definição por vértices
Um polítopo convexo P ⊆ Rn é o invólucro convexo de um número
finito de pontos em Rn .
Ou equivalentemente,
Definição por semi-espaços
Um polítopo convexo P ⊆ Rn é um conjunto limitado obtido pela
intersecção de semi-espaços, isto é, o conjunto de pontos (x 1 , · · · , x n )
verificando um número finito de desigualdades do tipo
a1 x 1 + a2 x 2 + · · · + an x n ≤ a0 .
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
10 / 29
Exemplos de polítopos
Dois exemplos de famílias simples de polítopos convexos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
11 / 29
Exemplos de polítopos
Dois exemplos de famílias simples de polítopos convexos.
n-cubo unitário
É o invólucro convexo de todos
os pontos em Rn cujas
componentes são zero ou um.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
11 / 29
Exemplos de polítopos
Dois exemplos de famílias simples de polítopos convexos.
n-cubo unitário
É o invólucro convexo de todos
os pontos em Rn cujas
componentes são zero ou um.
É o espaço cortado pelas
desigualdades
x1 ≥ 0, · · · , xn ≥ 0 e
1 − x1 ≥ 0, · · · , 1 − xn ≥ 0.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
11 / 29
Exemplos de polítopos
Dois exemplos de famílias simples de polítopos convexos.
n-cubo unitário
É o invólucro convexo de todos
os pontos em Rn cujas
componentes são zero ou um.
É o espaço cortado pelas
desigualdades
x1 ≥ 0, · · · , xn ≥ 0 e
1 − x1 ≥ 0, · · · , 1 − xn ≥ 0.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
11 / 29
Exemplos de polítopos
Dois exemplos de famílias simples de polítopos convexos.
n-cubo unitário
n-símplice unitário
É o invólucro convexo de todos
os pontos em Rn cujas
componentes são zero ou um.
É o invólucro convexo da
origem e dos n vectores
unitários canónicos em Rn .
É o espaço cortado pelas
desigualdades
x1 ≥ 0, · · · , xn ≥ 0 e
1 − x1 ≥ 0, · · · , 1 − xn ≥ 0.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
11 / 29
Exemplos de polítopos
Dois exemplos de famílias simples de polítopos convexos.
n-cubo unitário
n-símplice unitário
É o invólucro convexo de todos
os pontos em Rn cujas
componentes são zero ou um.
É o invólucro convexo da
origem e dos n vectores
unitários canónicos em Rn .
É o espaço cortado pelas
desigualdades
x1 ≥ 0, · · · , xn ≥ 0 e
1 − x1 ≥ 0, · · · , 1 − xn ≥ 0.
É o espaço cortado pelas
desigualdades
x1 ≥ 0, · · · , xn ≥ 0 e
1 − x1 − x2 − · · · − xn ≥ 0.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
11 / 29
Exemplos de polítopos
Dois exemplos de famílias simples de polítopos convexos.
n-cubo unitário
n-símplice unitário
É o invólucro convexo de todos
os pontos em Rn cujas
componentes são zero ou um.
É o invólucro convexo da
origem e dos n vectores
unitários canónicos em Rn .
É o espaço cortado pelas
desigualdades
x1 ≥ 0, · · · , xn ≥ 0 e
1 − x1 ≥ 0, · · · , 1 − xn ≥ 0.
É o espaço cortado pelas
desigualdades
x1 ≥ 0, · · · , xn ≥ 0 e
1 − x1 − x2 − · · · − xn ≥ 0.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
11 / 29
Faces e Facetas de Polígonos Convexos
Dado um polígono P um subconjunto ∅ ( F ( P é uma face própria
de P, se existir uma recta L tal que L ∩ P = F e P está todo do mesmo
lado da recta.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
12 / 29
Faces e Facetas de Polígonos Convexos
Dado um polígono P um subconjunto ∅ ( F ( P é uma face própria
de P, se existir uma recta L tal que L ∩ P = F e P está todo do mesmo
lado da recta.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
12 / 29
Faces e Facetas de Polígonos Convexos
Dado um polígono P um subconjunto ∅ ( F ( P é uma face própria
de P, se existir uma recta L tal que L ∩ P = F e P está todo do mesmo
lado da recta.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
12 / 29
Faces e Facetas de Polígonos Convexos
Dado um polígono P um subconjunto ∅ ( F ( P é uma face própria
de P, se existir uma recta L tal que L ∩ P = F e P está todo do mesmo
lado da recta.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
12 / 29
Faces e Facetas de Polígonos Convexos
Dado um polígono P um subconjunto ∅ ( F ( P é uma face própria
de P, se existir uma recta L tal que L ∩ P = F e P está todo do mesmo
lado da recta.
Tudo se pode generalizar para Rn substituindo rectas por hiperplanos.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
12 / 29
Faces e Facetas de Polígonos Convexos
Dado um polígono P um subconjunto ∅ ( F ( P é uma face própria
de P, se existir uma recta L tal que L ∩ P = F e P está todo do mesmo
lado da recta.
Tudo se pode generalizar para Rn substituindo rectas por hiperplanos.
Faces próprias de dimensão máxima dizem-se facetas.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
12 / 29
2. Programação Linear
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
13 / 29
Exemplo
Um criador de porcos pretende determinar as quantidades de cada
tipo de ração que devem ser dadas diariamente a cada animal por
forma a conseguir uma certa qualidade nutritiva a um custo mínimo.
Proteína
Vitamina
Hid. Carbono
Custo
João Gouveia (UC)
Ração A
20
50
30
10
Ração B
50
10
30
5
Teorema de Yannakakis
Quantidade Requerida
≥ 200
≥ 150
≤ 600
Oráculo Delfos
14 / 29
Exemplo
Um criador de porcos pretende determinar as quantidades de cada
tipo de ração que devem ser dadas diariamente a cada animal por
forma a conseguir uma certa qualidade nutritiva a um custo mínimo.
Proteína
Vitamina
Hid. Carbono
Custo
João Gouveia (UC)
Ração A
20
50
30
10
Ração B
50
10
30
5
Teorema de Yannakakis
Quantidade Requerida
≥ 200
≥ 150
≤ 600
Oráculo Delfos
14 / 29
Exemplo - Interpretação Geométrica
Proteína
Vitamina
Hid. Carbono
Custo
João Gouveia (UC)
Ração A
20
50
30
10
Ração B
50
10
30
5
Teorema de Yannakakis
Quantidade Requerida
≥ 200
≥ 150
≤ 600
Oráculo Delfos
15 / 29
Exemplo - Interpretação Geométrica
Ração A Ração B Quantidade Requerida
Proteína
20
50
≥ 200
Vitamina
50
10
≥ 150
Hid. Carbono
30
30
≤ 600
Custo
10
5
x→ Quantidade de Ração A
y → Quantidade de Ração B.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
15 / 29
Exemplo - Interpretação Geométrica
Ração A Ração B Quantidade Requerida
Proteína
20
50
≥ 200
Vitamina
50
10
≥ 150
Hid. Carbono
30
30
≤ 600
Custo
10
5
x→ Quantidade de Ração A
y → Quantidade de Ração B.
x ≥ 0 e y≥ 0
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
15 / 29
Exemplo - Interpretação Geométrica
Ração A Ração B Quantidade Requerida
Proteína
20
50
≥ 200
Vitamina
50
10
≥ 150
Hid. Carbono
30
30
≤ 600
Custo
10
5
x→ Quantidade de Ração A
y → Quantidade de Ração B.
20x + 50y ≥ 200
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
15 / 29
Exemplo - Interpretação Geométrica
Ração A Ração B Quantidade Requerida
Proteína
20
50
≥ 200
Vitamina
50
10
≥ 150
Hid. Carbono
30
30
≤ 600
Custo
10
5
x→ Quantidade de Ração A
y → Quantidade de Ração B.
50x + 10y ≥ 150
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
15 / 29
Exemplo - Interpretação Geométrica
Ração A Ração B Quantidade Requerida
Proteína
20
50
≥ 200
Vitamina
50
10
≥ 150
Hid. Carbono
30
30
≤ 600
Custo
10
5
x→ Quantidade de Ração A
y → Quantidade de Ração B.
30x + 30y ≤ 600
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
15 / 29
Exemplo - Interpretação Geométrica
Ração A Ração B Quantidade Requerida
Proteína
20
50
≥ 200
Vitamina
50
10
≥ 150
Hid. Carbono
30
30
≤ 600
Custo
10
5
x→ Quantidade de Ração A
y → Quantidade de Ração B.
Minimizar 10x + 5y
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
15 / 29
Exemplo - Interpretação Geométrica
Ração A Ração B Quantidade Requerida
Proteína
20
50
≥ 200
Vitamina
50
10
≥ 150
Hid. Carbono
30
30
≤ 600
Custo
10
5
x→ Quantidade de Ração A
y → Quantidade de Ração B.
x = 55/23,
João Gouveia (UC)
y = 70/23
Teorema de Yannakakis
Oráculo Delfos
15 / 29
Programa Linear - Definição
Programa Linear
Um Programa Linear (PL) é um problema do tipo
min c1 x 1 + c2 x 2 + · · · cn x n
sujeito a
a11 x 1 + a21 x 2 + · · · + an1 x n ≥ b1 ,
..
.
a1m x 1 + a2m x 2 + · · · + anm x n ≥ b2 .
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
16 / 29
Programa Linear - Definição
Programa Linear
Um Programa Linear (PL) é um problema do tipo
min c1 x 1 + c2 x 2 + · · · cn x n
sujeito a
a11 x 1 + a21 x 2 + · · · + an1 x n ≥ b1 ,
..
.
a1m x 1 + a2m x 2 + · · · + anm x n ≥ b2 .
Ou de outra forma:
Programa Linear (versão 2)
Um Programa Linear (PL) é um problema do tipo
min c1 x 1 + c2 x 2 + · · · cn x n
sujeito a x pertencer a um polítopo P.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
16 / 29
Programação Linear - Complexidade
Quão difícil é resolver um programa linear?
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
17 / 29
Programação Linear - Complexidade
Quão difícil é resolver um programa linear?
Complexidade
O tempo que demora a optimizar sobre um polítopo P, cresce
polinomialmente com o mínimo entre o número de facetas e o número
de vértices de P.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
17 / 29
Programação Linear - Complexidade
Quão difícil é resolver um programa linear?
Complexidade
O tempo que demora a optimizar sobre um polítopo P, cresce
polinomialmente com o mínimo entre o número de facetas e o número
de vértices de P.
Mas o que fazer quando P tem muitos vértices e facetas?
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
17 / 29
3. De Volta aos Polítopos
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
18 / 29
Projecções de Polítopos
A projecção de um polítopo P ∈ Rn para Rm , com m ≤ n é o conjunto
πm (P) = {(x 1 , · · · , x m ) : ∃(x 1 , · · · , x m , x m+1 , · · · , x n ) ∈ P}.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
19 / 29
Projecções de Polítopos
A projecção de um polítopo P ∈ Rn para Rm , com m ≤ n é o conjunto
πm (P) = {(x 1 , · · · , x m ) : ∃(x 1 , · · · , x m , x m+1 , · · · , x n ) ∈ P}.
Projecção do Cubo em R2 :
Quadrado
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
19 / 29
Projecções de Polítopos
A projecção de um polítopo P ∈ Rn para Rm , com m ≤ n é o conjunto
πm (P) = {(x 1 , · · · , x m ) : ∃(x 1 , · · · , x m , x m+1 , · · · , x n ) ∈ P}.
Projecção do Cubo em R2 :
Quadrado
João Gouveia (UC)
Projecção do Cubo em R2 :
Hexágono
Teorema de Yannakakis
Oráculo Delfos
19 / 29
Facetas e Projecções
A projecção de um polítopo pode ter muito mais facetas que o politopo
original.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
20 / 29
Facetas e Projecções
A projecção de um polítopo pode ter muito mais facetas que o politopo
original.
Polítopo de Paridade
O polítopo de paridade em Rn é o invólucro convexo Pn de todos os
vectores de zeros e uns em Rn com um número ímpar de uns.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
20 / 29
Facetas e Projecções
A projecção de um polítopo pode ter muito mais facetas que o politopo
original.
Polítopo de Paridade
O polítopo de paridade em Rn é o invólucro convexo Pn de todos os
vectores de zeros e uns em Rn com um número ímpar de uns.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
20 / 29
Facetas e Projecções
A projecção de um polítopo pode ter muito mais facetas que o politopo
original.
Polítopo de Paridade
O polítopo de paridade em Rn é o invólucro convexo Pn de todos os
vectores de zeros e uns em Rn com um número ímpar de uns.
Tem 2n−1 vértices e 2n−1 facetas.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
20 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .Temos portanto (n + 1)dn/2e + n
variáveis.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .Temos portanto (n + 1)dn/2e + n
variáveis. Consideremos as relações:
(z 1 )i + (z 3 )i + · · · + (z n )i = x i , para i = 1, · · · , n;
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .Temos portanto (n + 1)dn/2e + n
variáveis. Consideremos as relações:
(z 1 )i + (z 3 )i + · · · + (z n )i = x i , para i = 1, · · · , n;
α1 + α3 + · · · + αn = 1;
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .Temos portanto (n + 1)dn/2e + n
variáveis. Consideremos as relações:
(z 1 )i + (z 3 )i + · · · + (z n )i = x i , para i = 1, · · · , n;
α1 + α3 + · · · + αn = 1;
(z k )1 + (z k )2 + · · · (z k )n = k αk para todo o k ímpar;
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .Temos portanto (n + 1)dn/2e + n
variáveis. Consideremos as relações:
(z 1 )i + (z 3 )i + · · · + (z n )i = x i , para i = 1, · · · , n;
α1 + α3 + · · · + αn = 1;
(z k )1 + (z k )2 + · · · (z k )n = k αk para todo o k ímpar;
0 ≤ (z k )i ≤ αk , para todo o i e k .
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .Temos portanto (n + 1)dn/2e + n
variáveis. Consideremos as relações:
(z 1 )i + (z 3 )i + · · · + (z n )i = x i , para i = 1, · · · , n;
α1 + α3 + · · · + αn = 1;
(z k )1 + (z k )2 + · · · (z k )n = k αk para todo o k ímpar;
0 ≤ (z k )i ≤ αk , para todo o i e k .
A projecção sobre as variáveis x dá o polítopo de paridade Pn .
Este só tem n2 facetas.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Facetas e Projecções - Continuação
Pn tem uma descrição mais pequena.
Consideremos x, e z k com k ímpar e 1 ≤ k ≤ n todos em Rn e αk ∈ R
para os mesmos valores de k .Temos portanto (n + 1)dn/2e + n
variáveis. Consideremos as relações:
(z 1 )i + (z 3 )i + · · · + (z n )i = x i , para i = 1, · · · , n;
α1 + α3 + · · · + αn = 1;
(z k )1 + (z k )2 + · · · (z k )n = k αk para todo o k ímpar;
0 ≤ (z k )i ≤ αk , para todo o i e k .
A projecção sobre as variáveis x dá o polítopo de paridade Pn .
Este só tem n2 facetas. Podíamos optimizar no polítopo com mais
variáveis em vez de optimizar na sua projecção.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
21 / 29
Exemplo - Optimização em Projecções
Queremos optimizar sobre um polítopo H
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
22 / 29
Exemplo - Optimização em Projecções
Queremos optimizar sobre um polítopo H
Consideramos o polítopo C cuja projecção é H.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
22 / 29
Exemplo - Optimização em Projecções
Queremos optimizar sobre um polítopo H
Consideramos o polítopo C cuja projecção é H.
Optimizamos sobre C.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
22 / 29
Exemplo - Optimização em Projecções
Queremos optimizar sobre um polítopo H
Consideramos o polítopo C cuja projecção é H.
Optimizamos sobre C.
Projectamos a solução.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
22 / 29
Exemplo - Optimização em Projecções
Queremos optimizar sobre um polítopo H
Consideramos o polítopo C cuja projecção é H.
Optimizamos sobre C.
Projectamos a solução.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
22 / 29
Problema
O nosso problema é então dado um polítopo P, encontrar um polítopo
Q com o mínimo possível de facetas cuja projecção seja P.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
23 / 29
Problema
O nosso problema é então dado um polítopo P, encontrar um polítopo
Q com o mínimo possível de facetas cuja projecção seja P.
Precisamos de uma definição.
Matriz de Folga
Se P é um polítopo com vértices p1 · · · pn e facetas dadas por
l 1 (x) ≥ 0, · · · , l f (x) ≥ 0, então a matriz de folga de P é


l 1 (p1 ) l 1 (p2 ) l 1 (p3 ) · · · l 1 (pv )
 l 2 (p1 ) l 2 (p2 ) l 2 (p3 ) · · · l 2 (pv ) 




..
..
..
..


.
.
.
.
l f (p1 ) l f (p2 ) l f (p3 ) · · · l f (pv )
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
23 / 29
Exemplo - Cubo
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
24 / 29
Exemplo - Cubo
0
0
0
x ≥0
y ≥0
z≥0
1−x ≥0
1−y ≥0
1−z ≥0
João Gouveia (UC)
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
0
1
1
1
1
















Teorema de Yannakakis
Oráculo Delfos
24 / 29
Exemplo - Cubo
x ≥0
y ≥0
z≥0
1−x ≥0
1−y ≥0
1−z ≥0
João Gouveia (UC)

0
0
0
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
0
1
1
1
1
0
1
0
0
1
0
1
1















Teorema de Yannakakis
Oráculo Delfos
24 / 29
Exemplo - Cubo
x ≥0
y ≥0
z≥0
1−x ≥0
1−y ≥0
1−z ≥0
João Gouveia (UC)
0
0
0
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
0
1
1
1
1
0
 0






1
0
0
1
0
0
1
1
0
1
1
0

1
1 







Teorema de Yannakakis
Oráculo Delfos
24 / 29
Exemplo - Cubo
x ≥0
y ≥0
z≥0
1−x ≥0
1−y ≥0
1−z ≥0
João Gouveia (UC)








0
0
0
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
0
1
1
1
1
0
0
0
1
1
1
1
0
0
0
1
1
0
1
0
1
0
1
0
0
1
1
1
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
0
Teorema de Yannakakis








Oráculo Delfos
24 / 29
Factorizações não negativas
Seja M uma matriz m por n, não negativa.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
25 / 29
Factorizações não negativas
Seja M uma matriz m por n, não negativa. M tem uma factorização
não negativa de ordem k , se existirem vectores
negativos
não
a1 , · · · , am e b1 , · · · bn em Rk tais que M i,j = ai , bj .
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
25 / 29
Factorizações não negativas
Seja M uma matriz m por n, não negativa. M tem uma factorização
não negativa de ordem k , se existirem vectores
negativos
não
a1 , · · · , am e b1 , · · · bn em Rk tais que M i,j = ai , bj .
Ou seja, se existirem A, m por k , e B, k por n, não negativas com
M = A × B.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
25 / 29
Factorizações não negativas
Seja M uma matriz m por n, não negativa. M tem uma factorização
não negativa de ordem k , se existirem vectores
negativos
não
a1 , · · · , am e b1 , · · · bn em Rk tais que M i,j = ai , bj .
Ou seja, se existirem A, m por k , e B, k por n, não negativas com
M = A × B.
Exemplo


10 4 0 2
M= 6 4 4 4 
3 6 12 9
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
25 / 29
Factorizações não negativas
Seja M uma matriz m por n, não negativa. M tem uma factorização
não negativa de ordem k , se existirem vectores
negativos
não
a1 , · · · , am e b1 , · · · bn em Rk tais que M i,j = ai , bj .
Ou seja, se existirem A, m por k , e B, k por n, não negativas com
M = A × B.
Exemplo

 
2 0
10 4 0 2
5 2 0 1




6 4 4 4
= 1 1 ×
,
M=
1 2 4 3
0 3
3 6 12 9

João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
25 / 29
Factorizações não negativas
Seja M uma matriz m por n, não negativa. M tem uma factorização
não negativa de ordem k , se existirem vectores
negativos
não
a1 , · · · , am e b1 , · · · bn em Rk tais que M i,j = ai , bj .
Ou seja, se existirem A, m por k , e B, k por n, não negativas com
M = A × B.
Exemplo

 
2 0
10 4 0 2
5 2 0 1




6 4 4 4
= 1 1 ×
,
M=
1 2 4 3
0 3
3 6 12 9

Logo M tem uma factorização não negativa de ordem 2.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
25 / 29
Teorema de Yannakakis
Teorema de Yannakakis-1991
Seja P um polítopo e S a sua matriz de folga. Então os dois seguintes
números são iguais.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
26 / 29
Teorema de Yannakakis
Teorema de Yannakakis-1991
Seja P um polítopo e S a sua matriz de folga. Então os dois seguintes
números são iguais.
O menor número de facetas possível de um polítopo Q cuja
projecção seja P.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
26 / 29
Teorema de Yannakakis
Teorema de Yannakakis-1991
Seja P um polítopo e S a sua matriz de folga. Então os dois seguintes
números são iguais.
O menor número de facetas possível de um polítopo Q cuja
projecção seja P.
O menor número k tal que S tenha uma factorização não negativa
de ordem k .
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
26 / 29
Teorema de Yannakakis
Teorema de Yannakakis-1991
Seja P um polítopo e S a sua matriz de folga. Então os dois seguintes
números são iguais.
O menor número de facetas possível de um polítopo Q cuja
projecção seja P.
O menor número k tal que S tenha uma factorização não negativa
de ordem k .
Mais ainda, é possível encontrar o polítopo Q a partir da factorização
de S.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
26 / 29
O Hexágono
Considere o hexágono regular.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
27 / 29
O Hexágono
Considere o hexágono regular.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
27 / 29
O Hexágono
Considere o hexágono regular.
Tem uma matriz de folga 6 × 6.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
27 / 29
O Hexágono
Considere o hexágono regular.
Tem uma matriz de folga 6 × 6.








0
1
2
2
1
0
0
0
1
2
2
1
1
0
0
1
2
2
2
1
0
0
1
2
João Gouveia (UC)
2
2
1
0
0
1
1
2
2
1
0
0








Teorema de Yannakakis
Oráculo Delfos
27 / 29
O Hexágono
Considere o hexágono regular.
Tem uma matriz de folga 6 × 6.









0
1
2
2
1
0
0
0
1
2
2
1
1
0
0
1
2
2
2
1
0
0
1
2
João Gouveia (UC)
2
2
1
0
0
1
1
2
2
1
0
0














=





1
0
1
0
0
1
0
0
0
1
0
0
0
1
2
0
1
0
0
1
0
1
1
0
0
0
0
2
1
0
Teorema de Yannakakis















0
0
0
1
2
1
1
2
1
0
0
0
0
1
1
0
0
1
0
0
1
1
0
0
0
0

0 


0 


0 

1
Oráculo Delfos
27 / 29
Hexágono - continuação.
É a projecção da fatia de R5+ cortada por
y1 + y2 + y3 + y5 = 2,
João Gouveia (UC)
y3 + y4 + y5 = 1.
Teorema de Yannakakis
Oráculo Delfos
28 / 29
Hexágono - continuação.
É a projecção da fatia de R5+ cortada por
y1 + y2 + y3 + y5 = 2,
João Gouveia (UC)
y3 + y4 + y5 = 1.
Teorema de Yannakakis
Oráculo Delfos
28 / 29
Hexágono - continuação.
É a projecção da fatia de R5+ cortada por
y1 + y2 + y3 + y5 = 2,
y3 + y4 + y5 = 1.
Hexágonos Irregulares não são projecções de polítopos de 5 faces.
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
28 / 29
Fim da Apresentação
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
29 / 29
Fim da Apresentação
Mas muitos problemas por resolver
João Gouveia (UC)
Teorema de Yannakakis
Oráculo Delfos
29 / 29