Купить СНПЧ А7 Архангельск, оперативня доставка

crosscheckdeposited

Uma Aplicação de Grafos a Um Problema Agrícola, Envolvendo Distribuição de Água e Transportes

DOI: http://dx.doi.org/10.13083/1414-3984.v19n03a02

http://www.seer.ufv.br/seer/index.php/reveng/index 

downloadpdf

Amarildo de Vicente1 & Rogério L. Rizzi2

 

Resumo: Propriedades agrícolas têm necessidade de melhor planejamento da distribuição de tubulações utilizadas para irrigação e, ainda, de racionalização de estradas para veículos. Por isso, este trabalho está subdividido em dois objetivos: o primeiro consiste em determinar por onde deve passar uma rede de tubos, destinada à ligação de diversos pontos em uma área de cultivo, a fim de minimizar a quantidade de tubos; o segundo consiste em encontrar, nesta área, o menor caminho para a passagem de um veículo, que deve visitar os pontos citados, contidos em um projeto agrícola para uma propriedade rural, situada no noroeste do Paraná. Estes problemas foram resolvidos, usando-se recursos da teoria dos grafos. O primeiro, por meio de uma árvore geradora mínima e, o segundo, por meio de um algoritmo para o problema do caixeiro viajante. As soluções destes problemas mostraram que o produtor poderia ter usado 139,4 metros a menos de tubos, em relação ao sistema já implantado, bem como um caminho com 65,3 metros a menos, em relação ao caminho ora utilizado.

Palavras-chave: distribuição de água, árvore de expansão mínima, caminho mínimo

 

Abstract: Agricultural properties need to have better planning of distribution pipes used for irrigation and also to rationalize road vehicles. Therefore, this paper is divided into two objectives: the first is to determine by where to pass a network of tubes, for the lead of several points in a cultive area in order to minimize the amount of tubes; the second consists of find in this area, the shortest path for passage of a vehicle which must visit the points above, contained in an agricultural project for a rural property, situated in the northwest of Paraná. These problems were solved, using resources of graph theory. The first, using a minimum spanning tree and the second by means of an algorithm for the traveling salesman problem. Solutions of these problems showed that the producer could have used less than 139.4 meters tubes in relation to the system already set up and a way with 65.3 meters unless on the path now used.

Key words: water distribution, minimum spanning tree, minimum path

 

1 Graduado em Licenciatura em Matemática pela UEM. Doutor em Engenharia de Produção pela UFSC. Docente do Programa de Pós-Graduação em Energia na Agricultura, Centro de Ciências Exatas e Tecnológicas - Unioeste/Cascavel, email: amarildo.vicente@unioeste.br
2 Graduado em Licenciatura em Matemática pela UNIOESTE. Doutor em Ciência da Computação pela UFRGS. Docente do Centro de Ciências Exatas e Tecnológicas da Unioeste/Cascavel, email: rogeriorizzi@gmail.com.

 

Literatura Citada

BARÃO, F.R.; KRIPKA, M.; KRIPKA, R.M.L. Determinação da Rota Ótima para a Coleta de Resíduos Sólidos Urbanos no Município de Passo Fundo – RS. In: XXXI CONGRESSO NACIONAL DE MATEMÁTICA APLICADA E COMPUTACIONAL, 08 a 11 de setembro de 2008, Belém. Anais... Belém: CNMAC, 2008. p.7

BOAVENTURA, P.O.N. Teoria e Modelos de Grafos. São Paulo: Editora Edgard Blücher, 2003. 314p.

CHEKURI, C.; PAL, M. An O(log n) approximation Ratio for the Asymmetric Traveling Salesman Path Problem. Theory of Computation, cidade, v.3, p.197-209, 2007. Disponível em <http:// www.theoryofcomputing.org/articles/v003a010>. Acesso em 04 ago. 2010.

GOLDBARG, M.C; LUNA H.P.L. Otimização Combinatória e Programação Linear: modelos e algoritmos. Rio de Janeiro: Editora Campus, 2005. 51 p.

LARSON, R.C.; OLDONI, A.R. Urbans Operations Research. New Jersey: Prentice-Hall, Inc., Englewood Cliffs, 1981. 571p.

RABUSKE, M.A. Introdução à Teoria dos Grafos. Florianópolis: Editora da UFSC, 1992. 173 p.

RADUAN, A. C. Roteirização Parcialmente Dinâmica Aplicada a Serviços de Campo. 2009. 121f Dissertação (Mestrado em Engenharia) Escola Politécnica da Universidade de São Paulo - Departamento de Engenharia de Transportes, São Paulo. 2009.

SANTOS, A.C. Utilização da Programação Linear na Determinação da Combinação que Maximize a Renda da Empresa Rural. Caderno de Administração Rural, Lavras, v.2, n.2, p.109-125, jul./dez. 1990.

SNYDER, T.L.A. Priori Inequalities for the Euclidean Travelling Salesman Problem. Proceedings of the Eight Annual Symposium: Computational Geometry, New York, ACM Press, v.24, p.344-349, 1992. Disponível em <http://www-stat.wharton.upenn.edu/~steele/Publications>. Acesso em 04 ago. 2010.

VEREIJKEN, P. Experimental Systems of Integrated and Organic Wheat Production. Agricultural Systems, England, Elsevier Science Publishers Ltd, v.30, p.187-197, 1989.

VEREIJKEN, P. From Conventional to Integrated Agriculture. Netherlands Journal of Agricultural Science, Wageningen, v.34, n.3, p.387-393, 1986.