Teoria dos Grafos e Otimização em Redes - Conceitos e Aplicações

Otimização em Redes Teoria de Grafos Introdução à Teoria de Grafos Problema do Caminho Mínimo Ormeu Coelho da Silva Júnior DSc Departamento de Engenharia de Produção Revisão Breno dos Santos de Assis abr2018 CONCEITOS PRELIMINARES Em inúmeras aplicações 2 são facilitadas com a adoção diagramas CONCEITOS PRELIMINARES Em redes orientadas as ligações são chamadas arcos e possuem sentidos específicos para a movimentação dos fluxos por elas enquanto nas redes nãoorientadas as ligações são arestas através das quais a movimentação pode ocorrer em ambos sentidos O conjunto das arestas de um grafo é denotado usualmente por E do inglês edge e o conjunto de arcos por A arcs sendo o grafo denotado por G VE ou G VA Na construção de modelos a partir de grafos não raro é necessário associar valores a seus nós eou ligações Temse assim grafos valorados ou nãovalorados sendo os primeiros muitas vezes denominados de rede As Figuras 1 e 2 ilustram respectivamente um grafo nãoorientado nãodirecionado e outro orientado EXEMPLOS DAS DEFINIÇÕES ANTERIORES G VE G VA Figura 1 Grafo a nãoorientado e b grafo orientado Fonte Arenales et al 2007 ALGUMAS DEFINIÇÕES Caminho Um caminho de um nó i a um nó i é uma sequência de arcos na qual o nó inicial de cada arco à exceção de i é o nó final do arco imediatamente anterior Cadeia É uma estrutura similar ao caminho com a diferença de que os arcos não precisam estar orientadas à medida que ela é percorrida de i a i Circuito É um caminho fechado isto é que tem os mesmos nós inicial e final Ciclo Analogamente um ciclo é uma cadeia fechada Grafos conexos Existe uma cadeia talvez caminho entre cada para de vértices ALGUMAS DEFINIÇÕES Árvore É 6 EXEMPLOS DAS DEFINIÇÕES ANTERIORES Figura 3 Árvores geradoras para o grafo da figura 2 Fonte Arenales et al 2007 Os subgrafos a e c são apenas cadeias no grafo da Figura 2 enquanto b é um caminho 3 1 4 2 a 3 1 4 2 b 3 1 4 2 c 7 EXEMPLOS DAS DEFINIÇÕES ANTERIORES Figura 4 Subgrafos que não são árvores geradoras para o grafo da figura 2 e desconexos 3 1 4 2 3 1 4 2 8 ESTRUTURAS DE DADOS PARA REPRESENTAÇÃO DE GRAFOS Para que se possa programar os modelos de redes em um computador é preciso usar estruturas de dados que reflitam a estrutura e os valores associados às redes A representação matricial de grafos é talvez a forma mais direta entretanto menos eficiente de se representar as relações denotadas por um grafo Neste sentido as estruturas mais comuns são Matriz de adjacência uma relação de nó para nó Matriz de incidência uma relação de nó para arestaarco Lista de encadeadas 9 ESTRUTURAS DE DADOS PARA REPRESENTAÇÃO DE GRAFOS Exemplo2 Matriz de incidência para os grafos das figuras 1 e 2 Matriz de adjacência para o grafo da Figura 1 Matriz de adjacência para o grafo da Figura 2 ESTRUTURAS DE DADOS PARA REPRESENTAÇÃO DE GRAFOS Exemplo1 Matriz de adjacência para os grafos das figuras 1 e 2 Matriz de adjacência para o grafo da Figura 1 Matriz de adjacência para o grafo da Figura 2 ESTRUTURAS DE DADOS PARA REPRESENTAÇÃO DE GRAFOS Existem outras estruturas de dados mais sofisticadas e que devem ser levadas em consideração para uma implementação eficiente dos algoritmos de Otimização em Redes Por exemplo o uso de listas encadeadas para cada vértice Via de regra com estruturas de dados mais elaboradas é possível reduzir significativamente o esforço de processamento e a memória requerida Nas referências bibliográficas ao final desta aula é possível obter uma descrição geral de algumas estruturas comumente usadas 12 OTIMIZAÇÃO EM REDES O uso de um grafo ou uma rede como suporte à modelagem é ainda mais importante no estudo dos problemas de Otimização em Redes nos quais fluxos produtos pessoas energia etc circulam em uma rede segundo regras de conservação Inúmeras aplicações relevantes em Engenharia são assim modeladas Projeto de redes de dutos que conectam poços e plataformas na exploração offshore de Petróleo e Gás Natural Determinação do caminho mais curto entre pares de pontos cidades ou endereços em uma rede de transporte Determinação da capacidade máxima de transporte de fluídos em redes de dutos com capacidade limitada Planejamento dos fluxos de produtos que minimizam o custo de transporte em uma rede composta de fábricas armazéns e lojas de clientes 13 OTIMIZAÇÃO EM REDES Nesta aula serão apresentados quatro problemas clássicos de Otimização em Redes assim como alguns algoritmos para resolvêlos Problema dá Árvore Geradora de Peso Mínimo Problema do Caminho Mínimo Problema do Fluxo Máximo Problema do Fluxo de Custo Mínimo Também serão estudos algoritmos para resolver os três primeiros problemas acima citados Mais precisamente serão apresentados algoritmos exatos e eficientes para resolvêlos Por exatos entendase que os mesmos convergem para uma solução ótima em um número finito de iterações 14 OTIMIZAÇÃO EM REDES Algoritmos eficientes são aqueles capazes de convergir para uma solução ótima em tempo polinomial Ou equivalentemente que requerem um número de iterações polinomial em função dos dados de entrada A existência de ao menos um algoritmo eficiente para um dado problema permite considerálo bem resolvido O estudo da Complexidade de Algoritmos divide os problema de decisão e consequentemente suas versões de otimização em Classes de Complexidade Problemas bem resolvidos pertencem à Classe P ao passo que a ampla maioria dos problemas de Programação Inteira e de Programação Não Linear pertencem à Classe NPdifícil Mais à frente neste curso será feita uma caracterização mais precisa destas classes de problemas Por enquanto apenas aceite que estão entre os mais difíceis problemas em matemática 15 OTIMIZAÇÃO EM REDES Nesta e na próxima aula você verá algoritmos eficientes para os três primeiros problemas mencionados no slide anterior A saber Algoritmo de Kruskal para o Problema da Árvore Geradora de Peso Mínimo Algoritmos de Dijkstra e Floyd para o Problema da Caminho Mínimo Algoritmo de FordFulkerson para o Problema do Fluxo Máximo Cabe observar porém que existem outros algoritmos eficientes para resolver estes problemas Mas seu estudo pode ser considerado objeto de um curso mais aprofundado em problemas de Otimização em Redes 16 PROBLEMA DE CAMINHO MÍNIMO Problemas do Caminho consistem na determinação de caminhos entre pares de vértices que caracterizam origens e destinos em uma rede G VA segundo algum critério de otimização Dentre estes problemas o mais largamente conhecido é o Problema de Caminho Mínimo que consiste em encontrar um caminho entre um dado par de vértices r origem e s destino cuja soma dos pesos dos arcos eou arestas usados seja mínima Em Engenharia de Produção as aplicações mais conhecidas do Problema do Caminho Mínimo provêm da área de Logística onde é usado na modelagem ou no tratamento dos dados de entrada de problemas de distribuição de bens físicos e nos estudos de localização de facilidades Nas redes destes problemas em geral os arcos e arestas da rede representam as distâncias os tempos de deslocamento ou os custoslucros incorridos para percorrêlas 17 PROBLEMA DE CAMINHO MÍNIMO Entretanto não são raras as aplicações nas quais os valores das ligações têm outras interpretações físicas como por exemplo em problemas de dimensionamento de lotes ou na determinação de pontos de inspeção em um processo produtivo com vários estágios Também é praxe procurar os caminhos mínimos entre todos os pares de vértices de uma rede Isto é necessário em problemas de localização nos quais ainda não sabemos onde serão posicionadas as facilidades que posteriormente enviarão ou receberão fluxo de outros vértices da rede Em problemas de roteamento de veículos é preciso que se conheçam todos os pares de caminhos mínimos na rede pois ainda não se conhece as sequências de visitas que serão executadas 18 PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO ALGÉBRICA GERAL Conjuntos V conjunto de vértices da rede A conjunto de arcos Parâmetros Cij distância percorrida tempo de viagem através do arco ij r vértice de origem s vértice de destino Variáveis de decisão xij 1 se o arco ij pertence ao caminho mínimo 0 caso contrário 19 PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO ALGÉBRICA GERAL min sa 1 se nódeorigem 1 se nódedestino 0 se nódetransbordo 01 ij ij i j A ij ji j i j A j j i A ij z C x i r x x i s i V i t x i j A Formulação matemática 20 Soma dos fluxos que saem do vértice i Soma dos fluxos que entram no vértice i PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO ALGÉBRICA GERAL As restrições do problema definem uma regra de conservação do fluxo através da rede similar à Lei de Kirchoff das correntes Em um circuito elétrico com resistores em série eou em paralelo a soma dos fluxos que convergem para um nó deve ser igual a soma dos fluxos que dele saem Ou seja existe conservação total da carga No vértice de origem i r a soma dos possíveis fluxos de saída deve ser igual a 1 Ou seja uma unidade de fluxo deverá obrigatoriamente se deslocar por exatamente um dos arcos de saída existentes Condição análoga existe para o vértice de destino i s no qual a soma dos fluxos de entrada deve ser igual a 1 Nos demais vértices vale a mesma lei de conservação isto é a soma dos fluxos de saída é igual a soma dos fluxos de entrada Nos vértices que pertencerem ao caminho de comprimento mínimo ambas são iguais a 1 e nos demais são iguais a 0 21 PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO ALGÉBRICA GERAL Exemplo3 Um serviço de entrega expressa precisa transportar uma encomenda entre a loja do contratante e o endereço de um cliente indicados respectivamente pelos vértices 0 e 10 na rede da Figura 5 Os arcos indicam vias de mão única e seus valores os tempos esperados de deslocamento através deles Apresente uma formulação de Programação Inteira para determinar o caminho que minimiza o tempo de entrega 22 Loja 1 2 3 4 5 6 7 8 9 Cliente 15 25 10 20 25 5 8 8 5 7 15 15 2 10 2 7 0 10 Figura 5 Rede orientada representativa do exemplo3 Fonte Goldbarg Luna 2005 PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO ALGÉBRICA GERAL Resolução Seja o grafo G V A o grafo orientado e valorado do enunciado tal que V 01210 é o conjunto de seus vértices e A 01 02 13 14 910 o conjunto de seus arcos Variáveis de decisão Formulação matemática min z 25x01 15x02 10x13 5x14 25x23 20x24 7x35 5x36 8x46 8x47 2x58 10x68 15x69 15x79 2x810 7x910 sujeito a PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO ALGÉBRICA GERAL Resolução x₀₁ x₀₂ 1 x₀₁ x₁₃ x₁₄ 0 x₀₂ x₂₃ x₂₄ 0 x₁₃ x₂₃ x₃₅ x₃₆ 0 x₁₄ x₂₄ x₄₆ x₄₇ 0 x₃₅ x₅₈ 0 x₃₆ x₄₆ x₆₈ x₆₉ 0 x₄₇ x₇₉ 0 x₅₈ x₆₈ x₈₁₀ 0 x₆₉ x₇₉ x₉₁₀ 0 x₈₁₀ x₉₁₀ 1 xᵢⱼ 01 ij A PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO MATEMÁTICA Conforme se comentou nas primeiras partes desta aula existem algoritmos eficientes para otimizar o Problema do Caminho Mínimo Mas há outra propriedade que torna sua solução fácil a presença da unimodularidade1 Nos Problemas de Programação Inteira com esta propriedade se todos os termos independentes forem inteiros todas as bases viáveis ou seja todos os vértices da região viável da RPL corresponderão a soluções inteiras E desta forma a solução ótima da RPL também será inteira Logo ao invés de usar um método para Programação Inteira como o método Branch andBound podese usar um método eficiente para Programação Linear como alguns algoritmos de Pontos Interiores capazes de resolver PPLs em tempo polinomial Também é possível usar o método Simplex mas seu desempenho de pior caso é exponencial Na média entretanto é bastante satisfatório 25 1 Esta propriedade será discutida mais à frente através de uma nota de aula complementar PROBLEMA DO CAMINHO MÍNIMO FORMULAÇÃO MATEMÁTICA Também se pode demonstrar que as restrições usadas na formulação matemática aqui apresentada para o Problema do Caminho Mínimo definem a casca convexa do conjunto de soluções inteiras Ou seja temse uma descrição polinomial da casca convexa ao passo que na maioria dos PPIs o número de restrições a serem separadas para definir sua casca convexa é exponencial inviabilizando sua obtenção de forma eficiente 26 ALGORITMOS EFICIENTES PARA PROBLEMA DO CAMINHO MÍNIMO Algoritmos de tempo polinomial para o Problema do Caminho Mínimo Algoritmo de Dijkstra On2 Premissa Cij 0 Algoritmo de Ford Omn Premissa Inexistência de circuitos de custo negativo mas é capaz de detectálos caso existam Algoritmo de Floyd On3 Premissa Inexistência de circuitos de custo negativo mas é capaz de detectálos caso existam e enumerálos 27 ALGORITMO DE DIJKSTRA Suponha por simplicidade que r 1 e s n A estratégia deste algoritmo é determinar a cada iteração k k 1n o késimo nó mais próximo da origem o nó r 1 Em outras palavras na iteração 1 se determina o primeiro nó mais próximo de 1 na iteração 2 o segundo mais próximo e assim sucessivamente até que o nó de destino r n seja alcançado Suponha que numa dada iteração k os k1 nós mais próximos de 1 já tenham sido determinados e que se deseja determinar agora o késimo nó mais próximo Suponha ainda que este é o nó t 28 ALGORITMO DE DIJKSTRA O caminho que leva a este nó passa por um dos k1 nós mais próximos já determinados ou vai direto de 1 a t através do arco 1t caso este exista Se o caminho passasse por qualquer um dos demais nós o nó t não seria o késimo mais próximo como se assumiu por hipótese A Figura 6 ilustra este argumento Vêse que se o caminho passasse por um nó p diferente dos k1 mais próximos ele seria o késimo no mais próximo e não o nó t Por consequência o caminho deve passar por um dos k1 nós mais próximos ou vai direto de 1 a t através do arco 1t 1 p t Caminho de 1 a p Caminho de p a t 29 Figura 6 Ilustração do argumento anterior Fonte Arenales et al 2007 ALGORITMO DIJKSTRA R conjunto de nós rotulados NR conjunto de nós não rotulados pi predecessor do nó i di distância de 1 até i PASSO 1 Iniciando o algoritmo R 1 NR 2n d1 0 p1 0 para i NR faça di pi n1 ultimo 1 fimpara k 1 PASSO 2 seleção do késimo nó mais próximo de 1 para i NR faça se di dultimo Cultimo i então di dultimo Cultimo i pi ultimo fimse fimpara se di para todo i NR então PARE o grafo é desconexo e não existe caminho entre os vértices em R e aqueles em NR senão dk miniNRdi NR NR k R R U k ultimo k fimse k k 1 PASSO 3 teste de parada se ultimo n então recupere a rota ótima k1pn k2pk1 k3pk2 até atingir a origem o nó 1 senão volte ao PASSO 2 fimse 30 ALGORITMO DE DIJKSTRA Exemplo4 Encontre o caminho mínimo entre os vértices 1 e 6 na rede da Figura 2 utilizando o algoritmo de Dijkstra c₁₂5 c₂₄2 c₄₆3 c₁₄10 c₂₅2 c₄₅1 c₁₃4 c₂₃2 c₅₆2 c₃₅5 Figura 7 Rede do exemplo 4 ALGORITMO DE DIJKSTRA Passo 1 R 1 NR 2 3 4 5 6 d1 0 p1 0 di para todo i em NR pi 7 para todo i em NR ultimo 1 Passo 2 k 1 1ª iteração d2 min 05 5 p2 1 d3 min 04 4 p3 1 d4 min 010 10 p4 1 d5 d6 NR 2 4 5 6 R 1 3 ultimo 3 Passo 3 Nodo 6 ainda não rotulado Retorne ao Passo 2 32 ALGORITMO DE DIJKSTRA Passo 2 k 2 2ª iteração d2 5 d4 10 d5 min 4 5 9 p5 3 d6 NR 4 5 6 R 1 2 3 ultimo 2 Passo 3 Nodo 6 ainda não rotulado Retorne ao Passo 2 Passo 2 k 3 3ª iteração d4 min10 5 2 7 p4 2 d5 min9 5 2 7 p5 2 d6 NR 4 6 R 1 2 3 5 ultimo 5 Passo 3 Nodo 6 ainda não rotulado Retorne ao Passo 2 33 ALGORITMO DE DIJKSTRA Passo 2 k 3 3ª iteração d4 7 d6 min 7 2 9 p6 5 NR 6 R 1 2 3 4 5 ultimo 4 Passo 3 Nodo 6 ainda não rotulado Retorne ao Passo 2 Passo 2 k 4 4ª iteração d6 9 NR R 1 2 3 4 5 6 ultimo 6 Passo 3 Nodo 6 rotulado Recuperando o caminho p6 5 p5 2 p2 1 O caminho mínimo do nó 1 ao nó 6 é C 122556 cujo valor é 9 34 ALGORITMO DE DIJKSTRA Na Figura Encontre o caminho mínimo entre r 5 e s 2 no grafo abaixo utilizando o algoritmo de Dijkstra c₁₂5 c₂₄2 c₄₆3 c₁₄10 c₂₅2 c₄₅1 c₁₃4 c₂₃2 c₅₆2 c₃₅5 Figura 8 Caminho mínimo entre 1 e 6 na rede do exemplo 2 ALGORITMO DE DIJKSTRA Se houver empates escolhese aleatoriamente o próximo nodo a rotular e aqueles que forem preteridos serão escolhidos nas próximas iterações No exemplo 2 o empate entre os nodos 4 e 5 para escolha do 3º nó mais próximo foi quebrado em favor do nó 5 E por que o algoritmo falha na presença de custos negativos Vejamos o exemplo apresentado por Arenales et al 2007 que consiste na determinação de um caminho mínimo entre 5 e 2 na rede da Figura 9 1 2 3 4 6 5 5 10 4 7 5 1 2 3 2 4 36 Figura 9 Falha do algoritmo de Dijkstra na presença de arcos negativos Fonte Arenales et al 2007 ALGORITMO DE DIJKSTRA Na segunda iteração do algoritmo de Dijkstra o nó 4 seria rotulado e não mais avaliado com distância d4 5 e p4 6 Entretanto é fácil notar que o caminho ótimo até 4 é 534 cujo comprimento é d4 3 sendo p4 3 O algoritmo de Ford é desenhado para contornar esta falha através da reavaliação a cada iteração de todos os nós Inclusive os já rotulados Por limitações de tempo este algoritmo não será apresentado no presente curso assim como o algoritmo de Floyd usado da determinação dos caminhos mínimos entre todos os pares de vértices de uma rede Sugerese como leitura complementar a descrição destes algoritmos na bibliografia indicada ao final desta aula 37 BIBLIOGRAFIA ARENALES M et al Pesquisa Operacional para Cursos de Engenharia Rio de Janeiro Elsevier 2007 GOLDBARG MC e LUNA HP Otimização Combinatória e Programação Linear Rio de Janeiro Elsevier 2005 TAHA HA Pesquisa Operacional 8 ed São Paulo Pearson Prentice Hall 2008 WOLSEY LA Integer Programming New York John Wiley Sons 1998 38