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.
(a) Defina uma desigualdade redundante para um conjunto poliedral.
(b) Existe alguma desigualdade redundante para o conjunto poliedral a seguir? Justifique.
Passo 1
O enunciado pede:
(a) dar a definição de “desigualdade redundante” num conjunto poliedral;
(b) verificar se, no poliedro definido por
(a) dar a definição de “desigualdade redundante” num conjunto poliedral;
(b) verificar se, no poliedro definido por
alguma dessas desigualdades é redundante.
Para resolver, precisamos entender que uma desigualdade é redundante se sua remoção não altera o conjunto viável.
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
em um sistema
é dita redundante se o poliedro
não muda quando excluímos essa desigualdade. Equivalente dizer que ela é implicada pelas demais, ou seja, todo
que satisfaz as outras desigualdades já satisfaz
.
Passo 3
Analisamos a desigualdade
. Nas demais temos
e
. Para qualquer ponto viável:
Logo toda solução das outras desigualdades também satisfaz
. Portanto
é redundante.
Passo 4
Analisamos a desigualdade
. Das outras restrições temos
e
. Então
Logo qualquer ponto que satisfaça
e
já satisfaz
. Assim
também é redundante.
Passo 5
Analisamos a parte
. Como já temos
, todo ponto viável satisfaz automaticamente
. Portanto a desigualdade
é redundante.
Passo 6
Verificamos as demais:
-
não é implicada por nenhuma outra (é “definidora” do limite superior conjunto). -
não é implicada pelas outras (sem ela o valor mínimo de cairia até zero). -
não é implicada (sem ela poderia ficar negativo).
Resposta
As desigualdades redundantes são