unidade IV

Prévia do material em texto

Métodos Quantitativos Aplicados
Capítulo 6: Aplicações
APLICAÇÕES DE MÉTODOS QUANTITATIVOS
	6.1. CONCEITOS
A Teoria de Grafos trata de abstrações de certos problemas práticos encontrados em diferentes áreas de conhecimento. Muitos destes problemas podem ser descritos na forma de um grafo. Os problemas consistem em encontrar uma configuração ótima (máxima ou mínima, conforme o caso) de certo tipo no grafo. A dificuldade de todos os problemas de Grafos está em desenvolver algoritmos eficientes que encontrem a configuração ótima desejada. Para alguns dos problemas, algoritmos eficientes muito interessantes já foram descobertos, mas para muitos outros, a procura por algoritmos eficientes continua. Existem as técnicas mais tradicionais, bem como algoritmos paralelos, algoritmos probabilísticos e algoritmos que buscam soluções "aproximadamente ótimas".
De acordo com a Teoria da Complexidade Computacional, pode-se concluir que ainda não existem algoritmos eficientes para muitos problemas. Pergunta-se: "Que tipos de problemas são intrinsecamente difíceis?". Esta é uma questão fundamental que tem preocupado um grande número de pesquisadores nos últimos anos.
Em resumo, denomina-se grafo um conjunto de pontos, chamados nós, conectados entre si por linhas chamadas arcos, como exemplificado no desenho abaixo:
�
Os círculos são denominados nós e as linhas são denominadas de arcos.
	6.2. REDE
É um grafo com algum tipo de fluxo fluindo entre os nós através dos arcos.
Ex: Uma rede de estradas (arcos) unindo várias cidades (nós). O conjunto de veículos andando nas estradas é o fluxo que flui na rede.
	6.3. VOCABULÁRIO
1.	NÓS - São as representações das localidades nos problemas resolvidos por grafos.
É exposto por um círculo com um número ou uma letra dentro (.
2.	CAMINHO MÍNIMO - É o caminho entre dois nós diferentes que tem o menor custo, dados os nós de entrada e saída.
3.	NÓS ACESSÍVEIS - São todos os nós acessíveis de um nó dado como entrada.
4.	COMPONENTE CONEXA - É o nome dado a dois nós que são acessíveis um pelo outro por um caminho direto.
	6.4. TIPOS DE PROBLEMAS E RESOLUÇÕES
PROBLEMAS DE EXTENSÃO MÍNIMA
É descrito por um conjunto de nós não orientados, onde o objetivo é construir uma rede conexa, contendo os nós cujos custos associados aos ramos utilizados sejam mínimos.
ÁRVORE GERADORA MÍNIMA
É o conjunto de arcos da rede que ligam todos os nós e tem o menor custo.
Ex. Entrega dos correios
�
PROBLEMAS DE PERCURSO MÍNIMO
É a determinação de um percurso através da interligação do nó de entrada, FONTE, ao nó de saída, SUMIDOURO, tal que a soma dos custos associados ao trajeto seja mínima.
CAMINHO MAIS CURTO
Constrói-se uma lista de distâncias, em ordem crescente, e, através de um processo de escolha e eliminação, cortam-se os ramos que indicam um percurso de custo mais elevado. Os ramos que levam a nós já selecionados são eliminados e assim vai-se escolhendo os nós e ramos até que se chegue ao sumidouro.
Ex. Escolha de um caminho, dentre vários, para a entrega de uma carga
PROBLEMAS DE FLUXO MÁXIMO
É a construção de um esquema de transporte que maximize a quantidade de material enviada entre dois pontos.
Da fonte ao sumidouro existem várias rotas diretas ou intermediárias, que serão usadas passando o máximo de fluxo, até que todas as possibilidades estejam esgotadas.
Ex. Reestruturação de vias de tráfego de veículos em horário de ‘pico’.
PROBLEMA DO CAIXEIRO VIAJANTE
Tem por objetivo passar por todos os nós da rede uma única vez.
Ex. Entrega de Correspondências.
�
6.4.1. ÁRVORE GERADORA MÍNIMA
Um problema de extensão mínima envolve um conjunto de nós e um conjunto de ramos propostos, nenhum deles orientado. Cada ramo proposto possui um custo não negativo associado. O objetivo é construir uma rede conexa contendo todos os nós e tal que a soma dos custos associados aos ramos realmente utilizados seja mínima.
Não é difícil constatar que o problema de extensão mínima é sempre resolvido por meio de uma árvore. Uma árvore de extensão mínima pode ser obtida selecionando-se, inicialmente, qualquer nó e determinando-se que ramo incidente no nó selecionado possui o menor custo. Este ramo é aceito como parte da rede inicial. A rede é, então, completada de forma iterativa. A cada estágio do processo iterativo, a atenção é focalizada sobre os nós já interligados, conectando - se a eles o ramo de menor custo. Os empates são decididos arbitrariamente. O processo iterativo termina quando todos os nós foram interligados.
Ex.
Z = 1+1+4+3+3+5 = 17
�
6.4.2. CAMINHO MAIS CURTO
Um problema de percurso mínimo envolve uma rede conexa dotada de custos não negativos, associados a cada um dos ramos. Um nó designado como fonte e um outro designado como sumidouro. O objetivo é determinar um percurso interligando a fonte e o sumidouro, tal que a soma dos custos associados aos ramos do percurso seja mínima. Os problemas de percurso mínimo são resolvidos por meio do seguinte algoritmo, no qual todos os empates são decididos arbitrariamente:
Passo 1: Constrói - se uma lista principal, tabulando-se sob cada nó, em ordem crescente de custo, os ramos aí incidentes. Cada ramo sob um determinado nó é escrito com este nó como sendo o primeiro. Omite-se da lista qualquer ramo que tenha a fonte como segundo nó, ou o sumidouro como seu primeiro nó.
Passo 2: Assinala-se com asterisco o nó fonte, alocando - lhe o valor zero. Localiza-se o ramo de menor custo incidente na fonte, assinalando-o com um círculo. Assinala-se com asterisco o segundo nó deste ramo e aloca – se a este nó um valor igual ao custo do ramo. Elimina-se da lista principal todos os outros ramos que possuem o nó recém – assinalado com asterisco, como sendo segundo nó.
Passo 3: Se o nó recém – assinalado com asterisco for o sumidouro, vai-se para o passo 5, caso contrário, continue.
Passo 4: Consideram-se, na lista principal corrente, todos os nós assinalados com asterisco, sob os quais haja ramos não envoltos por círculos. Para cada um destes nós, adiciona-se ao valor que lhe é alocado, o custo do ramo de menor custo não envolto por círculo sob o nó em pauta. Designa-se a menor dessas somas por M e circunda-se o ramo cujo custo contribuiu para M. Assinala-se com asterisco o segundo nó deste ramo e aloca - se a ele o valor M. Exclui-se da lista principal todos os outros ramos que possuam o nó recém – assinalado por asterisco, como segundo nó. Vá para o passo 3.
Passo 5: Z é o valor alocado ao sumidouro. Um percurso de custo mínimo é obtido, recursivamente, começando-se com o sumidouro, pela inclusão no percurso de cada um dos ramos circundados, cujo segundo nó pertença ao percurso.
	0
A*
	12
B*
	19
C*
	33
D*
	45
E*
	AB=12
	BC=14
	CD=16
	DE=13
	
	AC=19
	BD=23
	CE=26
	
	
	AD=33
	BE=38
	
	
	
	AE=49
	
	
	
	
Caminho mais curto: A – C – E
6.4.3. PROBLEMAS DE FLUXO MÁXIMO
O objetivo num problema de fluxo máximo é desenvolver um esquema de transporte que maximize a quantidade de material enviada entre dois pontos. O ponto de origem é chamado fonte; o destino, sumidouro. Existem várias rotas interligando a fonte ao sumidouro diretamente, ou por localidades intermediárias chamadas junções. Admite-se que as junções não podem estocar material, isto é, todo material que chegue a uma junção é expedido imediatamente para outra localidade.
O problema de fluxo máximo pode ser modelado por uma rede, associando a cada ramo (rota) uma capacidade de fluxo, representando a maior quantidade de material possível de ser transportada por cada ramo.
Os problemas de fluxo máximo podem ser resolvidos por meio do seguinte algoritmo:
Passo 1: Acha-se um percurso, da fonte ao sumidouro, que possa acomodar um fluxo positivo de material. Se não existir, vai-se para o passo 5.
Passo 2: Determina-se o fluxo máximoque pode ser transportado ao longo deste percurso e designa-se este custo por k.
Passo 3: Reduz-se de k a capacidade direta, isto é, a capacidade no sentido do fluxo de k unidades de cada ramo deste percurso e aumenta-se a capacidade inversa de k. Adiciona-se k unidades às quantidades entregues ao sumidouro.
Passo 4: Volte ao passo 1.
Passo 5: O fluxo máximo é a quantidade de material entregue ao sumidouro. O esquema de transporte ótimo é determinado comparando-se as redes original e final. Toda redução na capacidade significa um transporte.
Ex.
C
D
B
A
E
F
G
5
3
7
3
8
7
10
1
1
2
10
4
4
G
F
C
B
E
D
A
A
B
C
D
E
19
14
12
26
16
38
49
23
13
33
4
4
8
7
0
0
10
0
f=15
f=15
B
C
D
A
7
3
5
5
4
4
0
7
0
0
10
8
f=7
f=7
B
C
D
A
0
10
5
5
4
4
0
0
D
10
B
f=0
f=0
8
0
6
5
4
2
3
1
C
A
7
4
8
8
16
1
1
7
6
5
4
2
3
1
2
2
2
5
5
3
7
A
D
C
B
f=22
f=22
0
3
0
7
0
8
0
8
2
8
0
10
Profª Márcia Machado.
� PAGE \* MERGEFORMAT �65�