Studing system of linear inequalities

Neste trabalho abordamos o problema de descrever o conjunto solução de um sistema de inequações lineares. Este problema está fortemente relacionado com o problema clássico da enumeração de vértices de um poliedro. Descrevemos o método de Fourier-Motzkin que pode ser utilizado para eliminar variáveis de um sistema de inequações lineares e projetar a região de solução num espaço de dimensão menor. Mostramos como o problema da enumeração de vértices pode ser convertido em um problema de encontrar o fecho convexo do conjunto de pontos dual ao sistema de inequações lineares, uma vez encontrado um ponto interior factível. Alguns algoritmos para o fecho convexo de um conjunto finito de pontos e também para encontrar um ponto interior factível são estudados. Nosso interesse, além de listar os vértices e as faces é também visualizar a região de solução utilizando um programa computacional. Para tanto propomos um método que constrói a lista dos vértices e faces do poliedro definido por um dado sistema de inequações lineares e grava o resultado num arquivo de texto puro com extensão obj, que é compatível com os principais softwares de visualização gráfica 3D. O método foi implementado no Octave e diversos testes foram feitos, analisando o custo computacional e possíveis dificuldades que podem surgir devido a erros numéricos ou falta de memóriaIn this work we approach the problem of describing the solution of a system of linear inequalities. This problem is closely related to the classical problem known as vertex enumeration. We describe the method of Fourier-Motzkin, that can be used to eliminate variables in a system of linear inequalities, projecting its solution in a lower dimensional space. We show how the vertex enumeration problem can be converted into an equivalent problem of finding the convex hull of a set of dual points, once found a feasible interior point. Some algorithms for convex hull and also for finding a feasible interior point are studied. Our interest is not only to store the vertices and faces but also visualize the correspondent polyhedron using a computer graphics software. In this way we propose a method that stores the polyhedron's vertices and faces and output the results into a plain text _le with extension obj, which is a geometric definition file format that can be opened with all major 3D graphics software. The method was implemented in Octave and several tests were made, analyzing the computational cost and possible difficulties that may arise due to numerical errors or memory requirement