Problemas de Árvore Mínima e Fluxo Máximo

Prévia do material em texto

Disciplina Pesquisa Operacional 
Aula 4 
Professor Ricardo Zanardini 
 
Objetivos do Estudo 
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. 
Para que possamos saber mais sobre os temas que serão abordados, vamos assistir à videoaula do 
professor Ricardo que está disponível no material on-line. 
Acompanhe! 
 
 
 
Agora que você já viu o vídeo, 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? 
Acesse o material on-line novamente e leia o texto atentamente! Em seguida assista ao vídeo que está 
disponível. O professor Ricardo dará explicações mais detalhadas sobre problemas de árvore mínima, 
para que você apreenda melhor ainda o que é isto. Acompanhe! 
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. Vamos ver como isso pode ser feito com o texto que está disponível no material 
on-line. Lá você também pode conferir como resolver problemas de árvore mínima com o uso do WinQSB 
assistindo à videoaula que o professor Ricardo preparou para você! 
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 conferir! 
http://arquivo.ulbra-to.br/ensino/43020/artigos/anais2005/anais/GRASP.pdf 
 
Problemas de Fluxo Máximo 
 
Além dos problemas de árvore mínima que vimos, existem também os problemas de fluxo máximo. 
Antes da explicação do professor Ricardo sobre isto, acesse o material on-line e leia com atenção o que é 
este problema. Em seguida, assista à videoaula em que o professor Ricardo irá explicar o que é este 
problema e algumas de suas aplicações para que você não fique com dúvidas! 
Vamos prosseguir? 
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. 
Acesse o material on-line para ler um texto sobre o assunto e para assistir a videoaula que está 
disponível. O professor Ricardo irá nos explicar como é possível fazer uso do WinQSB na resolução de 
problemas de fluxo máximo. Assista atentamente para apreender bem a explicação. 
 
 
Sugestão de leituras 
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. 
Exercícios 
Contextualização 
Agora que já sabemos o que são problemas de árvore mínima e problemas de fluxo máximo, 
chegou a hora de colocarmos em prática os conhecimentos adquiridos. 
Bons Estudos! 
 
 
 
 
 
 
 
1. Uma empresa de comunicações está implantando uma rede de fibra ótica e precisa conectar 6 
pontos. A figura a seguir ilustra as localizações desses pontos e apresenta as distâncias, em 
quilômetros, entre os pontos. 
 
 
Determine quais conexões devem ser feitas para que o total necessário de cabos de fibra ótica seja o 
menor possível. 
2. Quais ligações devem ser feitas para que a instalação de uma rede elétrica em uma residência seja 
feita com o menor custo possível? A figura a seguir apresenta as localizações de cada tomada a ser 
colocada bem como as distâncias em metros entre os pontos. 
 
 
 
 
 
 
3. Determine a árvore mínima que interliga todos os pontos do seguinte grafo. 
 
 
4. Determine a capacidade máxima de distribuição da seguinte rede. 
 
 
 
 
 
5. A figura a seguir apresenta equipamentos de uma rede de transmissão de dados que podem estar 
conectados de diversas formas: através de cabos de rede, bluetooth, Wi-Fi, modem... Sabemos que 
nem sempre uma rede consegue operar com a capacidade máxima devido a interferências e 
quantidade de tráfego de dados. A figura a seguir apresenta o volume de dados dessa rede onde os 
valores se referem à quantidade de kbytes por segundo (kbps) que são efetivamente transmitidos. 
Sendo assim, determine a capacidade máxima de transmissão de dados, do ponto A ao ponto F. 
 
 
 
Gabarito 
Exercício 1 
 
 
Conexões: 
A-B 
A-C 
C-D 
D-E 
D-F 
Total: 149 
 
 
 
Exercício 2 
 
 
Conexões: 
A-C 
B-D 
C-E 
D-E 
D-F 
Total: 44 
 
 
 
 
Exercício 3. 
 
 
Conexões: 
1-5 
2-3 
2-4 
3-5 
5-7 
6-7 
Total: 346 
 
 
 
Exercício 4. 
Fluxo máximo: 160 
 
Exercício 5. 
Capacidade máxima: 110 kbps