Estudo de um problema de programação linear de grande porte para a alocação de sortimentos baseado em um caso real - Coliboro, Thiane Pereira Poncetta (2024)
Este trabalho estuda e discute métodos de resolução de um problema de programação linear de grande porte proveniente da modelagem de um problema real de alocação de sortimento. Traz um estudo do problema e do modelo matemático, desde o banco de dados até a interpretação da solução ótima obtida para a empresa. São analisados aspectos teóricos, computacionais e numéricos do problema. Considerando as características do problema, a abordagem escolhida para resolvê-lo é o método de pontos interiores, comparando a resolu- ção dos sistemas lineares por métodos diretos e por métodos iterativos, este último usando o método dos gradientes conjugados com uma abordagem híbrida de precondicionamento. É proposta uma redução no modelo matemático do problema que melhora a convergência dos métodos de pontos interiores, sem depender de um preprocessamento intensivo. São testados também diferentes métodos e softwares, livres e comerciais, para a sua resolução, cujo número de iterações do método de pontos interiores é muito maior do que usual. É apresentado um estudo do condicionamento dos sistemas lineares e da influência e eficiência dos precondicionadores para o número de condição das matrizes dos sistemas lineares. São propostos aprimoramentos para a abordagem híbrida, modificando o valor inicial do parâmetro de preenchimento da fatoração incompleta utilizada e alterando o critério de atualização desse parâmetro. São discutidos os comportamentos dos resíduos primal e dual e do gap de dualidade, bem como alternativas para acelerar a convergência dos métodos de pontos interiores. Também, são apresentados resultados de testes feitos com outro software baseado na resolução iterativa dos sistemas lineares, além dos resultados com outra variante de resolução baseada em fatorações incompletas. Resultados de testes computacionais para instâncias com diferentes abordagens de resolução são apresentados e discutidos.