Orientador : Prof. Dr. Arinei Carlos Lindbeck da Silva / Tese (doutorado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 12/09/2014 / Inclui referências / Resumo: Dentre os problemas de Pesquisa Operacional, o Problema de Transporte (PT) é destacado como um dos mais importantes, devido a sua estrutura especial e, principalmente, pelas aplicações que não se limitam a problemas de distribuição. Para a resolução do Problema de Transporte, é amplamente conhecido na literatura e utilizado o método MODI, no qual são calculadas as variáveis duais e com base nelas recalculados os valores dos custos atualizados e que apresenta economia de tempo para resolução em relação ao método Stepping Stone. Na presente tese, a resolução do PT pelo método MODI foi realizada por uma implementação utilizando estrutura de quadro para armazenamento de informações e outra de árvore, sendo concluído que a resolução em árvore gerou uma economia média de 60,24% de tempo em relação à resolução em quadro. Foi demonstrado, sem a utilização das variáveis duais, que é possível o recálculo dos custos atualizados somente em função dos custos atualizados da iteração anterior e com a implementação deste resultado houve redução de 80,78% no tempo de resolução em relação à implementação do método MODI em árvore. Desta forma, a redução média da implementação em árvore recalculando somente os custos atualizados necessários foi de 92,34% em relação à implementação em quadro. Para reduzir ainda mais o tempo de resolução foi proposta uma nova forma de critério para escolha da variável não básica a entrar na base, utilizando uma lista, denominada ReferenciaCAN, menor de variáveis candidatas a tornarem-se básica na iteração e também um parâmetro, denominado PercentualEconomiaAnterior, para evitar a seleção de variáveis não básicas que não gerassem uma economia unitária menor que a desejada. Com isso foi possível reduzir o tempo médio de resolução em 37,06% em relação a situação anterior. De forma final, o tempo de resolução para o método e implementação final proposto na presente tese obteve uma redução de 95,18% em relação ao tempo médio da implementação clássica do método MODI em quadro. Palavras-chave: Problema de Transporte, método MODI, melhoria de solução, recálculo de custos atualizados, implementação computacional. / Abstract: Among the Operational Research problems, the Transportation Problem (TP) is highlighted as one of the most important, due to its special structure, and especially by applications that are not limited to distribution problems. In order to solve the Transportation Problem, it is widely known in the literature and used the MODI method, in which the dual variables are calculated and based on them the reduced costs are recalculated, providing time saving when compared to the Stepping Stone method. In this thesis, the PT solver by MODI method was performed by using an implementation in the tableau structure for storing information and other using tree structure. It was concluded that when the problems were solved using tree structure it was generated an average savings of 60.24% of time in comparison to tableau structure. Therefore, it was demonstrated without the use of the dual variables, that it is possible recalculation of reduced costs only considering reduced costs of the previous iteration and the implementation of this rule resulted in 80.78% reduction in time to solve when compared to the implementation of the method MODI using tree structure. Thus, the average reduction in tree implementation recalculating only the updated costs required was 92.34% in relation to the implementation in tableau structure. In order to reduce again the time a new way has been proposed as criteria for the choice of the non basic variable to enter the basis, using a list, called ReferenciaCAN, with fewer variables candidates to become basic at current iteration and also a parameter, called PercentualEconomiaAnterior, to avoid the selection of non-basic variables that do not generate a smaller unitary economy than desired. It was then possible to reduce the average resolution time by 37.06% compared to the previous situation. After the modifications, the solver time for the final implementation and method proposed in this thesis achieved a reduction of 95.18% compared to the average time the classical implementation of MODI method in tableau structure. Keywords: Transportation Problem, MODI method, solution improvement, reduced costs computing, computational implementation.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.c3sl.ufpr.br:1884/36338 |
| Date | January 2014 |
| Creators | Loch, Gustavo Valentim |
| Contributors | Silva, Arinei Carlos Lindbeck da, 1960-, Universidade Federal do Paraná. Setor de Tecnologia. Programa de Pós-Graduação em Métodos Numéricos em Engenharia |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 188f. : il. algumas color., grafs., tabs., application/pdf |
| Source | reponame:Repositório Institucional da UFPR, instname:Universidade Federal do Paraná, instacron:UFPR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Disponível em formato digital |
Page generated in 0.0133 seconds