Closed Circuit Optimization in Oriented Graphs

• Grant number: 11/03486-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: June 01, 2011
• End date: May 31, 2012
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Geometry and Topology
• Principal Investigator: Eduardo Garibaldi
• Grantee: Rodolfo Nobre Bitu de Morais
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 07/06896-5 - Geometry of control, dynamical and stochastic systems, AP.TEM

Abstract

Como pode uma empresa de distribuição de mercadorias escolher quais os pontos em uma metrópole nos quais estabelecer sua sede operacional significa ter a sua disposição o maior número de rotas com custo médio minimal para explorar? Esta e outras perguntas semelhantes envolvendo a determinação de percursos com, por exemplo, máxima rentabilidade ou mínimo desperdício médios podem ser abordadas em uma formulação matemática geral: a otimização ergódica de processos markovianos com um número finito de estados. Em termos teóricos, dado um grafo finito orientado transitivo, associa-se a cada aresta um valor numérico indicando, conforme o caso, despesa ou premiação ao trafegar entre os vértices por esta unidos. Há particular interesse em examinar circuitos fechados, isto é, caminhos sobre o grafo que iniciam e terminam em um mesmo vértice. A meta é discutir técnicas assegurando identificação de todos os circuitos fechados com média optimal de percurso.