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
x_1 + 2(15-3x_1)=10 \;\Longrightarrow\; x_1 +30 -6x_1 =10 \;\Longrightarrow\; -5x_1 = -20 \;\Longrightarrow\; x_1 = 4,
e assim x_2 = 15-3\cdot4 = 3. O vértice é (4,3).
Portanto os vértices de P são
(0,0),\;(5,0),\;(4,3),\;(0,5).

Passo 3

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\}.
Em forma matricial H:\;H\,x\le h podemos escrever
H = \begin{pmatrix} -1 & 0\\\\ 0 & -1\\\\ 1 & 2\\\\ 3 & 1 \end{pmatrix},\qquad h = \begin{pmatrix} 0\\\\ 0\\\\ 10\\\\ 15 \end{pmatrix}.

Exercícios de Livros Relacionados