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

Endereço:
Rua. Gen. Osório - Centro
Bento Gonçalves / RS
Site: https://periodicos.ifrs.edu.br/index.php/REMAT
Telefone: (54) 3204-2100
ISSN: 2447-2689
Editor Chefe: Greice da Silva Lorenzzetti Andreis
Início Publicação: 02/08/2015
Periodicidade: Semestral
Área de Estudo: Ciências Exatas, Área de Estudo: 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

Ano: 2021 | Volume: 7 | Número: 1
Autores: André Rodrigues Monticeli, Paulo César Mappa
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.