A otimização linear tem sido objeto de estudo desde a publicação do método simplex em 1947, o qual vem sendo utilizado na prática com relativa eficiência. Com isso, inúmeras variantes deste método surgiram na tentativa de se obter métodos mais eficientes, além de várias implementações objetivando a resolução de problemas de grande porte. Os problemas de otimização linear canalizados e esparsos, objeto principal deste trabalho, são problemas de grande interesse prático, pois representam vários problemas reais, como por exemplo, problemas da programação da produção, problemas de mistura e muitos outros. O método dual simplex canalizado com busca linear por partes é um método do tipo simplex especializado para os problemas de otimização linear canalizados e será detalhado neste trabalho. Experiências computacionais foram realizadas para algumas classes de problemas de otimização linear com o objetivo de analisar o desempenho deste método, o qual foi implementado com algumas heurísticas de pivoteamento e formas de atualização da matriz básica para tentar manter a esparsidade presente e reduzir o tempo de resolução dos problemas.

Linear optimization has been studied since 1947 when the simplex method was published by George Dantzig, and ií is still successlully used in practice. A number of varianls to the simplex method have been proposed trying to obtain better efficiency. In addition, various implementations have been proposed to deal with large scale problems. Two-side constraints and sparse linear optimization problems, the main object of this work, are of great interest in practice, since they represent a number of real problems, such as, production planning problems. mix problems and others. This work presents a simplex-typed method, named two-side constraint dual simplex method with piecewise linear search. This method was implemented together with some heuristics to handle sparsity and run to solve a set of linear optimization problems in order to analyse their computational performance.