APLICAÇÕES DAS BASES DE GROEBNER NA PROGRAMAÇÃO LINEAR INTEIRA

  • Juliana Barcelos Cordeiro
  • Oscar Alfredo Paz La Torre
Palavras-chave: Aneis de polinômios em varias variaveis, Bases de Groebner, Programação Linear Inteira

Resumo

Nos últimos anos o avanço na área da informática possibilitou a implementação de novas técnicas computacionais. As Bases de Groebner, considerada como um recurso teórico, sofre uma transformação e atualmente é considerado um recurso em potencial em diversas áreas entre elas a de Programação Linear Inteira. O objetivo do meu trabalho é o estudo das bases de Groebner paralelamente à teoria de Programação Linear Inteira assim como seus métodos de resolução para poder efetuar estudos comparativos. O trabalho foi desenvolvido em três etapas: Primeira etapa: estudamos os conceitos algébricos necessários para a teoria de Bases de Groebner e os problemas relacionados a ela tais com: resolução de sistema de equações polinomiais e o problema de adesão a um ideal. Segunda etapa: Estudo de Programação Linear Inteira e de seu principal método de resolução: Branch and Bound. Terceira etapa: Transformamos os problemas de Programação linear inteira para sua resolução com Bases de Groebner e comparamos os resultados obtidos com o método de Branch and Bound. Para isto utilizamos os softwares: MAPLE e LINGO, respectivamente. Com os conhecimentos adquiridos trabalhamos na resolução de Problemas de Programação linear inteira de pequeno porte. Utilizamos as duas técnicas e efetuamos as comparaçãoes pertinentes. Em alguns casos encontramos soluções distintas e a melhor “solução ótima” foi fornecida pela técnica de bases de Groebner. No contexto do nosso trabalho podemos afirmar que esta técnica de resolução de PPLI´s, com fundamento teórico nas bases de Groebner, se apresenta como uma boa alternativa.
Publicado
03-05-2013