Dúvida boba

Dúvida boba

por daniel reverbel -
Número de respostas: 1

Marcelo, fiquei com uma dúvida conceitual boba relativa à pergunta que te fiz no final da aula passada (e que não vejo relação com a provinha então não vi problema em perguntar).

Para relembrar, e situar quaisquer colegas interessados, quando estavamos vendo o tratamento de direções viáveis para vértices degenerados, tive a impressão que a(s) restrição(ões) que causa(m) a degenerecência era(m) supérflua(s) ao problema e poderia(m) ser eliminada (tendo em mente um exemplo simples de 3 retas em R2), assim transformando o vértice em não-degenerado.

O professor me lembrou do caso da pirâmide em R3 (R8 para representação canônica), no qual o topo da pirâmide é um vértice degenerado, e cuja degenerecência é essencial à representação do poliedro. E ficou claro que a degenerecência não era necessáriamente supérflua.

Depois de pensar um pouco mais no assunto fiquei com a impressão que a degenerecência supérflua que eu estava imaginando inicialmente jamais ocorreria em nossos problemas porque sempre trabalhamos sob a hipótese fundamental (A com linhas LI). Dessa forma toda degenerecência que encontrarmos seria como o caso da pirâmide, ou seja, todas restrições tem importância na representação do poliedro.

 

Estou correto?

Pensei em tentar provar isso como um exercício, mas tive dificuldade de mostrar que a HI implica degenerecências não superfluas (não soube formalizar a idéia de degenerecência não-supérflua para elaborar uma prova).

Em resposta à daniel reverbel

Re: Dúvida boba

por Marcelo Queiroz -

Oi, Daniel! Primeiramente, sua dúvida não é boba...

Pra deixar mais claro o exemplo para os outros, estávamos falando de uma pirâmide de base quadrada em R3, que poderia ser algo como

P={(x,y,z)' | x-z>=0, y-z>=0, x+z<=2, y+z<=2, z>=0}

onde o ponto v=(1,1,1)' é o ápice da pirâmide. Este é um vértice degenerado, pois as 4 primeiras restrições são ativas em v, mas nenhuma das restrições é supérflua na definição de P (no sentido de que eliminar qualquer restrição muda o conjunto resultante).

A questão de restrições supérfluas (ou não) no poliedro canônico esbarra na seguinte dificuldade: pode ser que uma restrição seja supérflua (no sentido indicado acima), mas sua eliminação destrói a forma canônica! Um exemplo muito simples seria {x=1,x>=0}, um poliedro canônico que corresponde a um conjunto unitário em R1, ou um exemplo menos bobo {x-y=0, x,y>=0}, um poliedro canônico em R2 que define uma semi-reta passando pela origem. No primeiro caso a restrição de sinal é supérflua no sentido de não ser necessária para definir o lugar geométrico dos pontos viáveis, mas sem ela o poliedro deixa de ser canônico; no segundo caso qualquer uma das restrições de sinal implica na outra, pelo fato de x=y (1ª restrição), mas outra vez aquela representação é a mais enxuta possível respeitando a forma canônica.

Para efeito de exercício, você pode provar que a hipótese fundamental garante que o sistema Ax=b não contém restrições supérfluas, seja para um poliedro definido apenas por estas restrições (isso é bem parecido com o que a gente já provou) ou para o poliedro canônico definido por estas restrições mais as restrições de sinal. Nesse último caso você teria que considerar o poliedro canônico Q com uma restrição de igualdade a menos do que o poliedro canônico P, e mostrar que P!=Q, ou seja, que existe algum ponto em Q que não está em P (isso porque a inclusão P C Q é trivial). Acho que esse seria o resultado mais próximo do tipo de caracterização que você estava buscando, embora só diga respeito à "não-superfluidade" das restrições de igualdade.

Para identificar restrições de desigualdade supérfluas o problema é mais complicado do que só testar independência linear, mas poderia ser resolvido com programação linear: Seja d'x>=e uma restrição que você quer saber se é supérflua, ou seja, se é implicada pelas demais restrições Ax>=b. Nesse caso basta resolver o PL {min d'x s.a Ax>=b}. Se o valor ótimo for >=e, você sabe que todo ponto que satisfaz Ax>=b também satisfaz d'x>=e, ou seja, a restrição d'x>=e é supérflua; se o valor ótimo for <e, você terá na mão um ponto (a solução ótima) que confirma que aquela restrição não era supérflua no poliedro {Ax>=b, d'x>= e}.

Marcelo