Encontre a representação mínima do politopo P definido pelas desigualdades A \mathbf{x} \leq \mathbf{b} e \mathbf{x} \geq \mathbf{0}, em que A=\left[\begin{array}{ll}1 & 3 \\\\ 1 & 2 \\\\ 2 & 1\end{array}\right] e \mathbf{b}=\left[\begin{array}{r}12 \\\\ 9 \\\\ 12\end{array}\right].
Passo 1
O problema define o politopo
P = \{\,\mathbf{x}\in\mathbb{R}^2 \mid A\mathbf{x}\le \mathbf{b},\\ \mathbf{x}\ge\mathbf{0}\},
onde
A = \begin{pmatrix}1&3\\\ 1&2\\\ 2&1\end{pmatrix},\quad \mathbf{b} = \begin{pmatrix}12\\\ 9\\\ 12\end{pmatrix},
Queremos a representação mínima em forma de meio-espaços (H-representação irredundante), ou seja, eliminar quaisquer desigualdades que sejam consequência das outras.
Passo 2
Para ver se alguma desigualdade é redundante, primeiro localizamos os vértices do politopo. Todo vértice surge da interseção de duas retas ativas (igualdades) dentre as cinco. As retas candidatas são