Responda os itens a seguir
(1) Dado um conjunto poliedral qualquer. Defina uma desigualdade redundante para este conjunto.
(2) Considere o conjunto poliedral a seguir
3 x1-x2 & >= 3 x1+x2 & <= 4 x1 & <= 2 x1, x2 & >= 0
Existe alguma desigualdade redundante para este conjunto poliedral? Justifique.

Passo 1

O enunciado trata de poliedros descritos por desigualdades lineares e pede:
  1. Definir o que é uma desigualdade redundante num conjunto poliedral.
  2. No poliedro dado por
3x1-x2 &>= 3, x1+x2 &<= 4, x1 &<= 2, x1,,x2 &>= 0,
identificar se alguma dessas desigualdades é redundante.

Passo 2

Seja um poliedro
P = xin R^n mid A x <= b,
com AinR^mtimes n e binR^m. A i-ésima desigualdade
ai^T x <= bi
é dita redundante se, mesmo removendo-a, o poliedro não se altera, isto é, se
xmid A-ix <= b-i = P,
onde A-i,b-i são A,b sem a linha i. Equivalente: ela já é implicada pelas demais restrições.

Passo 3

Vamos reescrever as desigualdades do poliedro em forma padronizada “ ” ou “ ”:
Queremos ver se alguma delas é implicada pelas outras.

Passo 4

Examinemos a desigualdade x1>= 0 (4). Das restrições (1) e (5) temos
3x1-x2>= 3 e x2>= 0
Como x2>= 0, da primeira segue
3x1 ;=; (3x1-x2) + x2 ;>=; 3 + 0 ;=;3 Longrightarrow x1>= 1
Logo qualquer ponto que satisfaça (1) e (5) já cumpre x1>=1>0. Portanto ao retirar (4) o conjunto factível não muda, e (4) é redundante.

Passo 5

Para garantir que nenhuma outra é redundante, basta notar que, se tirarmos isoladamente cada uma das desigualdades restantes, obtemos sempre pontos que violam exatamente aquela e satisfazem todas as demais. Por exemplo, sem (3) podemos tomar x1=3,x2=0 e ver que falha x1<=2 mas atende às outras, e assim por diante para (1), (2) e (5). Portanto nenhuma delas é implicada pelas demais.

Resposta

A desigualdade redundante é
x1>= 0,
pois ela já está implícita pelas restrições 3x1-x2>=3 e x2>=0.

Exercícios relacionados