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}.
5. A=\left[\begin{array}{ll}1 & 2 \\\\ 3 & 1\end{array}\right], \mathbf{b}=\left[\begin{array}{l}10 \\\\ 15\end{array}\right]
Passo 1
O enunciado pede a representação mínima (isto é, apenas as desigualdades faceta‐definidoras, sem redundâncias) do politopo
P = \{\,x\in\mathbb{R}^2 \mid A x \le b,\;x\ge0\},
onde
A = \begin{pmatrix}1 & 2\\\ 3 & 1\end{pmatrix},\quad b = \begin{pmatrix}10\\\ 15\end{pmatrix},
e x\ge0 significa x_1\ge0,\;x_2\ge0. Vamos primeiro entender a forma de P encontrando seus vértices e depois verificar se alguma das quatro desigualdades originais é redundante.
Passo 2
Encontramos os vértices de P\) intersectando pares de restrições:
1. As duas restrições de não‐negatividade \(x_1=0\) e \(x_2=0\) intersectam em \((0,0)\).
2. Interseção de \(x_2=0\) com \(3x_1 + x_2 = 15\) dá \(3x_1 = 15\), logo \((5,0)\).
3. Interseção de \(x_1=0\) com \(x_1 + 2x_2 = 10\) dá \(2x_2 =10\), logo \((0,5)\).
4. Interseção das duas desigualdades ativas
\[\begin{cases} x_1 + 2x_2 = 10,\\\\ 3x_1 + x_2 = 15 \end{cases}
resolvemos por substituição: de 3x_1 + x_2 =15\] vem \(x_2=15-3x_1. Substituindo em x_1+2x_2=10 obtém‐se
Cada aresta do polígono P deve repousar numa das quatro retas dadas pelas desigualdades originais. Como vemos:
A aresta entre (0,0) e (5,0) vem de x_2\ge0.
A aresta entre (0,0) e (0,5) vem de x_1\ge0.
A aresta entre (5,0) e (4,3) vem de 3x_1 + x_2 \le 15.
A aresta entre (0,5) e (4,3) vem de x_1 + 2x_2 \le 10.
Nenhuma das quatro desigualdades é implicada pelas outras três, então todas são facetas de P. Logo a descrição mínima em forma H é manter exatamente essas quatro.
Resposta
A representação mínima do politopo é
P = \{\,x\in\mathbb{R}^2 \mid x_1\ge0,\;x_2\ge0,\;x_1+2x_2\le10,\;3x_1+x_2\le15\}.