Nova metodologia para resolução de problemas de transporte em casos esparsos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSilva, Arinei Carlos Lindbeck da, 1960--
Autor(es): dc.contributorUniversidade Federal do Paraná. Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia-
Autor(es): dc.creatorSilva, Tânia Cordeiro Lindbeck da-
Data de aceite: dc.date.accessioned2019-08-21T23:58:56Z-
Data de disponibilização: dc.date.available2019-08-21T23:58:56Z-
Data de envio: dc.date.issued2012-05-21-
Data de envio: dc.date.issued2012-05-21-
Data de envio: dc.date.issued2012-05-21-
Fonte completa do material: dc.identifierhttp://hdl.handle.net/1884/26810-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/26810-
Descrição: dc.descriptionResumo: Entre áreas de estudo da Programação Linear o Problema de Transporte é uma das aplicações de destaque. Os Problemas de Transporte podem ser classificados em densos ou esparsos. O modelo é denominado denso quando existem todas as ligações entre origens e destinos e esparsos quando algumas ou várias destas ligações não existem. O presente trabalho propõe uma alteração no algoritmo de resolução do Problema de Transporte para o caso esparso, que consiste basicamente da inclusão de uma nova origem e um novo destino com elevado custo de transporte para as origens e destinos originais e custo nulo entre a origem e destino acrescentados. O método é demonstrado e testado para instâncias geradas aleatoriamente. Depois de feita a explanação sobre o funcionamento do método e de demonstrar a validade das modificações, os conceitos são implementados computacionalmente. Os testes realizados mostram ganhos significativos no tempo de processamento. Para problemas com densidade 0,05, este tempo chega a ser de somente 25% do necessário para resolver o mesmo problema através do algoritmo tradicional, onde as ligações não existentes são admitidas com custo extremamente elevado. Em problemas com densidade 0,3 este tempo é de aproximadamente 50% daquele necessário pelo tradicional. O método desenvolvido tem desempenho equivalente quando utilizado sobre Problemas Densos. Também é feita uma explanação sobre a utilização de grafos, que são facilitadores na determinação de locais para colocação de variáveis degeneradas e sua aplicação na determinação dos ciclos. Discute-se a importância de utilizar características peculiares de um problema para métodos específicos de resolução. A economia no processamento pode viabilizar a utilização de modelagens deste tipo em processos meta-heurísticos que utilizem iterativamente o problema de transporte.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Palavras-chave: dc.subjectTeses-
Palavras-chave: dc.subjectProgramação linear-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectAlgoritmos-
Título: dc.titleNova metodologia para resolução de problemas de transporte em casos esparsos-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.