Grafos

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:
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.
a. 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.
Resposta:
Método utilizado: Árvore Geradora Mínima. Justificativa: O algoritmo da árvore geradora mínima trata de conectar os nós de uma rede, direta ou indiretamente, usando o comprimento total mais curto de ramos conectores.
b. Determinar o caminho mais curto entre duas cidades em uma rede de rodovias existentes.
Resposta:
Método utilizado: Algoritmo do Caminho mais curto. Justificativa: O problema do caminho mínimo determina o caminho mais curto entre um destino e uma origem em uma rede de transporte.
c. Determinar a capacidade máxima de escoamento de uma tubulação de lama de carvão que liga duas minas.
Resposta:
Método utilizado: Algoritmo do Fluxo Máximo. Justificativa: O algoritmo de fluxo máximo é baseado em achar rotas de passagem com fluxo líquido positiva entre os nós de origem e sorvedouro. Cada rota compromete parte ou toda a capacidade de seus arcos ao fluxo na rede.
d. Determinar um cronograma para as atividades de um projeto de construção de uma casa.
Resposta:
Método utilizado: Algoritmo de Caminho Crítico. Justificativa: O Método do Caminho Crítico é um algoritmo baseado em cálculos para programar um conjunto de atividades do projeto. Esse processo determina quais atividades são “críticas” (no caminho mais longo) e quais possuem folga (que não atrasariam o projeto caso fossem adiadas).