Pular para o conteúdo principal

Problemas de Fluxos em Redes

Introdução​

Problemas de Fluxos em Redes são um conjunto de problemas de otimização que lidam com o transporte ou a distribuição de recursos em uma rede. Esses problemas são fundamentais em diversas áreas, incluindo logística, engenharia de tráfego, distribuição de energia, e muitos outros. Vamos explorar a teoria, algoritmos e aplicações associadas a esses problemas.

Uma rede é composta por nós (ou vértices) e arestas (ou arcos) que conectam os nós. Em um problema de fluxo, nós representam locais, como cidades, e as arestas representam conexões, como estradas.

  • Nó Origem: De onde o fluxo começa.
  • Nó Destino: Onde o fluxo deve chegar.
  • Capacidade: O fluxo máximo que uma aresta pode suportar.

Problema de Fluxo Máximo/Corte Mínimo​

O objetivo é maximizar o fluxo da origem ao destino sem exceder as capacidades das arestas.

Max-Flow Problema Primal LP​

O problema Max-Flow é definido em um grafo dirigido onde e , respectivamente, denotam os conjuntos de vértices e arestas. O termo "dirigido" simplesmente significa que cada aresta é como uma rua de mão única - o fluxo é unidirecional. O objetivo do problema Max-Flow é maximizar o fluxo do nó de origem para o nó de destino sujeito a limites no fluxo permitido em cada aresta do grafo.

Para formular o problema, seja e . O conjunto representa os vértices vizinhos de através de arestas entrantes e o conjunto vizinho de através de arestas saindo. Para , seja uma variável representando o fluxo na aresta , e seja o limite superior em . Então, o problema max-flow pode ser formulado como:

Uma abordagem importante consiste em acrescentar uma aresta extra do vértice alvo (sumidouro) para o vértice origem .

Nesta formulação, o objetivo é maximizar a soma dos fluxos em todas as arestas que entram no vértice alvo. Para simplificar, supomos que para todos e que existe pelo menos um caminho de para de modo que a solução seja garantida como não-trivial (ou seja, ).

O equilíbrio de fluxo é imposto em todos os vértices, exceto no sumidouro , onde idealmente há um excedente líquido, e na fonte , onde há um déficit correspondente.

Intuitivamente, o fluxo total que entra em deve ser igual ao fluxo que sai de . De fato, essa condição é garantida pelas restrições de equilíbrio de fluxo.

Embora esta condição seja supérflua, ela serve de base para uma reformulação conveniente. Definindo uma nova variável , podemos reformular o problema considerando o grafo com um conjunto de arestas aumentado .

Isso permite que todo o fluxo que entra em recircule de volta para em um ciclo, tornando o equilíbrio de fluxo aplicável a todos os nós, incluindo e .

Max-Flow Problema Dual LP​

Para formar o dual deste problema, reescrevemos de forma compacta usando matrizes e vetores e distinguindo entre quantidades relativas ao grafo original e à aresta adicionada :

Aqui, denota a matriz de adjacência nó/aresta para o grafo original . As linhas de são indexadas em e as colunas em . A coluna de correspondente à aresta tem um na linha correspondente ao nó e um na linha correspondente ao nó . O vetor denota um vetor de incidência similar para a aresta .

Para formar o dual deste problema, reescrevemos de forma compacta usando matrizes e vetores e distinguindo entre quantidades relativas ao grafo original e à aresta adicionada :

Aqui, denota a matriz de adjacência nó/aresta para o grafo original . As linhas de são indexadas em e as colunas em . A coluna de correspondente à aresta tem um na linha correspondente ao nó e um na linha correspondente ao nó . O vetor denota u vetor de incidência similar para a aresta .

Método Simplex para Fluxo de Redes​

O método Simplex para fluxo de redes é uma adaptação do algoritmo primal Simplex com variáveis limitadas. Ele é especialmente eficiente para resolver problemas de otimização que podem ser modelados como fluxos de rede. Abaixo estão os principais componentes e etapas do método:

  1. Representação da Base como Árvore Geradora

    • A base é representada como uma árvore geradora enraizada da rede subjacente.

    • Nesta árvore, as variáveis são representadas pelos arcos e os multiplicadores simplex pelos potenciais dos nós.

  2. Iteração Simplex

    • Seleção da Variável Entrante: Uma variável entrante é selecionada por alguma estratégia de precificação, que é baseada nos multiplicadores duais (potenciais dos nós).

    • Formação de Ciclo: O arco entrante forma um ciclo com os arcos da árvore geradora enraizada.

      • Seleção da Variável Saindo: O arco que sai é o arco do ciclo com o menor fluxo de aumento.
í
  • Pivô: A substituição do arco entrante pelo arco saindo e a reconstrução da árvore é chamada de pivô.

  1. Condição de Parada

    • Quando nenhum arco não básico permanece elegível para entrar, a solução ótima foi alcançada.

  2. Atualização dos Potenciais dos Nós

    • Os potenciais dos nós são atualizados para refletir as mudanças na base.
óóç

Esta abordagem explora eficientemente a estrutura esparsa e a topologia da rede, tornando o método Simplex para fluxo de redes computacionalmente mais eficiente para esse tipo de problema em comparação com o Simplex tradicional.

Algoritmos Alternativos​

  • Algoritmo de Ford-Fulkerson: Utiliza caminhos aumentantes para encontrar o fluxo máximo.
  • Algoritmo de Edmonds-Karp: Variação do Ford-Fulkerson que garante a convergência.

Algoritmo de Ford-Fulkerson​

O Algoritmo de Ford-Fulkerson é uma técnica iterativa para resolver o problema de fluxo máximo em um gráfico. Ele funciona encontrando caminhos aumentantes, ou seja, caminhos que ainda têm capacidade disponível da origem ao destino, e aumentando o fluxo ao longo desses caminhos. O algoritmo pode ser resumido nos seguintes passos:

  1. Inicializar: Defina o fluxo em cada aresta como 0.
  2. Encontrar um Caminho Aumentante: Utilize qualquer método de busca (como a busca em profundidade) para encontrar um caminho da origem ao destino que ainda tenha capacidade disponível.
  3. Aumentar o Fluxo: Aumente o fluxo ao longo do caminho aumentante pela quantidade de capacidade mínima encontrada no caminho.
  4. Repetir: Continue encontrando caminhos aumentantes e aumentando o fluxo até que não haja mais caminhos aumentantes.
  5. Resultado: O fluxo atual é o fluxo máximo.

Algoritmo de Edmonds-Karp​

O Algoritmo de Edmonds-Karp é uma variação específica do Ford-Fulkerson que utiliza a busca em largura para encontrar o caminho aumentante de menor comprimento em cada iteração. Isso garante a convergência do algoritmo em um número finito de passos.

O uso da busca em largura implica que o Edmonds-Karp sempre escolhe o caminho aumentante com o menor número de arestas. Isso elimina o risco de selecionar caminhos que poderiam levar a uma execução infinita no caso de Ford-Fulkerson.

Comparação​

  • Ford-Fulkerson: É mais geral e pode ser implementado usando diferentes métodos de busca para encontrar caminhos aumentantes. No entanto, em casos específicos, pode não convergir.
  • Edmonds-Karp: É uma versão mais segura que garante a convergência usando a busca em largura para encontrar caminhos aumentantes. É mais lento por iteração, mas o número total de iterações é limitado.

Problema de Fluxo de Custo Mínimo​

O problema de fluxo de custo mínimo é uma extensão do problema de fluxo máximo, onde além das capacidades das arestas, também temos um custo associado a enviar fluxo através de cada aresta. O objetivo é encontrar o fluxo de custo mínimo que satisfaça a demanda e a oferta em cada nó.

Formulação de Programação Linear (PL)​

O problema pode ser formulado como um problema de Programação Linear da seguinte forma:

  • é o custo por unidade de fluxo na aresta .
  • é o fluxo da aresta .
  • é a demanda (ou oferta, se negativa) no nó .
  • é o conjunto de vértices e é o conjunto de arestas.

Algoritmos para Resolver o Problema​

Este problema pode ser resolvido usando algoritmos de fluxo de custo mínimo, como o Algoritmo de Dijkstra com potenciais ou o Algoritmo de Bellman-Ford para redes com custos negativos.

O problema de fluxo de custo mínimo é comumente aplicado em logística e cadeias de suprimentos para otimizar o transporte de mercadorias com o menor custo possível, respeitando as capacidades e demandas.

Método de Bellman-Ford: Pode ser usado para encontrar o fluxo de custo mínimo.

O algoritmo de Bellman-Ford é usado principalmente para encontrar as distâncias mais curtas de um vértice de origem para todos os outros vértices em um grafo ponderado. No contexto de fluxos em redes, pode ser usado para encontrar o fluxo de custo mínimo, ou seja, o fluxo que satisfaz as demandas com o menor custo total possível. A seguir, a descrição básica do método:

  • Inicializar: Defina a distância para o vértice inicial como 0 e para todos os outros vértices como infinito. Defina o fluxo nas arestas como 0.
  • Relaxamento: Para cada vértice, examine todas as suas arestas de saída. Para uma aresta ) com peso e fluxo, se a capacidade restante na aresta é positiva e a distância para u mais w for menor que a distância para v, atualize a distância para v e aumente o fluxo na aresta. Repetir: Repita o passo de relaxamento vezes, onde é o número de vértices no gráfico.
  • Verificação de Ciclos Negativos: Execute o passo de relaxamento mais uma vez para todos os vértices e verifique se ainda há atualizações. Se houver, isso indica a presença de um ciclo negativo.
  • Resultado: As distâncias finais representam os custos mínimos da origem a cada vértice. O fluxo associado nas arestas representa o fluxo de custo mínimo.

Problema de Transporte​

É um caso especial do problema de fluxo de custo mínimo em que se busca minimizar o custo de transportar produtos entre várias origens e destinos.

Método de Vogel: Algoritmo utilizado para resolver problemas de transporte.

Passos do Método de Vogel

  • Cálculo das Penalidades: Para cada linha e coluna da tabela de custos, calcule a diferença entre os dois menores custos. Essa diferença é chamada de "penalidade" e indica o aumento no custo total se a alocação óbvia (isto é, a de menor custo) não for escolhida.
  • Seleção da Maior Penalidade: Identifique a linha ou coluna com a maior penalidade. Se houver um empate, selecione qualquer uma das opções empatadas.
  • Alocação: Na linha ou coluna selecionada, faça a alocação na célula com o menor custo. A alocação deve ser tanto quanto possível, respeitando as restrições de oferta e demanda.
  • Atualização da Oferta e Demanda: Subtraia a quantidade alocada das ofertas e demandas relevantes.
  • Eliminação de Linhas e Colunas: Se uma oferta ou demanda for totalmente atendida, elimine a linha ou coluna correspondente da tabela.
  • Repetição: Repita os passos 1 a 5 até que todas as ofertas e demandas sejam atendidas.
  • Solução: A solução final é a alocação que minimiza o custo total de transporte.

Exemplo​

Consideremos o seguinte exemplo simples:

Origens: Duas fábricas com ofertas de 20 e 30 unidades.

Destinos: Três lojas com demandas de 10, 20 e 20 unidades.

Custos de Transporte: Definidos em uma matriz, como [5,8,7],[6,7,6].

Vamos resolver o exemplo mencionado usando o Método de Vogel (VAM). Temos duas origens com ofertas de 20 e 30 unidades, respectivamente, e três destinos com demandas de 10, 20 e 20 unidades, respectivamente. A matriz de custos de transporte é dada por:

Loja 1Loja 2Loja 3
Fáb. 1587
Fáb. 2676

Aqui estão os passos para resolver o problema usando o VAM:

Passo 1: Cálculo das Penalidades

Calcule a diferença entre os dois menores custos para cada linha e coluna:

  • Fábrica 1: 8 - 5 = 3
  • Fábrica 2: 7 - 6 = 1
  • Loja 1: 6 - 5 = 1
  • Loja 2: 8 - 7 = 1
  • Loja 3: 7 - 6 = 1

Passo 2: Seleção da Maior Penalidade

A maior penalidade é 3 na Fábrica 1.

Passo 3: Alocação

Aloque o máximo possível na célula com o menor custo na Fábrica 1, ou seja, 20 unidades para a Loja 1. Atualize as ofertas e demandas:

Loja 1Loja 2Loja 3
Fáb. 10/2087
Fáb. 2676

Passo 4: Repetição

Repita os passos 1 a 3:

  1. Cálculo das Penalidades: 2 (Fáb. 2), 1 (Loja 3)
  2. Maior Penalidade: Fáb. 2
  3. Alocação: 20 unidades para a Loja 3 (menor custo).

Atualização:

Loja 1Loja 2Loja 3
Fáb. 10/2087
Fáb. 26710/20

Continue repetindo os passos até que todas as ofertas e demandas sejam atendidas. Finalmente, você terá:

Loja 1Loja 2Loja 3
Fáb. 10/2020/200
Fáb. 20030/30

Conclusão

A solução ótima é:

  • Transportar 20 unidades da Fábrica 1 para a Loja 1.
  • Transportar 20 unidades da Fábrica 1 para a Loja 2.
  • Transportar 30 unidades da Fábrica 2 para a Loja 3.

O custo total será: .

Sim, problemas de transporte são um subconjunto específico de problemas de fluxo em redes. Eles podem ser formulados e resolvidos como problemas de otimização em redes, onde o objetivo é minimizar o custo total de transporte de mercadorias de vários fornecedores a vários consumidores, respeitando as capacidades de fornecimento e demanda.

Formulação de Programação Linear para o Problema de Transporte​

O problema de transporte pode ser formulado como um problema de Programação Linear (PL) da seguinte forma:

  • é o custo de transporte da unidade de mercadoria do fornecedor ao consumidor .
  • é a quantidade de mercadoria a ser transportada do fornecedor ao consumidor .
  • é a oferta do fornecedor .
  • é a demanda do consumidor .
  • é o número de fornecedores e é o número de consumidores.

O objetivo é minimizar o custo total de transporte, sujeito às restrições de oferta e demanda.

Algoritmos para Resolver o Problema​

Embora o problema de transporte possa ser resolvido como um problema de PL genérico, existem algoritmos especializados, como o Método de Transporte e o Método de Vogel, que são mais eficientes para resolver esse tipo específico de problema de otimização em redes.

Outros​

  • Extensões e Variações

Fluxos Multicommodity: Onde vários produtos são transportados.

Redes Dinâmicas: Onde as capacidades e custos podem mudar com o tempo.

  • Aplicações Práticas

Logística: Otimização de rotas de entrega.

Engenharia de Tráfego: Gerenciamento de fluxo de tráfego.

Telecomunicações: Otimização do fluxo de dados em uma rede.

  • Desafios

Complexidade: Os problemas podem se tornar complexos com o aumento do tamanho da rede.

Dados Incertos: A incerteza nas capacidades e demandas pode levar a soluções subótimas.

Conclusão​

Problemas de Fluxos em Redes são uma área rica e diversificada, com relevância em vários campos da ciência e engenharia. A compreensão dos diferentes problemas, seus algoritmos de resolução, e suas aplicações, é vital para qualquer profissional que trabalhe com otimização, logística, e áreas relacionadas. As técnicas desenvolvidas para esses problemas têm o potencial de fornecer soluções poderosas e eficientes para os desafios contemporâneos em transporte e distribuição, tornando essa área de estudo não apenas teoricamente interessante, mas também altamente prática e aplicável.