Errata Lista 5 - Problema do Fluxo Máximo

Prévia do material em texto

LISTA 5 
 
Centro Federal de Educação Tecnológica Celso Suckow da Fonseca 
Departamento de Engenharia de Produção 
Disciplina: Pesquisa Operacional II 
Tema: Problema do Fluxo Máximo 
Professor: Ormeu Coelho da Silva Júnior 
1 – Encontre o corte mínimo entre fonte (so) e sumidouro (si) nas redes 1, 2 e 3, abaixo ilustradas. A 
seguir encontre os fluxos através da rede que maximizam o fluxo entre so e si. Além disso, construa 
um PPL que possa ser usado para determinar o fluxo máximo na rede. 
(a) Rede 1 
(b) Rede 2 
 
(c) Rede 3 
 
2 – Uma estação de tratamento de esgoto precisa determinar sua máxima capacidade de tratamento 
em termos da vazão (em 103 m3/s). A rede abaixo ilustra as conexões existentes entre o ponto de 
recebimento dos efluentes (vértice A), os tanques de tratamento (vértices D a E) e o ponto de despejo 
da água tratada (vértice F). Os arcos indicam as possíveis conexões e os valores as capacidades (em 
103 m3/s). 
 
 
(a) Determine, por inspeção, o corte de menor capacidade nesta rede. A partir dele, pode-se 
dizer qual o valor do fluxo máximo ou pelo menos estabelecer um limite superior para ele? 
(b) Empregue o algoritmo de Ford-Fulkerson para determinar os fluxos em cada arco que 
maximizam a quantidade de esgoto tratada. 
 
3 – Quatro trabalhadores estão disponíveis para executar as tarefas 1-4. Infelizmente, três 
trabalhadores só podem executar determinadas tarefas: trabalhador 1, apenas a tarefa 1; trabalhador 
2, apenas as tarefas 1 e 2; trabalhador 3, apenas a tarefa 2, trabalhador 4, qualquer tarefa. Desenhe a 
rede para o problema de fluxo máximo que possa ser usada para determinar se todas as tarefas podem 
ser atribuídas a um trabalhador adequado. 
 
4 – As famílias Araújo, Braga, Coelho e Duarte estão indo para o seu churrasco familiar anual. Quatro 
carros estão disponíveis para transportar as famílias para o churrasco. Os carros podem transportar 
o seguinte número de pessoas: carro 1, quatro; carro 2, três; carro 3, três; carro 4, quatro. Existem 
quatro pessoas em cada família e nenhum carro pode transportar mais de duas pessoas de nenhuma 
família. Formule o problema de transportar o maior número possível de pessoas para o churrasco 
como um problema de fluxo máximo. 
 
5 – Suponha que a capacidade de processamento de cada tanque intermediário indicado no exercício 
2 é de 8x103m3. Como seria possível representar essa restrição através de uma restrição de capacidade 
de arco de modo que o problema ainda pudesse ser resolvido pelo algoritmo de Ford-Fulkerson para 
achar o fluxo máximo entre A e F. 
 
 
 
Breno
Realce