Bruno Nantes
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.
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.
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.
Portuguese