Four perspectives about extreme point based methods for linear programming

Orientador: Sandra Augusta SantosDissertação (mestrado) Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação CientíficaResumo: Este trabalho apresenta dois métodos para a solução do problema de Programação Linear, Mé- todo de Cones de Crescimento e Método de Cones com Redução Viável, que utilizam mecanismos algébricos diferentes do Simplex e do Dual Simplex. Para tal, apresentamos duas formas de pen- sar geometricamente o problema de Programação Linear por pontos extremos, viáveis ou não, e duas formas de representar geometricamente estes pontos, via soluções básicas e translações bá- sicas. É demonstrada a equivalência entre as abordagens algébricas usadas pelos quatro métodos e, por não se basear na dedução do Método Simplex e nem na teoria de dualidade, este trabalho constitui um outro caminho para demonstrar os métodos tradicionais e a dualidade entre problemas de Programação Linear. Por fim, ilustramos a equivalência por testes computacionais em problemas selecionados, e apresentamos uma implementação revisada do Método de Cones de Crescimento e sua comparação com o Método Simplex do pacote MATLAB® em testes no conjunto de problemas NETLIBAbstract: In this work two methods for Linear Programming are presented: the Increasing Cones Method and the Method of Cones with Feasible Reduction. The algebraic schemes of these methods are different from those of the Simplex Method and of the Dual Simplex Method. Two ways of geomet- rically addressing the Linear Programming problem by means of the geometric representation of the extreme points are discussed based on basic solutions and basic translations. Equivalence among the algebraic schemes are proved. By not employing techniques from the Simplex Method nor from duality theory, this work can be seen as an option to reach the traditional methods and duality in Linear Programming. The equivalences are illustrated by means of simple examples and computa- tionally validated with a revised implementation of the Increasing Cones Method in comparison with the Simplex Method (routine linprog of MATLAB®) for the solution of selected problems from the NETLIB collectionMestradoMatematica AplicadaMestre em Matemática AplicadaCAPESFuncam