Baixe o app para aproveitar ainda mais
Prévia do material em texto
Profº Túlio de Almeida Pesquisa Operacional II 1. TEORIA DOS GRAFOS E OTIMIZAÇÃO EM REDES Pontes de Königsberg na Prússia que cruzam o rio Pregel (atual Kalingrado na Rússia). Seria possível percorrer todas as quatro seções e voltar ao local de partida cruzando uma ponte de cada vez? Resolvido por Leonhard Euler XVIII, resposta: NÃO É POSSÍVEL REALIZAR TAL PERCURSO! A Teoria dos Grafos auxilia na solução de problemas similares, podendo ser aplicada em várias situações onde se pretende obter por exemplo: A melhor maneira de interligar lugares onde é necessário uma conexão eficiente e/ou mais econômica entre eles; O menor caminho possível; O maior fluxo de materiais, insumos e/ou produtos; O funcionamento de atividades em rede e identificação de gargalos. 1.1. A TEORIA DOS GRAFOS De uma forma geral, os grafos podem ser vistos como modelos de rede que são utilizados em casos especiais de problemas de programação linear (PPL) dos quais podem ser representados melhor de forma gráfica. Importantes problemas de otimização tais como problemas de distribuição logística e energia, produção e outros, são eficientemente resolvidos se modelados como problema de rede. 1.1.1. Definição de Grafos Um grafo é uma noção simples e abstrata utilizada para representar a ideia de relação entre elementos. Tais elementos podem ser entendidos como cidades, máquinas, postos de trabalho, fábricas entre outros. Definição Matemática Os grafos podem ser definidos por )A;V(G , onde V é o conjunto de vértices e A é o conjunto de ligações entre vértices. Grafos Não-Orientados: Ligações do tipo aresta, onde as ligações que representam os pares de vértice (i,j) não possuem uma ordem ou um sentido obrigatório., ou seja, (i,j) = (j,i) = [i,j]. Características do Grafo G. V = (1, 2, 3, 4, 5) A = ([1,2], [1,3], [1,5], [2,3], [2,4], [3,4], [3,5[, [4,5]) n = 5 (número de vértices) m = 8 (número de arestas) Grafos Orientados ou Dígrafos Ligações do tipo arco, onde a ordem dos pares de vértice (i,j) importa, sendo assim (i,j) ≠ (j,i). Características do Grafo G V = (A, B, C, D, E) A = ((A,B), (A,C), (A,D), (B,C), (C,E), (D,E), (E,D)) Profº Túlio de Almeida Pesquisa Operacional II n = 5 (número de vértices) m = 7 (número de arestas) 1.1.2. Representação de um Grafo Listas de Adjacências Armazena o relacionamento entre os vértices em uma estrutura de listas. Trata-se de uma estrutura econômica do ponto de vista computacional. Para grafos orientados há 2 listas: 1. origem-destinos 2. destino-origens 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) Matriz de Adjacências Valorada Trata-se de uma matriz que atribui valores as arestas ou arcos, sendo estes valores relacionados a distâncias, custos, capacidade etc. São valores associados a matriz D. A)j,i(d A)j,i(cd ji0d D ij ijij ij Exemplo: 1.1.3. O Problema do Caixeiro Viajante Trata-se de um percurso Hamiltoniano, onde cada vértice deve ser visitado uma única vez. Conceito Histórico Antigamente muitos vendedores, chamados de caixeiros viajantes, ganhavam a vida oferecendo seus produtos em diferentes cidades. Imagine que um caixeiro viajante escolhesse algumas cidades e precisasse encontrar o caminho mais curto para suas andanças. Em que ordem ele deveria percorrer as cidades escolhidas? Se fossem poucas cidades, seria fácil descobrir. Objetivo: O caixeiro viajante deve percorrer todas as cidades (vértices) passando por cada uma delas apenas UMA vez. Contextualizando ... Mas e se o caixeiro estivesse em Brasília e quisesse percorrer as capitais de todos os 26 estados brasileiros? Em que ordem ele deveria visitar essas cidades? Como descobrir qual o caminho mais curto? Uma opção seria considerar todas as possíveis ordenações das 26 cidades. Mas são tantas, que se levássemos apenas 1 segundo para calcular a distância total de cada possível percurso, levaríamos cerca de um bilhão de vezes a idade do universo para encontrar a resposta. Isso acontece porque o número de percursos alternativos cresce assustadoramente quando aumentamos o número de cidades. Profº Túlio de Almeida Pesquisa Operacional II Esse é o chamado Problema do Caixeiro Viajante, uma questão matemática muito importante para a indústria. Quem encontrar um método eficiente para resolvê-lo pode ganhar uma verdadeira fortuna! 1.1.4. O Problema do Carteiro Chinês Trata-se de um percurso Euleriano, onde cada arco ou aresta devem ser visitados uma única vez. Conceito Histórico A literatura relata um grande número de otimização combinatória associadas aos percursos desenvolvidos sobre as arestas de um grafo G. O Problema do Carteiro Chinês foi relatado inicialmente por Kwan Mei-Ko em 1962, na revista Chinese Mathematics. O problema consiste em determinar um caminho fechado (circuito) de custo mínimo que passe por cada aresta de um grafo G conectado pelo menos uma vez. Objetivo: O carteiro chinês deve percorrer todas as ruas (arestas e arcos) passando por cada uma delas apenas UMA vez. Contextualizando Se o carteiro chinês, estivesse em Volta Redonda na Vila Santa Cecília? Como ele poderia entregar as correspondências, passando apenas uma vez em cada rua ou avenida. E se ele estiver em um veículo automotor? Terá de respeitar as leis de trânsito, ou seja, a mão da via. 1.2. A ÁRVORE GERADORA MÍNIMA 1.2.1. Como Assim? Árvore? A árvore geradora mínima está relacionada a combinação de menor custo relacionada a um grafo G. O formato de árvore refere-se às conexões entre os vértices que são o suficiente para conectar todos eles. Normalmente tem o formato de árvore (tronco + galhos). Grafo Conexo Quando existe pelo menos um percurso (sequência) entre cada par de vértices. Árvore Geradora É um subgrafo de G que contém todos os vértices de G. 1.2.2. Algoritmo de Prim Profº Túlio de Almeida Pesquisa Operacional II O algoritmo de Prim segue as seguintes etapas: 1. Selecionar qualquer vértice (o vértice pertence à árvore geradora) 2. Adicionar o vértice mais próximo à árvore, caso o vértice forme um ciclo, deve-se selecionar o seguinte. Exemplo: Dado o grafo G a seguir, determine sua AGM, pelo algoritmo de Prim. 1.2.3. Algoritmo de Kruskal O algoritmo de Kruskal segue as seguintes etapas: 1. Selecionar as arestas por ordem crescente de custo; 2. Caso a aresta forme um ciclo, deve-se selecionar a seguinte. Exemplo: Dado o grafo G a seguir, determine sua AGM, pelo algoritmo de Prim. 1.3. O PROBLEMA DO CAMINHO MÍNIMO O Problema de Caminho Mínimo tem como principal objetivo minimizar o custo de percurso entre 2 vértices, custo este dado pela soma dos custos de cada aresta percorrida. Modelando conforme um PPL, obtem-se o seguinte modelo: m1,2,...,ji, 1;ou 0x mi se,1 m1ou i se,0 1i se,1 xx :a sujeito xcMin ij m 1j m 1j kjij m 1i m 1j ijij Função Objetivo de minimização de custos Restrições: conservação de fluxo Variáveis binárias Observação: trata-se de um problema de programação linear binária. Para a determinação exata deste problema, serão abordados 2 algoritmos: Djikstra e Floyd. 1.3.1. Algoritmo de Dijkstra Seja ui a distância mais curta do nó de origem ao nó i, e defina-se dij (≥0) como o comprimento do arco (i,j). Então, o algoritmo define o rótulo para um nó imediatamente posterior, j, como: 0d],i,du[]i,u[ ijijij Observação: o algoritmo de Djikstra determina o custo mínimo ou distância mínima entre uma origem e um destino. Etapas do Algoritmo 1. Para cada vértice, usa-se a notação [c,j] X, chamada de rótulo. Onde c é o custo (acumulado) até o momento e j é o vértice precedente. Quanto ao X, este pode assumir a condição T (temporário) ou P (permanente) 2. O vértice da origem começará por [0,-] P 3. Analisar os vértices adjacentes e colocar rótulos temporários (T) alocando o custo ou distância acumulada nos mesmos Profº Túlio de Almeida Pesquisa Operacional II 4. Para cada vértice, escolhe-se o menor custo ou distância. Para o rótulo de menor custo atribui-se o rótulo permanente (P) 5. Caso todos os rótulos estejam como permanente (P), pare. Se não, escolha o de menor custo voltando ao passo anterior. Exemplos: São obtidas tiras de alumínio de 2 cm a partir de outras de 12 cm de espessura por meio de um processo de redução. A tabela descreve os custos de redução para cada 100 metros de alumínio. Determine a forma mais econômica de se obter tiras de 2 cm. Espessura Redução em cm 2 4 6 12 6,2 7,2 8,5 10 6,8 7,4 9,2 08 7,1 12,8 15,2 06 8,2 14,6 04 10,5 - 12 cm 10 cm 8 cm 6 cm 4 cm 2 cm (0,-)P origem [6,2;12] P [7,2;12] P [8,5;12] P ∞ ∞ [13,0;10] T [13,6;10] T [15,4;10] P ∞ [14,3;8] T [20,0;8] T [22,4;8] P [16,7;6] T [23,1;6] T [25,9;4] T Lendo de trás para frente, ou seja, do destino para a origem tem-se: 12 cm 8cm 2 cm Resposta: A redução ideal deve ocorrer em duas etapas. A 1ª etapa ocorre de 12 para 8 centímetros (- 4) e 2ª etapa ocorre de 8 para 2 centímetros (-6). Uma empresa está planejando a substituição de sua frota de veículos para o período de 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 substituída 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 número de anos em operação. Determine o planejamento ótimo para a substituição da frota. Ano em que a frota foi adquirida Custo de substituição por anos de operação 1 2 3 2006 3800 4100 6800 2007 4000 4800 7000 2008 4200 5100 7200 2009 4800 5700 - 2010 5300 - - 200 6 2007 2008 2009 2010 2011 (0,- )P [3800;200 6] P [4100;200 6] P [6800;2006 ] P ∞ ∞ [7800;200 7] T [11600;200 7] T [10800;200 7] T ∞ [8300;2008 ] T [9200;2008 ] P [11300;200 8] P [11600;200 9] T [12500;200 9] T [14500;201 0] T Lendo de trás para a frente obtém-se que 2006 2008 2011 Resposta: A melhor estratégia de renovação da frota dos veículos adquiridos no ano de 2006 é trocar a frota no ano de 2008, tendo como horizonte de tempo o ano de 2011. 1.3.2. Algoritmo de Floyd O algoritmo representa uma rede de n nós como uma matriz uma matriz quadrada com n linhas e n colunas. A entrada (i.j) da matriz dá a distância (ou custo), dij, do nó i ao nó j, que é finita se i estiver ligado diretamente a j, caso contrário, é infinita. Observação: o algoritmo de Floyd determina os custos ou distâncias mínimas entre todos os pares de vértices. A Operação Tripla de Floyd O conceito do algoritmo de Floyd é objetivo. Dados 3 nós i, j e k, o caminho mais curto de ir i até j passando por k. Profº Túlio de Almeida Pesquisa Operacional II Ou seja, busca situações onde: ijkjik ddd No caso, é ótimo substituir a rota direta de i j pela rota indireta i k j. Essa operação tripla de troca é aplicada sistematicamente à rede. Etapas do Algoritmo 0. Defina a matriz de distâncias D 0 e a matriz de relações dos nós R 0 . Os elementos da diagonal são marcados com – para indicar que estão bloqueados. Determine k = 1. A)j,i(d A)j,i(cd ji0d D ij ijij ij 0 contrário caso0r djr R ij 0 ijij0 1. Defina a linha k e a coluna k como a linha pivô e coluna pivô (travar). Aplique a operação tripla a cada elemento dij em D k-1 para todo i e j. Se a condição for satisfeita, faça as seguintes mudanças: a. Crie D k substituindo dij em D k-1 por dik + dkj b. Crie R k substituindo rij em R k-1 por k. Determine k = k+1. Se k = n+1, pare; caso contrário, repita a etapa k. Reduzindo o Trabalho... 1. A diagonal não muda 2. Na k-ésima iteração, não haverá mudança na linha pivô (linha k) e na coluna pivô (coluna k) 3. 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 nesta iteração 4. 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 nesta iteração Exemplos: Para a rede apresentada, encontre os caminhos mais curtos entre todos os conjuntos de 2 nós. As distâncias em milhas são dadas nos arcos. O arco (3,5) é direcional, de modo que nenhum tráfego é permitido do nó 5 para o nó 3. Todos os outros nós permitem tráfego no dois sentidos. Etapa 0: Obtendo a Matriz D 0 54321 4 465 15610 53 103 5 4 3 2 1 D0 Obtendo a Matriz R 0 54321 4321 5321 5421 5431 5432 5 4 3 2 1 R 0 Etapa 1: Obtendo a Matriz D 1 k. Profº Túlio de Almeida Pesquisa Operacional II 54321 4 465 1561310 5133 103 5 4 3 2 1 D1 Obtendo a Matriz R 1 54321 4321 5321 5411 5411 5432 5 4 3 2 1 R1 Etapa 2: Obtendo a Matriz D 2 54321 4 4658 1561310 5133 8103 5 4 3 2 1 D2 Obtendo a Matriz R 2 54321 4321 5322 5411 5411 5232 5 4 3 2 1 R 2 Etapa 3: Obtendo a Matriz D 3 54321 4 4658 1561310 285133 258103 5 4 3 2 1 D2 Obtendo a Matriz R 3 54321 4321 5322 5411 3411 3232 5 4 3 2 1 R 2 Etapa 4: Obtendo a Matriz D 4 54321 410912 4658 1061110 95113 128103 5 4 3 2 1 D2 Obtendo a Matriz R 4 54321 4444 5322 4441 4441 4232 5 4 3 2 1 R 2 Etapa 5: Não há melhorias a serem feitas, agora basta interpretar a matriz resultante na 4ª iteração (etapa 4). v v v v v Profº Túlio de Almeida Pesquisa Operacional II DESAFIO! Etapa 0 Obtendo a Matriz D 0 TEDCBAO 71 5 41 34 72 452 T E D C B A O D0 Obtendo a Matriz R 0 TEDCBAO 7654321 7654321 7654321 7654321 7654321 7654321 7654321 T E D C B A O R 0 1.4. O PROBLEMA DO FLUXO MÁXIMO Contextualizando ... Considere uma rede de tubulações que transporte petróleo cru de poços de petróleo e refinarias. Estações intermediárias de impulsores auxiliares e de bombeamento são instalados a distâncias adequadas para transportar o petróleo cru pela rede. Cada segmento de tubulação tem uma taxa de descarga máxima finita (ou capacidade) de fluxo de petróleo cru. Um seguimento de tubulação pode ser unidirecional ou bidirecional, dependendo de seu projeto. Como podemos determinar a capacidade máxima da rede entre poços e refinarias? Formulação Matemática Aj)i, (,ux d,ok,xx Fx Fx :a sujeito FMax ijij m A)j,k( kj A)k,i( ik A)d,i( id A)j,o( oj Capacidade do arco (i,j) = uij Fluxo Máximo = F Quantidade Transportada no Arco (i,j) = xij Observação: quantidade transportada não pode ultrapassar a capacidade. 1.4.1. Algoritmo de Ford-Fulkerson Simplificado Etapas do Algoritmo Em cada arco coloque o rótulo (a, b) a – fluxo disponível no arco b – fluxo enviado pelo arco 1. Encontre um caminho da origem ao destino que ainda possua um fluxo disponível 2. Atualize os valores do par ordenado 3. Caso não encontre um caminho com fluxo disponível, pare, caso contrário volte a etapa 2. Exemplo: Profº Túlio de Almeida Pesquisa Operacional II 1.4.2. Algoritmo de Ford-Fulkerson O Algoritmo de Fluxo Máximo é baseado em achar rotas de passagem com fluxo positivo entre os nós de origem e o sorvedouro. Cada rota compromete parte ou toda a capacidade de seus arcos ao fluxo de rede. Considere o arco (i,j) inicialmente com capacidade (Cij, Cji). À medida que porções dessas capacidades são comprometidas ao fluxo do arco, as capacidades residuais (ou capacidades restantes) do arco são atualizadas. Usamos a notação (cij, cji) para representar essas capacidades residuais. Para um nó j que recebe fluxo do nó i, anexamos um rótulo [aj, i], no qual aj é o fluxo do nó i ao nó j. Etapas do Algoritmo Deve-se considerar um fluxo residual nos dois sentidos. Constrói-se um caminho aumentado: caminho da origem para o destino com fluxo residual estritamente positivo. 1. Encontre um caminho da origem ao destino que ainda possui fluxo residual positivo, caso não encontre, a solução é ótima 2. Determine a capacidade residual máxima desse caminho, subtraia da capacidade residual de cada arco e adicione a capacidade residual na direção oposta. Retorne ao passo 1. Exemplo: 1.5. BIBLIOGRAFIA E REFERÊNCIAS [1] TAHA, Hamdy. Pesquisa Operacional. 8ª Edição. São Paulo: Pearson Prentice Hall, 2008. [2] HILLIER, Frederick S. & LIEBERMAN, Gerald J. Introduction to Operations Research. 7th Edition. McGraw Hill. 2001. [3] MEZA, Lidia Angulo. Teoria dos Grafos com Algoritmo Ótimo de Fluxo Máximo. Universidade Federal Fluminense. Disciplina: Pesquisa Operacional II. 32 slides. 2010. [4] LACHTERMACHER, Gerson. Pesquisa Operacional na Tomada de Decisões. Modelagem em Excel. Rio de Janeiro: Elsevier, 2007.
Compartilhar