Pert - análise de redes

5. ANÁLISE DE REDES
Na antiguidade: redes (problemas)...
• Fluviais / marítimas (transportes)
• Para abastecimento de água
• De esgotos
Na actualidade: redes (problemas)...
• Ferroviárias / rodoviárias
• Eléctricas
• De comunicações
Modelação / resolução de problemas: através de redes...
• Gestão de projectos (PERT / CPM)
• Gestão da produção
• Problemas de transporte / distribuição
Optimização de redes vs. Programação linear
Problemas simples (árvore de cobertura mínima, caminho mais curto, ...) vs. Problemas difíceis (caixeiro-viajante, ...)
Conceitos base:
Redes (ou grafos): nós + arcos (orientados, se lhes estiverem associados sentidos) Arcos conexos: arcos com um nó comum
Rede conexa: qualquer par de nós, tem, sempre, um caminho a ligá-los
Árvore: rede conexa, em que o caminho a ligar qualquer par de nós é único DEG, Acácio Porta Nova (rev. 2004, João Lourenço)

145

Cadeia: sequência de arcos tal que um está ligado ao arco anterior por uma extremidade e ao arco seguinte pela outra extremidade (corresponde a um caminho num grafo orientado)
Caminho: sequência de arcos tal que a extremidade final de cada arco coincide com a extremidade inicial do seguinte
Ciclo: cadeia finita que parte de um nó e alcança esse mesmo nó
(corresponde a um circuito num grafo orientado)
Circuito: caminho finito no qual o nó inicial do primeiro arco coincide com o nó final do último arco
Lacete: circuito constituido por um só arco e um só nó

Problema: Uma autarquia local quer levar energia eléctrica a um pequeno lugar, constituído por sete casas isoladas, entre as quais a Casa do Povo comunitária (4). As ligações serão feitas por cabos aéreos, suportados por postes, que também servirão para iluminação pública; para facilitar o cabimento das despesas de instalação, deseja-se minimizar o comprimento total dos cabos eléctricos, mas assegurando a ligação de todas as casas.
A figura a seguir mostra as distâncias aproximadas entre as várias