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},
isto é, pelas desigualdades
\begin{cases} x_1+3x_2 \le 12,\\\ x_1+2x_2 \le 9,\\\\ 2x_1+x_2 \le 12,\\\ x_1 \ge 0,\quad x_2\ge 0. \end{cases}
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
L_1:\;x_1+3x_2=12,\quad L_2:\;x_1+2x_2=9,\quad L_3:\;2x_1+x_2=12,\quad x_1=0,\quad x_2=0.
Calculamos as interseções viáveis (que satisfazem também as outras desigualdades):
  1. x_1=0\) e \(x_2=0 \longrightarrow V_0=(0,0)\). 2. \(x_2=0\) e \(L_3 \longrightarrow 2x_1=12\implies V_1=(6,0)\). 3. \(L_3\) e \(L_2 \longrightarrow \begin{cases}2x_1+x_2=12\x_1+2x_2=9\end{cases} \implies V_2=(5,2).
  2. L_2\) e \(L_1 \longrightarrow \begin{cases}x_1+2x_2=9\x_1+3x_2=12\end{cases} \implies V_3=(3,3).
  3. L_1 e x_1=0 \longrightarrow 3x_2=12\implies V_4=(0,4).
Verificamos que nenhum destes pontos viola as demais desigualdades. Assim os vértices de P são
V_0=(0,0),\;V_1=(6,0),\;V_2=(5,2),\;V_3=(3,3),\;V_4=(0,4).

Passo 3

Agora associamos cada aresta a uma desigualdade ativa:
  • Aresta (0,0)\to(6,0) vem de x_2=0.
  • Aresta (6,0)\to(5,2) vem de 2x_1+x_2=12.
  • Aresta (5,2)\to(3,3) vem de x_1+2x_2=9.
  • Aresta (3,3)\to(0,4) vem de x_1+3x_2=12.
  • Aresta (0,4)\to(0,0) vem de x_1=0.
Cada uma das cinco desigualdades é a fronteira de alguma face de dimensão 1, logo nenhuma é consequência das outras.

Passo 4

Como todas as cinco desigualdades geram arestas não-vazias, nenhuma é redundante. Portanto a H-representação irredundante de P é exatamente
\begin{cases} x_1+3x_2 \le 12,\\\ x_1+2x_2 \le 9,\\\\ 2x_1+x_2 \le 12,\\\ x_1 \ge 0,\\\ x_2 \ge 0. \end{cases}

Resposta

A representação mínima (irredundante) em forma de meio-espaços de P é
x_1+3x_2 \le 12,\quad x_1+2x_2 \le 9,\quad 2x_1+x_2 \le 12,\quad x_1 \ge 0,\quad x_2 \ge 0.
Opcionalmente, a V-representação mínima (hull dos vértices) é
P = \operatorname{conv}\{(0,0),(6,0),(5,2),(3,3),(0,4)\}.