Nos Exercícios 5 a 8, encontre a representação mínima do politopo definido pelas desigualdades A \mathbf{x} \leq \mathbf{b} e \mathbf{x} \geq \mathbf{0}.
6. A=\left[\begin{array}{ll}2 & 3 \\\\ 4 & 1\end{array}\right], \mathbf{b}=\left[\begin{array}{l}18 \\\\ 16\end{array}\right]
Passo 1
O enunciado pede a representação mínima (isto é, sem desigualdades redundantes) do politopo \{\,\mathbf{x}\in\mathbb{R}^2 : 2x_{1}+3x_{2}\le18,\;4x_{1}+x_{2}\le16,\;x_{1}\ge0,\;x_{2}\ge0\}.
O conteúdo usado será a caracterização de vértices por interseção de linhas e o teste de redundância via atividade das desigualdades.
Passo 2
Para achar os vértices, construímos as interseções de cada par de fronteiras ativas:
i) 2x_{1}+3x_{2}=18,\quad4x_{1}+x_{2}=16.
Da segunda equação segue x_{2}=16-4x_{1}. Substituindo em 2x_{1}+3x_{2}=18 vem
Testamos cada um desses quatro pontos em todas as desigualdades: (0,0), (0,6), (3,4) e (4,0) satisfazem simultaneamente 2x_{1}+3x_{2}\le18,\;4x_{1}+x_{2}\le16,\;x_{1}\ge0,\;x_{2}\ge0.
Logo, são os vértices do politopo.
Passo 4
Cada desigualdade está ativa (com valor igual ao limite) exatamente em dois desses vértices, definindo uma aresta. Portanto nenhuma delas é redundante e todas são necessárias na descrição.