[MAC 315] Re: Dúvida sobre algoritmo de enumeracao explicita

[Leonidas O Brandao <leo@ime.usp.br>]

On Mon, 1 May 2000, André Casado Castaño wrote:

> Estive tentando entender o algoritmo de enumeracao explicita mas estou
> com sérias dificuldades... Acredito que eu não sou o único com essas
> dificuldades.
> Será que não poderia ser feito um comentário mais detalhado de como ele
> funciona?
> Iria ajudar muito tanto pra estudar pra prova quanto pra resolver o
> exercício da lista...
> falou..

Bem, nao sei exatamente qual a questao, assim aqui vai um esquema do que
e' o algoritmo de enumeracao:

 - ideia central: gerar todos os candidatos a vertices
                  pelo teor. 2.2, todos x tq {A^i}_{i em I(x)} l.i.
                  testar se e' vertice
 - Fila <- todas as bases dentre A_{m x n} (m colunas de A)
   q <- prim( Fila ); Fila <- Fila / {q}
   max <- -infinito; sol <- empty
   enquanto Fila nao vazia
            B <- matriz com colunas de q
            se det(B)<>0 entao       // candidato a vertice
               x <- B^(-1) b
               se x>=0 entao         // e' vertice
                  se c'x > max entao // fc objetivo max c'x
                     sol <- x
                     max <- c'x
            q <- prim( Fila ); Fila <- Fila / {q}

Se lerem com atencao o codigo Scilab verao que, em resumo, e' o que
esquematizei acima (nao garanto que seja identico, pois agora - quando
escrevi o alg. acima - nao tenho o texto em maos).

Ate'
Leonidas
 
 --------------------------------------------------------------------------
 Leônidas de Oliveira Brandão - Computer Science Dep. of IME-USP  (Brazil)
 leo@ime.usp.br - http://www.ime.usp.br/~leo - +55 (011) 818 [6298 | 6135]