Texto completo
| |
| Autor(es): |
Lidio Nunes de Abreu Junior
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2000-05-29 |
| Membros da banca: |
João Carlos Setubal;
Cid Carvalho de Souza
|
| Orientador: | João Carlos Setubal |
| Resumo | |
O assunto principal desta tese é o problema da designação: dado um grafo bipartido com custos nas arestas, obter um emparelhamento perfeito de custo mínimo. Na primeira parte do trabalho apresentamos uma revisão detalhada dos conceitos e principais resultados da literatura sobre esse problema. Na segunda parte, discutimos uma variante paramétrica, na qual cada aresta e tem seu custo dado por uma expressão do tipo ce° + ?ce?, onde ce° e ce? são constantes e ? é o parâmetro, cujo valor é real e varia. Nesta variante o objetivo é obter todas as soluções do problema para um intervalo de valores de A no menor tempo possível. Nesta parte inicialmente fazemos uma revisão de resultados da literatura que apresentam técnicas gerais para a resolução de problemas paramétricos em Otimização Combinatória. Em seguida apresentamos uma abordagem, também da literatura, específica para o problema do fluxo de custo mínimo, do qual o problema da designação é um caso especial. Esta abordagem se baseia em propriedades do algoritmo simplex de rede. Em seguida apresentamos uma nova abordagem, baseada numa relação entre o problema do fluxo de custo mínimo e o problema do ciclo de razão mínima. A complexidade desta nova abordagem é insatisfatória quando se quer resolver uma instância do problema da designação paramétrico, pois a complexidade conhecida do problema do ciclo de razão mínima é maior do que a complexidade conhecida do problema da designação. Esta nova abordagem entretanto é satisfatória do ponto de vista teórico quando aplicada ao problema do fluxo de custo mínimo paramétrico. O trabalho finaliza apresentando uma comparação experimental entre as abordagens "simplex de rede" e "ciclo de razão mínima" para o problema do fluxo mínimo paramétrico, mostrando que a primeira é muito superior à segunda. (AU) | |
| Processo FAPESP: | 97/11222-0 - Computacao local e o problema da designacao. |
| Beneficiário: | Lidio Nunes de Abreu Junior |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |