Um politopo é o conjunto de todas as combinações convexas de um conjunto finito de vetores. Este apêndice faz um resumo da relação entre o conceito de politopo e o conceito de poliedro do apêndice B.
Seja $E$ um conjunto finito e $S$ um conjunto finito de vetores indexados por $E$. Em outras palavras, $S$ um subconjunto finito do espaço $\R^E$. Uma combinação convexa dos elementos de $S$ é qualquer vetor da forma \[\textstyle \sum_{s \in S} \lambda_s s\,\text{,} \] sendo $\lambda_s$ números em $\Rplus$ tais que $\sum_{s \in S}\nolimits \lambda_s = 1$. Os números $\lambda_s$ são os coeficientes da combinação convexa. O casco convexo (= convex hull de $S$ é o conjunto de todas as combinações convexas dos elementos de $S$ e será denotado por \[ \convex(S)\text{.} \]
Exemplo D.1: Todas as combinações convexas de $2$ pontos no plano pertencem ao segmento de reta que liga os dois pontos. (Como de hábito, um ponto no plano representa o vetor que vai da origem do sistema de coordenadas ao ponto em questão.) As combinações convexas de $3$ pontos no plano pertencem ao triângulo que liga os três pontos. A figura abaixo mostra um conjunto $S$ de $11$ pontos no plano e o casco convexo $\convex(S)$. [CCPS fig.6.1]
Um politopo (= polytope) é o casco convexo de um conjunto finito de vetores. Em outras palavras, um politopo é qualquer conjunto da forma $\convex(S)$, onde $S$ é um subconjunto finito de $\R^E$. (Em geral, muitos conjuntos $S$ diferentes representam o mesmo politopo.)
Um subconjunto $C$ de $\R^E$ é convexo se a combinação convexa de quaisquer dois de seus elementos está em $C$. Todo politopo é um conjunto convexo. Todo poliedro também é um conjunto convexo.
Para qualquer conjunto finito $S$ com dois ou mais vetores, o conjunto $\convex(S)$ é muito maior que $S$. Apesar disso, minimizar uma função linear sobre $\convex(S)$ produz o mesmo resultado que minimizar sobre $S$:
Lema D.1 Para qualquer subconjunto finito $S$ de $\R^E$ e qualquer vetor $c$ em $\R^E$, tem-se $\max\left(cs : s \in S\right) = \max\left(cx : x \in \convex(S)\right)$.
Prova: É claro que $\max\left(cs : s \in S\right) \leq \max\left(cx : x \in \convex(S)\right)$ uma vez que $S \subseteq \convex(S)$. Resta mostrar a desigualdade contrária. Suponha, por exemplo, que $S=\conj{s,s'}$ e ajuste a notação de modo que $cs \leq cs'$. Todo elemento de $\convex(S)$ tem a forma $\lambda s + \lambda' s'$, sendo $\lambda$ e $\lambda'$ números reais no intervalo fechado $[0,1]$ tais que $\lambda+\lambda'=1$. Portanto \[ c(\lambda s + \lambda' s') = \lambda c s + (1-\lambda) c s' = \lambda (cs - cs') + cs' \leq cs'\text{.} \]
Uma generalização desse argumento mostra que $\max\left(cx : x \in \convex(S)\right) \leq \max\left(cs : s \in S\right)$ para qualquer $S$. ■
$\min$no lugar de
$\max$.
Para qualquer subconjunto finito $S$ de $\R^E$, é fácil provar que um dado vetor $v$ está em $\convex(S)$: basta exibir os coeficientes de uma combinação convexa dos elementos de $S$ que produz $v$. A questão complementar é mais difícil: como provar que $v$ não está em $\convex(S)$? Podemos fazer isso exibindo um hiperplano que separa $v$ de $\convex(S)$.
Lema D.2 (da separação) Para qualquer subconjunto finito $S$ de $\R^E$ e qualquer vetor $v$ em $\R^E$, se $v \notin \convex(S)$ então existe um vetor $h$ e um número $l$ tais que $h\,v > l$ e $h\,x \leq l$ para todo $x$ em $\convex(S)$.
Prova:
Seja $M$ uma matriz cujas linhas são os elementos de $S$.
Em outras palavras, $M$ é a matriz indexada por $S\times E$
tal que $M[s,E] = s$ para cada $s$ em $S$.
Toda combinação convexa das linhas de $M$
tem a forma $gM$, sendo $g$ é um vetor indexado por $S$ tal que
\[
g \geq 0 \quad \text{e} \quad g1 = 1\,\text{.}
\]
(Aqui,
o primeiro $1$
representa o vetor constante indexado por $S$
cujos elementos são todos iguais a $1$.
Portanto, $g1 = \sum_{s\in S}g_s$.
Essa convenção evita o incômodo de definir um símbolo especial
para o vetor constante.)
Seja $v$ um vetor em $\R^E$ e suponha que $v$ não pertence a $\convex(S)$. Então o programa linear \begin{equation}\label{lp:primal-separation} \begin{split} \text{minimize} \enspace g\,0 & \\ \text{sob as restrições} \enspace gM &= v \\ g1 &= 1 \\ g &\geq 0 \end{split} \end{equation}
é inviável. Este pl tem essencialmente a mesma forma que o pl \eqref{lp:reference-dual} do apêndice C. Para tornar isso mais evidente, vamos introduzir um pouco de notação adicional. Seja $e'$ algum índice que não pertence a $E$; seja $E'=E\cup\conj{e'}$; seja $M'$ a matriz indexada por $S\times E'$ e definida pelas propriedades $M'[S,E] = M$ e $M'[S,e'] = 1$; e seja $v'$ o vetor indexado por $E'$ e definido pelas propriedades $v'[E] = v$ e $v'[e'] = 1$. O pl \begin{equation}\label{lp:primal-separation-equiv} \begin{split} \text{minimize} \enspace g\,0 & \\ \text{sob as restrições} \enspace gM' &= v' \\ g &\geq 0 \end{split} \end{equation}
é equivalente ao pl \eqref{lp:primal-separation} e portanto inviável. Assim, a versão apropriada do lema de Farkas no apêndice C garante que existe um vetor de inviabilidade para \eqref{lp:primal-separation-equiv}. (Veja um dos exercícios na seção C.5 do apêndice C.) Trata-se de um vetor $h'$ tal que \[ M'h' \leq 0 \quad \text{e} \quad v'h' > 0\text{.} \]
Se denotarmos por $h$ o vetor $h'[E]$ e por $l$ o número $-h'[e']$, teremos $sh - l \leq 0$ e $vh - l > 0$ para cada linha $s$ de $M$. Em outras palavras, \[ sh \leq l \quad \text{e} \quad vh > l\text{.} \]
Isso vale não só para os elementos de $S$ como também para todo elemento $x$ de $\convex(S)$. Com efeito, $x$ em tem a forma $\sum_{s\in S}\lambda_s s$, com $\sum_{s\in S} \lambda_s = 1$ e $\lambda_s \geq 0$, e portanto \[\textstyle xh = \left(\sum_{s\in S} \lambda_s s \right) h = \sum_{s\in S} \lambda_s s h \leq \sum_{s\in S} \lambda_s l = l\text{.} \]
Resumindo: $v\,h > l$ e $x\,h \leq l$ para todo $x$ em $\convex(S)$. ■
A conclusão desse lema pode ser verbalizada assim: o hiperplano $hs\,{=}\,l$ separa $v$ do casco convexo de $S$.
A intuição sugere que todo politopo tem a forma $\conj{x : Ax \leq b}$ para alguma matriz $A$ e algum vetor $b$. A intuição também sugere que odo poliedro limitado tem a forma $\convex(S)$ para algum conjunto finito $S$ de vetores. O seguinte par de teoremas de Minkowski e Weyl confirma essa intuição.
Teorema D.3 (Minkowski–Weyl) Todo poliedro limitado é um politopo.
Esboço da prova: Seja $P$ o poliedro definido por uma matriz $A$ e um vetor $b$, isto é, $P=\conj{x : Ax \leq b}$. Suponha que $P$ é limitado. Se $P$ é vazio então $P=\convex(\emptyset)$. Suponha agora que $P$ não é vazio e seja $S$ o conjunto dos vértices de $P$. De acordo com o lema B.4 no apêndice B, $S$ não é vazio. De acordo com o corolário B.3, $S$ é finito.
Para todo $x$ em $\convex(S)$, temos $Ax \leq b$. Reciprocamente, de acordo com o lema da separação, todo vetor $x$ que satisfaz as restrições $Ax\leq b$ está em $\convex(S)$. Portanto $P=\convex(S)$. ■
Teorema D.4 Todo politopo é um poliedro limitado.
Esboço da prova: Seja $S$ um subconjunto finito de $\R^E$ e considere o politopo $T=\convex(S)$. Com o auxílio do lema D.2, da separação, é possível mostrar que existe uma matriz $A$ e um vetor $b$ tais que $T = \conj{x : Ax \leq b}$. ■
Poliedros limitados e politopos correspondem a duas maneiras diferentes de descrever um conjunto de vetores. A primeira permite decidir facilmente se um dado vetor pertence ao conjunto (mas é inadequada para exibir um vetor do conjunto), enquanto a segunda permite exibir facilmente um vetor do conjunto (mas é inadequada para decidir se um dado vetor pertence ao conjunto). Essas duas maneiras de descrever um conjunto de vetores estão intimamente relacionadas com o fenômeno da dualidade em programação linear e servem de fundamento para os métodos geométricos em combinatória.
Exemplo D.2: O conjunto de todos os vetores $(x_1,x_2)$ que satisfazem o sistema de desigualdades abaixo é um poliedro limitado. A figura mostra o poliedro e a combinação convexa dos seus vértices. [CCPS fig.6.2] \[ \begin{array}[b]{rcr@{\quad}c@{\enspace}r} 1x_1 &+& 3x_2 & \leq & 18\\ 1x_1 &+& 0x_2 & \leq & 6\\ 1x_1 &-& 2x_2 & \leq & 2\\ -1x_1 &-& 1x_2 & \leq & -5\\ -2x_1 &+& 1x_2 & \leq & -1\\ & & & & % hack \end{array} \]
