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

Autores

  • André Rodrigues Monticeli Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil
  • 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 R2 e o R3.

Downloads

Não há dados estatísticos.

Biografia do Autor

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

Possui Doutorado em Engenharia de Produção, na área de Modelagem e Otimização, pela Universidade Federal de Itajubá - UNIFEI, Mestrado em Matemática pela Universidade Estadual de Campinas - UNICAMP e Graduação em Matemática pelo Centro Universitário do Sul de Minas - UNIS. Atualmente é professor efetivo EBTT do Centro Federal de Educação Tecnológica de Minas Gerais - CEFET/MG. Tem experiência na área de Matemática, com ênfase em Matemática Aplicada, atuando principalmente nos seguintes temas: ensino de matemática e pesquisa operacional - Otimização.

Paulo César Mappa, Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil

Doutor(2004) em ciências da Engenharia Mecânica, análise computacional de estruturas, pela COPPE, Universidade Federal do Rio de Janeiro, mestre em ciências da Engenharia Civil, análise computacional de estruturas, pela COPPE, Universidade Federal do Rio de Janeiro (1999), e Engenheiro Civil pela Universidade Federal de Ouro Preto (1991). Atualmente é professor do CEFET-MG, Unidade de Varginha, Tem interesse na áreas de Otimização Estrutural, Métodos Computacionais em Engenharia e Computação Científica.

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.

Downloads

Publicado

2021-01-15

Como Citar

MONTICELI, A. R.; MAPPA, P. C. 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, v. 7, n. 1, p. e3004, 15 jan. 2021.

Edição

Seção

Matemática