ResolucaoDeProblemasDeArvoreMinimaUtilizandoOWinQSB

Prévia do material em texto

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. 
 
 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, 
depoi disso, em Node Names. 
 
 
 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.