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
Existe alguma desigualdade redundante para este conjunto poliedral? Justifique.
(1) Dado um conjunto poliedral qualquer. Defina uma desigualdade redundante para este conjunto.
(2) Considere o conjunto poliedral a seguir
Passo 1
O enunciado trata de poliedros descritos por desigualdades lineares e pede:
- Definir o que é uma desigualdade redundante num conjunto poliedral.
- No poliedro dado por
identificar se alguma dessas desigualdades é redundante.
Passo 2
Seja um poliedro
com
e
. A
-ésima desigualdade
é dita redundante se, mesmo removendo-a, o poliedro não se altera, isto é, se
onde
são
sem a linha
. 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
(4). Das restrições (1) e (5) temos
Como
, da primeira segue
Logo qualquer ponto que satisfaça (1) e (5) já cumpre
. 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
e ver que falha
mas atende às outras, e assim por diante para (1), (2) e (5). Portanto nenhuma delas é implicada pelas demais.
Resposta
A desigualdade redundante é
pois ela já está implícita pelas restrições
e
.