Pesquisa Operacional: Algoritmos e Modelos de Fluxo em Redes

PESQUISA OPERACIONAL Organizador Rodrigo Rodrigues Catalogação na publicação Poliana Sanchez de Araujo CRB 102094 R696p Rodrigues Rodrigo Pesquisa operacional Rodrigo Rodrigues Porto Alegre SAGAH 2017 121 p il 225 cm ISBN 9788595020047 1 Pesquisa operacional Engenharia de produção I Título CDU 6585 ss39898 OOOO OU NIDADE Objetivos de aprendizagem Ao final deste texto vocé deve apresentar os seguintes aprendizados Definir a terminologia das redes M Descrever modelos de fluxo em redes em diversas aplicagdes M Resolver problemas classicos Introducao Fluxo em rede é um método de andlise da programacao linear que se destaca pela minimizacao de uma fundo que depende do fluxo custo lucro em uma rede Ha varios modelos de fluxos em rede indicados para diversas aplicacées Isso permite o desenvolvimento de algoritmos especializados com grandes vantagens computacionais Neste texto vocé vai estudar sobre os algoritmos utilizados na reso lugdo de problemas de fluxo em rede aprender métodos utilizados nos problemas classicos além de ver definicdes importantes para o estudo de fluxos em redes Terminologia das redes Alguns sistemas sao abordados como redes sistemas de produgaodistribui cao sistemas de trafego urbano sistemas de rodovias transporte sistemas de comunicagao rede de dutostubulagées sistemas de localizacao redes elétricas entre outros sistemas 76 Pesquisa operacional Em fluxos em rede ha alguns problemas que sao classicos e tentam res ponder a certas questdes por exemplo Problema do caminho minimo PCM qual é a melhor forma de per correr uma rede indo de um dado ponto a outro com o menos custo possivel Problema de fluxo maximo PFM é uma rede com arcos capacitados Como e qual é o maximo de fluxo possivel de se enviar de um dado ponto a outro da rede respeitando a capacidade dos arcos Problema de fluxo com custo minimo PFCM considerando um dado custo por unidade de fluxo em uma rede nos seus arcos com arcos capacitados e que precisamos enviar unidades de fluxo alocadas em determinados nds ofertaprodugao para outros nds demandaconsumo como fazélo com o menor custo possivel Alguns problemas de fluxo em rede por serem formulados como um pro blema de programacao linear podem ser resolvidos pelo método simplex de modo que qualquer um dos pacotes utilizados por esse método também podera ser usado Entretanto é possivel a utilizacgao com eficiéncia de algoritmos para a resolucao desses problemas Algoritmos Pelo fato de o problema do fluxo maximo por exemplo ser formulado como um problema de programagao linear podese resolvélo pelo método simplex de modo que qualquer um dos pacotes de software de programacao linear possa ser usado Contudo um algoritmo de caminhos aumentados eficiente encontra se disponivel para resolver esse tipo de problema Esse algoritmo baseiase em dois conceitos intuitivos uma rede residual e um caminho aumentado Segundo Hillier e Lieberman 2013 um caminho aumentado 6 um caminho direcionado da origem para o escoadouro na rede residual de modo que nele todo arco tenha capacidade residual estritamente positiva Capacidade residual de caminho aumentado é a denominaaéo para o minimo dessas capacidades residuais pois ele representa a quantidade de fluxo que pode ser adicionada de maneira vidvel ao caminho todo Desse modo cada caminho aumentado fornece uma oportunidade de se aumentar ainda mais 0 fluxo pela rede original Modelos de fluxos em rede O algoritmo do caminho aumentado seleciona algum caminho desses e apresenta um fluxo igual a sua capacidade residual ao caminho na rede original Esse processo continua até que nao haja mais caminho aumentado de modo que o fluxo partindo da origem e indo para 0 escoadouro nao possa ser mais aumentado A estratégia para garantir que a solugao final seja necessariamente otima o fato de os caminhos para fluxos designados nao poderem impedir o emprego de uma combinagao melhor de designagées de fluxo Resumindo cada iteragao do algoritmo consiste nas trés etapas indicadas a seguir Algoritmo do caminho aumentado para o problema do fluxo maximo 1 Identifique um caminho aumentado encontrando algum caminho di recionado da origem para o escoadouro na rede residual tal que cada arco desse caminho tenha capacidade residual estritamente positiva Se nao existir algum caminho aumentado os fluxos de rede ja constituem um padrao de fluxo 6timo 2 Identifique a capacidade residual c desse caminho aumentado encon trando o minimo das capacidades residuais dos arcos nesse caminho Aumente o fluxo nesse caminho de c 3 Diminua de c a capacidade residual de cada arco nesse caminho au mentado Aumente de c a capacidade residual de cada arco na diregao oposta nesse caminho aumentado Retorne a etapa 1 Quando a etapa for executada em geral ha uma série de caminhos aumen tados alternativos para se escolher Embora a estratégia algoritmica para fazer essa selecao seja importante para a eficiéncia de implementacdes em grande escala nao iremos nos aprofundar nesse topico relativamente especializado O uso de algoritmos na busca da solucao serve para encontrar nos de uma rede com determinadas caracteristicas Muitas variantes estao nos algoritmos de fluxo maximo e fluxo com caminho mais curto As aplicagdes mais comuns sao Encontre todos os nds que estao ligados a um dado no origem por meio de um caminho direcionado e viceversa Identifique todos os componentes conexos de uma dada rede Determine se uma dada rede bipartida Encontre um ciclo direcionado em uma rede Árvore de valor mínimo Existem diferentes e importantes tipos de algoritmos para a determinação de árvores de valor mínimo Aqui será apresentado apenas o algoritmo de Kruskal devido à sua simplicidade Antes disso definiremos grafo estrutura que corresponde a um par de conjuntos G N E em que N é um conjunto de entidades Por exemplo essas entidades podem estar associadas a pontos locais pessoas áreas geográficas e E é um conjunto em que seus elementos são ligações ou interrelações entre os elementos de N que podem ser estradas parentescos e fronteiras entre áreas geográficas Algoritmo de Kruskal Dado um grafo G NE não orientado e valorado para a construção de uma árvore de valor mínimo partese do grafo trivial G N0 que é constituído apenas pelos nós do grafo original G acrescentandose iterativamente a aresta de menor valor que não forma ciclo com as já escolhidas O comprimento mínimo será obtido pela soma dos valores associados às arestas da árvore resultante do procedimento descrito anteriormente Na Figura 1 estão um grafo sua árvore mínima e o valor do comprimento mínimo associado Figura1 Grafo e uma árvore parcial mínima Pesquisa operacional 78 Caminho mais curto A determinação de um caminho mais curto em um grafo devido à sua apli cabilidade prática é um problema importante em várias áreas como na área de logística por exemplo O comprimento de um caminho P é definido como sendo a soma dos comprimentos de todos os arcos de P O problema é encon trar o caminho mais curto de um nó inicial s para um nó terminal t Aqui se considera um grafo valorado simples isto é sem laços e arcos paralelos G com n nós que pode ser descrito por uma matriz Dnxn dij em que Em geral dij dji e a desigualdade do triângulo não precisa ser satisfeita ou seja dij djk pode ser menor que dik Então se a desigualdade do triângulo é satisfeita para todo i j e k o problema seria trivial pois o arco direto x y seria o caminho mais curto do vértice x ao y Vejamos a seguir o algoritmo de Dijkstra que foi um dos primeiros a serem propostos para resolver problemas do caminho mais curto Sua aplicação se dá quando os comprimentos de cada arco são dij 0 O algoritmo não se aplica nos casos em que os comprimentos são negativos Algoritmo de Dijkstra O algoritmo de Dijkstra usa uma técnica de rotulação dos nós a partir de s o nó inicial do caminho Há dois tipos de rotulação temporária e definitiva O valor do nível em que um nó j é rotulado definitivamente a partir de s é exatamente o comprimento do caminho mais curto entre s e j Em cada iteração do algoritmo alguns nós são rotulados temporariamente e outros definitiva mente assim aplicase o algoritmo até se conseguir rotular definitivamente o nó terminal do caminho que é o nó t BOAVENTURA NETTO 2003 79 Modelos de fluxos em rede 80 Pesquisa operacional Aplicagdo do algoritmo de Dijkstra Passo 1 Inicializagao rotule definitivamente RD 0 no s a um nivel 0 e rotule temporariamente RT os demais nos a um nivel Passo 2 todo no j ainda nao rotulado definitivamente deve receber uma nova rotulacao temporaria cujo valor sera min valor da rotulagao temporaria atual de j valor da rotulagao definitiva de 1 d onde i o no rotulado definitivamente na iteracao anterior Passo 3 rotule definitivamente o nd i associado ao menor valor de rotulos encontrados no Passo 1 Passo 4 repita Os Passos e 2 até conseguir rotular definitivamente o no terminal do caminho t O valor da rotulacao definitiva do n6 t correspondera ao compri mento do caminho mais curto entre s e t Para determinar quais sao os nos intermediarios do caminho mais curto entre s e t trabalhe do final do caminho para o comeco backtracking da seguinte forma a A partir do not procure achar qual foi o primeiro no responsavel pelo seu valor de rotulo definitivo Suponha que tenha sido 0 nd k Ele é denominado de no Pai do no t b Procure achar qual foi o primeiro no i do Passo 2 responsavel pelo valor de rotulo definitivo de k c Aplique o mesmo procedimento para encontrar 0 no Pai do no k e repita 0 Sucessivamente até encontrar 0 no inicial s como sendo o no Pai responsavel pelo valor do rotulo definitivo de algum no intermediario d Os nos assim determinados irao compor 0 caminho mais curto Veja o grafo da Figura 2 e determine o caminho mais curto entre os nos B Sera 0 no s e G sera 0 no t Determine também o comprimento total minimo do caminho Figura 2 Rede do exemplo para a aplicação do algoritmo de Dijkstra Figura 3 Algoritmo de Dijkstra aplicado ao grafo da Figura 2 Na resolução adotase um vetor de dimensão 1 x 7 para mostrar os níveis de rotulações temporárias RT e definitivas RD dos nós enquanto caminhase para a solução ótima como na Figura 3 81 Modelos de fluxos em rede As rotulações definitivas são colocadas dentro de um quadrado e o último nível de rotulação definitiva do vetor é indicado por A solução ótima é O comprimento total mínimo valor do nível de rotulação definitiva do nó terminal G 7 e o caminho mais curto obtido do fim para o começo é G E C B Fluxo máximo Na análise do desempenho de um grafo valorado com frequência é necessário calcular o valor ótimo de uma função do fluxo entre dois vértices o vértice fonte e o vértice t conhecido como destino Agora apresentamos uma situação em que há apenas um tipo de fluxo no grafo que pode ser eletricidade água informação ou tráfego por exemplo Na literatura especializada esse caso é conhecido como The OneCommodity Flow Problem e o grafo é denominado rede Seja βi o conjunto de nós ligados ao nó i por arcos orientados no sentido de chegada em i e αi o conjunto de nós ligados ao nó i por arcos orientados no sentido de saída de i Uma função fij definida em E com valores reais é dita ser um fluxo para um grafo orientado G N E se Em que uij é a capacidade do arco ij ou seja a quantidade máxima de fluxo que pode ser remetida de i para j A condição 2 representa a hipótese da conservação de fluxo na rede porém há estudos referentes a redes em que indicam que podem haver ganhos ou perdas de fluxo F é o valor do fluxo que pode ser enviado da fonte s ao destino t por meio da rede G N E Pesquisa operacional 82 É importante notar que o valor máximo de F é limitado pelas capacidades associadas a cada arco da rede e determinado por corte uma propriedade fundamental de uma rede Um corte é um conjunto de arcos que se forem removidos de uma rede desconectam um conjunto de nós dos demais Na Figura 4 percebese que o corte formado pelos arcos 2 4 e 3 4 desconectam o nó 4 dos nós 1 2 e 3 Figura 4 Exemplo de corte Nos problemas de fluxo máximo o interesse é colocar cortes que separem nó fonte do nó destino O valor do corte ou a capacidade do corte é a soma das capacidades dos arcos do corte em uma dada direção Na Figura 4 o valor do corte é igual a u24 u34 O algoritmo descrito a seguir se baseia em um princípio muito simples Seja X um subconjunto de N tal que s X e t X O conjunto AX de arcos que tem orientação de chegada em nós de X e origem em nós que não pertencem a X por definição é um corte na rede G Se cAX é o valor desse corte então o valor máximo de fluxo F que pode ser enviado de s para t satisfaz F c AX Isso significa que o fluxo máximo em uma rede é limitado pelo valor do corte de menor capacidade que nada mais é do que a própria capacidade Está estabelecido então um dos mais importantes resultados na teoria de fluxos em redes que é o teorema que veremos a seguir 83 Modelos de fluxos em rede Teorema do fluxo máximo e corte mínimo Em redes com fonte e destino únicos o fluxo viável máximo que pode ser enviado da fonte ao destino t é igual ao valor do corte mínimo corte com menor capacidade entre os cortes da rede Para ilustrar podemos verificar que o fluxo máximo na rede da Figura 5 é 3 Os números que aparecem ao lado dos arcos representam suas capacidades nas direções especificadas pelas setas O corte mínimo consiste dos arcos s2 e 3t e tem valor igual a 3 Figura 5 Corte mínimo Observe que o problema fluxo máximo em uma rede pode ser expresso como um problema de programação linear seja o fluxo fij em uma rede G N E em que N s 2t e uij é a capacidade do arco ij O valor desse fluxo é F se Então temos a seguinte formulação Pesquisa operacional 84 Desse modo pode ser aplicado o método simplex na resolução de um problema de fluxo máximo Apresentamos a seguir um algoritmo mais eficiente que usa um procedimento de rotulação e gera uma sequência de fluxos crescentes até atingir o máximo Com o teorema do corte mínimo e fluxo máximo podemos encontrar o fluxo máximo determinando a capacidade de todos os cortes e escolhendo o de capacidade mínima Embora isso nos dê o valor máximo de F não é possível especificar como o fluxo circula pela rede Algoritmo do fluxo máximo Esse método é baseado no teorema de Ford e Fulkerson e busca encontrar uma cadeia por meio da qual um fluxo positivo possa ser enviado da fonte s ao destino t Essas cadeias são denominadas de cadeias de fluxo ampliável CFA As cadeias são utilizadas para transmitir o máximo possível fluxo de s para t O processo é repetido até não ser mais possível encontrar alguma CFA o que indica que encontramos o fluxo máximo Rotina de Rotulação encontrar uma CFA Iniciamos a rotulação do nó s Um nó j pode ser rotulado se um fluxo positivo pode ser enviado de s para j Em geral do nó i podemos rotular um nó j se uma das seguintes condições for satisfeita 1 O arco que liga o nó i ao nó j é um arco que chega em j arco forward e sua capacidade fij uij é maior que o fluxo que há nele 2 O arco que liga o nó i ao nó j é um arco que sai de j arco backward e o fluxo nele é maior que zero fij 0 Continuase nessa rotina até rotular o destino t obtendo assim uma CFA 85 Modelos de fluxos em rede Fases do algoritmo 1 Inicialização obtenha um fluxo viável em todos os arcos ou seja um fluxo que atenda às restrições de capacidade nos arcos e de conservação de fluxo nos nós 2 Obtenha uma CFA iniciando em s e terminando em t Vá para a Fase 3 Caso não seja possível PARE O fluxo máximo foi encontrado 3 Calcule o fluxo máximo δ que pode ser enviado pela última CFA obtida Aumente de δ o fluxo nos arcos forward da cadeia e decresça o fluxo de δ nos arcos backward Volte a Fase 2 Determine o fluxo máximo F da fonte s ao destino t na rede a seguir Fig 6 em que os números ao lado dos arcos representam suas capacidades Figura 6 Rede para o exemplo Inicialização faça fij 0 em todos os arcos Veja a Tabela 1 Pesquisa operacional 86 Continua Passo 1 Vamos encontrar uma CFA de s para t Então rotule inicialmente s rótulos são representados por asteriscos De s rotule o nó 1 pois s 1 é um arco forward levando um fluxo fs1 us1 7 Do nó 1 rotule o nó 2 pelo arco forward 12 e finalmente rotule o destino t Desse modo obtémse a CFA formada somente por arcos forward Os números nos arcos indicam o fluxo máximo permitido em cada um deles Assim o máximo valor de fluxo para essa CFA é 3 Isso aumenta F de 3 unidades e o fluxo sobre todos os arcos forward da cadeia aumenta de 3 unidades também Passo 2 Repetindo a rotina de rotulação você chega a uma nova CFA Agora o fluxo máximo permitido é 4 Com isso aumenta o fluxo F pela rede para 7 unidades Passo 3 O nó 1 não pôde ser rotulado a partir de s pois o arco s1 é forward e fs1 us1 7 Isso aumenta o fluxo total F de 5 unidades como mostra no próximo passo Partindose de s rotule o nó 2 mas não será possível rotular t a partir dele pois o arco 2t já alcançou sua capacidade Mas o nó 1 pode ser rotulado a partir de 2 pois o arco 12 é backward contendo um fluxo positivo E a partir do vértice 1 rotule t Tabela 1 Teoremas do fluxo de rede 87 Modelos de fluxos em rede 1 Podese usar o teorema de Ford e Fulkerson para provar que o fluxo máximo é realmente F 15 Basta considerar o corte que separa os vértices rotulados dos não rotulados na última linha Isso fornece os arcos s1 e 2t cuja capacidade valor é 15 Observe que o arco 12 não pertence ao corte Como F não pode exceder a capacidade de nenhum corte que separe s de t o valor de F 15 é o máximo fluxo possível O corte mostrado na última linha é o corte mínimo 2 Para encontrar o fluxo máximo em uma rede G N E não orientada primeiro convertaa em uma rede orientada equivalente e então aplique o algoritmo Passo 4 Agora temse uma CFA com dois arcos forward s2 e 1t e um backward 12 Para aumentar o fluxo por essa cadeia aumente o fluxo nos arcos forward e decresça no arco backward O máximo valor que se pode aumentar em F é de 3 unidades e o novo fluxo na rede é fornecido a seguir Apesar do nó 2 poder ser rotulado a partir de s nunca rotule o destino t Desse modo nenhuma outra CFA pode ser encontrada Essa figura representa a configuração ótima de fluxo na rede com fluxo máximo de 15 entre s e t Tabela 1 Teoremas do fluxo de rede Continuação Pesquisa operacional 88 A maioria dos problemas do fluxo máximo que surgem na prática é consideravelmente extensa Alguns deles têm milhares de nós e arcos O algoritmo do caminho aumentado é muito mais eficiente que o método simplex genérico para resolver esses problemas de grandes dimensões Entretanto para problemas de tamanho modesto uma alternativa adequada seria o usar o Solver com base no método simplex genérico do Excel 89 Modelos de fluxos em rede 1 Em relação aos modelos de fluxo em rede marque a alternativa correta a Fluxo em rede é um método de análise da programação não linear que se destaca pela maximização de uma função que depende do fluxo custolucro em uma rede b Há poucos modelos de fluxos em rede indicados para aplicações limitadas c Alguns sistemas são abordados como redes como os sistemas de rodovias transporte por exemplo d Alguns problemas de fluxo em rede por ser formulado como um problema de programação linear podem ser resolvidos pelo método simplex não sendo possível a utilização de algoritmos para a resolução desses problemas e A geometria de uma rede não pode ser desenhada no plano 2 Com base no que foi estudado sobre algoritmos marque a alternativa correta a O uso de algoritmos na busca da solução serve para encontrar arcos de uma rede b São usados exclusivamente para identificar todos os componentes conexos de uma dada rede c O algoritmo de Kruskal é o único tipo de algoritmo para a determinação de árvores de valor mínimo d O algoritmo de Dijsktra é utilizado para resolver problemas do caminho mais curto e Em cada iteração do algoritmo os nós são sempre rotulados temporariamente 3 Observe as alternativas a seguir e indique a afirmação correta com relação ao Algoritmo do Fluxo Máximo a O algoritmo do Fluxo Máximo é um método baseado no Teorema de Fourier b As cadeias são utilizadas para transmitir o mínimo possível fluxo de s para t c Na Rotina de Rotulação para encontrar uma CFA ao iniciar a rotulação do nó s um nó j não pode ser rotulado se um fluxo positivo pode ser enviado de s para j d Na Rotina de Rotulação em geral do nó i podemos rotular um nó j somente se o arco que liga o nó i ao nó j é um arco que chega em j arco forward e sua capacidade fij uij é maior que o fluxo que há nele e Para obter uma CFA a rotina de rotulação deve seguir até rotular o destino t 4 Com relação à resolução de problemas por meio de algoritmos marque a alternativa correta a O algoritmo de caminhos aumentados é um eficiente método disponível para resolver problemas de fluxo mínimo Esse algoritmo baseiase em dois conceitos intuitivos uma rede residual e um caminho aumentado b Um caminho aumentado é Pesquisa operacional 90 um caminho direcionado do escoadouro para a origem na rede residual c Capacidade residual de caminho aumentado é a denominação para o mínimo dessas capacidades residuais pois ele representa a quantidade de fluxo que pode ser adicionada de maneira viável ao caminho todo d O algoritmo do caminho aumentado seleciona algum caminho entre os caminhos encontrados e apresenta um fluxo diferente à sua capacidade residual ao caminho na rede original e A estratégia para garantir que a solução final seja necessariamente ótima é o fato de os caminhos para fluxos designados poderem impedir o emprego de uma combinação melhor de designações de fluxo 5 Observe o problema a seguir e marque a alternativa correta Apresentamos alguns exemplos de redes em que os nós s representam as ofertas os nós t representam as demandas e os demais nós são nós de transbordo Os valores em cada arco representam em geral custos de transporte distâncias ou tempos de viagem entre cada par de nós a Na Figura 2 temos o caso mais simples em que há somente um nó de oferta e um de demanda b Não é possível termos restrições de capacidade nos nó1s c Na Figura 1 temos diversos nós de oferta e de demanda d Na Figura 2 há um nó de oferta que possui diversos centros de distribuição que por sua vez distribuem o produto pela rede até outros centros intermediários atacadistas ou armazéns que abastassem o consumidor e O que se busca nos problemas representados nas figuras é determinar o fluxo da rede de modo que o custo o tempo ou a distância total de transporte seja minimizado ou que o fluxo total seja maximizado 91 Modelos de fluxos em rede BOAVENTURA NETTO P O Teoria e Modelos de Grafos São Paulo Edgard Blucher Ltda 2003 HILLIER F S LIEBERMAN G J Introdução à pesquisa operacional 9 ed Porto Alegre AMGH 2013 Ebook Leituras recomendadas ANDRADE MCQ Criação no processo decisório Rio de Janeiro LTC 1980 GOLDBARG M C LUNA H P L Otimização combinatória e programação linear mo delos e algoritmos Rio de Janeiro Campus 2000 LACHTERMACHER G Pesquisa operacional na tomada de decisões Rio de Janeiro Campus 2002 Pesquisa operacional 92 Encerra aqui o trecho do livro disponibilizado para esta Unidade de Aprendizagem Na Biblioteca Virtual da Instituição você encontra a obra na íntegra