Abordagens híbridas na solução de problemas de programação inteira da teoria e prática

• Ano de defesa: 2010
• Autor(a) principal: Rodrigues, Carlos Diego
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Programação (Matemática); Teoria dos jogos; Métodos híbridos
• Link de acesso: http://www.repositorio.ufc.br/handle/riufc/61245

0 objetivo principal dessa tese é mostrar como a hibridização de métodos de áreas relacionadas nos permite avançar na resolução de problemas difíceis da Programação Matemática. Para este fim, nós aplicamos técnicas que combinam a Programação Matemática com outras teorias, especificamente a Programação por Restrições e Teoria dos Jogos, e aplicamos à problemas clássicos da teoria (Problema das Mochilas Múltiplas e Problema da Mochila Quadrática) e a um problema prático (Busca de um alvo inteligente). Para o estudo dos problemas teóricos partimos do Problema da Mochila, clássico problema NP-difícil da literatura que possui soluções eficazes. No entanto, as variantes que estudamos, o Problema das Mochilas Múltiplas e o Problema da Mochila Quadrático, mostram-se desafiadoras mesmo para instâncias relativamente pequenas. Tais problemas interessam à área por serem a base de muitos outros problemas de Programação MatemAtica. Já para o estudo prático, partimos de um problema clássico da Teoria dos Jogos, o problema de busca de um alvo móvel e inteligente. Para resolvê-lo, modelamos tal problema como um problema de programação linear 0-1. Essa abordagem inovadora permite uma resoluç'do do problema por meio (de simulação. Para cada um dos problemas fizemos experimentos computacionais que atestam o desempenho das técnicas propostas e os resultados foram comparados aos melhores resultados conhecidos em cada um dos casos. Podemos atestar, seguindo diversas referências na Area, que as técnicas híbridas proveem um importante conjunto de ferramentas matemáticas para a solução de problemas de diversos domínios.