Atividade 3 Pesquisa Operacional

Prévia do material em texto

Atividade 3 – Pesquisa Operacional. 
 
"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. 
 
Situação 1: Árvore geradora mínima: consiste em conectar um conjunto de pontos (nós ou 
vértices) em uma rede com o menor tamanho possível. 
Situação 2: Algoritmo de caminho mais curto: O objetivo é ligar um nó de origem a um nó de 
destino, passando por outros nós que fazem parte da rede pelo menor caminho possível. Usa-se, 
por exemplo, dois algoritmos: o algoritmo de Dijkstra e o algoritmo de Floyd. 
Situação 3: Algoritmo de fluxo máximo: permite encontrar o caminho em que a maior 
quantidade possível de fluxo chegue à outra extremidade. 
Situação 4: Algoritmo de caminho crítico: O método do caminho crítico (CPM) e a técnica de 
revisão e avaliação do programa (PERT) são usados, principalmente, para a elaboração de redes 
que visam planejar, programar ou controlar projetos [...] é possível obter uma visão gráfica de 
todas as atividades envolvidas em um projeto, a duração do projeto, quais atividades são críticas 
e o tempo de folga das atividades não críticas [...] 
 
Fontes de pesquisa: 
TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. pag. 105. (acesso através 
do Leitor - Biblioteca Virtual Universitária, plataforma.bvirtual.com.br). 
Santiago, R. E. F. Pesquisa Operacional, EAD. br. Unidade 3, Otimização em Grafos.