Baixe o app para aproveitar ainda mais
Prévia do material em texto
PESQUISA OPERACIONAL AULA 4 Prof. Ricardo Zanardini 2 CONVERSA INICIAL Olá! Nessa aula veremos o que é um problema de árvore mínima e como problemas desse tipo são importantes. Que eles podem ser facilmente resolvidos com o uso do algoritmo de Kruskal ou com o uso do WinQSB. Veremos também o que são problemas de fluxo máximo, suas aplicações e resolução utilizando o WinQSB. Que tal começar com a definição de um problema de árvore mínima e logo em seguida ver como podemos resolver esses problemas utilizando o algoritmo de Kruskal? Problemas de árvore mínima consistem em situações onde o objetivo é interligar todos os nós de um grafo com o menor custo possível. Problemas assim aparecem com muita frequência em diversas situações: Interligar computadores de uma rede com o menor gasto referente ao cabeamento. Conectar caixas eletrônicos de um determinado banco. Instalar um sistema de segurança nas residências de um condomínio. Interligar máquinas, equipamentos e computadores de uma empresa. O algoritmo mais utilizado para que se possa obter a solução de um problema de árvore mínima é o algoritmo de Kruskal. O algoritmo consiste em ligar todos os nós de um grafo onde a soma dos custos referentes às conexões entre dois nós é o menor possível. O princípio básico do algoritmo de Kruskal consiste em, a partir de um grafo com pesos, isto é, com custos associados a cada arco, a cada iteração marcar o arco de menor custo. Caso haja formação de ciclo, eliminar os respectivos arcos. Em seguida, repetir esse processo até que todos os arcos estejam marcados ou eliminados. 3 Para ilustrar melhor, vamos considerar o seguinte problema: Uma companhia de TV a Cabo está instalando decodificadores nas residências de um condomínio. A figura a baixo ilustra as localizações de cada decodificador e os respectivos custos, em reais. Determine como o técnico da empresa deve proceder para que todas as residências fiquem interligadas e o custo total de instalação seja o menor possível. O primeiro passo é determinar qual é a conexão de menor custo. Observando a figura, vemos que o arco C-E tem um custo igual a 4. Marcamos esse arco. 4 O próximo passo é determinar o próximo arco de menor custo. Observe que os arcos A-B e E-F têm um custo igual a 5. Nesse caso escolheremos ao acaso o arco A-B. O próximo arco a ser escolhido é o arco E-F. Como não podemos fechar um ciclo, devemos eliminar o arco C-F. 5 O próximo arco a ser escolhido é B-D ou D-E, ambos com custo igual a 6. Escolheremos, ao acaso, o arco B-D. O próximo passo é escolher agora o arco D-E, também de custo igual a 6. Note que agora precisaremos eliminar alguns arcos. Primeiramente iremos eliminar o arco B-E. 6 Como ainda temos a possibilidade de fechar um ciclo, iremos eliminar o arco A-E. Devemos fazer o mesmo para o arco A-C, pois também forma um ciclo. Dentre os arcos restantes, o de menor custo é o D-G. Marcamos então esse arco. 7 Agora, para não formar ciclo, devemos eliminar o arco E-G. Faremos o mesmo com o arco F-G. Como todos os arcos foram marcados ou eliminados, obtivemos a solução ótima do problema de árvore mínima. 8 Os nós a serem interligados são A-B, B-D, C-E, D-E, D-G e E-F, com um custo mínimo de 5+6+4+6+7+5 que totaliza R$ 33,00 referentes à instalação dos decodificadores. Mesmo sendo simples obtermos a solução de um problema de árvore mínima através do uso do algoritmo de Kruskal, o WinQSB é uma importante ferramenta que pode nos ajudar na resolução de problemas desse tipo. TEMA 1 - RESOLUÇÃO DE PROBLEMAS DE ÁRVORE MÍNIMA UTILIZANDO O WINQSB Podemos resolver um problema de árvore mínima utilizando o WinQSB. O primeiro passo é clicar no menu Iniciar. Em seguida, WinQSB, Network Modeling. A tela de abertura irá aparecer. Agora basta clicar em File e, em seguida, em New Problem. Teremos então que selecionar a opção Mínimal Spanning Tree no campo Problem Type. O critério da função objetivo é Minimization e o formato ideal para a entrada dos dados é Spreadsheet Matrix Form, ou seja, o formato matricial. É importante informar corretamente o número de nós do problema no campo Number of Nodes. Nesse caso temos 7 nós. 9 Teremos então uma tabela contendo 7 nós distribuídos em linhas e colunas, mas ainda com os nomes que são padrão do WinQSB: Node 1, Node 2... O próximo passo é alterar os nomes dos nós. Basta clicar no menu Edit e, depois disso, em Node Names. 10 Agora é só efetuar a troca dos nomes por A, B, C, D, E, F e G. O próximo passo é preencher a tabela com base na figura. Note que iremos adicionar apenas as conexões diretas entre os nós. Como o nó A está ligado com os nós B, C e E, na linha de A teremos os números 5, 7 e 11 nas colunas dos respectivos nós B, C e E. O mesmo ocorre com os demais nós. Após o preenchimento da tabela, basta clicar em Solve and Analyze e depois em Solve the Problem para que possamos obter a solução do problema de árvore mínima. Para esse problema, a solução ótima consiste em interligar os nós A-B, E-C, B-D, D-E, E-F e D-G, com um custo mínimo total de R$ 33,00. 11 O link a seguir no leva a um artigo que trata de uma metaheurística GRASP para o problema da árvore geradora de custo mínimo com grupamentos. É uma leitura bem interessante, não deixe de clicar no botão e conferir! http://arquivo.ulbra-to.br/ensino/43020/artigos/anais2005/anais/GRASP.pdf TEMA 2 - PROBLEMAS DE FLUXO MÁXIMO Além dos problemas de árvore mínima que vimos, existem também os problemas de fluxo máximo. Fluxo Máximo Um problema de fluxo máximo consiste em determinarmos a capacidade máxima de transporte de uma rede formada por arcos e nós, com dois nós especiais: um nó representando a origem e um nó representando o final da rede. As aplicações de problemas de fluxo máximo ocorrem nas mais diversas áreas. Podemos determinar, por exemplo, a capacidade máxima de distribuição de gás, petróleo ou água em uma rede formada por tubulações e estações intermediárias que muitas vezes servem para impulsionar o fluxo. Podemos também determinar a capacidade máxima de transporte de passageiros em uma rede de ônibus, trens ou metrôs. Também é possível determinarmos a capacidade máxima de uma linha de produção ou a capacidade máxima de atendimento de pessoas em um hospital ou repartição. Um problema de fluxo máximo é um caso particular de um problema de programação linear e pode ser resolvido pelo método simplex. Mas, devido às características do problema, existem algoritmos mais eficientes para a solução de problemas de fluxo máximo, tais como o algoritmo do caminho aumentado e o algoritmo dos caminhos parciais. Para que possamos entender melhor o que é um problema de fluxo máximo, vamos considerar um problema de uma empresa que precisa transportar gás natural. O nó A indica a origem da rede e o nó E indica o final. Os nós B, C e D são estações intermediárias. A capacidade máxima das tubulações (arcos), em bilhões de litros por dia, pode ser vista na figura a seguir. 12 O objetivo é determinar qual é a capacidade máxima de transporte de gás natural da rede. Observe que, mesmo que a capacidade inicial (arcos AB e AC) seja de 38 bilhões de litros por dia,a quantidade que chega ao destino nem sempre é a mesma. Isso ocorre pois muitas vezes há uma redução da capacidade de transmissão ao longo da rede. É como se uma avenida com quatro pistas, em um determinado momento, tiver uma redução para duas pistas. O número de automóveis que circulam, em um determinado intervalo de tempo, no trecho de quatro pistas muitas vezes não será o mesmo que conseguirá circular no trecho de duas pistas. Veremos adiante como é possível resolver o problema de fluxo máximo utilizando o WinQSB. Existem algoritmos destinados à resolução desses problemas. No caso destes problemas que estamos estudando, veremos como é possível utilizar o WinQSB para que possamos obter uma forma rápida e efetiva de encontrar a solução desses problemas. TEMA 3 - RESOLUÇÃO DE PROBLEMAS DE FLUXO MÁXIMO UTILIZANDO O WINQSB Para resolvermos problemas de fluxo máximo utilizando o WinQSB, o procedimento é bastante simples. Como exemplo, utilizaremos o problema da empresa que precisa transportar gás natural por uma rede de distribuição. 13 A figura a seguir apresenta os dados do problema. A capacidade máxima de transporte da rede pode ser encontrada utilizando o WinQSB. O primeiro passo é clicarmos em Iniciar, Todos os Programas, WinQSB. Em seguida, iremos clicar na opção Network Modeling. 14 O próximo passo é clicar em File, New Problem. A opção a ser selecionada é Maximal Flow Problem (problema de fluxo máximo). O número de nós, no nosso exemplo, é igual a 5. Depois é só clicarmos em OK. A tela para que possamos informar os dados do problema é a seguinte: 15 É interessante alterarmos os nomes dos nós. Para isso, precisamos clicar em Edit, Node Names e colocarmos os novos nomes dos nós. Vamos agora preencher os dados com as capacidades de cada arco. É importante cuidarmos com o sentido de cada arco. Para resolvermos o problema, basta clicarmos em Solve and Analyze, Solve the Problem. Podemos também clicar no ícone . 16 Devemos agora determinar quem é o nó inicial (start node) e quem é o nó final (end node). A solução ótima do problema é a seguinte: O WinQSB fornece o valor do fluxo máximo: 26 bilhões de litros de gás por dia. Além disso, fornece também a quantidade efetiva que está sendo transportada em cada arco. O arco AB tem uma capacidade total de 20 bilhões de litros por dia, mas passarão apenas 15 bilhões de litros. O arco AC, mesmo 17 que tenha uma capacidade total de 18 bilhões de litros, transportará apenas 11 bilhões. O arco BE terá toda a sua capacidade, que é de 15 bilhões de litros por dia, utilizada. O mesmo ocorre com o arco CD. Quanto ao arco DE, mesmo que a capacidade total seja de 19 bilhões de litros, a quantidade efetiva a ser transportada é de 11 bilhões de litros de gás natural por dia. Sugestão de leitura Como sugestão de leitura, temos os capítulos 5 e 6 da obra Iniciação à pesquisa operacional no ambiente de gestão, dos professores Marcos A. Barbosa e Ricardo A. D. Zanardini, editora Intersaberes. E também a seção 6.4 da obra Pesquisa operacional, de Hamdy A. Taha, editora Pearson.
Compartilhar