Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306525
Type: TESE DIGITAL
Title: Quatro perspectivas sobre métodos baseados em pontos extremos para programação linear
Title Alternative: Four perspectives about extreme point based methods for linear programming
Author: Lemos, Luiz Fernando Ramos, 1985-
Advisor: Santos, Sandra Augusta, 1964-
Abstract: Resumo: 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 NETLIB

Abstract: 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 collection
Subject: Programação linear
Algoritmos
Dualidade (Matemática)
Simplex (Matemática)
Experimentos numéricos
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Lemos_LuizFernandoRamos_M.pdf14.5 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.