Busca avançada
Ano de início
Entree


O problema da designação e sua variante parametrica

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:
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