·
Engenharia de Produção ·
Métodos Quantitativos Aplicados
Send your question to AI and receive an answer instantly
Recommended for you
31
Teoria dos Jogos - Jogos de Soma Zero e Estrategias Mistas - Notas de Aula
Métodos Quantitativos Aplicados
PUC
22
Notas de Aula Metodos Quantitativos Tomada de Decisao Otimizacao e Heuristicas
Métodos Quantitativos Aplicados
PUC
23
Algoritmo de Teitz-Bart para Problema das P-Medianas: Notas de Aula e Exemplo Prático
Métodos Quantitativos Aplicados
PUC
42
Notas de Aula - Problema do Caixeiro Viajante PCV e Algoritmos de Resolução
Métodos Quantitativos Aplicados
PUC
28
Notas de Aula - Métodos Quantitativos - Problema dos Múltiplos Caixeiros Viajantes PMCV
Métodos Quantitativos Aplicados
PUC
22
AHP - Metodologia de Decisão Multicritério - Notas de Aula
Métodos Quantitativos Aplicados
PUC
21
Notas de Aula - Métodos Quantitativos - Problemas de Localização de Facilidades e Algoritmos de Transporte
Métodos Quantitativos Aplicados
PUC
29
Simulated Annealing - Notas de Aula sobre Metaheurística para Otimização
Métodos Quantitativos Aplicados
PUC
38
Problema do Carteiro Chinês - Conceito e Aplicações em Métodos Quantitativos
Métodos Quantitativos Aplicados
PUC
20
Notas de Aula - Heurística dos Savings de Clarke Wright para PCV
Métodos Quantitativos Aplicados
PUC
Preview text
Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 02 Matriz de distâncias mínimas entre pares de nós Algoritmo de Floyd É uma generalização do algoritmo de Dijkstra estudado na disciplina de Otimização Avançada de Processos ou POII e aplicado na resolução do Problema do Caminho Mínimo The ShortestPath Problem Algoritmo de Floyd Christofides 1975 9 Matriz inicial Algoritmo de Floyd Método exato 3 2 Determinava entre vários existentes o caminho de custo mínimo entre dois pontos origem e destino Determina as distâncias mínimas entre todos os pares de nós 4 5 2 3 6 1 Floyd 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 j i j i Matriz final distâncias mínimas entre todos os pares 4 4 4 5 5 10 10 9 15 Algoritmo de Dijkstra Google Maps EX Caminho mínimo de A para B Grafo A B Edsger W Dijkstra Fornece os caminhos de mínimo custo para todos os pares de vértices Sejam C cij a matriz de custos arcos de conexão direta e T tij a matriz de caminhos trajetos associados aos custos ambas vinculadas a um grafo G X A onde X é o conjunto de vértices e A é o conjunto de arcos definidas como 1 Faça k 0 2 k k 1 3 Para todo i k tal que cik e todo j k tal que ckj faça a operação cij min cij cik ckj 4 a Se k n pare A solução foi alcançada e cij fornece os custos mínimos para cada par de vértices b Se k n volte a 2 Algoritmo de Floyd Método exato n 12 i para i j t A se i j n 12 j para i se i 0 A indicado em cada arco i j se i j custo c ij ij 3 Christofides 1975 O algoritmo pode ser implementado a fim de apresentar além dos custos mínimos entre os pares de pontos os caminhos trajetos nos quais estes custos foram obtidos Para tanto Te Chiang Hu 1969 sugere o armazenamento de uma segunda matriz T tij onde tij é o vértice predecessor do vértice j no caminho mínimo entre os vértices i e j Inicialmente tij i j A atualização desta matriz será feita da seguinte forma c c se c t c c se c t t kj ik ij ij kj ik ij kj ij Exemplo de referência da aplicação do Algoritmo de Floyd Em uma região industrial determinada empresa de segurança planeja definir um circuito de comprimento mínimo para ronda tática de monitoramento interligando 5 cinco fábricas através do sistema viário já implantado na região A figura a seguir mostra a localizações das fábricas 1 2 3 4 e 5 e dos segmentos de vias existentes Os números presentes em cada arco indicam as extensões em quilômetros dos segmentos das vias Assim determine as mínimas distâncias entre todos os pares de nós fábricas Aplicando o algoritmo de Floyd determine a mínima distância entre todos os pares de nós vértices do grafo GX A apresentado a seguir Exemplo de referência da aplicação do Algoritmo de Floyd 1 5 3 2 4 1 8 4 2 3 3 4 4 Grafo GX A Conj dos nós vértices 12345 X Conj dos arcos 45 53 54 23 24 35 41 12 13 14 15 i j A 5 n 6 i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 0 2 5 4 2 0 j i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 j 1 5 3 2 4 1 8 4 2 3 3 4 4 n 12 n e j 12 i para i t A se i j n 12 j para i se i 0 A do arco i j se i j custo c ij ij Inicialmente tij i nó predecessor j k0 C k0 T 0 k Nós predecessores dos j 45 53 54 23 24 35 41 12 13 14 15 i j A i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 0 2 5 4 2 0 j i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k0 C k1 C c min c c c kj ik ji ij c c se c t c c se c t t kj ik ij ij kj ik ij kj ij i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 j k0 T i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k1 T c min c c c 1j i1 ji ij todos os outros c c se c t 4 3 e 1 3 c c se c t t 1j i1 ij ij 1j i1 ij 1j ij 8 1 k 3 Para todo i k tal que cik e todo j k tal que ckj faça a operação cij min cij cik ckj 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 1 i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k1 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k1 T i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k2 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k2 T c min c c c 2 j i2 ji ij c c se c t c c se c t t 2j i2 ij ij 2j i2 ij 2j ij Sem alterações k 2 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 2 Sem alterações i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k2 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k2 T c min c c c 3j i3 ji ij c c se c t 4 4 c c se c t t 3j i3 ij ij 3j i3 ij 3j ij i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 8 3 0 4 4 3 4 7 0 2 5 4 2 0 j k3 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k3 T 10 k 3 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 3 c min c c c 4 j i4 ji ij c c se c t 4 2 3 2 2 3 8 3 3 2 3 8 c c se c t t 4j i4 ij ij 4j i4 ij 4j ij i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 8 3 0 4 4 3 4 7 0 2 5 4 2 0 j k3 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k3 T i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 0 4 4 3 4 7 0 2 5 5 6 4 2 0 j k4 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 3 3 3 3 3 4 4 1 1 4 4 5 4 1 5 5 5 j k4 T k 4 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 4 c min c c c 5j i5 ji ij c c se c t 4 2 2 7 4 6 4 5 4 c c se c t t 5j i5 ij ij 5j i5 ij 5j ij i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 0 4 4 3 4 7 0 2 5 5 6 4 2 0 j k4 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 3 3 3 3 3 4 4 1 1 4 4 5 4 1 5 5 5 j k4 T i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 j k5 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 4 1 3 5 3 4 4 1 5 4 4 5 4 1 5 5 5 j k5 T Matrizes Finais 5 k 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 5 i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 j k5 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 4 1 3 5 3 4 4 1 5 4 4 5 4 1 5 5 5 j k5 T 1 5 3 2 4 1 8 4 3 4 4 Sentido do deslocamento 32 O predecessor do nó 2 é o nó 1 do 1 é o 4 do 4 é o 5 do 5 é o 3 e do 3 é o próprio 3 que indica o fim do trajeto 2 3 a Com base nas duas matrizes encontradas determine o caminho de menor custo para o deslocamento do nó 3 até o nó 2 13 Trajeto 3 4 1 2 5 Custo distância mínimo C42 4 2 3 1 10 i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 j k5 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 4 1 3 5 3 4 4 1 5 4 4 5 4 1 5 5 5 j k5 T 1 5 3 2 4 1 8 4 2 3 3 4 4 O predecessor do nó 2 é o nó 1 do 1 é o 4 do 4 é o 4 e do 4 é o próprio 4 que indica o fim do trajeto Sentido do deslocamento 42 Trajeto 4 Custo distância mínimo C42 3 1 4 b Com base nas duas matrizes encontradas determine o caminho de menor custo para o deslocamento do nó 4 até o nó 2 2 1 OBS Se ao aplicar o algoritmo de Floyd nenhuma alteração na tabela inicial for observada isto significa que esta tabela já contemplava as distâncias mínimas entre todos os pares de nós Todas distâncias de todas ligações existentes entre todos os pares de pontos conectados 1 5 3 2 4 1 8 4 2 3 3 4 4 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 0 2 5 4 2 0 j i Apenas as distâncias mínimas das rotas entre todos os pares de pontos Matriz obtida pela aplicação do Método Floyd 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 i j 1 5 3 2 4 1 8 4 2 3 3 4 4 Circuito que parte e retorna para 1 passando uma única vez por cada ponto com comprimento mínimo Prob do Caixeiro Viajante PCV Exemplo de uma aplicação do algoritmo de Floyd como prérequisito para aplicação posterior de algoritmos que resolvem o Problema do Caixeiro Viajante PCV Floyd 123541 Solução do PCV 1 5 4 2 3 5 9 7 2 3 3 3 6 7 6 10 5 4 1 4 1 Determine as matrizes finais C e T 2 Qual o custo e o trajeto do melhor caminho do nó 1 até o nó 7 Dado o seguinte grafo determine as mínimas distâncias entre todos os pares de nós Algoritmo de Floyd j i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 3 0 5 10 0 3 6 0 2 7 5 1 0 Atividade Formativa 6 1º TDE Metodologia Sala de Aula Invertida OBS A realização desta atividade faz parte do processo de ensino e aprendizagem contribuindo em muito com a consolidação deste conhecimento Não é necessária sua entrega e se qualquer dúvida permanecer após o feedback dado nos próximos slides esta deverá ser sanada com o professor nos horários das aulas Tk0 k0 C i 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 3 0 5 10 0 3 6 0 2 7 5 1 0 j j j i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 9 3 0 5 10 15 0 3 6 0 2 7 5 1 0 Ck1 k1 T i 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 4 4 4 5 5 1 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j Feedback da Atividade Formativa 6 1º TDE j i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 9 3 0 5 10 15 0 3 6 0 2 7 5 1 0 Ck1 k1 T i 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 4 4 4 5 5 1 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 2 0 6 7 3 3 0 9 4 4 4 9 3 0 12 5 10 15 21 22 0 3 6 0 2 7 5 1 0 Ck2 k2 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 4 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 2 0 6 7 3 3 0 9 4 4 4 9 3 0 12 5 10 15 21 22 0 3 6 0 2 7 5 1 0 Ck2 k2 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 4 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 1 14 9 0 Ck3 k3 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 2 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 3 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 1 14 9 0 Ck3 k3 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 2 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 3 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 11 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck4 k4 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 4 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 11 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck4 k4 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 4 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 2 11 0 6 7 3 6 3 19 24 0 31 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck5 k5 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 1 2 4 2 2 2 2 5 2 3 5 1 3 2 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 2 11 0 6 7 3 6 3 19 24 0 31 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck5 k5 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 1 2 4 2 2 2 2 5 2 3 1 5 3 2 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 19 24 0 31 9 4 6 4 4 9 3 0 12 7 9 5 10 15 21 22 0 3 5 6 0 2 7 5 10 4 1 13 8 0 Ck6 k6 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 1 5 3 2 3 3 6 4 4 1 4 4 2 3 6 5 5 1 2 2 5 5 6 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 19 24 0 31 9 4 6 4 4 9 3 0 12 7 9 5 10 15 21 22 0 3 5 6 0 2 7 5 10 4 1 13 8 0 Ck6 k6 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 1 5 3 2 3 3 6 4 4 1 4 4 2 3 6 5 5 1 2 2 5 5 6 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 11 16 0 7 9 4 6 4 4 9 3 0 12 7 9 5 10 15 9 6 0 3 5 6 7 12 6 3 15 0 2 7 5 10 4 1 13 8 0 Ck7 k7 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 4 1 3 7 3 3 6 4 4 1 4 4 2 3 6 5 5 1 4 7 5 5 6 6 4 1 4 7 2 6 6 7 4 1 4 7 2 3 7 j 1 5 4 2 3 5 9 7 2 3 3 3 6 7 6 10 5 4 1 4 Tk7 k7 C i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 4 1 3 7 3 3 6 4 4 1 4 4 2 3 6 5 5 1 4 7 5 5 6 6 4 1 4 7 2 6 6 7 4 1 4 7 2 3 7 i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 11 16 0 7 9 4 6 4 4 9 3 0 12 7 9 5 10 15 9 6 0 3 5 6 7 12 6 3 15 0 2 7 5 10 4 1 13 8 0 1 5 4 2 3 7 6 24 Trajeto 12567 Custo distância mínimo C17 13 j j Notas de Aula Prof Edgard 1 Arenales M Armentano V Morabito R E Yanasse H Pesquisa Operacional para cursos de Engenharia Editora Campus Rio de Janeiro 2007 2 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 3 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 4 Goldbarg M C e Luna H P Otimização Combinatória e Programação Linear Modelos e Algoritmos Editora Campus Rio de Janeiro 2000 5 Hillier F S e Lieberman G J Introdução à Pesquisa Operacional traduzido McGrawHill São Paulo 2006 6 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 7 Puccini A de L e Pizzolato N D Programação Linear Livros Técnicos e Científicos Ed Ltda Rio de Janeiro 1990 Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do Curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras
Send your question to AI and receive an answer instantly
Recommended for you
31
Teoria dos Jogos - Jogos de Soma Zero e Estrategias Mistas - Notas de Aula
Métodos Quantitativos Aplicados
PUC
22
Notas de Aula Metodos Quantitativos Tomada de Decisao Otimizacao e Heuristicas
Métodos Quantitativos Aplicados
PUC
23
Algoritmo de Teitz-Bart para Problema das P-Medianas: Notas de Aula e Exemplo Prático
Métodos Quantitativos Aplicados
PUC
42
Notas de Aula - Problema do Caixeiro Viajante PCV e Algoritmos de Resolução
Métodos Quantitativos Aplicados
PUC
28
Notas de Aula - Métodos Quantitativos - Problema dos Múltiplos Caixeiros Viajantes PMCV
Métodos Quantitativos Aplicados
PUC
22
AHP - Metodologia de Decisão Multicritério - Notas de Aula
Métodos Quantitativos Aplicados
PUC
21
Notas de Aula - Métodos Quantitativos - Problemas de Localização de Facilidades e Algoritmos de Transporte
Métodos Quantitativos Aplicados
PUC
29
Simulated Annealing - Notas de Aula sobre Metaheurística para Otimização
Métodos Quantitativos Aplicados
PUC
38
Problema do Carteiro Chinês - Conceito e Aplicações em Métodos Quantitativos
Métodos Quantitativos Aplicados
PUC
20
Notas de Aula - Heurística dos Savings de Clarke Wright para PCV
Métodos Quantitativos Aplicados
PUC
Preview text
Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 02 Matriz de distâncias mínimas entre pares de nós Algoritmo de Floyd É uma generalização do algoritmo de Dijkstra estudado na disciplina de Otimização Avançada de Processos ou POII e aplicado na resolução do Problema do Caminho Mínimo The ShortestPath Problem Algoritmo de Floyd Christofides 1975 9 Matriz inicial Algoritmo de Floyd Método exato 3 2 Determinava entre vários existentes o caminho de custo mínimo entre dois pontos origem e destino Determina as distâncias mínimas entre todos os pares de nós 4 5 2 3 6 1 Floyd 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 j i j i Matriz final distâncias mínimas entre todos os pares 4 4 4 5 5 10 10 9 15 Algoritmo de Dijkstra Google Maps EX Caminho mínimo de A para B Grafo A B Edsger W Dijkstra Fornece os caminhos de mínimo custo para todos os pares de vértices Sejam C cij a matriz de custos arcos de conexão direta e T tij a matriz de caminhos trajetos associados aos custos ambas vinculadas a um grafo G X A onde X é o conjunto de vértices e A é o conjunto de arcos definidas como 1 Faça k 0 2 k k 1 3 Para todo i k tal que cik e todo j k tal que ckj faça a operação cij min cij cik ckj 4 a Se k n pare A solução foi alcançada e cij fornece os custos mínimos para cada par de vértices b Se k n volte a 2 Algoritmo de Floyd Método exato n 12 i para i j t A se i j n 12 j para i se i 0 A indicado em cada arco i j se i j custo c ij ij 3 Christofides 1975 O algoritmo pode ser implementado a fim de apresentar além dos custos mínimos entre os pares de pontos os caminhos trajetos nos quais estes custos foram obtidos Para tanto Te Chiang Hu 1969 sugere o armazenamento de uma segunda matriz T tij onde tij é o vértice predecessor do vértice j no caminho mínimo entre os vértices i e j Inicialmente tij i j A atualização desta matriz será feita da seguinte forma c c se c t c c se c t t kj ik ij ij kj ik ij kj ij Exemplo de referência da aplicação do Algoritmo de Floyd Em uma região industrial determinada empresa de segurança planeja definir um circuito de comprimento mínimo para ronda tática de monitoramento interligando 5 cinco fábricas através do sistema viário já implantado na região A figura a seguir mostra a localizações das fábricas 1 2 3 4 e 5 e dos segmentos de vias existentes Os números presentes em cada arco indicam as extensões em quilômetros dos segmentos das vias Assim determine as mínimas distâncias entre todos os pares de nós fábricas Aplicando o algoritmo de Floyd determine a mínima distância entre todos os pares de nós vértices do grafo GX A apresentado a seguir Exemplo de referência da aplicação do Algoritmo de Floyd 1 5 3 2 4 1 8 4 2 3 3 4 4 Grafo GX A Conj dos nós vértices 12345 X Conj dos arcos 45 53 54 23 24 35 41 12 13 14 15 i j A 5 n 6 i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 0 2 5 4 2 0 j i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 j 1 5 3 2 4 1 8 4 2 3 3 4 4 n 12 n e j 12 i para i t A se i j n 12 j para i se i 0 A do arco i j se i j custo c ij ij Inicialmente tij i nó predecessor j k0 C k0 T 0 k Nós predecessores dos j 45 53 54 23 24 35 41 12 13 14 15 i j A i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 0 2 5 4 2 0 j i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k0 C k1 C c min c c c kj ik ji ij c c se c t c c se c t t kj ik ij ij kj ik ij kj ij i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 j k0 T i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k1 T c min c c c 1j i1 ji ij todos os outros c c se c t 4 3 e 1 3 c c se c t t 1j i1 ij ij 1j i1 ij 1j ij 8 1 k 3 Para todo i k tal que cik e todo j k tal que ckj faça a operação cij min cij cik ckj 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 1 i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k1 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k1 T i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k2 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k2 T c min c c c 2 j i2 ji ij c c se c t c c se c t t 2j i2 ij ij 2j i2 ij 2j ij Sem alterações k 2 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 2 Sem alterações i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 4 7 0 2 5 4 2 0 j k2 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k2 T c min c c c 3j i3 ji ij c c se c t 4 4 c c se c t t 3j i3 ij ij 3j i3 ij 3j ij i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 8 3 0 4 4 3 4 7 0 2 5 4 2 0 j k3 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k3 T 10 k 3 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 3 c min c c c 4 j i4 ji ij c c se c t 4 2 3 2 2 3 8 3 3 2 3 8 c c se c t t 4j i4 ij ij 4j i4 ij 4j ij i 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 8 3 0 4 4 3 4 7 0 2 5 4 2 0 j k3 C i 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 1 1 4 4 5 5 5 5 5 5 j k3 T i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 0 4 4 3 4 7 0 2 5 5 6 4 2 0 j k4 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 3 3 3 3 3 4 4 1 1 4 4 5 4 1 5 5 5 j k4 T k 4 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 4 c min c c c 5j i5 ji ij c c se c t 4 2 2 7 4 6 4 5 4 c c se c t t 5j i5 ij ij 5j i5 ij 5j ij i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 0 4 4 3 4 7 0 2 5 5 6 4 2 0 j k4 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 3 3 3 3 3 4 4 1 1 4 4 5 4 1 5 5 5 j k4 T i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 j k5 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 4 1 3 5 3 4 4 1 5 4 4 5 4 1 5 5 5 j k5 T Matrizes Finais 5 k 1 5 3 2 4 1 8 4 2 3 3 4 4 Haveria entre as rotas pressentes na tabela alguma que reduziria seu custo se inseríssemos nela a passagem pelo nó 5 i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 j k5 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 4 1 3 5 3 4 4 1 5 4 4 5 4 1 5 5 5 j k5 T 1 5 3 2 4 1 8 4 3 4 4 Sentido do deslocamento 32 O predecessor do nó 2 é o nó 1 do 1 é o 4 do 4 é o 5 do 5 é o 3 e do 3 é o próprio 3 que indica o fim do trajeto 2 3 a Com base nas duas matrizes encontradas determine o caminho de menor custo para o deslocamento do nó 3 até o nó 2 13 Trajeto 3 4 1 2 5 Custo distância mínimo C42 4 2 3 1 10 i 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 j k5 C i 1 2 3 4 5 1 1 1 1 1 4 2 4 2 2 2 4 3 4 1 3 5 3 4 4 1 5 4 4 5 4 1 5 5 5 j k5 T 1 5 3 2 4 1 8 4 2 3 3 4 4 O predecessor do nó 2 é o nó 1 do 1 é o 4 do 4 é o 4 e do 4 é o próprio 4 que indica o fim do trajeto Sentido do deslocamento 42 Trajeto 4 Custo distância mínimo C42 3 1 4 b Com base nas duas matrizes encontradas determine o caminho de menor custo para o deslocamento do nó 4 até o nó 2 2 1 OBS Se ao aplicar o algoritmo de Floyd nenhuma alteração na tabela inicial for observada isto significa que esta tabela já contemplava as distâncias mínimas entre todos os pares de nós Todas distâncias de todas ligações existentes entre todos os pares de pontos conectados 1 5 3 2 4 1 8 4 2 3 3 4 4 1 2 3 4 5 1 0 1 4 3 8 2 0 4 3 3 0 4 4 3 0 2 5 4 2 0 j i Apenas as distâncias mínimas das rotas entre todos os pares de pontos Matriz obtida pela aplicação do Método Floyd 1 2 3 4 5 1 0 1 4 3 5 2 6 0 4 3 5 3 9 10 0 6 4 4 3 4 6 0 2 5 5 6 4 2 0 i j 1 5 3 2 4 1 8 4 2 3 3 4 4 Circuito que parte e retorna para 1 passando uma única vez por cada ponto com comprimento mínimo Prob do Caixeiro Viajante PCV Exemplo de uma aplicação do algoritmo de Floyd como prérequisito para aplicação posterior de algoritmos que resolvem o Problema do Caixeiro Viajante PCV Floyd 123541 Solução do PCV 1 5 4 2 3 5 9 7 2 3 3 3 6 7 6 10 5 4 1 4 1 Determine as matrizes finais C e T 2 Qual o custo e o trajeto do melhor caminho do nó 1 até o nó 7 Dado o seguinte grafo determine as mínimas distâncias entre todos os pares de nós Algoritmo de Floyd j i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 3 0 5 10 0 3 6 0 2 7 5 1 0 Atividade Formativa 6 1º TDE Metodologia Sala de Aula Invertida OBS A realização desta atividade faz parte do processo de ensino e aprendizagem contribuindo em muito com a consolidação deste conhecimento Não é necessária sua entrega e se qualquer dúvida permanecer após o feedback dado nos próximos slides esta deverá ser sanada com o professor nos horários das aulas Tk0 k0 C i 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 3 0 5 10 0 3 6 0 2 7 5 1 0 j j j i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 9 3 0 5 10 15 0 3 6 0 2 7 5 1 0 Ck1 k1 T i 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 4 4 4 5 5 1 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j Feedback da Atividade Formativa 6 1º TDE j i 1 2 3 4 5 6 7 1 0 5 2 0 6 7 3 3 0 9 4 4 4 9 3 0 5 10 15 0 3 6 0 2 7 5 1 0 Ck1 k1 T i 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 4 4 4 5 5 1 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 2 0 6 7 3 3 0 9 4 4 4 9 3 0 12 5 10 15 21 22 0 3 6 0 2 7 5 1 0 Ck2 k2 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 4 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 2 0 6 7 3 3 0 9 4 4 4 9 3 0 12 5 10 15 21 22 0 3 6 0 2 7 5 1 0 Ck2 k2 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 4 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 1 14 9 0 Ck3 k3 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 2 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 3 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 1 14 9 0 Ck3 k3 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 2 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 3 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 11 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck4 k4 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 4 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 15 2 11 0 6 7 3 10 3 0 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck4 k4 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 3 1 2 4 2 2 2 2 3 2 3 3 3 3 3 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 2 11 0 6 7 3 6 3 19 24 0 31 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck5 k5 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 1 2 4 2 2 2 2 5 2 3 5 1 3 2 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 2 11 0 6 7 3 6 3 19 24 0 31 9 4 4 4 9 3 0 12 7 5 10 15 21 22 0 3 6 0 2 7 5 10 4 1 13 8 0 Ck5 k5 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 1 2 4 2 2 2 2 5 2 3 1 5 3 2 3 3 3 4 4 1 4 4 2 3 4 5 5 1 2 2 5 5 5 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 19 24 0 31 9 4 6 4 4 9 3 0 12 7 9 5 10 15 21 22 0 3 5 6 0 2 7 5 10 4 1 13 8 0 Ck6 k6 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 1 5 3 2 3 3 6 4 4 1 4 4 2 3 6 5 5 1 2 2 5 5 6 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 19 24 0 31 9 4 6 4 4 9 3 0 12 7 9 5 10 15 21 22 0 3 5 6 0 2 7 5 10 4 1 13 8 0 Ck6 k6 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 1 5 3 2 3 3 6 4 4 1 4 4 2 3 6 5 5 1 2 2 5 5 6 6 6 6 6 6 6 6 6 7 4 1 4 7 2 3 7 j j i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 11 16 0 7 9 4 6 4 4 9 3 0 12 7 9 5 10 15 9 6 0 3 5 6 7 12 6 3 15 0 2 7 5 10 4 1 13 8 0 Ck7 k7 T i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 4 1 3 7 3 3 6 4 4 1 4 4 2 3 6 5 5 1 4 7 5 5 6 6 4 1 4 7 2 6 6 7 4 1 4 7 2 3 7 j 1 5 4 2 3 5 9 7 2 3 3 3 6 7 6 10 5 4 1 4 Tk7 k7 C i 1 2 3 4 5 6 7 1 1 1 2 2 2 5 6 2 4 2 2 2 2 5 6 3 4 1 3 7 3 3 6 4 4 1 4 4 2 3 6 5 5 1 4 7 5 5 6 6 4 1 4 7 2 6 6 7 4 1 4 7 2 3 7 i 1 2 3 4 5 6 7 1 0 5 11 12 8 11 13 2 11 0 6 7 3 6 8 3 11 16 0 7 9 4 6 4 4 9 3 0 12 7 9 5 10 15 9 6 0 3 5 6 7 12 6 3 15 0 2 7 5 10 4 1 13 8 0 1 5 4 2 3 7 6 24 Trajeto 12567 Custo distância mínimo C17 13 j j Notas de Aula Prof Edgard 1 Arenales M Armentano V Morabito R E Yanasse H Pesquisa Operacional para cursos de Engenharia Editora Campus Rio de Janeiro 2007 2 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 3 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 4 Goldbarg M C e Luna H P Otimização Combinatória e Programação Linear Modelos e Algoritmos Editora Campus Rio de Janeiro 2000 5 Hillier F S e Lieberman G J Introdução à Pesquisa Operacional traduzido McGrawHill São Paulo 2006 6 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 7 Puccini A de L e Pizzolato N D Programação Linear Livros Técnicos e Científicos Ed Ltda Rio de Janeiro 1990 Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do Curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras