Question 2. (2.0)
(a) Defina uma desigualdade redundante para um conjunto poliedral.
(b) Existe alguma desigualdade redundante para o conjunto poliedral a seguir? Justifique.
x1+x2 & <= 3 x1 & <= 2 x2 & <= 4 x2 & >= 1 x1, x2 & >= 0

Passo 1

O enunciado pede:
(a) dar a definição de “desigualdade redundante” num conjunto poliedral;
(b) verificar se, no poliedro definido por
x1+x2 &<= 3, x1 &<= 2, x2 &<= 4, x2 &>= 1, x1,,x2 &>= 0,
alguma dessas desigualdades é redundante.
Para resolver, precisamos entender que uma desigualdade é redundante se sua remoção não altera o conjunto viável.

Passo 2

Definimos formalmente: uma desigualdade a^Tx <= b em um sistema Ax <= b é dita redundante se o poliedro
P = ,xmid Ax<= b,
não muda quando excluímos essa desigualdade. Equivalente dizer que ela é implicada pelas demais, ou seja, todo x que satisfaz as outras desigualdades já satisfaz a^Tx<= b.

Passo 3

Analisamos a desigualdade x1<= 2. Nas demais temos x1+x2<= 3 e x2>= 1. Para qualquer ponto viável:
x1 = (x1+x2) - x2 <= 3 - 1 = 2
Logo toda solução das outras desigualdades também satisfaz x1<= 2. Portanto x1<= 2 é redundante.

Passo 4

Analisamos a desigualdade x2<= 4. Das outras restrições temos x1>= 0 e x1+x2<= 3. Então
x2 = (x1+x2) - x1 <= 3 - 0 = 3 < 4
Logo qualquer ponto que satisfaça x1+x2<=3 e x1>=0 já satisfaz x2<=4. Assim x2<= 4 também é redundante.

Passo 5

Analisamos a parte x2>= 0. Como já temos x2>= 1, todo ponto viável satisfaz automaticamente x2>=0. Portanto a desigualdade x2>=0 é redundante.

Passo 6

Verificamos as demais:
  • x1+x2<=3 não é implicada por nenhuma outra (é “definidora” do limite superior conjunto).
  • x2>=1 não é implicada pelas outras (sem ela o valor mínimo de x2 cairia até zero).
  • x1>=0 não é implicada (sem ela x1 poderia ficar negativo).

Resposta

As desigualdades redundantes são
x1<= 2, x2<= 4, x2>= 0

Exercícios relacionados