Apêndice B
Poliedros

Exemplo B.1: Considere a matriz $A$ e o vetor $b$ representados abaixo, com o vetor $b$ na vertical à direita da matriz $A$.

O poliedro $\{x:Ax\le b\}$ é o conjunto de todos os vetores $(x_1,x_2,x_3,x_4,x_5)$ que satisfazem o sistema de desigualdades:

Exemplo B.2: O conjunto de todos os vetores $(x_1,x_2)$ que satisfazem o sistema de desigualdades abaixo é um poliedro. (Todos os coeficientes são inteiros, mas isso é irrelevante.)

Exemplo B.3: As figuras abaixo sugerem dois poliedros em ${\mathbf{R}}^E$ com $E=\{1,2,3\}$.

Exemplo B.4: Seja $P$ o conjunto de todos os vetores $(x_1,x_2,x_3)$ que satisfazem o sistema de desigualdades abaixo. Esse sistema é equivalente ao que aparece em seguida e tem a forma especificada na definição $\text{(1)}$. Portanto, $P$ é um poliedro. Em notação matricial, o poliedro é definido por $Ax\le b$, sendo $A$ e $b$ a matriz e o vetor exibidos na última parte da figura.

As restrições que definem um poliedro não precisam ser independentes entre si. Nesse exemplo, a quarta e a quinta desigualdades do sistema à esquerda são redundantes: o poliedro não se altera se essas desigualdades forem apagadas.

Exemplo B.5: Seja $A$ uma matriz indexada por $V\times E$ e $c$ um vetor indexado por $E$. O conjunto de todos os vetores $y$ que satisfazem as restrições  $yA\le c$  é igual ao conjunto $\{y:A^{\mathsf{T}}y\le c\}$, onde $A^{\mathsf{T}}$ a matriz transposta de $A$. Como o último conjunto tem a forma especificada na definição $\text{(1)}$, $\{y:yA\le c\}$ é um poliedro.

Exemplo B.6: Considere o conjunto de todos os vetores $(x_1,x_2)$ que satisfazem as desigualdades a seguir. (Faça uma figura.)

O vetor $(+1,+1)$ é um vértice nesse conjunto.

Exemplo B.7: Considere o conjunto de todos os vetores $(x_1,x_2)$ que satisfazem as restrições a seguir.

Os vértices desse conjunto são $(0,0)$, $(\frac{3}{2},\frac{3}{2})$ e $(3,0)$. (Faça uma figura.)

Exemplo B.8: Para a matriz $A$ e o vetor $b$ definidos abaixo, considere o poliedro $\{x:Ax\le b\}$.

O vetor $x$ e os vetores $x+d$ e $x-d$ estão no poliedro. Portanto, $x$ não é vértice do poliedro.

Exemplo B.9: Nem todo poliedro tem vértices. Considere o poliedro $P:=\{x:Ax\le b\}$, com $A$ e $b$ dados a seguir. (Faça uma figura.)

Para qualquer $x$ em $P$, tanto $x+d$ quanto $x-d$ estão em $P$.

Exemplo B.10: Seja $P$ o poliedro definido pelas desigualdades $Ax\le b$. Seja $\hat{x}$ um vetor de $P$ tal que $A\hat{x}=b$. Suponha que $\hat{x}$ não é vértice de $P$. Então existe um vetor não nulo $d$ tal que $A(\hat{x}+d)\le b$ e $A(\hat{x}-d)\le b$. Segue daí que $$Ad=0$$ e portanto o conjunto das colunas de $A$ é linearmente dependente.

Exemplo B.11: O lado esquerdo da figura abaixo mostra uma matriz $A$, um vetor $b$ (à direita da matriz), e um vetor $\hat{x}$ (abaixo da matriz). Seja $I(\hat{x})$ o conjunto das $6$ primeiras linhas de $A$. Então $A[i,\ast ]\hat{x}=b[i]$ se e somente se $i\in I(\hat{x})$. Observe que o conjunto das colunas de $A[I(\hat{x}),\ast ]$ é l.i.. (Portanto, o conjunto das colunas de $A$ também é l.i..)  O vetor $\hat{x}$ é vértice do poliedro $Ax\le b$.

Agora considere os objetos $A$, $b$ e $\hat{x}$ do lado direito da figura. Seja $I(\hat{x})$ o conjunto das $4$ últimas linhas de $A$. Então $A[i,\ast ]\hat{x}=b[i]$ se e somente se $i\in I(\hat{x})$. Embora o conjunto das colunas de $A$ seja l.i., o conjunto das colunas de $A[I(\hat{x}),\ast ]$ é l.d.. Portanto, o vetor $\hat{x}$ não é vértice do poliedro $Ax\le b$.

Exemplo B.12: Considere novamente o poliedro $P$ do exemplo B.4. Veja abaixo, mais uma vez, o sistema de desigualdades que define $P$. O subsistema formado pela primeira, segunda e sexta desigualdades (veja a coluna esquerda da segunda parte da figura) é satisfeito com igualdade pelo vetor $(1,2,3)$ e por nenhum outro. Esse vetor pertence a $P$ e portanto é um vértice de $P$.

O subsistema formado pela primeira, terceira e sexta desigualdades (veja a coluna direita da segunda parte da figura) é satisfeito com igualdade apenas por $(1,4,3)$. Esse vetor pertence a $P$ e portanto é um vértice de $P$. Analogamente, o subsistema formado pela segunda, terceira e sexta desigualdades define o vértice $(3,2,3)$. Esses são os três únicos vértices de $P$.

Agora veja alguns subsistemas que não definem vértices. O subsistema formado pela primeira, quarta, e sexta desigualdades é satisfeito com igualdade apenas pelo vetor $(1,-\frac{1}{2},3)$, mas esse vetor não pertence a $P$. O subsistema formado pela primeira, segunda, terceira e sexta desigualdades não é satisfeito com igualdade por nenhum vetor. O subsistema formado pela primeira e segunda desigualdades é satisfeito com igualdade por mais de um vetor.

Exemplo B.13: Considere o conjunto de todos os vetores $(x_1,x_2)$ que satisfazem as desigualdades abaixo. (Faça uma figura.) Esse poliedro é ilimitado.

Exemplo B.14: Considere novamente o poliedro do exemplo B.4. Trata-se do conjunto de todos os vetores $(x_1,x_2,x_3)$ que satisfazem o sistema de desigualdades abaixo. Esse poliedro é limitado pois $0\le x_i\le 5$ para todo $i$. (Verifique!)