Exercício Otimização de Redes

UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 1 EXERCÍCIOS DE OTIMIZAÇÃO EM REDES 1) Resolva o seguinte problema de custo mínimo, indicando qual algoritmo deve ser utilizado: Algoritmo utilizado: FLOYD . (é o algoritmo que permite fluxo negativo) D(0 ) 1 2 3 4 1 -- - 6 5 in f 2 in f -- - -2 in f 3 in f in f -- - 2 4 in f in f in f -- - P(0 ) 1 2 3 4 1 0 1 1 0 2 0 0 2 0 3 0 0 0 3 4 0 0 0 0 D(1 ) 1 2 3 4 1 -- - 6 5 in f 2 in f -- - -2 in f 3 in f in f -- - 2 4 in f in f in f -- - P(1 ) 1 2 3 4 1 0 1 1 1 2 0 0 2 0 3 0 0 0 3 4 0 0 0 0 D(1 ) 1 2 3 4 1 -- 6 4 in P(1 ) 1 2 3 4 1 0 1 2 1 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 2 - f 2 in f -- - -2 in f 3 in f in f -- - 2 4 in f in f in f -- - 2 0 0 2 0 3 0 0 0 3 4 0 0 0 0 D(1 ) 1 2 3 4 1 -- - 6 4 6 2 in f -- - -2 0 3 in f in f -- - 2 4 in f in f in f -- - P(1 ) 1 2 3 4 1 0 1 2 3 2 0 0 2 3 3 0 0 0 3 4 0 0 0 0 D(1 ) 1 2 3 4 1 -- - 6 4 2 2 in f -- - -2 0 3 in f in f -- - 2 4 in f in f in f -- - P(1 ) 1 2 3 4 1 0 1 2 3 2 0 0 2 3 3 0 0 0 3 4 0 0 0 0 2) Resolva o problema de fluxo máximo, apresentando a rede de fluxo e a rede residual. Considere o nó 1 como a fonte e o nó 5 como o destino do fluxo: UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 3 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 4 3) Resolva o problema de fluxo máximo (O é fonte e T é destino): Resultado: 4) Resolva por: a) Djikstra (início no nó a) UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 5 b) Prim (nó inicial: a) c) Kruskal 5) Resolva por: UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 6 a) Floyd b) Dijkstra (a) c) Prim d) Kruskal 6) Determine os caminhos mais curtos (via algoritmo de Floyd) entre todos os nós. (Em cada aresta está indicada a distância) 7) Resolva o problema de fluxo máximo do nó fonte F até o nó S. 8) Seja a matriz de distâncias entre as cidades A, B, C e D, onde ∞ indica que não há ligação direta. A=(0 4 ∞750∞1811∞0610230) a) Represente o grafo da matriz A. b) Determine as rotas mais curtas entre todas as cidades (Algoritmo de Floyd). c) Qual o caminho mais curto de B até C? Extraia o caminho do resultado do item b 9) Três meninos, Alberto, Bruno e Carlos, participarão de uma corrida. Cada um deles parte de um ponto diferente, mas todos devem terminar no mesmo ponto N. Alberto começa no ponto A, Bruno no ponto B e Carlos no ponto C. O diagrama a seguir mostra a rede de ruas que eles podem percorrer. Os números nos arcos representam o tempo (em segundos), necessários para percorrer cada rua. UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 7 Use o algoritmo de Dijkstra para determinar a rota a ser percorrida pelo menino que primeiro vai chegar no ponto N. Mostre todo o seu trabalho em cada vértice. 10) Determine o caminho mais curto entre A e I. 11) Seja a Rede a) Considere os números em cada aresta como sendo distâncias. Encontre a árvore geradora mínima para a rede. Sua resposta deve identificar a árvore geradora mínima e seu custo. Você deve explicar o método usado para encontrar a solução. b) Suponha agora que os números em cada aresta sejam as capacidades máximas que podem ser transportadas ao longo das arestas. Determine o fluxo máximo do nó 0 até o nó 8. 12) Encontre a árvore geradora mínima (fixe o nó A como raiz da árvore). 13) Dado o grafo (em cada aresta está indicada a distância) UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 8 a) Use o algoritmo de Prim para determinar a árvore geradora mínima (MST) do grafo b) Use o algoritmo de Kurskal para determinar a árvore geradora mínima (MST) do grafo 14) Dado o grafo abaixo, resolva o problema do caixeiro viajante-TSP via algoritmo de Christofides. Considere que o caixeiro sai do nó central. Árvore geradora mínima Identificar vértices de grau ímpar Realizar matching perfeito União árvore e matching Exclusão de arestas (A,D) e (C,A) UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 9 15) Partindo do nó 6, resolva o grafo G pelo algoritmo de Christofides. Árvore geradora mínima T obtida a partir de G. Destacar nós de grau ímpar. Matching perfeito de custo mínimo. União das arestas da árvore geradora mínima e do casamento perfeito mínimo. Exclusão da aresta (1,6) e de uma das arestas (6,3) e adição da aresta “shortcut” (1,3) 16) Resolva o problema do caixeiro viajante-TSP via algoritmo de Christofides. Considere que o caixeiro sai do nó 1. 17) Sejam 10 nós com demanda. Seja o problema de roteamento de veículos-VRP de definir veículos e rotas para atender as demandas. Cada veículo tem capacidade de 4 unidades. São dadas as coordenadas geográficas (x, y), a matriz de distâncias (dij) e a matriz de savings (sij). Os veículos saem da origem 0. Resolva o VRP via algoritmo de Clarke e Wright. UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 10 N ó 0 1 2 3 4 5 6 7 8 9 1 0 x 3 5 6 8 1 0 0 1 4 7 8 y 6 1 0 8 7 1 0 8 2 5 3 1 4 demanda 0 2 1 1 2 1 1 2 1 1 2 dij 0 1 2 3 4 5 6 7 8 9 1 0 sij 0 1 2 3 4 5 6 7 8 9 1 0 0 0, 0 4, 5 3, 6 5, 1 4,5 3, 6 5, 0 2, 2 3, 2 6,4 5, 4 0 --- --- --- --- --- --- --- --- --- --- --- 1 4, 5 0, 0 2, 2 4, 2 4,0 5, 4 9, 4 6, 4 7, 1 9,2 6, 7 1 --- --- 5, 8 5, 3 4, 9 2, 7 0, 0 0, 3 0, 6 1, 7 3, 1 2 3, 6 2, 2 0, 0 2, 2 5,4 6, 0 8, 5 5, 8 5, 4 7,1 4, 5 2 --- 5, 8 --- 6, 5 2, 7 1, 2 0, 1 0, 0 1, 4 2, 9 4, 5 3 5, 1 4, 2 2, 2 0, 0 7,6 8, 1 9, 4 7, 3 5, 7 6,1 3, 0 3 --- 5, 3 6, 5 --- 2, 0 0, 6 0, 7 0, 1 2, 6 5, 4 7, 5 4 4, 5 4, 0 5, 4 7, 6 0,0 2, 2 8, 1 5, 0 7, 6 10, 8 9, 2 4 --- 4, 9 2, 7 2, 0 --- 5, 8 1, 4 1, 7 0, 0 0, 1 0, 6 5 3, 6 5, 4 6, 0 8, 1 2,2 0, 0 6, 0 3, 2 6, 4 9,9 8, 9 5 --- 2, 7 1, 2 0, 6 5, 8 --- 2, 6 2, 7 0, 4 0, 1 0, 0 6 5, 0 9, 4 8, 5 9, 4 8,1 6, 0 0, 0 3, 2 4, 1 7,1 8, 2 6 --- 0, 0 0, 1 0, 7 1, 4 2, 6 --- 4, 1 4, 0 4, 3 2, 1 7 2, 2 6, 4 5, 8 7, 3 5,0 3, 2 3, 2 0, 0 3, 6 7,2 7, 1 7 --- 0, 3 0, 0 0, 1 1, 7 2, 7 4, 1 --- 1, 8 1, 4 0, 6 8 3, 2 7, 1 5, 4 5, 7 7,6 6, 4 4, 1 3, 6 0, 0 3,6 4, 1 8 --- 0, 6 1, 4 2, 6 0, 0 0, 4 4, 0 1, 8 --- 6, 0 4, 4 9 6, 4 9, 2 7, 1 6, 1 10, 8 9, 9 7, 1 7, 2 3, 6 0,0 3, 2 9 --- 1, 7 2, 9 5, 4 0, 1 0, 1 4, 3 1, 4 6, 0 --- 8, 6 1 0 5, 4 6, 7 4, 5 3, 0 9,2 8, 9 8, 2 7, 1 4, 1 3,2 0, 0 1 0 --- 3, 1 4, 5 7, 5 0, 6 0, 0 2, 1 0, 6 4, 4 8, 6 --- 18) Um agente de saúde contratado por uma prefeitura precisa visitar 4 moradores que residem no mesmo município. Ele sai de casa (vértice A) visita os 4 munícipes (em qualquer ordem) e retorna para a casa dele (vértice A) no final do dia. O grafo abaixo mostra as distâncias (em quilômetros) entre as 5 residências. Determine, via algoritmo de Clarke-Wright, o trajeto ótimo para este problema do caixeiro viajante (TSP) que dê o menor custo (em quilômetros). 19) Uma empresa vai visitar os clientes em uma cidade formada por quadras retangulares idênticas. Um diagrama da cidade é mostrado na Figura abaixo, com a localização da empresa marcada em preto (W) e os locais a serem visitados em azul. UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 11 Quadro 1: Distâncias (em quadras) dij A B C D E F G H I J K L M N O P W A --- 6 3 2 5 7 4 7 8 11 7 6 8 11 10 13 6 B 6 --- 9 8 5 3 8 5 8 5 13 12 12 9 16 9 8 C 3 9 --- 1 6 8 5 8 9 12 6 7 9 12 7 14 7 D 2 8 1 --- 5 7 4 7 8 11 5 6 8 11 8 13 6 E 5 5 6 5 --- 2 3 2 3 6 8 7 7 6 11 8 3 F 7 3 8 7 2 --- 5 2 5 4 10 9 9 6 13 6 5 G 4 8 5 4 3 5 --- 3 4 7 5 4 4 7 8 9 2 H 7 5 8 7 2 2 3 --- 3 4 8 7 7 4 11 6 3 I 8 8 9 8 3 5 4 3 --- 3 5 4 4 3 8 5 2 J 11 5 12 11 6 4 7 4 3 --- 8 7 7 4 11 4 5 K 7 13 6 5 8 10 5 8 5 8 --- 1 3 6 3 8 5 L 6 12 7 6 7 9 4 7 4 7 1 --- 2 5 4 7 4 M 8 12 9 8 7 9 4 7 4 7 3 2 --- 3 4 5 4 N 11 9 12 11 6 6 7 4 3 4 6 5 3 --- 7 2 5 O 10 16 7 8 11 13 8 11 8 11 3 4 4 7 --- 7 8 P 13 9 14 13 8 6 9 6 5 4 8 7 5 2 7 --- 7 W 6 8 7 6 3 5 2 3 2 5 5 4 4 5 8 7 --- Obs: temos um grafo completo não orientado Quadro 2: Savings sij A B C D E F G H I J K L M N O P A --- 8 10 10 4 4 4 2 0 0 4 4 2 0 4 0 B --- --- 6 6 6 10 2 6 2 8 0 0 0 4 0 6 C --- --- --- 12 4 4 4 2 0 0 6 4 2 0 8 0 D --- --- --- --- 4 4 4 2 0 0 6 4 2 0 6 0 E --- --- --- --- 6 2 4 2 2 0 0 0 2 0 2 F --- --- --- --- --- --- 2 6 2 6 0 0 0 4 0 6 G --- --- --- --- --- --- --- 2 0 0 2 2 2 0 2 0 H --- --- --- --- --- --- --- --- 2 4 0 0 0 4 0 4 I --- --- --- --- --- --- --- --- --- 4 2 2 2 4 2 4 J --- --- --- --- --- --- --- --- --- --- 2 2 2 6 2 8 K --- --- --- --- --- --- --- --- --- --- --- 8 6 4 10 4 L --- --- --- --- --- --- --- --- --- --- --- --- 6 4 8 4 M --- --- --- --- --- --- --- --- --- --- --- --- --- 6 8 6 N --- --- --- --- --- --- --- --- --- --- --- --- --- 6 10 O --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 8 P --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- a) Considere o algoritmo de Clark e Wright. Mostre os cálculos do saving sko e explique-o detalhadamente b) Execute as 10 primeiras iterações do algoritmo de Clark e Wright. Escolha o saving (em ordem decrescente) por linha da esquerda para a direita e de baixo para cima conforme constam no UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 12 Quadro 2. Se ocorrer empate na escolha do saving utilize o primeiro da lista que você encontrou. Mostre seus cálculos de forma bem objetiva. c) Represente graficamente (na Figura acima) todas as sub-rotas resultantes após concluída a iteração 10. 20) Seja o problema de Roteamento do Veículos com origem no nó 1, cuja distâncias e demandas são: Suponha que os veículos a serem despachados possuem capacidade de carga 14 unidades. Utilize o algoritmo de Clarke e Wright e determine o(s) roteiro(s) do(s) veículo(s) para atender a demanda de todos os 5 clientes. 21) O algoritmo da inserção mais barata consiste em construir uma rota partindo de um rota inicial, e a cada passo inserir um nó ainda não visitado entre uma aresta que já faz parte da rota cujo custo de inserção seja o mais barato dentre todas as arestas da rota já construída. 1. Seja o nó k não pertencente à rota atual. 2. Encontre as arestas (i,k ) e (k , j) tal que {cik+ckj−cij} seja mínimo considerando todas as arestas (i, j) da rota. 3. Insira o nó k entre i e j, ou seja, ative as arestas (i,k ) e (k , j) e desative a aresta (i, j). Neste instante teremos uma rota atualizada. 4. Se todos os nós foram adicionados à rota, pare, caso contrário volte ao Passo 1. Sejam as distâncias abaixo e o caminho inicial gerado pelo método Convex Hull. Construa o caminho do caixeiro viajante-TSP usando o algoritmo da inserção mais barata. Mostre seus cálculos. (Falta incluir 2 nós na rota TSP)