Uma análise da utilização do método de eliminação de Fourier-Motzkin para encontrar um ponto interior a um poliedro

André Rodrigues Monticeli; Paulo César Mappa

doi:10.35819/remat2021v7i1id4305

Autores

André Rodrigues Monticeli Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil https://orcid.org/0000-0003-4049-5581
Paulo César Mappa Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil https://orcid.org/0000-0001-8192-8991

DOI:

https://doi.org/10.35819/remat2021v7i1id4305

Palavras-chave:

Sistemas de Inequações Lineares, Poliedro, Ponto Interior, Eliminação de Fourier-Motzkin

Resumo

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² e o R³.

Downloads

Os dados de download ainda não estão disponíveis.

Biografia do Autor

André Rodrigues Monticeli, Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil

http://lattes.cnpq.br/0996675223199497
Paulo César Mappa, Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil

http://lattes.cnpq.br/0342332166757546

Referências

AJSPUR, Mai Lise; JENSEN, Rune Moller. Usubg Fourier-Motzkin-Elimination to Derive Capacity models of Container Vessels. IT University Thechnical Report Series, University of Copenhagen, Dinamarca, jan. 2017. Disponível em: https://en.itu.dk/research/technical-reports/technical-reports-archive/2017/tr-2017-197. Acesso em: 9 dez. 2020.

BARVINOK, Alexander; POMMERSHEIM, James E. An Algorithmic Theory of Lattice Points in Polyhedra. New Perspectives in Geometric Combinatorics, MSRI Publications, v. 38, 1999. Disponível em: https://www.maths.ed.ac.uk/~v1ranick/papers/barvpomm.pdf. Acesso em: 9 dez. 2020.

CARTIS, Coralia; Gould, Nicholas I. M. Finding a point in the relative interior of a polyhedron,

with applications to compressed sensing. In: SPARTS'09 – SIGNAL PROCESSING WITH ADAPTIVE SPARSE STRUCTURED REPRESENTATIONS, Saint Malo France, 2009. Disponível em: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.298&rep=rep1&type=pdf. Acesso em: 9 dez. 2020.

CUI, Shulin; ZHANG, Shuqing; CHEN, Xuanxi; PANG, Zhenping; FU, Xiaoyang; XU, Zhang. Point-in-polyhedra test with direct handling of degeneracies. Geo-spatial Information Science, v. 14, n. 2, p. 91-97, 2011. DOI: https://doi.org/10.1007/s11806-011-0453-8.

DAHL, Geir. Combinatorial properties of Fourier-Motzkin elimination. The Electronical Jounal of linear Algebra, v. 16, p. 334-346, out. 2007. Disponível em: https://www.elibm.org/article/10010887. Acesso em: 9 dez. 2020.

DEMMEL, James W. Applied Numerical Linear Algebra. Philadelphia: Society of Industrial and Applied Mathematics, 1997. DOI: https://doi.org/10.1137/1.9781611971446.

FOURIER, Jean-Baptiste J. Ouvress II. Paris, 1890.

LAURITZEN, Niels. Lectures on convex sets. Department Of Mathematical Sciences, University of Aarhus, Denmark, mar. 2009. Disponível em: https://www.fmf.uni-lj.si/~lavric/lauritzen.pdf. Acesso em: set. 2020.

MONTICELI, André R. Um estudo sobre sistemas de inequações lineares. Orientador: Cristiano Torezzan. 2010. 118 p. Dissertação (Mestrado em Matemática) – Instituto de Matemática, Estatística e Computação Científica (IMECC), Universidade Estadual de Campinas, Campinas, SP, 2010. Disponível em: http://repositorio.unicamp.br/bitstream/REPOSIP/306906/1/Monticeli_AndreRodrigues_M.pdf. Acesso em: 9 dez. 2020.

MONTICELI, André R.; TOREZZAN, Cristiano. Método de Eliminação de Fourier-Motzkin. In: ENCONTRO REGIONAL DE MATEMÁTICA APLICADA E COMPUTACIONAL (ERMAC 2010), 1., São João del-Rei, MG, 11 a 13 nov. 2010. Anais [...]. Universidade Federal de São João del-Rei, p. 258-264, 2010. Disponível em: https://www.ufsj.edu.br/portal2-repositorio/File/i-ermac/anais/sessoes-tecnicas/st11.pdf. Acesso em: 9 dez. 2020.

MOTZKIN, T. S. Beiträge zur Theorie der linearen Ungleichungen. Thesis, 1936. Reprinted in: Theodore S. Motzkin: selected papers (D. Cantor et al.), Birkhäuser, Boston, 1983.