Demostrar que el poliedro $P =\{(x_1, \ldots , x_m, y) \in \mathbb R_{+}^{m+1}: y \leq 1,x_i \leq y \text{ for } i = 1, \ldots , m \} $ tiene vértices enteros.
Me parece obvio, pero no sé cómo demostrarlo. ¿Alguna idea?
Respuesta
¿Demasiados anuncios?
Rodrigo de Azevedo
Puntos
608
Queremos demostrar que el poliedro
$$\mathcal P := \bigg\{ \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \in \mathbb R^{n+1} : \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \geq \begin{bmatrix} 0_n\\ 0\end{bmatrix}, \begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \leq \begin{bmatrix} 0_n\\ 1\end{bmatrix} \bigg\}$$
es integral es decir, tiene vértices enteros. Como la matriz es triangular superior Matriz de Frobenius ,
$$\begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix}^{-1} = \begin{bmatrix} \mathrm I_n & 1_n\\ 0_n^{\top} & 1\end{bmatrix}$$
que también es una matriz entera. Así, la matriz es unimodular . Como también es no negativo,
$$\begin{bmatrix} \mathrm x\\ y\end{bmatrix} \leq \begin{bmatrix} \mathrm I_n & 1_n\\ 0_n^{\top} & 1\end{bmatrix} \begin{bmatrix} 0_n\\ 1\end{bmatrix} = \begin{bmatrix} 1_n\\ 1\end{bmatrix}$$
lo que nos permite concluir que $\mathcal P \subset [0,1]^{n+1}$ es decir, es acotado . Del libro de Schrijver:
Así, $\mathcal P$ es integral si y sólo si el $(n+1) \times (n+1)$ matriz
$$\begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix}$$
es totalmente unimodular . Es fácil demostrar por agotamiento que la matriz es efectivamente totalmente unimodular cuando $n \in \{1,2\}$ . Si podemos demostrar que la matriz es totalmente unimodular también para $n \geq 3$ entonces demostramos que $\mathcal P$ es integral. Los capítulos 19-21 del libro de Schrijver deberían ayudar.
- Alexander Schrijver, Teoría de la programación lineal y entera John Wiley & Sons, julio de 1998.
