Aula - Teoria dos Grafos (2º de 2014)

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Pesquisa Operacional II
Profª Lidia
www.vep.uff.br
poiilidia
Bibliografia
Taha, H.A. “Pesquisa Operacional”, Ed. Pearson, 2007
Hillier & Lieberman “Introdução à Pesquisa Operacional”, , 2005
Notas de aula, material adicional na xerox
*
Conteúdo
Parte I
Teoria dos Grafos
Caminho Mínimo
Árvore Geradora Mínima
Fluxo Máximo 
Teoria da Decisão
Apoio Multicritério à Decisão
Decisão com incerteza
Decisão com risco
Teoria da Utilidade
*
Conteúdo
Parte II
Teoria dos Jogos
Jogos de Soma Zero
Jogos de Soma não constante
Cadeias de Markov
Teoria das Filas
M/M/1
M/M/S
*
Teoria dos Grafos
Pontes de Königsberg na Prússia que cruzam o rio Pregel (atual Kalingrado, na Russia): “seria possível percorrer todas as quatro seções e voltar ao local de partida cruzando cada ponte uma única vez?”
Resolvido por Leonhard Euler XVIII, resposta: não é possível realizar tal percurso
*
Teoria dos Grafos
Um grafo é uma noção simples e abstrata utilizada para representar a idéia de relação entre “elementos". Exemplos: relações de amizade, entre pais e filhos, entre irmãos, etc.
(X, Y) → X é pai/ mãe de Y
(X, Y) → X é irmão de Y
*
Teoria dos Grafos
Matematicamente: G = (V,A), onde V é o conjunto de vértices e A é o conjunto de ligações entre vértices.
Grafo não orientado: ligações representadas os pares de vértices não possuem uma ordem (i,j) = (j,i) = [i,j], aresta
Grafo orientado (dígrafo): ligações (arcos) representadas por partes ordenados (i,j)  (j,i)
*
Teoria dos Grafos
 Grafo não orientado Grafo orientado
	 V=(1,2,3,4,5,)		 V=(A,B,C,D,E)
 A=([1,2],[1,3],[1,5],[2,4],	 A=((A,B),(A,D),(A,C),(B,C),
	 [3,2][3,5],[3,4],[4,5])	 (C,E),(D,E),(E,D))
 n = 5, m=8			 n = 5, m = 7
Grafos valorados, valores associados às ligações = Redes 
*
Representação de um Grafo
Matriz de adjacências: dois vértices são adjacentes se estão unidos por uma aresta ou arco. Matriz Mnxn (n total de vértices)
	Exemplo:
*
Representação de um Grafo
Matriz de adjacências valorada - Matriz de Distâncias (custos): valores associados ás ligações, matriz D
Exemplo
*
Problemas estudados em Grafos
O Problema de Caminho Mínimo
O Problema de Fluxo Máximo
O Problema de Fluxo Máximo a custo mínimo
Árvore Geradora Mínima (AGM)
O Problema do Caixeiro Viajante
O Problema do Carteiro Chinês
Coloração em Grafos
Roteamento (roteirização) de veículos
Etc.
*
O Problema de Caminho Mínimo
Objetivo: minimização do custo de percurso de um grafo entre dois vértices, custo este dado pela soma dos custos de cada aresta percorrida.
Existem muitos algoritmos para resolver este problema, estudaremos dois: Dijkstra e Floyd
Algoritmo de Dijkstra: determina o custo ou distância mínima entre uma origem e um destino.
Algoritmo de Floyd: determina os custo ou distâncias mínimas entre todos os pares de vértices.
*
Algoritmo de Dijkstra
Para cada vértices usamos a notação: [c,j] X, chamada de rótulo
c custo até o momento, j vértice precedente, X pode ser T (temporário) ou P (permanente)
Início no vértice origem: [0,-]P
Analisar os vértices adjacentes e colocamos rótulos temporários, calculamos a distância até esse ponto, caso esteja rotulado escolhemos o de menor distância
Todos os vértices rotulados P, pare, caso contrário, escolha o de menor custo rotule como P e repetir o passo anterior
*
Algoritmo de Dijkstra
Exemplo:
*
Exercícios
São obtidas tiras de alumínio de 2cm a partir de outras de 12cm de espessura através de um processo de redução. A tabela descreve os custos de redução para cada 100m de alumínio. Determine a forma mais econômica de se obter tiras de 2cm.
*
Exercícios
Uma empresa está planejando a substituição da sua frota de carros para o período 2006-2011. No início de cada ano toma-se a decisão de se manter a frota operando ou se ela deve ser substituída. Essa substituição pode ocorrer no máximo após três anos de compra da frota. A tabela mostra o custo de substituição da frota como função do ano em que ela foi adquirida e o número de anos em operação. Determine o planejamento ótimo para a substituição da frota.
*
Algoritmo de Floyd
k iterações (k=1,..,n)
Verificar a iteração
Precisamos trabalhar com duas matrizes Dk e Rk
Passo inicial D0 e R0
*
Algoritmos de Floyd
Passo inicial D0 e R0 
Exemplo
*
Algoritmo de Floyd
Em cada iteração, podemos reduzir o trabalho levando em conta que:
A diagonal não muda;
Na k-ésima iteração, não haverá variação na linha pivô (linha k) e na coluna pivô (coluna k)
Na k-ésima iteração, caso exista na linha pivô (linha k) algum elemento onde dkj =∞ então a coluna j não irá variar nessa iteração;
Na k-ésima iteração, caso exista na coluna pivô (coluna k) algum elemento onde dik = ∞ então a linha i não irá variar nessa iteração.
*
Algoritmo de Floyd
O algoritmo:
Para k de 1 até n faça 	{k é a iteração}
	Se dik + dkj < dij então 	{verificamos as 		dij  dik + dkj		 distâncias}
		rij  rik
	fim se
Fim para
*
Algoritmo de Floyd
Iteração final
Como determinamos os caminhos mínimos entre pares de vértices?
 
 
*
Caminho mínimo
Formulação matemática
Função Objetivo de minimização de custos
Restrições: conservação de fluxo
Variáveis binárias
*
Formulação Matemática
Exemplo:
*
Árvores
Grafo conexo: quando existe pelo menos um percurso (seqüência) entre cada par de vértices
Árvore geradora: é um subgrafo de G, conexo e sem ciclos, e que contém todos os vértices de G 
 G		 Árvore 1		 Árvore 2
*
Árvore Geradora Mínima
É uma árvore de um grafo G de custo mínimo.
Algoritmos de solução: Kruskal e Prim
Algoritmo de Prim:
Selecionar qualquer vértice (o vértice pertence à árvore geradora)
Adicionar o vértice mais próximo à árvore, caso o vértice forme um ciclo selecionar o seguinte.
Algoritmo de Kruskal:
Selecionamos as arestas por ordem crescente de custo
Caso a aresta gere um ciclo selecionar a seguinte
*
Árvore Geradora Mínima
Seja o grafo G a seguir, determine a sua AGM.
*
Problemas de Fluxo Máximo
Formulação Matemática 
Capacidade do arco (i,j): uij 
Fluxo máximo: F 
Quantidade transportada no arco (i,j): xij
Quantidade transportada não pode ultrapassar a capacidade
*
PPL para o problema de Fluxo Máximo
Exemplo:
*
Algoritmo de Ford-Fulkerson Simplificado
Em cada arco rótulo (a,b)
a: fluxo disponível no arco
b: fluxo enviado pelo arco
Passo 1: encontre um caminho da origem ao destino que ainda possui fluxo disponível
Passo 2: Atualize os valores do par ordenado
Passo 3: caso não encontre um caminho com fluxo disponível, pare, caso contrário vá ao passo 2
*
Algoritmo de Ford-Fulkerson Simplificado
Exemplo:
*
Algoritmo de Ford-Fulkerson
Uso de fluxo positivos residuais nos dois sentidos.
Fluxo residual OB é 2; fluxo BO é 5
Construir um caminho aumentado: caminho da origem para o destino com fluxo residual estritamente positivo 
Passo 1: encontre um caminho da origem ao destino que ainda possui fluxo residual positivo, caso não encontre a solução atual é ótima
Passo 2: determine a capacidade residual máxima desse caminho, subtraia da capacidade residual de cada arco e adicionar à capacidade residual na direção oposta. Retorne ao passo 1.
*
Algoritmo de Ford-Fulkerson
Exemplo 1:
*
Algoritmo de Ford-Fulkerson
Exercício:
*
Percursos em grafos
Percurso ou itinerário ou ainda cadeia é uma família de ligações sucessivas adjacentes.
Hamiltoniano: percurso que visita cada vértice uma única vez. Problema do Caixeiro Viajante: “O Caixeiro Viajante deve sair da sua cidade (origem), visitar cada uma das outras (n-1) cidades uma única vez e retornar à cidade de origem, de forma tal
a percorrer uma única distância possível”
Percurso Hamiltoniano:
*
Percursos em grafos
Euleriano: percurso que usa cada ligação exatamente uma vez. Problema do Carteiro Chinês.: “o carteiro deseja percorrer todas as ruas da sua rota um número mínimo de vezes e voltar ao correio”
Percurso 
Euleriano:
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*