Optimização de redes Zuher Khalil,

Prévia do material em texto

Optimização de redes
 Uma rede consiste em um conjunto de pontos e um conjunto de linhas que unem certos pares de pontos. Os pontos se chamam nódulos (ou vértices). As linhas se chamam arcos (ramas). 
 Os modelos de redes proporcionam um poderoso apoio visual e conceitual para mostras as relações entre os componentes do sistema. 
 Os nódulos podem representar cidades, intersecções de caminhos, fontes de agua, bancos de materiais e etc. 
 Os arcos representam caminhos, rotas aéreas, redes de fibras ópticas, cabos elétricos. Os arcos podem ter um tipo de fluxo que passem por eles, por exemplo, volume veicular. Quando um arco o fluxo só se permite em uma direção, se chama arco dirigido e se representa com uma flecha, por outro lado se o fluxo se permite em ambos sentidos se chama ligadura. Se a rede está composta somente de arcos dirigidos se chama rede dirigida. 
 O que é um ciclo?
Uma trajetória que começa e termina em um mesmo nódulo. Por exemplo: DE-ED é um ciclo dirigido, por que toma a direção de D a E e volta no mesmo nódulo por outro arco. 
 Os modelos de redes surgem em uma grande variedade de situações da vida diária: 
· Redes de transporte, elétricas e de comunicações;
· Problemas de produção; 
· Problemas de distribuição;
· Planificação de projetos;
· Planificação financeira;
· Localização de instalações;
· Administração de recursos. 
 Se diz que uma rede está conectada o que é conexa se cada dois nódulos diferentes estão conectados por ao menos uma rota. 
Uma árvore é uma rede conectada livre de ciclos composta de um subconjunto de todos os nódulos. A árvore de expansão é uma que une todos os nódulos da rede.
 Técnicas 
· Árvore de expansão mínima: essa técnica implica conectar todos os nódulos de uma rede minimizando a distância entre eles. 
· Rota mais curta: se considera uma rede conexa com dois nódulos especiais chamados origem e destino. A cada arco se associa uma distância não negativa. O objetivo é encontrar a rota mais curta, desde a origem ao destino. 
· Fluxo máximo: é determinar a quantidade máxima de fluxo (veículos, mensagens, fluidos e etc.) que pode entrar e sair de uma rede em um período dado. 
· Agente viageiro: dado um conjunto de cidades para visitar, o agente viageiro deve encontrar a rota que lhe permita visitar todas as cidades uma única vez e voltando ao ponto de partida, assegurando que a distância recorrida seja mínima.