Pesquisa Operacional AULA 4

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.