Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/61245| Type: | Tese |
| Title: | Abordagens híbridas na solução de problemas de programação inteira da teoria e prática |
| Other Titles: | Approches hybrides dans la résolution de problèmes de théorie et de la pratique |
| Authors: | Rodrigues, Carlos Diego |
| Advisor: | Michelon, Philippe |
| Co-advisor: | Campêlo Neto, Manoel Bezerra |
| Keywords: | Programação (Matemática);Teoria dos jogos;Métodos híbridos |
| Issue Date: | 2010 |
| Citation: | RODRIGUES, Carlos Diego. Abordagens híbridas na solução de problemas de programação inteira da teoria e prática. 2010. 118 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2010. |
| Abstract in Brazilian Portuguese: | 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. |
| Abstract in French: | Le principal objectif de cette these est de montrer l'avantage que présente l'utilisation de techniques multidisciplinaires pour la resolution de problémes difficiles de la Programmation Mathématique. Pour cela, nous utilisons des techniques hybrides mélant la Programmation Math- ématique et d'autres theories comme la Programmation par Contraintes et la Théorie des Jeux. Puis nous appliquons ces techniques à des problémes classiques, disons aussi académiques (Probleme du Sac-d-dos Multidimensionnel et Sac-A-dos Quadratique) et, également, à un probleme pratique (la recherche d'une cible intelligente). Les problemes académiques étudiés sont lies au probleme classique du sac-A-dos pour lequel, malgré son caractere NP-difficile, il existe des méthodes exactes de resolution. Ses generalisations, le Probleme du Sac-d-dos Multidimensionnel et le Probleme du Sac-d-dos Quadratique se montrent en revanche plus hardues à résoudre, même pour des instances de petite taille. L'étude pratique est basée sur un probleme classique de la Théorie des Jeux, le probléme de la recherche d'une cible mobile et inteligente. Pour le résoudre nous le modelisons comme une Probléme de Programmation Linéaire en Nombres Entiers 0-1. Cette nouvelle approche permet tine solution du probléme au moyen de la simulation statistique. Des experimentations numériques sont menées pour chaque probleme traité et dómontrent la performance des techniques développées en comparaison avec les résultats de la littérature. Ces résultats nous aménent à penser que les techniques multidisciplinaires constituent tres certainement un outil efficace pour la resolution de problemes issus d'horizons divers |
| URI: | http://www.repositorio.ufc.br/handle/riufc/61245 |
| Appears in Collections: | DCOMP - Teses defendidas na UFC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2010_tese_cdrodrigues.pdf | 21,76 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.