[pt] Os problemas de alocação de recurso procuram encontrar uma repartição ideal de recursos a um número fixo de áreas. Nesta dissertação, consideramos um problema de alocação de recurso com uma função objetiva linear e dois conjuntos distintos de restrições: um conjunto de restrições aninhados, onde as somas parciais das variáveis de decisão são limitadas por cima e uma restrição linear que define um hiperplano. Propomos um algoritmo fracamente e um fortemente polinomial. O algoritmo fracamente polinomial requer algumas suposições sobre os dados e possui complexidade de O(n log n log |Λ|/|I|), onde n é o número de variáveis, Λ é um intervalo no espaço dual, e |I| está relacionado com a precisão dos dados. O algoritmo fortemente polinomial é baseado na técnica de busca paramétrica de Megiddo e obtém uma complexidade O(n log n). As complexidades obtidas são superiores à complexidade do método genérico de Pontos Interiores, O(n 3/ log n). Além disso, uma análise experimental foi realizada e os algoritmos mostraram-se mais eficientes e produziram soluções ótimas para instâncias de problemas com até 1.000.000 variáveis. / [en] The Resource Allocation Problems seek to find an optimal repartition of resources into a fixed number of areas. In this thesis, we consider a resource allocation problem with a linear objective and two distinct sets
of constraints: a set of nested constraints, where the partial sums of the decision variables are limited from above and a linear constraint that defines a hyperplane. We propose a weakly and a strongly polynomial algorithm. The weakly polynomial algorithm requires certain assumptions of the data and runs in O(n log n log |Λ|/|I|) time, where n is the number of decision variables, Λ is an interval in the dual space, and |I| relates to the precision of the data. The strongly polynomial algorithm is based on Megiddo s parametric search technique, and obtains a complexity of O(n log n). These are large improvements upon the O(n 3/ log n) complexity of the generic Interior Point Method. In addition, an experimental analysis was carried out and the algorithms showed to be more efficient and produced optimal solutions for problem instances with up to 1,000,000 variables.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:52179 |
| Date | 13 April 2021 |
| Creators | JOAO PEDRO TEIXEIRA BRANDAO |
| Contributors | THIBAUT VICTOR GASTON VIDAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0023 seconds