Algoritmo de Teitz-Bart para Problema das P-Medianas: Notas de Aula e Exemplo Prático

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 11 PLF nº e locais indefinidos heurística de Teitz Bart Algoritmo de Teitz Bart fornece uma solução heurística É um método aproximado baseado na substituição de vértices foi apresentado por Teitz e Bart em 1968 e é conhecido como o Algoritmo das p medianas de Teitz e Bart Algoritmo de Teitz e Bart Seja V v1 v2 v3 vn o conjunto de todos os vértices vi com i12n Passo 1 Selecione arbitrariarmente um conjunto S contido em V com p vértices para formar uma solução inicial para o problema das p medianas Passo 2 Rotule todos os vértices vj S como não analisados não testados Passo 3 Enquanto existirem vértices não analisados em V S faça a Selecione um vértice vj V S não analisado e calcule a redução ij do número de transmissão para todo vi S b Encontre v v σ S σ S Δ i j ij Δ Δ ij S v ij max i v v marque v como analizado e 0 substitua S por S Δ II 0 marque v como analisado e Δ I Se j i j ij j ij para o passo 2 volte para o passo 2 volte c Passo 4 Se no final da iteração verificarse que não houve alteração da solução inicial da iteração S PARE e apresente S como uma solução aproximada para o problema das pmedianas Em caso contrário comece a próxima usando como solução inicial a última solução com Δij 0 obtida na iteração que se finaliza Quando não existirem mais vértices não analisados em V S é o fim da iteração em curso Seja o Problema de Localização de Facilidades ou Problema das Pmedianas do qual são dados 5 vértices dos quais se deve selecionar 2 vértices ou seja P 2 para medianas do problema Utilize o Algoritmo de Teitz e Bart para solucionálo Considere a Matriz das distâncias mínimas aproximadas entre todos os pares de pontos dada a seguir caso contrário teria que aplicar o algoritmo de Floyd Exemplo Coord xy Demanda W v101 1 v2 02 2 v3 11 3 v4 20 1 v5 21 2 i j v1 v2 v3 v4 v5 W v1 0 1 1 2 2 1 v2 1 0 1 3 2 2 v3 1 1 0 1 1 3 v4 2 3 1 0 1 1 v5 2 2 1 1 0 2 medianas ex Escolas P as designaçõe s que receberão Vértices iv alunos Bairros c ex designados serão que Vértices jv Solução 4 1 v v v Inicial S Solução i 5 3 2 v v v v V S dos vértices não analisados Conjunto j 5 4 3 2 1 v v v v v V Passo 1 Selecione arbitrariamente um conjunto S contido em V com p vértices para formar uma solução inicial para o problema das p medianas Passo 2 Rotule todos os vértices vj S como não analisados não testados 1 v4 v S iv 5 3 2 v v v V S j v 5 4 3 2 1 v v v v v V i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 Para simplificar os cálculos podemos ponderar previamente todos os valores de cada linha distâncias multiplicandoos pelas respectivas demandas i j v1 v2 v3 v4 v5 W v1 0 1 1 2 2 1 v2 1 0 1 3 2 2 v3 1 1 0 1 1 3 v4 2 3 1 0 1 1 v5 2 2 1 1 0 2 Matriz das distâncias mínimas e demandas dada inicialmente i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 Matriz das distâncias ponderadas com as demandas wj dvi vj i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 a Selecione um vértice vj V S não analisado e calcule a redução ij do número de transmissão para todo vi S v v σ S σ S Δ i j ij Passo 3 Enquanto existirem vértices não analisados em V S faça Se selecionar vj v2 temse i j v1 v2 v3 v4 v5 V1 0 1 1 2 2 V2 2 0 2 6 4 V3 3 3 0 3 3 V4 2 3 1 0 1 v5 4 4 2 2 0 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 b Encontre Δ Δ ij S v ij max i 1ª Iteração e marque v como analisadoe volte para o passo 2 v v 0 substitua S por S Δ II 0 marque v como analisadoe volte para o passo 2 Δ I Se j i j ij j ij c v v 4 2 v v v v por S substitua S 1 2 4 1 Passo 2 v Analisado 2 1ª Iteração v v v e Analisad o 6 VS σ S v v S 2 5 3 v 4 2 V j i i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 Se o selecionado for vj v3 temse 5 2 1 2 σ v v 4 3 1 5 6 Δ23 v v v v Pv 4 3 3 4 i 3 no lugar de 2 Entra 2 2 2 v v v 4 1 1 2 σ v v 3 2 2 4 6 Δ43 v v v v Pv 3 2 3 2 i 3 no lugar de 4 Entra 4 4 4 v v v i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 2 Δ Δ ij S v 43 max i v e Analisado v 6 VS σ S 2 5 v j v v v S 3 4 2 V i Passo 3 Enquanto existirem vértices não analisados em V S faça a Selecione um vjV S e ache a redução ij do no de transmissão Ɐ vi S b Encontre v v σ S σ S Δ i j ij Δ Δ ij S v ij max i c Se Passo 2 v v e Analisado 4 VS σ S 3 2 v j v v v S 5 3 2 V i Passo 2 1ª Iteração v v marque v como analizado e 0 substitua S por S Δ II 0 marque v como analisado e Δ I j i j ij j ij para o passo 2 volte volte para o passo 2 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 Se o selecionado for vj v5 temse 4 1 2 1 v v 5 3 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 0 4 4 Δ25 v v v v Pv 5 3 5 3 i 5 no lugar de 2 Entra 2 2 2 v v v 5 1 3 1 v v 5 2 1 5 4 Δ35 v v v v Pv 5 2 5 2 i 5 no lugar de 3 Entra 3 3 3 v v v 0 Δ Δ ij S v 25 max i v v e Analisado 4 VS σ S 3 2 v j v v v S 5 3 2 V i Passo 2 Passo 3 Enquanto existirem vértices não analisados em V S faça a Selecione um vjV S e ache a redução ij do no de transmissão Ɐ vi S b Encontre v v σ S σ S Δ i j ij Δ Δ ij S v ij max i c Se Passo 2 v v v e Analisado 4 VS σ S 5 3 2 v j v v S 3 2 V i Fim da 1ª Iteração Então fica v v anteriorou seja S solução para o passo 2 Logo dáse continuidade com a 0 marque v como analisado e volte Δ Se 3 2 V j ij i Atenção 1ª Iteração v v marque v como analizado e 0 substitua S por S Δ II 0 marque v como analisado e Δ I j i j ij j ij para o passo 2 volte volte para o passo 2 Em nosso exemplo houve alteração da solução inicial Svi v1 v4 para a última obtida com Δij 0 ou seja Svi v2 v3 que será usada como solução inicial da segunda iteração que começa no passo 2 Passo 4 Se no final da iteração verificarse que não houve alteração da solução inicial da iteração S PARE e apresente S como uma solução aproximada para o problema das pmedianas Em caso contrário comece a próxima usando como solução inicial a última solução com Δij 0 obtida na iteração que se finaliza i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 Se o selecionado for vj v1 temse 5 2 1 2 σ v v 3 1 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 1 5 4 Δ21 v v v v Pv 3 1 1 3 i 1 no lugar de 2 Entra 2 2 2 v v v 9 4 2 3 σ v v 2 1 5 9 4 Δ31 v v v v Pv 2 1 1 2 i 1 no lugar de 3 Entra 3 3 3 v v v 1 Δ Δ ij S v 21 max i Passo 2 Passo 3 Enquanto existirem vértices não analisados em V S faça a Selecione um vjV S e ache a redução ij do no de transmissão Ɐ vi S b Encontre v v σ S σ S Δ i j ij Δ Δ ij S v ij max i c Se Passo 2 2ª Iteração e Analisado v v 4 VS σ S 5 4 v j v v v S 1 3 2 V i v e Analisado v 4 VS σ S 1 5 v j v v v S 4 3 2 V i Então fica v v anteriorou seja S solução para o passo 2 Logo dáse continuidade com a 0 marque v como analisado e volte Δ Se 3 2 V j ij i Atenção v v marque v como analizado e 0 substitua S por S Δ II 0 marque v como analisado e Δ I j i j ij j ij para o passo 2 volte volte para o passo 2 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 Se o selecionado for vj v4 temse 5 2 1 2 σ v v 4 3 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 1 5 4 Δ24 v v v v Pv 4 3 4 3 i 4 no lugar de 2 Entra 2 2 2 v v v 6 2 1 3 σ v v 4 2 2 6 4 Δ34 v v v v Pv 4 2 4 2 i 4 no lugar de 3 Entra 3 3 3 v v v 1 Δ Δ ij S v 24 max i Passo 2 Passo 3 Enquanto existirem vértices não analisados em V S faça a Selecione um vjV S e ache a redução ij do no de transmissão Ɐ vi S b Encontre v v σ S σ S Δ i j ij Δ Δ ij S v ij max i c Se Passo 2 2ª Iteração v v e Analisado 4 VS σ S 4 1 v j v v v S 5 3 2 V i Então fica v v anteriorou seja S solução para o passo 2 Logo dáse continuidade com a 0 marque v como analisado e volte Δ Se 3 2 V j ij i Atenção v e Analisado v 4 VS σ S 1 5 v j v v v S 4 3 2 V i v v marque v como analizado e 0 substitua S por S Δ II 0 marque v como analisado e Δ I j i j ij j ij para o passo 2 volte volte para o passo 2 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 Se o selecionado for vj v5 temse 4 1 2 1 σ v v 5 3 i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 2 0 2 6 4 v3 3 3 0 3 3 v4 2 3 1 0 1 v5 4 4 2 2 0 0 4 4 Δ25 v v v v Pv 5 3 5 3 i 5 no lugar de 2 Entra 2 2 2 v v v 5 1 3 1 σ v v 5 2 1 5 4 Δ35 v v v v Pv 5 2 5 2 i 5 no lugar de 3 Entra 3 3 3 v v v 0 Δ Δ ij S v 25 max i Passo 2 Passo 3 Enquanto existirem vértices não analisados em V S faça a Selecione um vjV S e ache a redução ij do no de transmissão Ɐ vi S b Encontre v v σ S σ S Δ i j ij Δ Δ ij S v ij max i v marque v como analisado e volte p o passo 2 v substitua S por S 0 marque v como analisado e volte para o passo 2 0 j i j j c Se ij Passo 2 2ª Iteração v v v e Analisado 4 VS σ S 5 4 1 v j v v S 3 2 V i Então fica v v anteriorou seja S solução para o passo 2 Logo dáse continuidade com a 0 marque v como analisado e volte Δ Se 3 2 V j ij i Atenção v v e Analisado 4 VS σ S 4 1 v j v v v S 5 3 2 V i Fim da 2ª Iteração Em nosso exemplo não houve alteração da solução inicial Svi v2 v3 durante esta iteração então PARE e apresente S como uma solução aproximada para o problema das pmedianas regra de parada Passo 4 Se no final da iteração verificarse que não houve alteração da solução inicial da iteração S PARE e apresente S como uma solução aproximada para o problema das pmedianas Em caso contrário comece a próxima usando como solução inicial a última solução com Δij 0 obtida na iteração que se finaliza Resposta 2 v3 v S i j v1 v2 v3 v4 v5 v1 0 1 1 2 2 v2 1 0 1 3 2 v3 1 1 0 1 1 v4 2 3 1 0 1 v5 4 4 2 2 0 AGRUPAMENTOS CLUSTERS Valor ótimo por coincidência pois é uma heurística Seja o Problema de Localização de Facilidades ou Problema das Pmedianas do qual são dados 5 vértices dos quais se deve selecionar 2 vértices ou seja P 2 para medianas do problema Utilize o Algoritmo de Teitz e Bart para solucionálo Considere a Matriz das distâncias mínimas aproximadas entre todos os pares de pontos dada a seguir Iniciaze o algoritmo com S V1 V2 Coord xy Demanda W v1 3 5 1 v2 310 1 v3 5 9 3 v4 7 7 2 v5 115 1 i j v1 v2 v3 v4 v5 W v1 0 5 4 4 8 1 v2 5 0 2 5 9 1 v3 4 2 0 2 7 3 v4 4 5 2 0 4 2 v5 8 9 7 4 0 1 Algoritmo de Teitz Bart cont fornece uma solução heurística Atividade Formativa 8 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 Matriz das distâncias ponderadas com as demandas wj dvi vj i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 5 4 3 2 1 v v v v v V 2 1 v v v Inicial S Solução i 5 4 3 v v v v Não analisados VS j Analisados A i j v1 v2 v3 v4 v5 W v1 0 5 4 4 8 1 v2 5 0 2 5 9 1 v3 4 2 0 2 7 3 v4 4 5 2 0 4 2 v5 8 9 7 4 0 1 22 8 8 6 σ S 1ª Iteração 2 1 v v v S i Sol Inicial 22 σ S i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 3 13 v S v2 Teste para v3 15 7 4 4 S σ 7 22 15 13 Δ i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 3 23 v S v1 13 7 4 2 S σ 9 22 13 23 Δ 5 4 v v v S V j v Analisados A 3 3 1 v v v S i 13 σ S 9 Δ Δ ij S v ij max i 5 4 v v v S V j v Analisados A 3 3 1 v v v S i 13 σ S i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 4 14 v S v3 Teste para v4 10 4 2 4 S σ 3 10 13 14 Δ i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 4 34 v S v1 15 4 6 5 S σ 2 13 15 34 Δ 5 v v S V j 3 v4 v Analisados A 4 3 v v v S i 10 σ S i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 5 35 v S v4 Teste para v5 15 6 5 4 S σ 5 10 15 35 Δ i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 5 45 v S v3 10 4 2 4 S σ 0 10 10 45 Δ S V j v 5 4 3 v v v Analisados A 4 3 v v v S i 10 σ S Permanece 3 Δ Δ ij S v ij max i 0 Δ Δ ij S v ij max i 5 2 1 v v v v S V j Analisados A 4 3 v v v S i 10 σ S Houve modificação 2ª Iteração i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 v4 1 31 v S Teste para v1 15 4 6 5 S σ 5 10 15 31 Δ i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 1v3 41 v S 13 7 4 2 S σ 3 10 13 41 Δ 5 2 v v v S V j v1 Analisados A 4 3 v v v S i 10 σ S Permanece i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 2 v4 32 v S Teste para v2 14 4 6 4 S σ 4 10 14 32 Δ i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 15 7 4 4 S σ 5 10 15 42 Δ 1 v2 v Analisados A 4 3 v v v S i 10 σ S Permanece 2 v3 42 v S 5 v v S V j 3 Δ Δ ij S v ij max i 4 Δ Δ ij S v ij max i 1 v2 v Analisados A 4 3 v v v S i 10 σ S 5 v v S V j i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 5 35 v S v4 15 6 5 4 S σ 5 10 15 35 Δ i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 10 4 2 4 S σ 0 10 10 45 Δ 5 2 1 v v v Analisados A 4 3 v v v S i 10 σ S 5 45 v S v3 S V j v Teste para v5 Permanece Não houve modificação durante toda a 2ª Iteração FIM 3 v4 Duas Medianas S v i j v1 v2 v3 v4 v5 v1 0 5 4 4 8 v2 5 0 2 5 9 v3 12 6 0 6 21 v4 8 10 4 0 8 v5 8 9 7 4 0 10 C v v v v v v v min 4 5 4 3 3 2 1 med med 1ª Hipótese ou 10 C v v v v v v v min 4 5 4 1 3 3 2 med med 2ª Hipótese 0 Δ Δ ij S v ij max i xy W v1 3 5 1 v2 310 1 v3 5 9 3 v4 7 7 2 v5 115 1 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