Modelos de Rede
Modelos de rede (em pesquisa operacional; em inglês: Network models) são uma classe de modelos matemáticos que representam um problema na forma de um grafo (rede), onde os vértices (nós) denotam objetos ou estados, e as arestas (arcos) representam as conexões ou processos entre eles[1]. No contexto da otimização, uma rede é frequentemente entendida como um grafo orientado, que na análise de operações é diretamente chamado de "rede"; os vértices dessa rede são chamados de nós, e as arestas são chamadas de arcos[2].
Os modelos de rede são uma ferramenta poderosa para a análise e otimização de sistemas complexos em áreas como logística, telecomunicações, gerenciamento de projetos e finanças. Sua força reside no alto nível de abstração: um nó pode representar uma cidade, um roteador de computador ou uma etapa de um projeto, enquanto um arco pode representar uma estrada, um canal de comunicação ou uma operação tecnológica.
Definição e Terminologia
A base para os modelos de rede é a teoria dos grafos. Os conceitos-chave são:
- Rede de fluxo (em inglês: flow network): um grafo orientado no qual cada aresta possui uma capacidade (capacity) e um fluxo (flow). No grafo, dois vértices especiais são destacados: a fonte (source), de onde o fluxo se origina, e o sorvedouro (sink), para onde ele flui[1].
- Lei da conservação do fluxo: Para qualquer vértice que não seja a fonte ou o sorvedouro, o fluxo total de entrada deve ser igual ao fluxo total de saída. Esta condição é um análogo discreto das leis físicas de conservação[3].
- Planejamento de rede: Um modelo que representa um projeto como um conjunto de operações (arcos) e eventos (nós) interligados. Tais redes são grafos acíclicos orientados, o que reflete a ordem de execução dos trabalhos[4].
Propriedades e Teoremas Fundamentais
Os modelos de rede possuem várias propriedades especiais que permitem a aplicação de algoritmos altamente eficientes para sua resolução.
- Integralidade das soluções: Muitos problemas de otimização de rede (por exemplo, fluxo máximo ou caminho mais curto) possuem a propriedade de unimodularidade total da matriz de restrições. Graças a isso, se os parâmetros do problema (capacidades, comprimentos) forem inteiros, a solução ótima encontrada por métodos de programação linear também será inteira, sem a necessidade de introduzir restrições adicionais[5][6].
- Teorema do fluxo máximo e corte mínimo: O resultado central da teoria dos fluxos. Afirma que o valor máximo do fluxo da fonte para o sorvedouro é igual à capacidade mínima entre todos os cortes que separam a fonte e o sorvedouro. Este teorema estabelece um critério de otimalidade para o fluxo e é a base de muitos algoritmos[6][7].
- Princípio da otimalidade para caminhos mais curtos: Se um caminho do ponto A ao ponto C é o mais curto, então qualquer um de seus segmentos (por exemplo, do ponto intermediário B ao C) também é o caminho mais curto entre os vértices correspondentes. Essa propriedade, que está na base da programação dinâmica, garante a correção de algoritmos como o de Dijkstra[8].
- Propriedades da árvore geradora mínima (AGM):
- Propriedade do corte: Para qualquer corte do grafo, a aresta com o peso mínimo que cruza o corte pertence a pelo menos uma AGM.
- Propriedade do ciclo: Em qualquer ciclo do grafo, a aresta com o peso máximo não pertence a nenhuma AGM.
A correção dos algoritmos "gulosos" de Prim e Kruskal baseia-se nessas propriedades[9].
Principais Problemas de Otimização em Rede
- Problema do caminho mais curto: Encontrar um caminho de comprimento (peso) total mínimo entre dois nós especificados. Resolvido pelo algoritmo de Dijkstra (para pesos não negativos) ou pelo algoritmo de Bellman-Ford (para pesos arbitrários)[8].
- Problema do fluxo máximo: Determinar o maior fluxo possível da fonte ao sorvedouro, dadas as capacidades dos arcos. O método clássico de resolução é o algoritmo de Ford-Fulkerson[6].
- Problema da árvore geradora mínima: Encontrar um subgrafo que conecte todos os vértices da rede e tenha o custo total mínimo das arestas.
- Método do caminho crítico (CPM): Em modelos de planejamento de rede, determinar a sequência mais longa de tarefas que estabelece o tempo mínimo possível para a conclusão de todo o projeto. As tarefas neste caminho têm folga de tempo zero[10].
Exemplos
- Caminho mais curto: A busca pela rota ótima por um sistema de navegação entre dois pontos em um mapa da cidade, onde as cidades são nós e as estradas são arcos com pesos iguais à distância ou ao tempo de viagem.
- Fluxo máximo: A determinação da capacidade máxima de uma rede de dutos, onde as estações de bombeamento são os nós e os dutos são os arcos com capacidade limitada.
- Árvore geradora mínima: O projeto de uma rede de comunicação (por exemplo, a instalação de cabos de fibra óptica) para conectar várias cidades com o menor comprimento total de cabo.
- Caminho crítico: Em um projeto de construção de uma casa, onde as tarefas (fundações, construção de paredes, instalação do telhado) têm durações e dependências tecnológicas definidas, o caminho crítico determina o prazo mínimo para a conclusão da construção. Qualquer atraso em uma tarefa neste caminho resultará no atraso de todo o projeto[10].
Ver também
- Pesquisa operacional
- Teoria dos grafos
- Problema de transporte
- Método do caminho crítico
- PERT
Notas
- ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
- ↑ "Tópico 10: Modelos de Rede". Manual de estudo. Gomel: BelGUT. [2]
- ↑ "Rede de transporte". Wikipédia. [3]
- ↑ "Planejamento de rede". Wikipédia. [4]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
- ↑ 6.0 6.1 6.2 "Problema do fluxo máximo". Wikipédia. [6]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
- ↑ 8.0 8.1 "Problema do caminho mais curto". Wikipédia. [8]
- ↑ "Árvore geradora mínima". Wikipédia.
- ↑ 10.0 10.1 "Método do caminho crítico". Wikipédia. [9]