Exercícios Resolvidos de Otimização em Redes - Fluxo Máximo, Custo Mínimo e Caminhos Mais Curtos

Universidade Federal do Paraná Departamento de Engenharia de Produção Tecnologia da Decisão II Prof Volmir Eugênio Wilhelm EXERCÍCIOS DE OTIMIZAÇÃO EM REDES Resolva o seguinte problema de custo mínimo indicando qual algoritmo deve ser utilizado Algoritmo utilizado FLOYD é o algoritmo que permite fluxo negativo D0 1 2 3 4 1 6 5 inf 2 inf 2 inf 3 inf inf 2 4 inf inf inf P0 1 2 3 4 1 0 1 1 0 2 0 0 2 0 3 0 0 0 3 4 0 0 0 0 D1 1 2 3 4 1 6 5 inf 2 inf 2 inf 3 inf inf 2 4 inf inf inf P1 1 2 3 4 1 0 1 1 1 2 0 0 2 0 3 0 0 0 3 4 0 0 0 0 D1 1 2 3 4 1 6 4 inf 2 inf 2 inf 3 inf inf 2 4 inf inf inf P1 1 2 3 4 1 0 1 2 1 2 0 0 2 0 3 0 0 0 3 4 0 0 0 0 D1 1 2 3 4 1 6 4 6 2 inf 2 0 3 inf inf 2 4 inf inf inf P1 1 2 3 4 1 0 1 2 3 2 0 0 2 3 3 0 0 0 3 4 0 0 0 0 D1 1 2 3 4 1 6 4 2 2 inf 2 0 3 inf inf 2 4 inf inf inf P1 1 2 3 4 1 0 1 2 3 2 0 0 2 3 3 0 0 0 3 4 0 0 0 0 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 Resolva o problema de fluxo máximo O é fonte e T é destino Resultado Resolva por Djikstra início no nó a Prim nó inicial a Kruskal Resolva por Floy d Dijkstra a Prim Kruskal s Determine os caminhos mais curtos via algoritmo de Floyd entre todos os nós Em cada aresta está indicada a distância Resolva o problema de fluxo máximo do nó fonte F até o nó S 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 7 5 0 18 11 0 6 10 2 3 0 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 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 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 Determine o caminho mais curto entre A e I Seja a Rede 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 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 Encontre a árvore geradora mínima fixe o nó A como raiz da árvore Dado o grafo em cada aresta está indicada a distância Use o algoritmo de Prim para determinar a árvore geradora mínima MST do grafo Use o algoritmo de Kurskal para determinar a árvore geradora mínima MST do grafo Dado o grafo abaixo resolva o problema do caixeiro viajanteTSP 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 AD e CA 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 16 e de uma das arestas 63 e adição da aresta shortcut 13 Resolva o problema do caixeiro viajanteTSP via algoritmo de Christofides Considere que o caixeiro sai do nó 1 Sejam 10 nós com demanda Seja o problema de roteamento de veículosVRP 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 Nó 0 1 2 3 4 5 6 7 8 9 10 x 3 5 6 8 1 0 0 1 4 7 8 y 6 10 8 7 10 8 2 5 3 1 4 demanda 0 2 1 1 2 1 1 2 1 1 2 d ij 0 1 2 3 4 5 6 7 8 9 10 s ij 0 1 2 3 4 5 6 7 8 9 10 0 00 45 36 51 45 36 50 22 32 64 54 0 1 45 00 22 42 40 54 94 64 71 92 67 1 58 53 49 27 00 03 06 17 31 2 36 22 00 22 54 60 85 58 54 71 45 2 58 65 27 12 01 00 14 29 45 3 51 42 22 00 76 81 94 73 57 61 30 3 53 65 20 06 07 01 26 54 75 4 45 40 54 76 00 22 81 50 76 108 92 4 49 27 20 58 14 17 00 01 06 5 36 54 60 81 22 00 60 32 64 99 89 5 27 12 06 58 26 27 04 01 00 6 50 94 85 94 81 60 00 32 41 71 82 6 00 01 07 14 26 41 40 43 21 7 22 64 58 73 50 32 32 00 36 72 71 7 03 00 01 17 27 41 18 14 06 8 32 71 54 57 76 64 41 36 00 36 41 8 06 14 26 00 04 40 18 60 44 9 64 92 71 61 108 99 71 72 36 00 32 9 17 29 54 01 01 43 14 60 86 10 54 67 45 30 92 89 82 71 41 32 00 10 31 45 75 06 00 21 06 44 86 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 ClarkeWright o trajeto ótimo para este problema do caixeiro viajante TSP que dê o menor custo em quilômetros 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 Quadro 1 Distâncias em quadras d ij 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 s ij 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 Considere o algoritmo de Clark e Wright Mostre os cálculos do saving s ko e expliqueo detalhadamente 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 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 Represente graficamente na Figura acima todas as subrotas resultantes após concluída a iteração 10 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 os roteiros dos veículos para atender a demanda de todos os 5 clientes 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 Seja o nó k não pertencente à rota atual Encontre as arestas ik e kj tal que c ik c kj c ij seja mínimo considerando todas as arestas i j da rota Insira o nó k entre i e j ou seja ative as arestas ik e kj e desative a aresta ij Neste instante teremos uma rota atualizada 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 viajanteTSP usando o algoritmo da inserção mais barata Mostre seus cálculos Falta incluir 2 nós na rota TSP