Algoritmos de cava otima - o que é pseudoflow
em , ,

Algoritmos de Cava Ótima: Pseudoflow

O que é Pseudoflow?

Anteriormente, conhecermos um pouco melhor sobre o que é Cava Ótima e sobre o clássico Algoritmo de Lerchs-Grossmann. Agora podemos avançar para um algoritmo mais recente, o Pseudoflow. Esse algoritmo sempre resulta na mesma solução que o algoritmo de Lerchs-Grossmann e é ainda mais rápido, o seu processamento.

 

Algoritmos de Cava Ótima: O Pseudoflow

O algoritmo Pseudoflow (pseudo-fluxo), descrito por Hochbaum, trata-se de um algoritmo pensado para resolver um problema de fluxo máximo em uma rede de fluxo. Descobriu-se que a solução desse problema é idêntica a solução do Lerchs-Grossmann para os mesmos dados de origem.

 

Pseudoflow para Cava Ótima

Para utilizar o algoritmo Pseudoflow a fim de resolver o problema da Cava Ótima, deve-se transformar os dados do modelo de blocos em um grafo direcionado representando uma rede de fluxo. Um grafo direcionado consiste em nós ligados por arcos que possuem direção e capacidade.

 

Fonte e Pia em grafos

Existem dois nós especiais: o nó chamado de “fonte” – que gera os fluxos – e o nó chamado de “pia” – que absorve os fluxos. Os outros nós representam os blocos do modelo. Além disso, os nós recebem um valor que é idêntico ao valor econômico do respectivo bloco. A fonte possui arcos que a ligam até os nós de valores positivos. Esses valores simbolizam o fluxo recebido pelo nó a partir da fonte e, como esse fluxo não sai deles, dizemos que esses nós possuem excesso e são nós fortes.

Analogamente, os nós negativos possuem arcos que os ligam à pia, os valores negativos simbolizam o fluxo que sai do nó, dizemos que esses nós possuem déficit e são fracos. Os nós fonte e pia podem ser representados como sendo apenas um nó, chamado raiz. Os nós com valores nulos podem ser adotados como fortes, ligados à fonte, ou fracos, ligados à pia.

Figura 1. Arcos entre cada bloco e a raiz. (Fonte: Bruno Nantes) - Artigo: Algoritmos de Cava Ótima: Pseudoflow
Figura 1. Arcos entre cada bloco e a raiz. (Fonte: Bruno Nantes)

Além desses arcos diretamente ligados à fonte e à pia, são criados arcos entre os nós comuns. Mas, neste caso, eles representam as regras de precedência da retirada dos blocos, ou seja, cada bloco possui arcos que saem de si em direção aos blocos situados na camada acima dele e que devem ser extraídos antes dele. Esses arcos possuem capacidade definida pelo excesso, déficit (valor em módulo) do nó de origem.

Figura 2. Arcos entre blocos, baseados nas regras de precedência para o Lerchs-Grossmann. (Fonte: HUSTRULID et al. 2006, p.464) - Algoritmo de Cava Ótima: Pseudoflow
Figura 2. Arcos entre blocos, baseados nas regras de precedência para o Lerchs-Grossmann. (Fonte: HUSTRULID et al. 2006, p. 464)

 

Fazendo a iteração do algoritmo

Após representar o modelo de blocos como um grafo direcionado o algoritmo pode ser iterado, a iteração consiste em procurar arcos que liguem nós fortes a nós fracos e fazer fluir o excesso através do arco de forma a tentar anular o déficit do nó fraco.

  • Caso o excesso do nó forte seja maior que o déficit do nó fraco, o nó fraco passa a ser considerado forte, contendo como excesso a diferença dos dois valores.
  • Caso o excesso seja menor que o déficit, o nó forte se torna fraco, com déficit igual a diferença dos dois valores.

No caso da capacidade do arco não ser tão grande quanto o excesso, apenas o fluxo capaz de passar flui, o restante fica no nó de origem e após essa operação o arco é removido. A iteração termina quando já não existe nenhum arco forte com um arco apontando para um nó fraco.

Descobrindo a Cava Ótima

A Cava Ótima é o conjunto dos nós fortes, e a receita esperada da extração dela é a soma dos excessos restantes, ou soma dos valores econômicos de todos os blocos contidos no conjunto.

 

 

Pseudoflow no Geokrige

Em breve, o Geokrige receberá uma adição em breve de um módulo para otimização de cava. O módulo está em desenvolvimento e utiliza o algoritmo Pseudoflow descrito nesse artigo. Além de contar com o Pseudoflow com otimizações que melhoram ainda mais seu desempenho, o programa contará com a funcionalidade de utilizar ângulos de taludes variáveis.

Mais detalhes serão revelados nos próximos artigos.

 

Referências

Hochbaum, D. S. 2008. The Pseudoflow Algorithm: a New Algorithm for the Maximum-Flow Problem, Operations Research, Vol. 56, No. 4, p. 992-1009.

HUSTRULID, William; KUCHTA, Mark; MARTIN, Randall K. Open Pit Mine: Planning and Design. 3ª edição, 2006. 1004p.

 

 

 

Módulo de cava ótima no Geokrige em breve - Geokrigagem
Fique atento para saber quando o módulo de cava ótima do Geokrige será disponibilizado.

Bruno Nantes

Escrito por Bruno Nantes

Bruno Roberto da Silva Nantes é graduando em Engenharia de Minas pela Escola Politécnica da USP e é Técnico em Programação de Sistemas pelo IFSP. É estagiário da Geokrigagem, atuando no desenvolvimento de softwares voltados para a Mineração.

Comentários

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Carregando...

0
GSLIB – Biblioteca de Software Geoestatístico e Guia do Usuário (Deutsch e Journel, 1992) Original: "GSLIB: Geostatistical Software Library and User's Guide".

Retrospectiva da Geoestatística XII: GSLIB (Deutsch e Journel, 1992)

Retrospectiva da Geoestatística; Geostatistics for Natural Resources Evaluation

Retrospectiva da Geoestatística XIII: Geoestatística Para Avaliação de Recursos Minerais (Goovaerts, 1997)