INVESTIGAÇÃO OPERACIONAL
 9ª Aula

Redes
As redes invadem o nosso mundo das mais diversas formas. As redes de transporte, eléctricas ou de
comunicação são disso exemplo.
No entanto, a representação sob a forma de rede pode ser utilizada em áreas tão diferentes como a
produção, distribuição, planeamento de projectos, localização de instalações, gestão de recursos, planeamento
financeiro, etc.
Para resolver estes problemas de redes, utilizam-se modelos de optimização que se baseiam em alguns
tipos de problemas de programação linear.
Neste capítulo iremos tratar dos seguintes tipos de problemas:




Cecília Rocha # 1
Caminho Mais Curto (shortest path)
Árvore de Ligações Mínimas (minimum spanning tree)
Fluxo Máximo (maximum flow)
Fluxo de Caixa Mínimo (minimum cost flow)
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Exercício Exemplo

O Parque Natural de Seervada teve recentemente de reduzir o n.º de visitantes e de Backpack Hiking.
Não é admitida a entrada de carros no Parque, embora exista um percurso estreito e sinuoso para
eléctricos e jeep’s dos guardas florestais. Este sistema de trilhos está representado na figura seguinte
em que O se refere à entrada do Parque, as outras letras correspondem a instalações da guarda
florestal e os números à distância entre cada ponto.
A
2
7
2
5
O
4
B
1


1
7
E
O Parque tem um cenário deslumbrante no ponto T e só um pequeno n.º de eléctricos faz o percurso da
entrada ao ponto T.
A administração do Parque enfrenta agora 3 problemas:



Cecília Rocha # 2
4
T
D
3
4
C
5
1º Determinar qual a rota que deve ser utilizada para reduzir a distância total a percorrer pelos eléctricos
2º Dado que é necessário instalar uma rede telefónica no Parque que estabeleça a ligação entre todas as
instalações da guarda florestal, ao longo dos trilhos, qual o percurso a escolher para minimizar os custos da linha
3º Durante a época alta, existem mais visitantes do que os que podem ser transportados pelos eléctricos, da
entrada até ao ponto T, qual a forma de maximizar o n.º de viagens sem perturbar o sistema ecológico e de vida
selvagem do Parque e respeitando o n.º limite de trajectos em cada linha.
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Termos utilizados em “Redes”
Uma rede consiste num conjunto de pontos e linhas que ligam certos pares de pontos
 Esses pontos denominam-se Nós
 As linhas entre os pontos denominam-se Arcos


Aos arcos estão associados fluxos
Se o fluxo só pode circular numa direcção – Arco Direccionado, cuja direcção corresponde à da seta representada
A






Cecília Rocha # 3
Quando não existem restrições de direcção de fluxo – Arco Não Direccionado ou Ligação
Se uma rede só utiliza arcos direccionados, designa-se por Rede Direccionada
Um percurso entre dois nós corresponde à sequência de arcos distintos que permite ligar esses nós


B
Um percurso direccionado do nó i ao nó j refere-se à sequência de arcos de ligação cuja direcção (se existir) é de i
para j e permite que haja fluxo ao longo deste percurso.
Um percurso não direccionado do nó i ao nó j é a sequência de arcos de ligação, direccionados ou não, que
permite o fluxo de e para o nó j.
Um percurso que começa e acaba no mesmo nó denomina-se ciclo
Dois nós dizem-se ligados se a rede contém pelo menos um arco não direccionado entre eles
Uma rede diz-se ligada se todos os pares de pontos estão ligados
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Termos utilizados em “Redes”






Considerando um conjunto de n nós, pode-se criar uma árvore adicionando arcos, um a um, entre os
diversos nós. Cada arco novo vai expandir a árvore que é uma rede ligada sem ciclos não direccionados.
Quando o arco (n-1) for adicionado o processo termina dado que a árvore resultante já liga os n nós.
Uma árvore expandida é uma rede ligada, para todos os n nós, que não contém nenhum ciclo não
direccionado e tem exactamente n-1 arcos, número necessário para ligar todos os nós sem criar ciclos.
O fluxo máximo que pode ser transportado por um dado arco designa-se por capacidade do arco
Um nó de origem é aquele em que o fluxo de saída é superior ao de entrada
Um nó de destino é aquele em que o fluxo de entrada excede o fluxo de saída
Um nó de transbordo é aquele em que o fluxo de entrada é igual ao fluxo de saída
D
A
C
B
Cecília Rocha # 4
D
A
C
E
B
D
A
C
E
B
D
A
C
E
B
D
A
C
E
B
E
2001/2002
INVESTIGAÇÃO OPERACIONAL
9ª Aula (cont.)


O
Problema do Caminho Mais Curto
2
Consideremos uma rede ligada e não direccionada com 2 nós
especiais – Origem e Destino.
A cada ligação está associada uma distância não negativa
O objectivo final será encontrar o percurso com menor distância
entre a Origem e o Destino.

Algoritmo de Resolução
 Objectivo da n- ésima iteração
Encontrar o n- ésimo nó mais próximo da Origem (repetir até que o
n- ésimo nó seja o destino)
 Dados para a n- ésima iteração
Os n-1 nós mais próximos da Origem (determinados na iteração
anterior e denominados nós resolvidos), incluindo o caminho mais
curto determinado até ao momento e a correspondente distância à
Origem
 Candidatos ao nó mais próximo
Cada nó resolvido está ligado por um arco a um ou mais nós por
resolver dos quais se irá escolher um candidato com a menor
distância para o arco de ligação
 Cálculos para o nó mais próximo
Para cada nó resolvido e respectivo candidato, adicionar a distância
do caminho mais curto já determinado, entre a origem e este nó. O
candidato com a menor distância total à origem será o n- ésimo nó
mais próximo.
Cecília Rocha # 5
4
5
A
2
1
C
B
7
3
4
4
E
1
D
7
5
T
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Exercício Exemplo

O Parque Natural de Seervada teve recentemente de reduzir o n.º de visitantes e de Backpack Hiking.
Não é admitida a entrada de carros no Parque, embora exista um percurso estreito e sinuoso para
eléctricos e jeep’s dos guardas florestais. Este sistema de trilhos está representado na figura seguinte
em que O se refere à entrada do Parque, as outras letras correspondem a instalações da guarda
florestal e os números à distância entre cada ponto.
A
2
7
2
5
O
4
B
1


1
7
E
O Parque tem um cenário deslumbrante no ponto T e só um pequeno n.º de eléctricos faz o percurso da
entrada ao ponto T.
A administração do Parque enfrenta agora 3 problemas:



Cecília Rocha # 6
4
T
D
3
4
C
5
1º Determinar qual a rota que deve ser utilizada para reduzir a distância total a percorrer pelos eléctricos
2º Dado que é necessário instalar uma rede telefónica no Parque que estabeleça a ligação entre todas as
instalações da guarda florestal, ao longo dos trilhos, qual o percurso a escolher para minimizar os custos da linha
3º Durante a época alta, existem mais visitantes do que os que podem ser transportados pelos eléctricos, da
entrada até ao ponto T, qual a forma de maximizar o n.º de viagens sem perturbar o sistema ecológico e de vida
selvagem do Parque e respeitando o n.º limite de trajectos em cada linha.
2001/2002
INVESTIGAÇÃO OPERACIONAL
9ª Aula (cont.)


O
2
Exercício- Exemplo
 1ª Iteração
Nó início
Origem
4
Nó final
distância
A
2
B
5 (> 4)
C
4
Origem/A
Origem/C
Nó final
distância
B
2+2=4
D
B
2+7=9
4 + 1 = 5 (> 4)
E
4+4=8
Nó final
distância
C
4 + 1 = 5 (> 4)
D
4+4=8
E
4+3=7
Nó início
Nó final
Origem/A/B/D
Término
distância
8 + 5 = 13 (Fim)
Origem/A/B
1
C
 3ª Iteração
Nó início
B
7
3
4
4
E
1
D
7
5
 4ª Iteração
Origem/A/B/E
Cecília Rocha # 7
A
2
 2ª Iteração
Nó início
5
D
7+1=8
Término
7 +7 = 14
T
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Problema do Caminho Mais Curto
Exercício
Uma pessoa que vive na Póvoa e trabalha no Porto pretende descobrir que o percurso que deverá seguir na viagem
matinal para o seu emprego, de forma a minimizar a duração da viagem. Durante algum tempo, teve o cuidado de
registar a duração da viagem ao longo das diferentes localidades intermédias . O resultado dessa análise está
apresentado no quadro seguinte onde se representou por “-” a inexistência de estradas a ligar essas localidades. Qual
será o percurso que essa pessoa seleccionou?
Póvoa
L1
L2
L3
L4
Porto
Cecília Rocha # 8
Póvoa
18
32
-
L1
18
12
28
-
L2
12
17
32
L3
32
28
17
4
17
L4
4
11
Porto
32
17
11
-
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Problema da Árvore de Ligações Mínimas
Consideremos uma rede ligada e não direccionada com 2 nós especiais – Origem e Destino.
A cada ligação está associada uma distância não negativa
O objectivo final será encontrar a árvore com menor comprimento total de ligações, de forma a que todos os
pares de nós estejam ligados, se que seja criado algum ciclo.
Num problema desta natureza não poderemos ter mais de n – 1 arcos (de outra forma estaríamos a formar um ciclo)
Este tipo de problema pode ser utilizado, por exemplo, para resolver um problema de planeamento de
transportes, no qual se pretendem servir diversas povoações garantindo o menor custo possível. Os dados de
base seriam as localidades, a distância entre si e os meios de transporte disponíveis.
Num caso genérico, começa-se por um nó escolhido arbitrariamente, procurando-se em seguida o arco com
menor valor para o próximo nó. O passo seguinte consiste em identificar o nó não ligado que está mais
próximo dos dois definidos inicialmente e adicionar o arco correspondente à rede. Este processo é repetido
até se terem ligado todos os nós. A rede resultante será uma Árvore de Ligações Mínimas.
Cecília Rocha # 10
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Exercício Exemplo

O Parque Natural de Seervada teve recentemente de reduzir o n.º de visitantes e de Backpack Hiking. Não é
admitida a entrada de carros no Parque, embora exista um percurso estreito e sinuoso para eléctricos e jeep’s
dos guardas florestais. Este sistema de trilhos está representado na figura seguinte em que O se refere à
entrada do Parque, as outras letras correspondem a instalações da guarda florestal e os números à distância
entre cada ponto.
A
2
7
2
5
O
4
B
1


1
7
E
O Parque tem um cenário deslumbrante no ponto T e só um pequeno n.º de eléctricos faz o percurso da
entrada ao ponto T.
A administração do Parque enfrenta agora 3 problemas:



Cecília Rocha # 11
4
T
D
3
4
C
5
1º Determinar qual a rota que deve ser utilizada para reduzir a distância total a percorrer pelos eléctricos
2º Dado que é necessário instalar uma rede telefónica no Parque que estabeleça a ligação entre todas as
instalações da guarda florestal, ao longo dos trilhos, qual o percurso a escolher para minimizar os custos da linha
3º Durante a época alta, existem mais visitantes do que os que podem ser transportados pelos eléctricos, da entrada até
ao ponto T, qual a forma de maximizar o n.º de viagens sem perturbar o sistema ecológico e de vida selvagem do Parque
e respeitando o n.º limite de trajectos em cada linha.
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)
Algoritmo
O
de Resolução aplicado ao Problema do Parque Seervada
2
 1ª Tarefa
4
5
Seleccionar um nó arbitrariamente (seja a Origem O)
A
Ligá-lo ao nó mais próximo (A – 2, B – 5 ou C – 4), neste caso nó A
2
1
C
 2ª Tarefa (repetir até ter ligado todos os nós)
B
7
Identificar o nó não ligado mais próximo de um nó já ligado
B  (BO = 5, BA = 2)
BA
C  (CO = 4, CB = 1)
CB
E  (EB = 3, EC = 4)
EB
3
4
4
E
1
D  (DA = 7, DB = 4, DE = 1) DE
T  (TD = 5, TE = 7)
D
TD
7
 Desempates
Os desempates para seleccionar o nó mais próximo de um já ligado,
pode ser quebrado arbitrariamente, dado que este procedimento não
irá alterar o resultado final. No entanto pode ser indicativo da
existência de múltiplas soluções óptimas.
5
T
 A resolução gráfica é a forma mais rápida de se obter uma solução.
Cecília Rocha # 12
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Problema de Árvore de Ligações Mínimas
Exercício
Determine a Árvore de Ligações Mínimas para o seguinte problema e respectivo custo de ligação:
E
10
7
A
2
8
B
5
1
1
D
4
10
3
4
C
Cecília Rocha # 13
F
7
G
3
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Problema do Fluxo Máximo
Com este tipo de problema pretende-se determinar as combinações de arcos que permitem maximizar o
fluxo numa dada rede.
Considerar uma rede direccionada e ligada, onde existe um nó de Origem – O, um nó de Destino – T e em
que todos os outros nós são nós de transbordo. São dados do problema as capacidades de cada ligação e o
objectivo final será determinar uma distribuição de fluxos admissível que maximiza o fluxo total na rede do nó
de Origem ao nó de Destino.
Depois de iniciar o processo de distribuição de fluxos, iremos obter uma Rede Residual, onde se evidenciam
os fluxos residuais que ainda podem ser transportados em cada ligação e que se representa da seguinte
forma:
A
B
O número à esquerda do arco refere-se à capacidade residual (que ainda pode ser transportada) do nó anterior para o
seguinte.
Antes de se iniciar a resolução deste tipo de problemas, propriamente dita, temos de transformar a rede
inicial direccionada e ligada numa rede residual ligada, na qual à esquerda de cada arco temos a capacidade
máxima do arco e à direita (lado da seta) o valor zero.
Cecília Rocha # 15
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Problema do Fluxo Máximo
Seguidamente, de cada vez que algum fluxo passa por esse arco é deduzido ao lado esquerdo e
aumentado ao direito.
Um Percurso Positivo é um percurso directo da Origem ao Destino, na Rede Residual, em que todos os
arcos têm capacidade residual estritamente positiva. O mínimo destas capacidades residuais denomina-se
capacidade residual do percurso positivo e corresponde ao fluxo que efectivamente pode ser
transportado ao longo de todo esse percurso.

Algoritmo de Resolução
1.
2.
3.
4.
Cecília Rocha # 16
Identificar um Percurso Positivo procurando uma sequência de arcos, da Origem ao Destino, cuja
capacidade residual seja estritamente positiva
Identificar a Capacidade Residual c* desse Percurso Positivo procurando o mínimo das capacidades
residuais dos arcos que o constituem. Aumentar o fluxo na rede desse valor c*
Deduzir a capacidade residual de cada arco de c*, à esquerda, nesse Percurso Positivo e adicionar a
mesma quantidade ao lado direito.
Voltar ao primeiro passo até distribuir o fluxo máximo pela rede.
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Exercício Exemplo

O Parque Natural de Seervada teve recentemente de reduzir o n.º de visitantes e de Backpack Hiking.
Não é admitida a entrada de carros no Parque, embora exista um percurso estreito e sinuoso para
eléctricos e jeep’s dos guardas florestais. Este sistema de trilhos está representado na figura seguinte
em que O se refere à entrada do Parque, as outras letras correspondem a instalações da guarda
florestal e os números à distância entre cada ponto.
A
5
3
1
7
O
4
B
2


1
6
E
O Parque tem um cenário deslumbrante no ponto T e só um pequeno n.º de eléctricos faz o percurso da
entrada ao ponto T.
A administração do Parque enfrenta agora 3 problemas:



Cecília Rocha # 17
4
T
D
5
4
C
9
1º Determinar qual a rota que deve ser utilizada para reduzir a distância total a percorrer pelos eléctricos
2º Dado que é necessário instalar uma rede telefónica no Parque que estabeleça a ligação entre todas as
instalações da guarda florestal, ao longo dos trilhos, qual o percurso a escolher para minimizar os custos da linha
3º Durante a época alta, existem mais visitantes do que os que podem ser transportados pelos eléctricos,
da entrada até ao ponto T, qual a forma de maximizar o n.º de viagens sem perturbar o sistema ecológico
e de vida selvagem do Parque e respeitando o n.º limite de trajectos em cada linha.
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)
Exercício- Exemplo

Problema Inicial
1ª Iteração
Percurso O- A- D- T
Rede Residual inicial
fluxo: min(5, 3, 9) = 3
O
O
4
A
7
7
2
C
3
5
4
D
2
0
5
0
B
3
4
0
0
6
D
0
2
0
5
0
B
4
0
E
1
0
0
6
9
6
0
0
4
0
1
2
0
C
0
E
A
0
4
0
1
2
0
B
3
A
1
E
2
0
4
4
O
4
7
5
C
5
3
D
6
9
T
Cecília Rocha # 18
0
T
0
0
T
3
2001/2002
INVESTIGAÇÃO OPERACIONAL
9ª Aula (cont.)

Exercício- Exemplo

1ª Iteração
Percurso O- A- D- T
2ª Iteração
Percurso O- A- B- D- T
3ª Iteração
Percurso O- C- E- T
fluxo: min (5, 3, 9) = 3
fluxo: min (2, 2, 4, 6) = 2
fluxo: min (4, 4, 6) = 4
O
4
2
O
4
7
0
7
3
2
C
2
5
4
0
0
B
0
E
0
0
0
6
D
3
2
0
5
Cecília Rocha # 19
T
3
2
B
0
4
1
2
0
6
0
4
D
3
2
0
5
T
5
2
B
2
0
E
1
2
0
2
4
0
0
0
0
0
E
A
C
2
6
0
5
0
4
0
1
0
0
C
4
7
A
0
0
0
5
A
0
O
0
3
D
4
4
T
5
2001/2002
INVESTIGAÇÃO OPERACIONAL
9ª Aula (cont.)

Exercício- Exemplo

3ª Iteração
Percurso O- C- E- T
4ª Iteração
Percurso O- B- D- T
5ª Iteração
Percurso O- B- E- D- T
fluxo: min (4, 4, 6) = 4
fluxo: min (7, 2, 4) = 2
fluxo: min (5, 5, 1, 2) = 1
O
0
0
O
0
7
0
5
5
0
C
2
5
0
4
2
B
0
E
4
2
0
2
D
3
2
0
5
Cecília Rocha # 20
T
5
2
B
0
4
1
4
0
2
0
4
D
3
2
0
4
T
7
2
B
0
1
E
0
4
1
2
2
4
0
3
0
0
E
A
C
0
4
4
5
2
0
0
1
0
4
C
2
4
A
0
0
0
5
A
4
O
0
3
D
1
4
T
8
2001/2002
INVESTIGAÇÃO OPERACIONAL
9ª Aula (cont.)

Exercício- Exemplo

5ª Iteração
Percurso O- B- E- D- T
6ª Iteração
Percurso O- B- E- T
Distribuição Final
Fluxo
fluxo: min (5, 5, 1, 2) = 1
fluxo: min (4, 4, 2) = 2
= 3+ 2+ 4 +2 +1 +2 = 14
O
0
0
O
0
4
0
2
5
0
C
2
4
0
4
2
B
0
E
4
4
1
2
D
3
2
0
2
Cecília Rocha # 21
T
8
2
B
0
4
0
4
1
0
0
4
D
3
2
0
2
T
8
2
B
0
3
E
0
4
1
0
1
6
0
5
0
3
E
A
C
0
1
4
5
5
0
1
0
0
4
C
0
2
A
3
0
0
5
A
4
O
0
3
D
1
6
T
8
2001/2002
INVESTIGAÇÃO OPERACIONAL

9ª Aula (cont.)

Problema do Fluxo Máximo
Exercício
Determine o fluxo máximo que pode ser transportado nesta rede:
D
8
8
A
10
B
7
10
10
C
Cecília Rocha # 22
2001/2002