Atividade Unidade 3 - Pesquisa Operacional

Prévia do material em texto

A otimização por grafos auxilia a resolução de diversos problemas inerentes ao 
engenheiro de produção, sendo que esses problemas podem estar relacionados a alguma 
organização ou a um setor da sociedade de modo geral. 
A seguir, estão alguns problemas comuns e que podem ser resolvidos utilizando a 
otimização por grafos ou redes: 
1. Projeto de construção de uma rede de tubulações para ligar uma plataforma de 
petróleo marítima localizada no Rio de Janeiro a um ponto de entrega na Terra, 
com objetivo de minimizar os custos de construção da rede. 
2. Determinar o caminho mais curto entre duas cidades em uma rede de rodovias 
existentes. 
3. Determinar a capacidade máxima de escoamento de uma tubulação de lama de 
carvão que liga duas minas. 
4. Determinar um cronograma para as atividades de um projeto de construção de 
uma casa. 
Relacione cada uma das situações citadas com um método de otimização por grafos que 
pode solucioná-las. Justifique por que está fazendo essa associação com base nos 
princípios de cada um dos métodos. 
RESPOSTA: 
1. Projeto de construção de uma rede de tubulações para ligar uma plataforma de 
petróleo marítima localizada no Rio de Janeiro a um ponto de entrega na Terra, 
com objetivo de minimizar os custos de construção da rede: 
Neste caso, o método mais propenso a ser utilizado seria o de Árvore Geradora Mínima 
(ou Árvore de Steiner). Isto porque, segundo estudado, este algoritmo consegue 
conectar os nós de uma rede usando o comprimento total mais curto. Desta forma, seria 
possível realizar a construção de uma rede de tubulações de maneira mais eficiente, uma 
vez que não seriam construídos caminhos de comprimentos maiores e que necessitariam 
de um custo maior para sua realização. 
2. Determinar o caminho mais curto entre duas cidades em uma rede de rodovias 
existentes: 
Neste caso, o método mais propenso seria o do Caminho Mais Curto, uma vez que este 
algoritmo, como o próprio nome já justifica, tem como objetivo identificar o roteiro que 
percorre a menor distância possível. Logo, o algoritmo fornece esta solução utilizando 
os nós existentes nesta problematização para que fosse possível identificar qual caminho 
seria mais curto para conectar as duas cidades. 
3. Determinar a capacidade máxima de escoamento de uma tubulação de lama de 
carvão que liga duas minas: 
Neste caso, o método mais propenso a ser utilizado é o de Emparelhamento Máximo. 
Este consiste em identificar o caminho em que a maior quantidade possível de fluxo 
chegue à outra extremidade. Esta é feita de maneira que cada iteração começa com um 
fluxo (f) que deve respeitar a capacidade de cada arco, onde a primeira iteração tem 
fluxo nulo e os processos seguintes continuam enquanto continuar havendo um caminho 
aumentador, pelo qual o fluxo, no caso a lama de carvão, consiga passar. 
4. Determinar um cronograma para as atividades de um projeto de construção de 
uma casa: 
Nesse caso, o método mais propenso é o Caminho Crítico. Este tem por objetivo 
programar um conjunto de atividades de um determinado projeto. Como o próprio nome 
indica, este algoritmo encarrega-se de identificar quais são os processos críticos e quais 
são os processos que não atrasariam o projeto de construção da casa caso estes fossem 
adiados.