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.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-16062015-111938 |
| Date | 17 December 2002 |
| Creators | Ghidini, Carla Taviane Lucke da Silva |
| Contributors | Arenales, Marcos Nereu |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0019 seconds