Algoritmo de Ford-Fulkerson

Prévia do material em texto

Mestrado de Engenharia e Gestão Industrial 
Trabalho de Métodos de Apoio à Decisão 
 
 
 
 
 
Fluxo em Redes: Ford-Fulkerson - Fluxo Máximo 
 
15/01/2019 
 
 
 
 
Docente: Maria do Céu Marques 
Discentes: Milani Matias 
 Stéphane Vicente 
 
1 
 
Resumo 
 
Este trabalho propõe e implementa a análise teórica e uma solução para a avaliação 
dos resultados obtidos com a execução do algoritmo de Ford e Fulkerson sobre uma rede de 
fluxo. Com esta solução é possível determinar a melhor alternativa de investimento para seguir 
com a exploração da rede, otimizando o aproveitamento dos recursos. O trabalho também 
levanta uma discussão sobre uma abordagem de avaliação completa da rede residual. 
 
2 
 
Índice 
0 
Resumo ................................................................................................................................................... 1 
Introdução ............................................................................................................................................... 3 
Definições................................................................................................................................................ 5 
Apresentação do Algoritimo de Ford-Fulkerlson .................................................................................... 7 
Inferências sobre a rede saturada ........................................................................................................ 11 
Aplicação ............................................................................................................................................... 13 
Análise de complexidade de tempo Ford Fulkerson ............................................................................. 14 
Caso prático .......................................................................................................................................... 14 
Conclusão .............................................................................................................................................. 24 
References ............................................................................................................................................ 25 
 
 
Lista de figuras 
Figura1: Rede original (G)……………………………………………….……………………………………………………..………...7 
Figura2:Rede residual (Gf)…………………………………………………….……………………………………………..…….…….7 
Figura 3: Rede de fluxo…………………………………………………………… …………………………………………………...…..8 
Figura4: 1º caminho de aumento ……………………………………………………………………………………….……………9 
Figura5: 2º caminho de aumento……………………………………………………………………………………………………..9 
Figura6: 3º caminho…………………………………………………………………………………………………………………..……10 
Figura7:4º caminho…………………………………………………………………………………………………………………………10 
Figura8: Fluxo máximo e corte mínimo da rede de fluxo………………………………………………………..……….11 
Figura9: - (a) aumento na rede de fluxo. (b) Rede de fluxo com a retirada de C……….…………………….12 
Figur10: - Capacidades residuais da rede ………………………………………………………………………….…………….12 
Figura11: - (a) Aumento pelo do incremento no arco D→T. (b) Aumento pelo do incremento no 
arco…………………………………………………………………………………………………………………………………………………13 
Figura12: Localização dos poços (Romero, 2017)…………………………………………………………………………….15 
Figura13: Distâncias e direções dos pipeline………………………………………………………………………………..….15 
3 
 
Introdução 
 
Embora acreditados em Dantzig no início dos anos 50, os antecessores do problema de 
fluxo máximo podem ser mostrados em materiais escritos desde 1930. A questão do 
transporte, que mais tarde evoluiu para o problema do fluxo máximo, à medida que as rotas 
de transporte se tornaram mais complexas, foi amplamente estudada na União Soviética pelo 
Comissariado Nacional de Transporte. O Comissariado, A.N. Tolstoi, examinou a solução ideal 
para o transporte de carga em toda a União Soviética através do sistema ferroviário com 
múltiplas fontes de produto e muitos destinos individuais. 
O problema do fluxo máximo tem uma longa história. O problema foi formulado por 
GB Dantzig "Aplicação do método simplex a um problema de transporte" em 1951. Ford e 
Fulkerson criaram o primeiro algoritmo conhecido em 1955. Desde 1955, os métodos 
evoluíram muito nos métodos que são usados para criar soluções e algoritmos de projeto para 
resolver problemas complexos. Essas novas técnicas de projeto levaram a uma diminuição no 
tempo de execução para algoritmos de fluxo máximo. A determinação dos parâmetros da 
situação propriamente dita também permite mudanças no tempo de execução, mas primeiro 
a visão geral do problema do fluxo máximo deve ser definida. 
No problema de fluxo máximo, recebemos um gráfico direcionado ou não direcionado, 
mais comumente direcionado em aplicações do mundo real, em que um vértice é considerado 
uma fonte e outro é o destino ou comumente referido como o coletor. Alguns objetos, em 
seguida, fluem ao longo das bordas do gráfico da fonte para o coletor. Cada borda ao longo do 
caminho recebe uma capacidade máxima que pode ser transportada ao longo dessa rota. A 
capacidade máxima pode variar de borda a borda e, nesse caso, o restante deve fluir ao longo 
de outra borda em direção ao coletor ou permanecer no vértice atual para que a borda seja 
limpa ou reduzida para que mais flua através dela. O objetivo deste problema é que a fonte 
não produza mais do que o necessário e possa atingir um fluxo máximo ao longo de todo o 
gráfico para obter resultados e “throughput” ideais. 
 A encarnação mais básica desse problema seria uma produtora que produz um 
produto em uma fábrica e o envia para locais em todo o país. A fábrica tem uma capacidade 
máxima de produção X por dia. Todos os dias, um caminhão sai da fábrica com a quantidade Y 
de produto. 
4 
 
Suponha que a fábrica (fonte) esteja no Centro-Oeste e a loja de varejo (coletor) esteja 
em algum lugar ao longo da costa leste. No cenário mais básico, existem duas paradas para os 
caminhões ao longo do caminho entre os dois locais. Neste caso, nos é dado um grafo básico 
direcionado com uma pia, fonte e dois vértices médios. 
Por uma questão de simplicidade, vamos chamar as paragens ao longo do caminho A e 
B. 
𝐹𝑎𝑏𝑟𝑖𝑐𝑎(𝑓𝑜𝑛𝑡𝑒) → 𝐴 → 𝐵 → 𝑆𝑡𝑜𝑟𝑒(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙) 
O camião que transporta o produto entre a fábrica e A pode transportar a quantidade 
máxima que pode ser produzida todos os dias da fábrica. Quando o caminhão chega a A, ele 
descarrega e retorna à fonte e outro caminhão o levará para o próximo ponto de parada. Se o 
caminhão, transportando o produto de A para B, tiver apenas 9/10 da capacidade que o 
primeiro caminhão tem, então, algum produto deve ser deixado na primeira parada e enviado 
a próxima passagem de fluxo. O restante sobre isso não é transportado é comumente referido 
no problema de fluxo máximo como o residual e a quantidade que pode ser enviada de A para 
B no próximo passe é Capacidade (caminhão1) - residual (A), que é conhecida como capacidade 
residual. Não é bom criar a quantidade máxima possível de produto na origem todos os dias, 
se nem todos puderem ser enviados de cada ponto, caso contrário, haveria um acúmulo de 
produto no vértice A conhecido como um bloco de rede, onde o fluxo é interrompido devido 
ao acúmulo. O algoritmo de fluxo máximo pode ser aplicado, neste caso, para determinar a 
quantidade ideal de produto que deve ser produzido na fábrica todos os dias, a fim de atingir 
o fluxo máximo dentro da rede e tornar o processo rentável. 
O problema do caminho único ao longo de um gráfico direcionado é um dos exemplos 
mais básicos do problema de fluxo máximo e é relativamente rápido de resolver com os 
algoritmos que foram projetados ao longodos anos. No entanto, outros fatores podem ser 
incorporados ao problema, o que o complica e torna o tempo de execução consideravelmente 
mais lento. À medida que mais vértices e arestas são adicionados ao gráfico, a velocidade com 
que esses algoritmos levam para criar uma solução de fluxo máximo cresce consideravelmente. 
Variáveis como comprimento (distância entre vértices / custo-benefício), número de vértices, 
número de arestas e capacidade de borda desempenham papéis vitais para encontrar um fluxo 
máximo (Hudson, 2004). 
5 
 
Definições 
 
Grafo direcionado G = (V, E): consiste em um conjunto V de vértices e um conjunto E de arestas. 
Assumimos, sem perda de generalidade, que V = {0, 1, ..., n - 1}, onde n é o número de vértices. 
As arestas são representadas como um par ordenado de seus vértices e é, E ⊆ V × V. 
 Rede capacitada: é um grafo direcionado cujas arestas possuem um valor numérico associado 
a ela. No caso do problema de fluxo máximo, esse valor representa a capacidade da borda. A 
capacidade de uma aresta é um mapeamento c: E → R + e representa a quantidade máxima 
de fluxo que pode passar pela aresta. A capacidade da borda (i, j) é denotada cij. 
Fonte :é um vértice arbitrário que possui pelo menos uma borda de saída. 
s ∈ V tal que ∃ (s, k) ∈ E com k ∈ V 
Terminal: é um vértice arbitrário que possui pelo menos uma borda de entrada. 
t ∈ V tal que ∃ (k, t) ∈ E com k ∈ V 
Fluxo:é um mapeamento f: E → R +. O fluxo entre i e j é denotado por fij e está sujeito a duas 
restrições: 
Limite de capacidade fij ≤ cij, para cada (i, j) ∈ E; 
Restrição de conservação de fluxo P(i, j) ∈E fij = P (j, i) ∈Efji, para cada j ∈ V \ {s, t}. 
Rede Residual: Para resolver o problema de fluxo máximo, é conveniente usar outra 
representação da rede capacitada. Para conseguir encontrar o fluxo máximo, vários algoritmos 
atualizam o fluxo atual em um processo incremental. Então, será útil ter uma representação 
do gráfico que forneça a quantidade de fluxo restante que pode ser adicionado ao fluxo atual 
através de uma aresta. Essa representação é chamada de rede residual. 
Dado um fluxo f em um grafo G, a capacidade residual cf (i, j) é definida como cf (i, j) = cij - fij. 
– cf (u, v) = c(u,v) ‐‐‐‐ f (u, v) 
Dado um fluxo f no gráfico G, a rede residual Gf é a rede direcionada (definida no mesmo 
conjunto de vértices) com todas as bordas da capacidade residual positiva, cada uma rotulada 
6 
 
por sua capacidade residual, ou seja uma Aresta Residual é uma aresta ou arco que pode 
admitir ainda algum fluxo maior que seja maior que zero. 
Fluxo em rede: é o envio de entidades de um nó (origem) até outro nó (destino), percorrendo 
alguns dos arcos da rede onde aqueles eles fazem parte. 
Um fluxo em rede G=(V,E) é um grafo orientado em que cada aresta (u,v)∈ E e tem uma 
capacidade não negativa c(u,v) ≥ 0. Onde u equivale a origem e v o destino. Em uma rede 
G=(V,E), cada vértice reside em algum caminho de u até v. 
Um fluxo em rede G=(V,E) é um grafo orientado em que cada aresta (u,v)∈ E e tem uma 
capacidade não negativa c(u,v) ≥ 0. Onde u equivale a origem e v o destino. Em uma rede 
G=(V,E), cada vértice reside em algum caminho de u até v. 
O Fluxo em redes deve respeitar as três propriedades seguintes: 
Restrição de capacidade: o fluxo que circulará em um grafo deve ser igual ou menor que a 
capacidade máxima deste fluxo. 
F(u,v) ≤c(u,v) 
Anti-simetria oblíqua: o fluxo em uma direção deve ser igual ao seu fluxo na direção oposta. 
Essa propriedade é válida para grafos não orientados 
f(u,v)=-f(u,v) 
Conservação de fluxo: O fluxo que entra deve ser igual ao que sai, exceto na origem e no 
sorvedouro 
 Caminhos de aumento: Dado um fluxo em rede G = (V;E) e um fluxo f, um caminho em 
ampliação (ou caminhos de aumento) é um caminho simples de s a t na rede residual Gf. A 
quantidade máxima pela qual o fluxo pode ser aumentado em um caminho de ampliação é 
chamada de capacidade residual de p, e é expressa por: 
cf (p) = minfcf (u; v) : (u; v) 
Ou seja, a capacidade residual de um caminho em ampliação p corresponde à menor dentre 
as capacidades das arestas que fazem parte de p. 
7 
 
Apresentação do Algoritimo de Ford-Fulkerlson 
 
O método de Ford Fulkerson depende de três ideais importantes: rede residual, caminho 
de aumento e cortes. 
• Rede residual 
 Figura1: Rede original (G) 
 
 Figura2:Rede residual (Gf) 
 
Os passos de cada interação do algoritmo podem ser resumidos do seguinte modo: 
• Escolhe-se um caminho qualquer desde a origem até ao sorvedor cujas arestas 
capacidade positiva (>0); 
• Procurar nesse caminho o arco orientado com menor capacidade c; 
• Diminuir de c a capacidade de fluxo em cada aresta do caminho no sentido direto e 
aumentar de c a capacidade das arestas no sentido inverso; 
• Regressar ao 1º passo. Se já não existir nenhum caminho em que todas as arestas 
tenham capacidade positiva, então o fluxo máximo já está determinado. 
 
8 
 
Pseudo Código: 
Ford-Fulkerson (G, s, t) 
• para cada aresta (u,v)← E[G] 
• faça f[u,v] ← 0 
f[v,u] ← 0 
• enquanto existir um caminho p de s até t na rede residual Gf 
• faça cf ← min{cf(u,v):(u,v) está em p 
• para cada aresta em (u,v) em p 
 
• faça f[u,v]← f[u,v]+ cf(p) 
• f[v,u] ← -f[u,v] 
 
Exemplo: 
Aumento de fluxo (FREITAS, 2014) 
Figura 3: Rede de fluxo 
Após a descoberta do primeiro caminho de aumento, a rede apresentará a configuração 
ilustrada na Figura 16. O fluxo passará a ser de uma unidade através de S→C→D→T. Este 
caminho é composto exclusivamente por arcos que escoam o fluxo no sentido da fonte para o 
sorvedouro, considerando os subgrupos de vértices (cortes) que são identificados ao longo do 
caminho. 
9 
 
Figura4: 
1º caminho de aumento 
 Analisando a metodologia do algoritmo, descobrimos o segundo caminho de aumento, 
apresentado pela figura abaixo. O incremento de 2 unidades se dá através do caminho 
S→C→E→T, atualizando o fluxo máximo da rede para 3 unidades. 
Figura5: 2º caminho de aumento 
Igualmente como o primeiro caminho de aumento, o segundo caminho S→C→E→T é 
composto exclusivamente por arcos de avanço que escoam o fluxo sempre no sentido de S 
para T. 
O terceiro aumento de fluxo pode se dar através do caminho S→A→B→C→E→T, que 
apresenta a mesma característica referente aos arcos de avanço dos caminhos anteriores. 
O aumento de fluxo de 1 unidade atualiza o fluxo total para 4. A representação da rede 
após a descoberta deste terceiro caminho é ilustrada abaixo. 
10 
 
Figura6: 3º caminho 
Neste ponto, uma observação não aprofundada da rede poderia levar à dedução de 
que não há como seguir aumentando seu fluxo. O caminho C→E→T é o único que ainda possui 
capacidade residual para escoar fluxo até o sorvedouro T, mas os dois arcos que transportam 
fluxo até o vértice C, a saber, S→C e B→C, já estão sobrecarregados. 
Ocorre que um quarto caminho de aumento ainda é possível através de 
S→A→B→D←C→E→T, como ilustrado a seguir. 
Figura7:4º caminho 
Este caminho se dá por meio do re-manejamento do fluxo de 1 unidade no arco de 
retorno D ← C para o arco C→E. O fluxo de 1 unidade escoando através de D→T é mantido 
pela distribuição das 2 unidades do fluxo que chega em B entre C e D. 
Percebe-se que o aumento de fluxo no caminho p descoberto não é mais determinado 
somente pela capacidade residual dos arcos de avanço, mas também pelo fluxo corrente no 
11 
 
arco de retorno. Observando novamente a Figura 6, percebe-se que embora todos os arcos de 
avanço no quarto caminho de aumento possam escoar até 2 unidades de fluxo, o arco de 
retorno D ← C só permite o re-manejamentode 1 unidade, tendo esta sido atribuída durante 
a descoberta do primeiro caminho de aumento. Esta mudança no fluxo do quarto caminho de 
aumento expressa no algoritmo por cf(p) deve ser incrementada nos arcos de avanço e 
deduzida nos arcos de retrocesso. 
O fluxo máximo de 5 unidades é então obtido e o corte mínimo da rede 
({S,A,B,D},{C,E,T}) descoberto, como exposto pela Figura abaixo. 
Figura8: 
Fluxo máximo e corte mínimo da rede de fluxo 
Os arcos S→C, B→C, D ← C e D→T são responsáveis pela comunicação do corte mínimo 
e, consequentemente, por escoar o fluxo máximo entre a fonte e o sorvedouro. Assim como 
no exemplo do capítulo 2, qualquer tentativa de aumentar o fluxo maximizado da rede deve, 
necessariamente, levar em consideração o aumento da capacidade de fluxo nesta região. 
Inferências sobre a rede saturada 
 
Uma vez saturada, é comum a rede de fluxo apresentar uma configuração residual 
subutilizada que pode servir para expandir seu fluxo máximo ainda mais. Naturalmente, isso 
só é possível com a expansão das capacidades de fluxo nos arcos do corte mínimo. 
Usando o exemplo de fluxo máximo dado: 
12 
 
Figura9: - (a) aumento na rede de fluxo . (b) Rede de fluxo com a retirada de C. 
Como exemplo a rede de fluxo do exemplo da figura 9, constata-se após sua saturação 
a existência de capacidades residuais em 60% de suas arestas, de acordo com a Figura 10. 
Figur10: Capacidades residuais da 
rede 
Considerando a possibilidade de expansão de capacidades nos arcos da rede, é 
importante verificar que embora os arcos com capacidade esgotada estejam espalhados, de 
nada adiantaria aumentá-los aleatoriamente sem levar em consideração que a origem do 
problema está localizada no corte mínimo. Sendo assim, se tomamos como objetivo o aumento 
do fluxo no do grafo ainda mais, deveremos escolher um entre os arcos D→T e E→T para 
aplicar o incremento. Considerando um possível incremento de apenas 1 unidade, não se 
observa nenhuma diferença entre escolher D→T e E→T, visto que o impacto de ambas 
escolhas no fluxo máximo da rede será igualmente de 1 unidade. Entretanto, para valores 
superiores a 1 unidade, verifica-se a existência de uma diferença no aumento global do fluxo. 
Para exemplificar, tomando-se o possível incremento como sendo de 2 unidades, é 
possível observar a diferença que se dá através do caminho escolhido. Na Figura 11 (a), o 
13 
 
caminho S→B→D→T só permite o aumento de 1 unidade, já através de S→C→F→E→T (Figura 
11 (b)), o aumento no fluxo máximo apresenta-se como sendo de 2 unidades. 
Figura11: - (a) Aumento pelo do incremento no arco D→T. (b) Aumento pelo do incremento 
no arco E→T 
Pode-se dizer que E→T é um arco mais promissor que D→T. Esta diferença no aumento 
de fluxo provém do desequilíbrio nas capacidades residuais dos arcos associados a estes 
terminais na rede saturada após a execução do algoritmo. Como explicado no capítulo 2, os 
recursos de transporte associados ao vértice C e às arestas S→C e C→F estavam subutilizados, 
de forma que poderiam ser removidos sem nenhum prejuízo para o fluxo máximo obtido. 
Entretanto, quando consideramos o incremento adicional no arco E→T, estes recursos outrora 
inutilizados ganham importância, permitindo o escoamento de mais fluxo através da rede 
(FREITAS, 2014). 
Aplicação 
 
O problema do fluxo máximo serve para enumeras situações, como por exemplo: 
• O envio de produtos do produtor ao distribuidor; 
• A deslocação das pessoas das suas casas para os locais de trabalho; 
• A expedição de cartas desde a estação de correio até os seus destinatários; 
• Modelagem de líquidos fluindo por tubos; 
• Peças por linha de montagem; 
• Informações por redes de comunicações; 
• Correntes por redes elétricas, etc 
14 
 
Análise de complexidade de tempo Ford Fulkerson 
 
Adicionando o caminho de aumento de fluxo ao fluxo já estabelecido no grafo, o fluxo 
máximo será alcançado quando não houver mais caminhos de aumento de fluxo no gráfico. 
No entanto, não há certeza de que essa situação será atingida, portanto, o melhor que pode 
ser garantido é que a resposta estará correta se o algoritmo for encerrado (JOSEFSSON & 
MÜTZELL, 2015). 
No caso em que o algoritmo é executado para sempre, o fluxo pode até não convergir 
para o fluxo máximo. No entanto, essa situação ocorre apenas com valores de fluxo irracionais. 
Quando as capacidades são inteiras, o tempo de execução de Ford-Fulkerson é limitado por O 
(Ef), onde E é o número de arestas no gráfico e f é o fluxo máximo no gráfico. Isso ocorre 
porque cada caminho de aumento pode ser encontrado no tempo O (E) e aumenta o fluxo por 
uma quantidade inteira, que é pelo menos. 
Podemos dizer o seguinte sobre a Análise de Tempo de Execução da Ford-Fulkerson: 
• Depende da ordem de escolha dos caminhos aumentados P 
• Cada iteração leva m tempo, onde m é o número de arestas no algoritmo de 
rede 
• A rede de fluxo aumenta pelo menos uma unidade a cada iteração 
• Para o fluxo máximo f *, o valor máximo | f * | denota um limite no número de 
iteração 
• O tempo total de execução é O (| f * | m). 
 
Caso prático 
 
Problemas atuais: 
A Junta de Água Potável e Alcantarillado de Yucatan, (JUPAY), no estado de Mérida, possui uma 
rede de tubulações que utiliza para transportar a água de seu poço 0 (P0) até seu poço final 
(PF), conforme Figura 12. A Figura 13 mostra a capacidade máxima diária que pode ser enviada, 
em milhares de litros e os arcos entre os nós (Romero, 2017). 
15 
 
Figura12: Localização dos poços (Romero, 2017). 
O cliente está solicitando à CIATEQ (Centro de tecnologia Avançada) que determine o tempo 
necessário para transportar 24.000 litros do Poço 0 (P0) para o Poço Final (PF) se a quantidade 
máxima possível for enviada a cada dia. 
Figura13: 
Distâncias e direções dos pipeline 
 
Solução: 
16 
 
 
17 
 
 
18 
 
 
19 
 
 
20 
 
 
 
21 
 
 
22 
 
 
23 
 
 
24 
 
Depois de chegarmos ao ponto que não existe mais nodos para fazer a ligação, acha-se 
o fluxo máximo somando os mínimos na qual obteve-se 12, substituindo os valores, seu valor 
máximo é de 12.000 litros por dia. Para sabermos quantos dias são necessários para enviar 24 
mil litros tem que se calcular: 
𝑛 =
24 × 103
12 × 103
= 2 
Serão necessários 2 dias para fazer o envio de 24 mil litros do poço P0 ate poço Pf. 
 
Sumário 
Rede de fluxo máximo é baseado na etapa de senso comum: encontre um caminho que 
inicie na origem e conclua em um ponto final estabelecido e deve procurar rotas que vão da 
origem para cada ponto que sejam maiores que zero para todos ramos respeitando a direção 
do fluxo. Nós encontraremos a solução uma vez que os pontos onde podemos traçar possíveis 
rotas se tornem zero, para finalmente adicionar os valores obtidos em cada iteração. Agora 
temos que explorar as condições físicas do terreno e ver a viabilidade da solução proposta. 
 
Conclusão 
 
Este trabalho foi desenvolvido objetivando expandir o algoritmo de aumento de fluxo 
de Ford e Fulkerson, que este método se propõe a procurar maneiras pelas quais o fluxo possa 
ser aumentado até que o fluxo máximo seja atingido, utilizando seus resultados e provendo 
decisões de otimização para a exploração dos recursos não aproveitados representados pelas 
capacidades residuais dos arcos não saturados na rede de fluxo. Sua metodologia propõe duas 
abordagens para avaliação destes arcos no corte mínimo, apresentando a implementação e 
validação de uma delas como resultado. Podemos resolver problemas como: fluxo de veículos, 
fluxo de água ou qualquer substância, redes de comunicação,etc. 
Com base no acima exposto, decisões podem ser tomadas sobre a distribuição de uma 
determinada rede, minimizando o custo no projeto ou retrabalhando durante sua 
implementação. 
25 
 
 References 
 
FREITAS, V. H. (2014). ANÁLISE COMPUTACIONAL DE OTIMIZAÇÃO EM REDES DE FLUXO SATURADAS 
PELA METODOLOGIA DO. MOSSORÓ. 
Hudson, I. (2004). The Maximum Flow Problem. 
 JOSEFSSON, M., & MÜTZELL, M. (2015). Max Flow Algorithms. STOCKHOLM, SWEDEN: KTH ROYAL 
INSTITUTE OF TECHNOLOGY. 
Mount, D. (2017). Network Flows: The Ford-Fulkerson Algorithm. CMSC 451. 
Park, J. (2015). Network Flow Problems. Stanford University. 
Romero, J. A. (2017). Cases of maximization of the flow into the supply chain, with the FordFulkerson 
algorithm. Mexico: Researchgate.