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
2x_{1}+3(16-4x_{1})=18\;\Longrightarrow\;-10x_{1}=-30\;\Longrightarrow\;x_{1}=3,\;x_{2}=4.
ii) 2x_{1}+3x_{2}=18,\quad x_{1}=0
x_{2}=6, ponto (0,6).
iii) 4x_{1}+x_{2}=16,\quad x_{2}=0
x_{1}=4, ponto (4,0).
iv) x_{1}=0,\quad x_{2}=0
é o ponto (0,0).

Passo 3

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.

Resposta

2x_{1}+3x_{2}\le18,\quad 4x_{1}+x_{2}\le16,\quad x_{1}\ge0,\quad x_{2}\ge0.

Exercícios de Livros Relacionados