Resumo: Neste trabalho, propomos um novo algoritmo que surgiu da generalização do algoritmo de redução por pesos, para resolver problemas de programação linear, o qual é chamado de algoritmo de redução por pesos para $p$ coordenadas. Este novo algoritmo foi desenvolvido com base no algoritmo de von Neumann e na ideia apresentada por \citet{Jair2009} para melhorar o desempenho do algoritmo de ajustamento pelo par ótimo, considerando $p$ coordenadas. Assim como o algoritmo de von Neumann, o novo algoritmo apresenta características interessantes, tais como rápida convergência inicial e simplicidade. No entanto, sua utilidade é limitada devido à sua convergência consideravelmente lenta. Dessa forma, o objetivo é melhorar o desempenho do algoritmo ao aumentar o número de coordenadas no cálculo das direções e utilizá-lo em conjunto com outros algoritmos, como por exemplo para auxiliar no cálculo do ponto inicial do método de pontos interiores. No método de redução por pesos, a direção $d$ é calculada utilizando apenas duas coordenadas, na nova proposta, a direção é calculada utilizando $p$ coordenadas, escolhendo $p/2$ colunas que formam os menores ângulos com o resíduo e $p/2$ colunas que formam os maiores ângulos. Ao utilizar mais coordenadas existe a possibilidade de encontrar uma direção melhor para mover o resíduo para mais perto da origem mais rapidamente, com isso o desempenho do algoritmo pode ser melhorado. Os primeiros experimentos computacionais realizados no Matlab mostraram que, ao usar o novo algoritmo, obtemos uma diminuição muito mais rápida no valor do resíduo à medida que o valor de $p$ aumenta. Analisamos também como o número de iterações exigidas para atender ao critério de parada e o tempo necessário variam em relação a cada valor de $p$. Além disso, com o objetivo de acelerar a convergência do método de pontos interiores, algumas iterações deste algoritmo generalizado são utilizadas em conjunto com a heurística de Mehrotra, que calcula o ponto inicial para o método de pontos interiores no \textit{software} PCx. Experimentos computacionais realizados em uma série de problemas de programação linear indicaram que essa ideia reduz tanto o número total de iterações quanto o tempo de processamento para muitos desses problemas, inclusive os de grande porte Ver menos

Abstract: In this work, we propose a new algorithm that emerged from the generalization of the weight reduction algorithm, to solve linear programming problems, which we call the weight reduction algorithm for $p$ coordinates. This new algorithm was developed based on the von Neumann algorithm and on the idea presented in \citet{Jair2009} to improve the performance of the optimal pair adjustment algorithm, considering $p$ coordinates. Like von Neumann's algorithm, the new algorithm exhibits interesting characteristics such as fast initial convergence and simplicity. However, its usefulness is limited due to its considerably slow convergence. Therefore, the objective is to enhance the algorithm's performance by increasing the number of coordinates in the calculation of directions and using it in conjunction with other algorithms, such as to assist in the calculation of the initial point of the interior point method. In the weight reduction method, the $d$ direction is calculated using only two coordinates, in the new proposal, the direction is calculated using $p$ coordinates, choosing $p/2$ columns that form the smallest angles with the residue and $p/2$ columns that form the largest angles. By using more coordinates there is the possibility of finding a better direction to move the residue closer to the origin more quickly, with this the performance of the algorithm can be improved. The first computational experiments conducted on Matlab showed that by using the new algorithm, we get a much faster decrease in the value of the residue as the value of $p$ increases. We also looked at how the number of iterations required to meet the stop criterion and the time required vary for each $p$ value. In addition, in order to accelerate the convergence of the interior point method, some iterations of this generalized algorithm are used in conjunction with the Mehrotra heuristic, which calculates the initial point for the interior point method in \textit{software} PCx. Computational experiments performed on a number of linear programming problems have indicated that this idea reduces both the total number of iterations and the processing time for many of these problems, including large ones Ver menos