Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/10085
Título: | Matroides e interseção de matroides em problemas de otimização combinatória |
Autor: | Dias, Ayagi da Mota |
Orientador: | Agra, Agostinho Miguel Mendes |
Palavras-chave: | Matemática aplicada Matróides Optimização combinatória Poliedros |
Data de Defesa: | 2012 |
Editora: | Universidade de Aveiro |
Resumo: | Nesta tese são revistos conceitos básicos que relacionam a teoria dos matroides com a otimização combinatória. São expostos, de
forma uniformizada, vários resultados e conceitos bem conhecidos, mas apresentados em textos diversos. Além dos conceitos básicos
são igualmente apresentados algoritmos exatos que permitem resolver problemas de otimização cujo conjunto de soluções admissíveis forma
um matroide ou corresponde à interseção de dois matroides. É dado ênfase ao estudo poliédrico dos problemas de otimização. Em
particular são estudadas algumas relações da função caraterística com restrições e desigualdades válidas para vários problemas de otimização bem conhecidos, como o problema do Saco-Mochila e da Arvore de Suporte de Custo Mínimo. Seguindo Amado, 1997, é estudada a estrutura poliédrica de famílias particulares do problema de sacomochila
cuja descrição poliédrica é feita com base em desigualdades de cobertura estendida. Com base nessa família são apresentados minorantes e majorantes para o problema do saco-mochila. In this thesis we revise basic concepts relating matroid theory with combinatorial otimization. We present, in an uni ed way, several well-known results and concepts that are given in di erent sources. In addition to the basic concepts we also give exact algorithms for otimization problems where the feasible set is either a matroid or it can be obtained as the intersection of two matroids. We focus on the polyhedral study of the otimization problem. In particular, we study the relation between the characteristic function and constraints and valid inequalities for several well-known optimization problems as the knapsack problem and the minimum spanning tree. Following Amado, 1997, we study the polyhedral of particular families of the knapsack problem whose polyhedral description is based on extended cover inequalities. Based on those families we discuss lower and upper bounds for the knapsack problem. |
Descrição: | Mestrado em Matemática e Aplicações - Matemática Empresarial e Tecnológica |
URI: | http://hdl.handle.net/10773/10085 |
Aparece nas coleções: | UA - Dissertações de mestrado DMat - Dissertações de mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
tese_ayagi dias.pdf | 862.22 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.