Uma análise da utilização do método de eliminação de Fourier-Motzkin para encontrar um ponto interior a um poliedro
REMAT: Revista Eletrônica da Matemática
Uma análise da utilização do método de eliminação de Fourier-Motzkin para encontrar um ponto interior a um poliedro
Autor Correspondente: André Rodrigues Monticeli | [email protected]
Palavras-chave: Sistemas de Inequações Lineares; Poliedro; Ponto Interior; Eliminação de Fourier-Motzkin
Resumos Cadastrados
Resumo Português:
O problema de encontrar um ponto interior a um poliedro tem aplicações em muitas áreas, sobretudo em programação linear. Neste trabalho, abordamos o problema de encontrar um ponto interior a um poliedro, utilizando como estratégia o Método de Eliminação de Fourier-Motzkin. Este método consiste em reduzir um sistema de inequações lineares que define o poliedro, através da eliminação de variáveis. Foi-se utilizada uma versão matricial deste método a fim de facilitar sua implementação computacional e, para ilustrar a metodologia proposta, exemplos são apresentados. Em seguida, fizemos a análise de complexidade do algoritmo, com a finalidade de investigar o comportamento da técnica quando do aumento do número de variáveis e de restrições e, dessa forma, apresentando um campo de aplicação da técnica. Pela análise do algoritmo, concluímos que este tem complexidade exponencial, pois o número de inequações cresce exponencialmente conforme se aumenta o número de variáveis no problema. O algoritmo se mostrou eficiente para problemas com um número pequeno de inequações para o R^2 e o R^3.
Resumo Inglês:
The issue of finding an interior point to a polyhedron has applications in many areas, especially in linear programming. In this work we approach the issue of finding an interior point to a polyhedron using the Fourier-Motzkin Elimination Method approach. It consists of reducing a system of linear inequalities that defines the polyhedron, by eliminating variables. A matrix version of this method was employed in order to facilitate its computational implementation, and some examples were presented with the purpose of illustrating the proposed methodology. Subsequently the complexity analysis of the algorithm was carried out in order to investigate the behavior of the technique when increasing the number of variables and restrictions and, thus, presenting a field of application to the technique. By analyzing the algorithm, we concluded that it has exponential complexity, since the number of inequalities grows exponentially as the number of variables in the issue increases. The algorithm proved to be efficient for issue with a small number of inequalities for R^2 and R^3.