Pesquisa Operacional II - Gabarito Comentado

Prévia do material em texto

1 
 
Exercícios – Unidade 1 
 
1) Considere o seguinte diagrama de transição de estados: 
 
Sobre esse diagrama é correto afirmar que: 
a) A probabilidade de transição do estado 2 para o estado 3 é igual a 1/3. 
b) A probabilidade de transição do estado 3 para o estado 1 é igual a 1/2. 
c) A probabilidade de transição do estado 1 para ele mesmo é igual a 1/2. 
d) TODAS as alternativas anteriores estão CORRETAS. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
Considere a seguinte cadeia de Markov para as questões 2, 3 e 4: 
 
Nela, o estado 1 representa um dia chuvoso, o estado 2 representa um 
dia nublado e o estado 3 um dia com sol. 
 
 
 
 
 
2 
2) Sobre essa cadeia de Markov, é correto afirmar que: 
a) Se hoje o dia é de sol, então a probabilidade de amanhã ser um dia 
chuvoso é igual a 0,3. 
b) Se hoje o dia é chuvoso, então a probabilidade de amanhã ser um dia 
chuvoso é igual a 0,3. 
c) Se um determinado dia estiver nublado, então a probabilidade de o dia 
seguinte ser de sol é de 0,6. 
d) Se um determinado dia for de sol, então a probabilidade de o dia 
seguinte ser de sol é de 0,8. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
3) Se considerarmos que o tempo em um determinado dia é de sol, qual 
é a probabilidade de os 7 dias seguintes serem dias de sol-sol-chuva-chuva-
sol-nublado-sol? 
a) 0,8. 
b) 0,2. 
c) 0,006. 
d) 2,3x10
-3 
e) 1,536x10
-4
 
 
Solução: 
Nesse caso, temos: 
a33xa33xa31xa11xa13xa32xa23 
= 0,8x0,8x0,1x0,4x0,3x0,1x0,2 = 0,0001536 = 1,536x10
-4 
 
 
 
 
3 
4) Considere que determinado dia seja chuvoso. Nesse caso, as 
probabilidades absolutas após 4 dias serão: 
a) a
(4)
 = (0,4 0,3 0,3) 
b) a
(4)
 = (0,25 0,33 0,42) 
c) a
(4)
 = (0,1939 0,2991 0,507) 
d) a
(4)
 = (0,1939 0,1994 0,169) 
e) a
(4)
 = (0,169 0,2383 0,5927) 
 
Solução: 
 
 
 
 
 
 
 
 
 
4 
5) Considere a seguinte cadeia de Markov de três estados (1, 2 e 3) dada 
pela seguinte matriz de transição: 
 
Sobre essa cadeia de Markov é correto afirmar que: 
a) O estado 1 é transiente. 
b) O estado 3 é absorvente. 
c) Ela é ergódica. 
d) Os estados 2 e 3 formam um conjunto fechado. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
Solução: o estado 1 é recorrente (não transiente), pois podemos retornar 
a ele. O estado 3 também é recorrente. Na verdade todos os estados são 
recorrentes, formando um conjunto fechado contendo todos os três estados 
(1, 2 e 3). Se calcularmos P
2
, P
3
, P
4
 e etc, veremos que p11, p22 e p33 tem 
sempre valores positivos (isso significa que os estados 1, 2 e 3 não são 
periódicos). Portanto essa cadeia de Markov é ergódica (pois podemos atingir 
qualquer estado partindo de qualquer estado, isto é, todos os estados são 
recorrentes, e todos os estados são aperiódicos). 
 
 
 
 
 
 
 
 
 
5 
6) Considere a seguinte cadeia de Markov: 
 
Sobre essa cadeia de Markov é INCORRETO afirmar que: 
a) Os estados 1 e 2 formam um conjunto fechado. 
b) Ela não é ergódica. 
c) O estado 3 é absorvente. 
d) Ela possui 3 conjuntos fechados. 
e) Os estados 4 e 5 são transientes. 
 
Solução: Na verdade ela possui 2 conjuntos fechados: um contendo os 
estados 1 e 2, e outro contendo apenas o estado 3 (que é absorvente). 
 
7) Considere a seguinte cadeia de Markov de três estados (1, 2 e 3) dada 
pela seguinte matriz de transição: 
 
Nesse caso, as probabilidades de estado no equilíbrio são: 
a) π = (0,3333 0,33333 0,3333). 
b) π = (0,1 0,7 0,2). 
c) π = (0 0,8 0,2). 
d) π = (0 0 0 ). 
 
6 
e) π = (0,2961 0,3618 0,3421) 
 
Solução: 
Temos o seguinte sistema de equações: 
π1 = 0,1π1 + 0,7π2 + 0,2π3 
π2 = 0π1 + 0,3π2 + 0,7π3 
π3 = 0,9π1 + 0π2 + 0,1π3 
π1 + π2 + π3 = 1 
Descartando, por exemplo, a primeira equação e isolando as incógnitas, 
chegamos ao seguinte sistema linear: 
0π1 - 0,7π2 + 0,7π3 = 0 
0,9π1 + 0π2 - 0,9π3 = 0 
π1 + π2 + π3 = 1 
A solução desse sistema linear é: π1 = 0,3333, π2 = 0,3333 e π3 = 
0,3333. Ou seja: 
π = (0,3333 0,3333 0,3333) 
Outra forma de obter esse resultado seria calcular P
100
, que resultaria 
em: 
 
Em que cada coluna representa os valores das probabilidades de estado 
no equilíbrio (coluna 1 representa o valor de π1, coluna 2 o valor de π2 e 
coluna 3 o valor de π3) 
 
 
 
 
7 
8) O resultado do tempo médio do primeiro retorno da questão 7 é: 
a) μ11 = 0,3333; μ22 = 0,3333 e μ33 = 0,3333. 
b) μ11 = 3; μ22 = 3 e μ33 = 3. 
c) μ11 = 10; μ22 = 2 e μ33 = 3. 
d) μ11 = 5; μ22 = 3,5 e μ33 = 7. 
e) μ11 = 1; μ22 = 7 e μ33 = 2. 
 
Solução: 
3
3333,0
1
11  3
3333,0
1
22  3
3333,0
1
33  
 
9) Considere a seguinte cadeia de Markov de quatro estados (1, 2, 3 e 4) 
dada pela seguinte matriz de transição: 
 
Classifique cada um dos estados dessa cadeia de Markov. 
 
Solução: 
O estado 1 é transiente (pois, uma vez que saímos dele não podemos 
retornar a ele). 
O estado 3 é absorvente (pois a probabilidade p33 = 1) 
Os estados 2 e 4 também são transientes (como o estado 3 é 
absorvente, a probabilidade do estado voltar para ele mesmo não é de 100% 
- caso o sistema atinja o estado 3, que é absorvente, ele não poderá voltar 
para o estado 2 ou para o estado 4, por isso eles são transientes). 
Devemos também testar a periodicidade de P: 
 
8 
 
Note que tanto p22 quanto p44 alternam entre 0 e positivo de 2 em 2 
transições. Logo, os estados 2 e 4, além de serem transientes, também são 
periódicos de período 2. 
 
10) A quantidade de itens em estoque consiste em uma cadeia de 
Markov de 3 estados: 100 itens em estoque (estado 1), 200 itens em estoque 
(estado 2) e 300 itens em estoque (estado 3). A quantidade de itens pode 
variar dependendo da demanda diária (que reduz a quantidade de itens em 
estoque) e a produção (que aumenta a quantidade de itens em estoque). A 
matriz de transição de estados dessa cadeia de Markov é mostrada a seguir: 
 
Sabe-se que o custo por item em estoque depende do número de itens 
no estoque: se o estoque possuir 100 itens, então o custo por item será de 
R$ 1,00, se o estoque possuir 200 itens, então o custo por item será de R$ 
 
9 
3,00 e se o estoque possuir 300 itens, então o custo por item será de R$ 
10,00. Nesse caso, determine: 
a) O custo diário esperado com estoque. 
b) O número médio de dias para o estoque retornar a 100 itens (µ11), 
retornar a 200 itens (µ22) e retornar a 300 itens (µ33). 
 
Solução: 
O custo esperado irá depender do número esperado de itens no estoque 
(o valor esperado para as probabilidades absolutas de cada estado). É 
importante observar que calcular o valor esperado das probabilidades 
absolutas é o mesmo que calcular as probabilidades de estado no equilíbrio 
(que determinam para qual probabilidade cada estado estará tendendo, ou 
seja, o valor médio das probabilidades). 
Dessa forma, temos o seguinte sistema de equações: 
π1 = 0,3π1 + 0,3π2 + 0,1π3 
π2 = 0,6π1 + 0,4π2 + 0,7π3 
π3 = 0,1π1 + 0,3π2 + 0,2π3 
π1 + π2 + π3 = 1 
Descartando, por exemplo, a primeira equação e isolando as incógnitas, 
chegamos ao seguinte sistema linear: 
0,6π1 - 0,6π2 + 0,7π3 = 0 
0,1π1 + 0,3π2 - 0,8π3 = 0 
π1 + π2 + π3 = 1 
A solução desse sistema linear é: π1 = 0,2547, π2 = 0,5189 e π3 = 
0,2264. Ou seja: 
π = (0,2547 0,5189 0,2264) 
Outra forma de obter esse resultado seria calcular E
100
, que resultaria 
em: 
 
10 
 
Em que cada coluna representa os valores das probabilidades de estado 
no equilíbrio (coluna 1 representa o valor de π1, coluna 2 o valor de π2 e 
coluna 3 o valor de π3) 
Temos então que os valores esperados para as probabilidades de cada 
estado são π1 = 0,2547, π2 = 0,5189 e π3 = 0,2264. Isso significa que em 
média a probabilidade de termos 100 itens no estoque é igual a 0,2547, de 
termos 200 itens no estoque é 0,5189 e de termos 300 itens no estoque é 
0,2264. Assim, o custo diárioesperado será: 
100x1x0,2547 + 200x3x0,5189 + 300x10x0,2264 = 1016,01 
Resposta: R$ 1.016,01. 
Na letra b devemos calcular o tempo médio de primeiro retorno para cada 
estado: 
926,3
2547,0
1
11  927,1
5189,0
1
22  417,4
2264,0
1
33  
Esses resultados mostram que em média, o estoque retorna para 100 
itens de 4 em 4 dias, para 200 itens de 2 em 2 dias e para 300 itens de 4 em 
4 dias. 
 
 
 
11 
 
Exercícios – Unidade 2 
 
1) Sobre os elementos de um modelo de filas é INCORRETO afirmar 
que: 
a) Os clientes são gerados por uma fonte. 
b) Nos modelos de fila, o tamanho da fila pode ser tanto finito quanto 
infinito. 
c) Na disciplina de filas FCFS, o primeiro cliente a chegar será o primeiro 
a ser atendido. 
d) Caso a fonte seja infinita então a capacidade da instalação é ilimitada. 
e) Na análise de filas, enquanto a chegada de clientes é dada pelo 
intervalo de tempo entre chegadas de clientes, o serviço é descrito pelo 
tempo de serviço. 
 
Solução: está incorreta, pois o que é ilimitado é a fonte de onde chegam 
os clientes (ela que é infinita, que significa que os clientes “nunca” param de 
chegar, não se esgotam). Ou seja, não tem relação com a capacidade da 
instalação (sistema). Esta poderia ser limitada (finita), mesmo com a fonte 
infinita. 
 
2) Considere que a chegada entre clientes em uma loja siga uma 
distribuição exponencial de média 5 minutos. Considere que a loja abra às 
8:00 horas da manhã. A probabilidade de chegada de cliente no intervalo 
entre 10:00 e 10:15 é igual a: 
a) 0. 
b) 1. 
c) 0,95. 
 
12 
d) 0,095. 
e) 0,05. 
 
Solução: 
Devido à ausência de memória da distribuição exponencial, a 
probabilidade de chegada não depende da hora em que o estabelecimento 
abriu (depende apenas do intervalo considerado de T = 15 minutos). A taxa 
de chegada de clientes é igual a λ = 1/5 = 0,2 clientes/minuto. Assim, temos: 
P [t ≤ T] = 1 – e
-λT
 = 1 – e
-0,2x15
 = 
Substituindo: 
P [t ≤ 15] = 1 – e
-0,2x15
 = 0,9502 
 
Considere o seguinte enunciado para as questões 3 e 4: 
Considere um sistema no qual só cheguem clientes, em que os tempos 
entre chegadas de clientes seguem uma distribuição exponencial com média 
4 horas. 
 
3) O número médio de chegadas de clientes em 1 mês (considere 1 mês 
igual a 30 dias) é: 
a) 90. 
b) 180. 
c) 250. 
d) 500. 
e) 1.000. 
 
Solução: 
 
13 
A taxa de chegada de clientes é λ = 1/4 = 0,25 clientes/hora. Como um 
dia tem 24 horas, então λ = 0,25 clientes/hora x 24 horas/dia = 6 clientes/dia. 
Em um mês temos λ = 6 clientes/dia x 30 dias/mês = 180 clientes/mês. Ou 
seja, em um período de 1 mês, chegam em média 180 clientes a esse 
sistema. 
 
4) A probabilidade de termos 2 clientes no sistema em 10 horas é igual a: 
a) 0,2565. 
b) 0,35. 
c) 0,5. 
d) 0,875. 
e) 1. 
 
Solução: 
Como só existem chegadas de clientes, o nosso problema segue um 
processo de nascimento puro, portanto usaremos o modelo de nascimento 
puro (em que o número de chegadas segue uma distribuição de Poisson – 
pois o intervalo entre chegadas segue uma distribuição exponencial) 
A taxa de chegada de clientes é λ = 1/4 = 0,25 clientes/hora. 
Temos que n = 2 clientes 
E t = 10 horas. 
Substituindo na fórmula da distribuição de Poisson: 
 
Temos: 
 
2565,0
!2
1025,0
)10(
1025,02
2 


e
p 
 
14 
5) Um caminhão possui um total de 30 itens a serem descarregados. O 
descarregamento desse caminhão segue uma distribuição exponencial com 
média 2 itens por minuto. Qual é a probabilidade de termos 2 itens ou 1 item 
em 15 minutos. 
a) 0. 
b) 0,0702. 
c) 0,1428. 
d) 0,8572. 
e) 1. 
 
Solução: 
Queremos saber qual é a probabilidade de termos 2 itens OU termos 1 
item. Matematicamente, queremos calcular: 
p2 + p1 
Como o nosso processo é de morte puro (apenas saídas), devemos 
utilizar o modelo de morte puro (em que o número de chegadas segue uma 
distribuição de Poisson – pois o intervalo entre chegadas segue uma 
distribuição exponencial). 
A taxa de saída (descarregamento) é µ = 2 itens/minuto 
O intervalo de tempo t = 15 minutos 
Também temos que o total de itens é N = 30 itens 
Substituindo na fórmula da distribuição de Poisson truncada: 
 
Temos: 
 
0702,0
)!230(
152
)15(
152230
2 



 e
p 
 
15 
 
0726,0
)!130(
152
)15(
152130
1 



 e
p 
Logo, 
p2 + p1 = 0,0702 + 0,0726 = 0,1428 
 
6) Considere a seguinte modelo de fila: (M/M/2):(LCFS/>∞/10). Sobre 
esse modelo é correto afirmar que: 
a) O tempo de serviço é constante. 
b) O número de clientes permitido no sistema é igual a 2. 
c) A disciplina da fila é o primeiro a chegar é o primeiro a ser atendido. 
d) O tamanho da fonte na qual os clientes chegam é infinita. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
Solução: 
Nesse modelo, as chegadas seguem uma distribuição de Poisson (ou 
intervalo de tempo exponencial entre chegadas), o tempo de serviço (duração 
do serviço) também é exponencial e o sistema possui 2 servidores em 
paralelo. A disciplina da fila é LCFS (último a chegar, primeiro a ser atendido), 
o número de clientes permitido no sistema é infinito e o tamanho da fonte na 
qual os clientes chegam é igual a 10. 
 
 
 
 
 
 
 
 
16 
Considere o seguinte enunciado para as questões 7 e 8: 
Um consultório médico possui um único médico. Os clientes que chegam 
a esse consultório são atendidos em ordem de chegada. O tempo entre 
chegadas de pacientes segue uma distribuição exponencial de média 20 
minutos. O tempo de atendimento (duração da consulta) também é 
exponencial de média 30 minutos. Entretanto, caso o número de pacientes na 
fila seja igual a 3, a média da duração da consulta passa a ser igual a 10 
minutos (o médico passa a atender mais rápido). Além disso, caso um 
paciente chegue ao consultório e encontre 3 pacientes na fila, ele irá desistir 
(irá embora). 
 
7) O número médio de clientes na fila, no estado de equilíbrio, é igual a: 
a) 1. 
b) 1,433. 
c) 2. 
d) 2,547. 
e) 3. 
 
Solução: 
λn = λ = 60/20 = 3 pacientes/hora 
µn = 60/30 = 2 pacientes/hora, n = 1,2,3 
µ4 = 60/10 = 6 pacientes/hora, n = 4 (pois 3 pacientes na fila é igual a 4 
pacientes no sistema – por termos 1 paciente em atendimento). 
Devemos então considerar a equação a seguir (dada anteriormente), 
substituindo os valores de λn e µn: 
,...3,2,1,
...
...
0
121
0121 









 npp
nn
nn
n


 
Temos que: 
 
17 
00
1
0
1 5,1 ppp 








 
002
2
0
12
01
2 25,2
2
3
pppp 

















 
003
3
0
123
012
3 375,3
2
3
pppp 



















 
003
4
0
1234
0123
4 6875,1
26
3
pppp 




















 
Para determinar p0 devemos considerar o somatório: 
1
4
0

n
np 
Ou seja, 
143210  ppppp 
Substituindo: 
16875,1375,325,25,1 00000  ppppp 
Resultando em: 
18125,9 0 p 
Isolando p0: 
8125,9
1
0 p 
Logo, p0 = 0,1019. Ou seja, no estado de equilíbrio, a probabilidade de 
não haver pacientes no consultório (no sistema) é igual a 0,1019. 
Substituindo o valor de p0 nas demais equações, temos: 
15285,05,1 01  pp 
2293,025,2 02  pp 
 
18 
3439,0375,3 03  pp 
17196,06875,1 04  pp 
Que são as probabilidades de termos 1, 2, 3 e 4 pacientes, 
respectivamente, no consultório. Para determinar o número médio de clientes 
na fila para consulta, podemos utilizar a equação: 
 


4
2
1
n
nq pnL 
Que resulta em: 
432 321 pppLq  
Ou seja, Lq = 1,433, no estado de equilíbrio. Em outras palavras, a fila do 
consultório possui em média 1,433 pacientes, no estado de equilíbrio. 
 
8) O tempo médio de espera do paciente na fila de atendimento, no 
estado de equilíbrio, é igual a: 
a) 15 minutos. 
b) 22,45 minutos. 
c) 29,66 minutos. 
d) 34,62 minutos. 
e)39,79 minutos. 
 
Solução: 
Em primeiro lugar devemos calcular: 
λeff = λ – λlost 
A taxa de perda é obtida como: 
λlost = λ.p4 = 3x0,17196= 0,5159 pacientes/hora 
Assim, 
 
19 
λeff = λ – λlost = 3 – 0,5159 = 2,4841 pacientes/hora 
Com isso temos que: 
577,0
4841,2
433,1

eff
q
q
L
W

 
Isto é, o tempo médio de espera para ser atendido é igual a 0,577 hora, 
ou 0,577x60 = 34,62 minutos. 
 
9) Calcule a probabilidade de chegarem ao menos 2 clientes em um 
intervalo de 3 horas, dado que a taxa de chegadas de clientes segue uma 
distribuição exponencial de média 1 cliente por hora. 
 
Solução: 
Temos λ = 1 clientes/hora e t = 3. 
Calcular a probabilidade de chegada de ao menos 2 clientes equivale a 
perguntar: 
pn(3) = ?, dado que n ≥ 2, ou seja, pn ≥ 2(3) = p2(3) + p3(3) + p4(3) + p5(3) + ... 
Poderíamos ir calculando os valores dessas probabilidades a partir da 
fórmula da distribuição de Poisson para calcular pn(3) para n = 2, n = 3, n = 
4... e depois somar todos os resultados. Entretanto, ainda assim teríamos que 
calcular pn(3) para diversos valores de n para conseguir obter um resultado 
satisfatório para essa questão. 
Uma forma mais correta de resolver essa questão seria considerar que: 
pn ≥ 2(3) = 1 – pn < 2(3) = 1 – [p0(3) + p1(3)] = 1 – p0(3) – p1(3) 
Ou seja, a probabilidade de chegada de pelo menos 2 clientes equivale a 
1 menos a probabilidade de chegadas de menos de 2 clientes (ou seja, de só 
chegarem 1 cliente ou nenhum cliente). Agora precisamos calcular apenas 
p0(t) e p1(t) para obter a solução do problema. Assim: 
 
20 
 
0498,0
!0
31
)3( 3
310
0 

 

e
e
p 
 
1494,03
!1
31
)3( 3
311
1 

 

e
e
p 
pn ≥ 2(3) = 1 – p0(3) – p1(3) = 0,8 
Ou seja, a probabilidade de chegarem ao menos 2 clientes é igual a 0,8. 
 
10) Aviões chegam a um aeroporto com taxa exponencial de média 4 
aviões por hora. O aeroporto possui 2 pistas para aterrissagem. O tempo de 
ocupação da pista por um avião é exponencial de média 20 minutos. Só pode 
haver no máximo 2 aviões à espera para a aterrissagem. Aviões que chegam 
e encontram 2 aviões à espera devem abortar a aterrissagem. Nesse caso, 
determine: 
a) A probabilidade de as duas pistas estarem em uso. 
b) A probabilidade de um avião que chega ao aeroporto não ter que 
esperar. 
c) O número médio de aviões no aeroporto (sistema). 
d) O tempo esperado até a conclusão da aterrissagem. 
e) A taxa média de ocupação das pistas de aterrissagem. 
 
Solução: 
λn = λ = 4 aviões/hora 
µ = 60/20 = 3 aviões/hora 
µn = 3xn aviões/hora, n = 1,2 
µn = 6 aviões/hora, n = 3,4 
Devemos então considerar a equação a seguir (dada anteriormente), 
substituindo os valores de λn e µn: 
 
21 
,...3,2,1,
...
...
0
121
0121 









 npp
nn
nn
n


 
Temos que: 
00
1
0
1 33,1 ppp 








 
00
2
0
12
01
2 889,0
36
4
pppp 


















 
00
3
0
123
012
3 5926,0
366
4
pppp 




















 
00
4
0
1234
0123
4 395,0
3666
4
pppp 




















 
Para determinar p0 devemos considerar o somatório: 
1
4
0

n
np 
Ou seja, 
143210  ppppp 
Substituindo: 
1395,05926,0889,033,1 00000  ppppp 
Resultando em: 
12066,4 0 p 
Isolando p0: 
2066,4
1
0 p 
 
22 
Logo, p0 = 0,2377. Ou seja, no estado de equilíbrio, a probabilidade de 
não haver aviões no aeroporto (no sistema) é igual a 0,2377. Substituindo o 
valor de p0 nas demais equações, temos: 
316,033,1 01  pp 
211,0889,0 02  pp 
141,05926,0 03  pp 
0939,0395,0 04  pp 
Que são as probabilidades de termos 1, 2, 3 e 4 aviões, respectivamente, 
no aeroporto. 
a) A probabilidade de as duas pistas estarem em uso é igual a 
probabilidade de termos 4 aviões no aeroporto (2 pistas em uso e 2 aviões na 
espera) mais a probabilidade de termos 3 aviões no aeroporto (2 pistas em 
uso e 1 avião na espera) mais a probabilidade de termos 2 aviões no 
aeroporto (2 pistas em uso e nenhum avião na espera). Ou seja 
4459,0234  ppp 
Ou seja, existe uma probabilidade de 0,4459 de as duas pistas estarem 
em uso (ocupadas). 
b) A probabilidade de o avião que chega não ter que esperar é igual a 
probabilidade de termos 0 aviões no aeroporto (as 2 pistas livres) somada 
com a probabilidade de termos 1 avião no aeroporto (1 pista livre). Em 
qualquer outra situação (estado), ambas as pistas estarão ocupadas. Logo 
5537,010  pp 
Ou seja, a probabilidade de um avião que chegar ao aeroporto não ter 
que esperar (encontrar pelo menos 1 pista livre) é igual a 0,5537. 
c) O número médio (esperado) de aviões no aeroporto (sistema) é dado 
por: 



4
1n
ns npL 
 
23 
Ou seja, 
5366,14321 4321  ppppLs aviões 
d) Em primeiro lugar devemos calcular: 
λeff = λ – λlost 
A taxa de perda é obtida como: 
λlost = λ.p4 = 4x0,0939 = 0,3756 aviões/hora (taxa de aviões que abortam a 
aterrissagem) 
Assim, 
λeff = λ – λlost = 4 – 0,3756 = 3,6244 aviões/hora 
Para determinar o tempo esperado até a conclusão da aterrissagem Ws 
precisamos da fórmula de Little: 
Ls = λeff Ws 
Isolando Ws: 
424,0
6244,3
5366,1

eff
s
s
L
W

 
Ou seja, o tempo esperado (médio) até a conclusão da aterrissagem é 
igual a 0,424 horas, ou 60x0,424 = 25,44 minutos (20 minutos ocupando a 
pista (1/µ) + 5,44 minutos em média à espera (Lq) – Verifique esse valor de 
5,44 a partir da fórmula de Lq). 
e) A taxa média de ocupação é dada por: 
604,0
32
6244,3





cc
c eff
 
Esse resultado mostra que em média as pistas ficaram ocupadas em 
0,604 (ou em 60,4% do tempo). Em outras palavras, a taxa de utilização das 
pistas do aeroporto é igual a 0,604, no estado de equilíbrio. Por outro lado, 
temos que as pistas ficam ociosas em 1 – 0,604 = 0,396 ou 39,6% do tempo, 
que corresponde a taxa de ociosidade da instalação (das pistas), isto é, o 
percentual de não utilização das pistas. 
 
24 
 
Exercícios – Unidade 3 
 
1) Considere o mesmo problema da Universidade, de Martin e Jane. Em 
que p e q, na primeira hierarquia, consistem nos pesos relativos dados às 
opiniões de Martin e de Jane no processo de. A segunda hierarquia usa os 
pesos p1 e p2 (para Martin) e q1 e q2 (para Jane), refletindo as preferências de 
cada um deles em relação à localização e à reputação de cada Universidade. 
Os pesos para cada Universidade segundo cada critério dado por Martin é 
representado por pij e para Jane é dado por qij, em que i = 1, 2 representa os 
critérios (localização e reputação) e j = 1, 2, 3 representa as alternativas, ou 
seja, as Universidades (Universidades A, Universidades B ou Universidades 
C). Os pesos para cada Universidade segundo cada critério dado por Martin 
é: 
 
E por Jane: 
 
Considere agora que o peso da decisão de Jane é 4 vezes maior do que 
o peso da decisão de Martin (não são mais iguais). Nesse caso, qual deve 
ser a Universidade escolhida e o seu respectivo peso composto? 
a) Universidade A, peso composto igual a 0,442. 
b) Universidade A, peso composto igual a 0,423. 
c) Universidade B, peso composto igual a 0,252. 
d) Universidade B, peso composto igual a 0,239. 
e) Universidade C, peso composto igual a 0,338. 
 
25 
Solução: 
Em primeiro lugar devemos determinar p e q. Sabemos que: 
q = 4p 
E que: 
p + q = 1 
Assim: 
p + 4p = 1 
5p = 1 
p = 1/5 = 0,2 
Com isso: 
p + q = 1 
q = 1 – p = 1 – 0,2 = 0,8 
Agora devemos calcular o peso composto para cada alternativa 
(Universidade): 
Universidade A: px(p1xp11 + p2xp21) + qx(q1xq11 + q2xq21) = 
0,2x(0,17x0,129 + 0,83x0,545) + 0,8x(0,3x0,2 + 0,7x0,5) = 0,423 
Universidade B: px(p1xp12 + p2xp22) + qx(q1xq12 + q2xq22) = 
0,2x(0,17x0,277 + 0,83x0,273) + 0,8x(0,3x0,3 + 0,7x0,2) = 0,239 
Universidade C: px(p1xp13 + p2xp23) + qx(q1xq13 + q2xq23) = 
0,2x(0,17x0,594+ 0,83x0,182) + 0,8x(0,3x0,5 + 0,7x0,3) = 0,338 
 
 
 
 
 
 
26 
Considere o seguinte enunciado para as questões 2, 3 e 4: 
O departamento de pessoal de uma empresa reduziu a procura por um 
funcionário potencial a três candidatos: Steve (S), Jane (J) e Maísa (M). A 
seleção se baseia em três critérios: entrevista pessoal (I), experiência (E) e 
referências (R). A matriz de comparação A define os pesos (importância) 
entre os três critérios. Após entrevistar os três candidatos, foram construídas 
as matrizes de comparação para cada critério (AI, AE e AR): 
 
 
2) Sobre as matrizes de comparação, é INCORRETO afirmar que: 
a) No critério de referências, Jane está 2 vezes melhor do que Steve. 
b) No critério de entrevista pessoal, Maísa está 4 vezes melhor do que 
Steve. 
c) No critério de experiência, Jane está 2 vezes pior do que Maísa. 
d) A matriz de comparação A mostra que Maísa está 5 vezes melhor do 
que Jane. 
e) A matriz de comparação A mostra que o critério entrevista pessoal é 2 
vezes mais importante do que experiência. 
 
Solução: 
A matriz de comparação A mostra a importância entre os critérios, não 
entre os candidatos. 
 
27 
3) Qual dos três candidatos deve ser escolhido e qual é o seu respectivo 
peso composto? 
a) Steve, com peso composto de 0,3686. 
b) Jane, com peso composto de 0,2792. 
c) Jane, com peso composto de 0,4104. 
d) Maísa, com peso composto de 0,3503. 
e) Maísa, com peso composto de 0,4104. 
 
Solução: 
Em primeiro lugar, devemos a matriz de comparação normalizada e os 
respectivos pesos relativos para cada matriz de comparação. 
Para a matriz de comparação A, temos que: 
Soma da coluna A: (1 + 1/2 + 4 = 5,5; 2 + 1 + 5 = 8; 1/4 + 1/5 + 1 = 1,45) 
= (5,5; 8; 1,45). 
Dividindo cada elemento pela soma da respectiva coluna (ou seja, cada 
elemento da coluna 1 dividido por 5,5, cada elemento da coluna 2 dividido por 
8 e cada elemento da coluna 3 dividido por 1,45), temos: 











69,0625,073,0
14,0125,009,0
17,025,018,0
N 
Com isso os pesos relativos para cada critério (média de cada linha) 
serão: 
2,0
3
17,025,018,0


Iw 
12,0
3
14,0125,009,0


Ew 
68,0
3
69,0625,073,0


Rw 
 
28 
Note que as referências (R) é o critério com maior peso (a entrevista é o 
segundo e a experiência é o terceiro). 
Fazendo o mesmo para as matrizes de comparação AI, AE e AR, temos: 
Soma da coluna AI: (1 + 1/3 + 1/4 = 1,58; 3 + 1 + 5 = 9; 4 + 1/5 + 1 = 5,2) 
= (1,58; 9; 5,2) 
Soma da coluna AE: (1 + 3 + 1/2 = 4,5; 1/3 + 1 + 2 = 3,3; 2 + 1/2 + 1 = 
3,5) = (4,5; 3,3; 3,5) 
Soma da coluna AR: (1 + 2 + 1 = 4; 1/2 + 1 + 2 = 3,5; 2 + 1/2 + 1 = 3,5) = 
(4; 3,5; 3,5) 
Com isso, chegamos as seguintes matrizes de comparação 
normalizadas: 











19,056,016,0
04,011,021,0
77,033,063,0
IN 











29,06,011,0
14,03,067,0
57,01,022,0
EN 











29,057,025,0
14,029,05,0
57,014,025,0
RN 
Com isso, os pesos relativos são: 
Para o critério de entrevista pessoal: 
577,0
3
77,033,063,0


ISw 
12,0
3
04,011,021,0


IJw 
303,0
3
19,056,016,0


IMw 
 
29 
Note que Steve foi o candidato mais bem avaliado nesse critério. 
Para o critério de experiência: 
297,0
3
57,01,022,0


ESw 
37,0
3
14,03,067,0


EJw 
333,0
3
29,06,011,0


EMw 
Note que Jane foi a candidata mais bem avaliada nesse critério. 
Para o critério de referências: 
32,0
3
57,014,025,0


RSw 
31,0
3
14,029,05,0


RJw 
37,0
3
29,057,025,0


RMw 
Note que Maísa foi a candidata mais bem avaliada nesse critério. 
Observe que esse problema possui apenas uma hierarquia de critério 
(contendo 3 critérios). Agora devemos calcular os pesos compostos para 
cada candidato (alternativa): 
Steve: 
3686,032,068,0297,012,0577,02,0  RSRESEISI wwwwww 
Jane: 
2792,031,068,037,012,012,02,0  RJREJEIJI wwwwww 
Maísa: 
3522,037,068,0333,012,0303,02,0  RMREMEIMI wwwwww 
Logo, o melhor candidato é o Steve, com peso composto de 0,3686. 
 
 
30 
4) A razão de consistência de cada uma das 4 matrizes de comparação 
está corretamente mostrada em: 
a) Para A, CR = 0,1; para AI, CR = 0,6; para AE, CR = 1,3 e para AR, CR 
= 1. 
b) Para A, CR = 0; para AI, CR = 1; para AE, CR = 0,6 e para AR, CR = 2. 
c) Para A, CR = 0,05; para AI, CR = 0,192; para AE, CR = 2,445 e para 
AR, CR = 1. 
d) Para A, CR = 0,0054; para AI, CR = 0,832; para AE, CR = 1,445 e para 
AR, CR = 0,25. 
e) Para A, CR = 0,0348; para AI, CR = 0,4312; para AE, CR = 1,114 e 
para AR, CR = 0,5. 
 
Solução: 
Observando as matrizes de comparação normalizadas (calculadas no 
exercício anterior), podemos notar que todas as matrizes não são 
consistentes (portanto as razões de consistência sempre darão um resultado 
maior do que 0). Para ser consistente, todas as colunas da matriz de 
comparação normalizada devem ser idênticas (como foram as matrizes N e 
NR do exemplo do Martin, dado no livro). 
Devemos então calcular a razão de consistência ou grau de consistência 
CR de cada matriz de comparação. 
Temos que: 
RI
CI
CR  
Em que: 
1
max



n
nn
CI 
n
n
RI
)2(98,1 
 
 
31 
Como todas as matrizes são 3 x 3, então n = 3 para todos os cálculos de 
CR. Assim, o valor de RI será: 
66,0
3
198,1)2(98,1





n
n
RI 
Agora, para calcular CI, precisamos do valor de nmax de cada matriz de 
comparação, calculado a partir de: 
 
Em que A é a matriz de comparação a ser considerada e w é o vetor 
média (é o vetor contendo os pesos relativos) dessa matriz de comparação. 
Para a matriz de comparação A do nosso exercício, temos o vetor média 
dado por (calculado no exercício anterior): (0,2 0,12 0,68). 
Com isso: 

































08,2
356,0
61,0
68,0
12,0
2,0
154
5/112/1
4/121
_
wA 
Resultando em: 
046,308,2356,061,0max n 
Então: 
023,0
2
046,0
13
3046,3
1
max 






n
nn
CI 
Para A temos: 
0348,0
66,0
023,0

RI
CI
CR 
Que é um nível de inconsistência aceitável (menor do que 0,1). 
Para a matriz de comparação AI temos o vetor média dado por (calculado 
no exercício anterior): (0,577 0,12 0,303). 
Com isso: 
 
32 

































0473,1
3729,0
149,2
303,0
12,0
577,0
154/1
5/113/1
431
_
wAI 
Resultando em: 
5692,30473,13729,0149,2max n 
Então: 
2846,0
2
5692,0
13
35692,3
1
max 






n
nn
CI 
Para AI temos: 
4312,0
66,0
2846,0

RI
CI
CR 
Que não é um nível de inconsistência aceitável (é maior do que 0,1). 
Para a matriz de comparação AE temos o vetor média dado por 
(calculado no exercício anterior): (0,297 0,37 0,333). 
Com isso: 

































2215,1
4275,1
0863,1
333,0
37,0
297,0
122/1
2/113
23/11
_
wAE 
Resultando em: 
7353,32215,14275,10863,1max n 
Então: 
7353,0
2
7353,0
13
37353,3
1
max 






n
nn
CI 
Para AE temos: 
114,1
66,0
7353,0

RI
CI
CR 
Que não é um nível de inconsistência aceitável (é maior do que 0,1). 
 
33 
Para a matriz de comparação AR temos o vetor média dado por 
(calculado no exercício anterior): (0,32 0,31 0,37). 
Com isso: 

































31,1
135,1
215,1
37,0
31,0
32,0
121
2/112
22/11
_
wAR 
Resultando em: 
66,331,1135,1215,1max n 
Então: 
33,0
2
66,0
13
366,3
1
max 






n
nn
CI 
Para AR temos: 
5,0
66,0
33,0

RI
CI
CR 
Que não é um nível de inconsistência aceitável (é maior do que 0,1). 
 
5) Um investidor deve decidir sobre o investimento em um dos três 
fundos: utilidade, crescimento agressivo e global.Sobre as condições do 
mercado, há uma chance de 10% de o mercado baixar, de 50% de o 
mercado manter-se moderado e de 40% de o mercado ficar em alta. A tabela 
a seguir mostra as variações percentuais no valor do investimento nas três 
condições: 
 
O retorno esperado para cada alternativa é mostrado na alternativa: 
 
34 
a) O retorno esperado para a utilidade é de 7%, para o crescimento 
agressivo é de 5% e para o global é de 7%. 
b) O retorno esperado para a utilidade é de 7,5%, para o crescimento 
agressivo é de 5% e para o global é de 10%. 
c) O retorno esperado para a utilidade é de 7,2%, para o crescimento 
agressivo é de 13,5% e para o global é de 11,7%. 
d) O retorno esperado para a utilidade é de 8,4%, para o crescimento 
agressivo é de 9,5% e para o global é de 7,1%. 
e) O retorno esperado para a utilidade é de 7%, para o crescimento 
agressivo é de 6,5% e para o global é de 10%. 
 
Solução: 
De forma geral, temos que o valor esperado de cada alternativa é dado 
por: 
niniii papapaEV  ...2211 , i = 1,2,3,...,n 
Como temos 3 (n = 3) estados da natureza (baixa, moderado, alta) e 3 (m 
= 3) alternativas (utilidade, crescimento agressivo e global), o valor esperado 
será: 
332211 papapaEV iiii  , i = 1,2,3 
Ou seja: 
2,74,085,071,053132121111  papapaEV 
5,134,0305,051,0103232221212  papapaEV 
7,114,0205,071,023332321313  papapaEV 
Assim, temos que a melhor alternativa é investirmos em crescimento 
agressivo, cujo retorno esperado é o maior (13,5% do valor investido). 
 
 
 
35 
Considere o seguinte enunciado para as questões 6, 7, 8, 9 e 10: 
Para a próxima estação de plantio, um fazendeiro pode plantar milho (a1), 
trigo (a2), ou soja (a3), ou utilizar a terra para pasto (a4). Os retornos 
associados com as diferentes ações são influenciados pela quantidade de 
chuva: grande precipitação pluvial (s1), precipitação pluvial moderada (s2), 
leve precipitação pluvial (s3) ou estação seca (s4). A matriz de retorno (em 
milhares de reais) é mostrada na matriz a seguir: 
 
6) A alternativa que expressa corretamente o valor esperado (E) de cada 
ação (1, 2, 3 e 4) e também a ação que deve ser escolhida é: 
a) E1 = 60, E2 = 50, E3 = 45 e E4 = 12. A ação a ser escolhida deve ser 
plantar milho (ação 1). 
b) E1 = 16,25, E2 = 31,25, E3 = 12,25 e E4 = 13. A ação a ser escolhida 
deve ser plantar trigo (ação 2). 
c) E1 = 65, E2 = 125, E3 = 85 e E4 = 52. A ação a ser escolhida deve ser 
plantar trigo (ação 2). 
d) E1 = 21,5, E2 = 12,5, E3 = 38,25 e E4 = 12. A ação a ser escolhida deve 
ser plantar soja (ação 3). 
e) E1 = 65, E2 = 125, E3 = 85 e E4 = 52. A ação a ser escolhida deve ser 
utilizar a terra para pasto (ação 4). 
 
Solução: 
Temos que o valor esperado de cada ação é dado por: 
 
36 
   


n
j
jii sav
n
aE
1
,
1
 
Como temos n = 4 estados da natureza (4 colunas) e m = 4 alternativas 
(ações), ou seja, 4 linhas. Temos: 
   


4
1
,
4
1
j
jii savaE 
Assim: 
      25,165306020
4
1
,
4
1 4
1
111  
j
jsavaEE 
      25,310355040
4
1
,
4
1 4
1
222  
j
jsavaEE 
      25,21104510050
4
1
,
4
1 4
1
333  
j
jsavaEE 
      1310151512
4
1
,
4
1 4
1
444  
j
jsavaEE 
Como o maior valor esperado ocorre para a ação 2, ela que deve ser 
escolhida. 
 
7) A alternativa que expressa corretamente o valor calculado através do 
critério maximin e também a ação que deve ser escolhida é: 
a) O valor calculado através do critério maximin é -20. A ação a ser 
escolhida deve ser plantar milho (ação 1). 
b) O valor calculado através do critério maximin é 0. A ação a ser 
escolhida deve ser plantar trigo (ação 2). 
c) O valor calculado através do critério maximin é -50. A ação a ser 
escolhida deve ser plantar soja (ação 3). 
 
37 
d) O valor calculado através do critério maximin é 10. A ação a ser 
escolhida deve ser utilizar a terra para pasto (ação 4). 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
Solução: 
No caso de termos uma matriz de retorno de ganho, a melhor alternativa 
segundo o critério maximin é: 
 








),(minmax ji
sa
sav
ji
 
Ou seja, devemos considerar o pior caso para cada alternativa (o valor 
mínimo de cada linha), que para a linha 1 é o -20, para a linha 2 é 0, para 
linha 3 é -50 e para linha 4 é o 10 e depois pegamos o maior dentre esses 
quatro valores (o máximo entre esses quatro valores, que é o melhor dentre a 
pior situação possível), ou seja o 10, que corresponde à ação 4. Logo, nesse 
caso, a melhor alternativa é a ação 4 (a4), que é a de utilizar a terra para 
pasto. Note que o maior valor, dentre os menores valores para cada ação 
(pior estado da natureza) ocorre para a ação 4 (na linha 4). Ou seja, estamos 
optando pela ação que é mais segura (vai ter a menor “perda” considerando 
que irá ocorrer o pior caso possível, isto é, a pior condição possível – o pior 
estado da natureza possível). 
 
8) A alternativa que expressa corretamente o valor calculado através do 
critério de Savage e também a ação que deve ser escolhida é: 
a) O valor calculado através do critério de Savage é 40. A ação a ser 
escolhida deve ser plantar milho (ação 1). 
b) O valor calculado através do critério de Savage é 15. A ação a ser 
escolhida deve ser plantar milho (ação 1). 
c) O valor calculado através do critério de Savage é 50. A ação a ser 
escolhida deve ser plantar trigo (ação 2). 
 
38 
d) O valor calculado através do critério de Savage é 0. A ação a ser 
escolhida deve ser plantar soja (ação 3). 
e) O valor calculado através do critério de Savage é 40. A ação a ser 
escolhida deve ser utilizar a terra para pasto (ação 4). 
 
Solução: 
Como a matriz de retorno é de ganho, então devemos utilizar a fórmula: 
  ),(),(),( max jijk
a
ji savsavsar
k
 
Ou seja, devemos subtrair cada elemento do máximo da coluna 
correspondente. O máximo da coluna 1 é 40, então r11 = 40 –(-20) = 60, r21 = 
40 – 40 = 0, r31 = 40 – (-50) = 90 e r41 = 40 – 12 = 28; o máximo da coluna 2 é 
100, portanto r12 = 100 – 60 = 40, r22 = 100 – 50 = 50, r32 = 100 – 100 = 0 e r42 
= 100 – 15 = 85; o máximo da coluna 3 é 45, portanto r13 = 45 – 30 = 15, r23 = 
45 – 35 = 10, r33 = 45 – 45 = 0 e r43 = 45 – 15 = 30; e o máximo da coluna 4 é 
10, portanto r14 = 10 – (-5) = 15, r24 = 10 – 0 = 10, r34 = 10 – (-10) = 20 e r44 = 
10 – 10 = 0. Com isso, temos a seguinte matriz de arrependimento: 














0308528
200090
1010500
15154060
 
Agora, devemos utilizar o critério minimax: devemos considerar o pior 
caso para cada alternativa (o maior valor de cada linha), que para a linha 1 é 
o 60, para a linha 2 é o 50, para a linha 3 é o 90 e para a linha 4 é o 85. E 
depois pegamos o menor dentre esses quatro valores (o mínimo entre esses 
quatro valores, que é o melhor dentre a pior situação possível), ou seja, o 50 
que corresponde à ação 2. Logo, nesse caso, a melhor alternativa é a ação 2 
(a2), pois é a ação que gerará o menor “arrependimento”. 
 
 
 
39 
9) Determine o valor calculado através do critério de Hurwicz e a ação 
que deve ser escolhida com: 
a) α = 1 
b) α = 0,25 
 
Solução: 
a) Com α = 1 (tomador de decisão otimista), então escolheremos a 
melhor das melhores opções. Como a matriz de retorno é de ganho, então 
escolheremos o maior dentre os maiores valores, ou seja, o 100, portanto 
escolheremos a ação 3, que consiste em plantar soja. 
Resposta: Valor calculado igual a 100, e a ação de plantar soja (ação 3) 
deve ser escolhida. 
b) Como a matriz de retorno é de ganho e fazendo α = 0,25, temos: 
   








 ),(75,0),(25,0 minmaxmax ji
s
ji
sa
savsav
jji
 
Para cada uma das ações, temos que pegar o maior valor da linha vezes 
0,25 somado com o menor valor da linha vezes 0,75, ou seja: 
Ação 1: 0,25x60 + 0,75x(-20) = 0Ação 2: 0,25x50 + 0,75x0 = 12,5 
Ação 3: 0,25x100 + 0,75x(-50) = -12,5 
Ação 4: 0,25x15 + 0,75x10 = 11,25 
Escolheremos a ação 2 (plantar trigo), pois é a maior (o máximo) dentre 
os resultados. 
Resposta: Valor calculado igual a 12,5, e a ação de plantar trigo (ação 2) 
deve ser escolhida. 
 
 
40 
10) Considere agora que a matriz de retorno do exercício seja de perda 
(agora queremos determinar a ação que minimize as perdas). Determine o 
valor calculado e a ação a ser tomada com: 
a) O critério de Laplace. 
b) O critério minimax. 
c) O critério de Savage. 
d) O critério de Hurwicz com α = 1. 
e) O critério de Hurwicz com α = 0,25. 
 
Solução: 
Agora iremos refazer os problemas, considerando a matriz de retorno 
como sendo de perda. 
a) O valor esperado já foi calculado no exercício 6: 
      25,165306020
4
1
,
4
1 4
1
111  
j
jsavaEE 
      25,310355040
4
1
,
4
1 4
1
222  
j
jsavaEE 
      25,21104510050
4
1
,
4
1 4
1
333  
j
jsavaEE 
      1310151512
4
1
,
4
1 4
1
444  
j
jsavaEE 
Como o menor valor esperado ocorre para a ação 4, ela que deve ser 
escolhida. 
Resposta: Valor calculado igual a 13 e ação a ser tomada é utilizar a 
terra para pasto (ação 4). 
 
 
41 
b) No caso de termos uma matriz de retorno de perda, a melhor 
alternativa segundo o critério minimax é: 
 








),(maxmin ji
sa
sav
ji
 
Ou seja, devemos considerar o pior caso para cada alternativa (o valor 
máximo de cada linha), que para a linha 1 é o 60, para a linha 2 é 50, para 
linha 3 é 100 e para linha 4 é o 15 e depois pegamos o menor dentre esses 
quatro valores (o mínimo entre esses quatro valores, que é o melhor dentre a 
pior situação possível), ou seja o 15, que corresponde à ação 4. Logo, nesse 
caso, a melhor alternativa é a ação 4 (a4), que é a de utilizar a terra para 
pasto. 
Resposta: Valor calculado igual a 15 e ação a ser tomada é utilizar a 
terra para pasto (ação 4). 
c) Como a matriz de retorno é de perda, então devemos utilizar a 
fórmula: 
 ),(),(),( min jk
a
jiji savsavsar
k
 
Ou seja, devemos subtrair cada elemento pelo mínimo da coluna 
correspondente. O mínimo da coluna 1 é -50, então r11 = -20 –(-50) = 30, r21 = 
40 –(-50) = 90, r31 = -50 –(-50) = 0 e r41 = 12 –(-50) = 62; o mínimo da coluna 
2 é 15, portanto r12 = 60 – 15 = 45, r22 = 50 – 15 = 35, r32 = 100 – 15 = 85 e r42 
= 15 – 15 = 0; o mínimo da coluna 3 é 15, portanto r13 = 30 – 15 = 15, r23 = 35 
– 15 = 20, r33 = 45 – 15 = 30 e r43 = 15 – 15 = 0; e o mínimo da coluna 4 é -
10, portanto r14 = -5 – (-10) = 5, r24 = 0 – (-10) = 10, r34 = -10 – (-10) = 0 e r44 = 
10 – (-10) = 20. Com isso, temos a seguinte matriz de arrependimento: 














200062
030850
10203590
5154530
 
 
42 
Agora, devemos utilizar o critério minimax: devemos considerar o pior 
caso para cada alternativa (o maior valor de cada linha), que para a linha 1 é 
o 45, para a linha 2 é o 90, para a linha 3 é o 85 e para a linha 4 é o 62. E 
depois pegamos o menor dentre esses quatro valores (o mínimo entre esses 
quatro valores, que é o melhor dentre a pior situação possível), ou seja, o 45 
que corresponde à ação 1. Logo, nesse caso, a melhor alternativa é a ação 1 
(a1), pois é a ação que gerará o menor “arrependimento”. 
Resposta: Valor calculado igual a 45 e ação a ser tomada é plantar milho 
(ação 1). 
d) Com α = 1 (tomador de decisão otimista), então escolheremos a 
melhor das melhores opções. Como a matriz de retorno é de perda, então 
escolheremos o menor dentre os menores valores, ou seja, o -50, portanto 
escolheremos a ação 3, que consiste em plantar soja. 
Resposta: Valor calculado igual a -50 e ação a ser tomada é plantar soja 
(ação 3). 
e) Como a matriz de retorno é de perda e fazendo α = 0,25, temos: 
   








 ),(75,0),(25,0 maxminmin ji
s
ji
sa
savsav
jji
 
Para cada uma das ações, temos que pegar o menor valor da linha vezes 
0,25 somado com o maior valor da linha vezes 0,75, ou seja: 
Ação 1: 0,25x(-20) + 0,75x60 = 40 
Ação 2: 0,25x0 + 0,75x50 = 37,5 
Ação 3: 0,25x(-50) + 0,75x100 = 62,5 
Ação 4: 0,25x10 + 0,75x15 = 13,75 
Escolheremos a ação 4 (utilizar a terra para pasto), pois é a menor (o 
mínimo) dentre os resultados. 
Resposta: Valor calculado igual a 13,75 e ação a ser tomada é utilizar a 
terra para pasto (ação 4). 
 
43 
 
Exercícios – Unidade 4 
 
1) Sobre a Teoria dos Jogos é correto afirmar que: 
a) Os jogadores não podem possuir um número infinito de estratégias. 
b) No caso dos jogos empresariais, as estratégias podem ser: definição 
de preços, estratégias de mercado, investimento em marketing ou em novas 
tecnologias. 
c) Para que um jogador ganhe é necessário que os demais percam. 
d) TODAS as alternativas anteriores estão CORRETAS. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
Solução: 
Os jogadores (por exemplo, empresas), possuem um número finito ou 
infinito de estratégias. 
É importante observar que para que alguém ganhe, nem sempre os 
demais devem perder. 
 
 
 
 
 
 
 
 
 
 
44 
2) Sobre a Teoria dos Jogos é correto afirmar que: 
a) Nas escolhas simultâneas, cada jogador toma as decisões sem 
conhecer as escolhas feitas pelos demais jogadores. 
b) A estratégia dominante é a melhor escolha possível para o jogador 
independente da escolha dos demais jogadores 
c) A melhor decisão individual nem sempre representa a melhor solução 
para o grupo de jogadores. 
d) TODAS as alternativas anteriores estão CORRETAS. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
Considere o seguinte enunciado para as questões 3 e 4: 
Duas empresas concorrentes (A e B) do setor alimentício planejam 
ampliar a participação no mercado. A tabela a seguir apresenta as previsões 
de lucros, em milhões de reais, referente às estratégias adotadas pelas 
empresas: 
 
3) É correto afirmar que: 
a) Caso a empresa A decida ampliar, o seu lucro passará para 7 milhões. 
b) Caso a empresa A decida ampliar, o seu lucro passará para 19 
milhões se a empresa B também ampliar. 
c) Caso ambas as empresas decidam não ampliar, os seus lucros 
passarão a ser de 5 milhões. 
 
45 
d) Caso a empresa B decida ampliar e a empresa A decida não ampliar, 
então o lucro da empresa B será de 19 milhões. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
Solução: 
O lucro da empresa A passará para 7 milhões apenas se B também 
ampliar. 
Caso a empresa A decida ampliar, o seu lucro passará para 19 milhões 
se a empresa B não ampliar. 
Caso ambas as empresas decidam não ampliar, o lucro de A será de 6 
milhões e o de B de 5 milhões. 
Caso a empresa B decida ampliar e a empresa A decida não ampliar, 
então o lucro da empresa B será de 15 milhões. 
 
4) É correto afirmar que: 
a) A estratégia dominante para ambas as empresas é ampliar. 
b) A estratégia dominante para a Empresa A é ampliar enquanto para a 
Empresa B é não ampliar. 
c) A estratégia dominante para a Empresa B é ampliar enquanto para a 
Empresa A é não ampliar. 
d) A estratégia dominante para ambas as empresas é não ampliar. 
e) Esse problema não apresenta estratégia dominante. 
 
Solução: 
Cada empresa deve observar a estratégia da concorrente para definir a 
melhor ação (estratégia) a ser tomada (ampliar ou não ampliar). A partir da 
matriz de resultados, a empresa A deve analisar as possíveis ações de B 
(ampliar ou não ampliar): se B ampliar e A também ampliar, A terá 7 milhões 
 
46 
de lucro, agora se B ampliar e A não ampliar, então A terá 5 milhões de lucro 
(nesse caso, ampliar é a melhor opção para A); agora se B não ampliar e A 
ampliar, A terá 19 milhões de lucro, e se B não ampliar e A também não 
ampliar, então A terá 6 milhões de lucro (nesse caso, a melhor opção para A 
também é ampliar). 
Para a empresa B: se A ampliar e B tambémampliar, B terá 6 milhões de 
lucro, agora se A ampliar e B não ampliar, então B terá 4 milhões de lucro 
(nesse caso, ampliar é a melhor opção para B); agora se A não ampliar e B 
ampliar, B terá 15 milhões de lucro, e se A não ampliar e B também não 
ampliar, então B terá 5 milhões de lucro (nesse caso, a melhor opção para B 
também é ampliar). 
Portanto, a estratégia dominante para ambas as empresas é ampliar a 
participação no mercado. 
 
Considere o seguinte enunciado para as questões 5 e 6: 
As empresas A e B, concorrentes entre si, atuam no ramo de telhas, 
podendo optar entre produzir telhas de maior ou de menor qualidade. Os 
lucros, em milhares de reais, referentes a cada estratégia são apresentados a 
seguir: 
 
 
 
 
 
 
 
47 
5) É coreto afirmar que: 
a) Caso a empresa A produza telhas de maior qualidade, o seu lucro será 
de 20 mil. 
b) Caso a empresa A produza telhas de maior qualidade, o seu lucro será 
de 110 mil se a empresa B produzir telhas de menor qualidade. 
c) Se ambas as empresas produzirem telhas de maior qualidade o lucro 
da empresa B será de 30 mil. 
d) Se a empresa B produzir telhas de menor qualidade enquanto a 
empresa A produzir telhas de maior qualidade, então o lucro da empresa B 
será de 840 mil. 
e) Se ambas as empresas produzirem telhas de maior qualidade os seus 
lucros passarão a ser de 60 mil. 
 
Solução: 
O lucro da empresa A será de 20 mil apenas se a empresa B também 
produzir telhas de maior qualidade. 
Caso a empresa A produza telhas de maior qualidade, o seu lucro será 
de 960 mil se a empresa B produzir telhas de menor qualidade. 
Se a empresa B produzir telhas de menor qualidade enquanto a empresa 
A produzir telhas de maior qualidade, então o lucro da empresa B será de 
500 mil. 
Se ambas as empresas produzirem telhas de menor qualidade os seus 
lucros passarão a ser de 60 mil. 
 
 
 
 
 
 
48 
6) É correto afirmar que: 
a) A estratégia dominante para ambas as empresas é produzir telhas de 
maior qualidade. 
b) A estratégia dominante para a Empresa A é produzir telhas de maior 
qualidade enquanto para a Empresa B é produzir telhas de menor qualidade. 
c) A estratégia dominante para a Empresa B é produzir telhas de maior 
qualidade enquanto para a Empresa A é produzir telhas de menor qualidade. 
d) A estratégia dominante para ambas as empresas é produzir telhas de 
menor qualidade. 
e) Esse problema não apresenta estratégia dominante. 
 
Solução: 
Cada empresa deve observar a estratégia da concorrente para definir a 
melhor ação (estratégia) a ser tomada (maior qualidade ou menor qualidade). 
A partir da matriz de resultados, a empresa A deve analisar as possíveis 
ações de B (maior qualidade ou menor qualidade): se B escolher maior 
qualidade e A também escolher maior qualidade, A terá 20 mil de lucro, agora 
se B escolher maior qualidade e A escolher menor qualidade, então A terá 
110 mil de lucro (nesse caso, menor qualidade é a melhor opção para A); 
agora se B escolher menor qualidade e A escolher maior qualidade, A terá 
960 mil de lucro, e se B escolher menor qualidade e A também escolher 
menor qualidade, então A terá 60 mil de lucro (nesse caso, a melhor opção 
para A é escolher maior qualidade). 
Para a empresa B: se A escolher maior qualidade e B também escolher 
maior qualidade, B terá 30 mil de lucro, agora se A escolher maior qualidade 
e B escolher menor qualidade, então B terá 500 mil de lucro (nesse caso, 
escolher menor qualidade é a melhor opção para B); agora se A escolher 
menor qualidade e B escolher maior qualidade, B terá 840 mil de lucro, e se A 
escolher menor qualidade e B também escolher menor qualidade, então B 
terá 60 mil de lucro (nesse caso, a melhor opção para B é escolher maior 
qualidade). 
 
49 
Portanto, Esse problema não apresenta estratégia dominante, ou seja, 
não possui solução de equilíbrio. 
 
Considere a seguinte matriz de retorno de para o jogador A, de um jogo 
de soma zero com duas pessoas, para as questões 7 e 8: 
 
7) É correto afirmar que: 
a) Caso o jogador A escolha a estratégia A3 e o jogador B escolha a 
estratégia B2 então o jogador B terá 7 de retorno. 
b) Caso o jogador A escolha a estratégia A4 e o jogador B escolha a 
estratégia B3 então o jogador A terá 9 de retorno. 
c) Caso o jogador A escolha a estratégia A1 e o jogador B escolha a 
estratégia B4 então o jogador B terá 6 de retorno. 
d) Caso o jogador A escolha a estratégia A2 e o jogador B escolha a 
estratégia B3 então o jogador B terá 9 de retorno. 
e) O menor retorno possível para o jogador B é -9. 
 
Solução: 
Caso o jogador A escolha a estratégia A3 e o jogador B escolha a 
estratégia B2 então o jogador B terá -7 de retorno (ou o A terá 7 de retorno). 
Caso o jogador A escolha a estratégia A4 e o jogador B escolha a 
estratégia B3 então o jogador A terá -9 de retorno (ou o jogador B terá 9 de 
retorno). 
 
50 
Caso o jogador A escolha a estratégia A1 e o jogador B escolha a 
estratégia B4 então o jogador B terá -6 de retorno (ou o jogador A terá 6 de 
retorno). 
O menor retorno possível para o jogador B é 7 (que é o valor máximo da 
matriz de retorno), ou então o menor retorno possível para o jogador A é -9 
(que é o valor mínimo da matriz de retorno). 
 
8) Assinale a alternativa que apresenta a solução de ponto de sela e o 
valor do jogo. 
a) A solução de ponto de sela é (A2, B2) e o valor do jogo é -4. 
b) A solução de ponto de sela é (A1, B3) e o valor do jogo é -5. 
c) A solução de ponto de sela é (A2, B4) e o valor do jogo é -2. 
d) A solução de ponto de sela é (A4, B4) e o valor do jogo é 5. 
e) A solução de ponto de sela é (A3, B2) e o valor do jogo é 7. 
 
Solução: 
Nesse tipo de jogo, a solução é baseada no princípio de garantir o melhor 
do pior para cada jogador. Note que, se A escolher a estratégia A1 então 
independente da estratégia de B, o pior que pode acontecer é A perder 5 
para B. Esse valor é o valor mínimo das entradas da linha 1. Se A escolher a 
estratégia A2 então o pior que pode acontecer é A perder 9 para B (mínimo 
da linha 2). Se A escolher a estratégia A3 então o pior que pode acontecer é 
A perder 9 para B (mínimo da linha 3). Se A escolher a estratégia A4 então o 
pior que pode acontecer é A perder 9 para B (mínimo da linha 4). Para 
conseguir o melhor do pior, o jogador A deve escolher a melhor dessas 
“piores” estratégias (o valor máximo entre -5, -9, -9 e -9), que corresponde ao 
valor de -5 obtido com a estratégia A1. 
Agora vamos considerar a estratégia do jogador B. Como a matriz de 
retorno dada é para o jogador A, quanto menor for o valor da matriz de 
retorno, maior é a perda de A (e portanto maior é o ganho de B). Isso significa 
 
51 
que o melhor do pior para B requer pegar o menor (mínimo) dentre os 
maiores valores, ou seja, utilizaremos o “critério minimax”. Temos que se B 
escolher a estratégia B1 então independente da estratégia de A, o pior que 
pode acontecer é B perder 7 para A. Esse valor é o valor máximo das 
entradas da coluna 1. Se B escolher a estratégia B2 então o pior que pode 
acontecer é B perder 7 para A (máximo da coluna 2). Se B escolher a 
estratégia B3 então o pior que pode acontecer é B ganhar 5 de A (máximo da 
coluna 3). Se B escolher a estratégia B4 então o pior que pode acontecer é B 
perder 6 para A (máximo da coluna 4). Para conseguir o melhor do pior, 
jogador B deve escolher a melhor dessas “piores” estratégias (o valor mínimo 
entre 7, 7, -5 e 6), que corresponde ao valor de -5 obtido com a estratégia B3. 
A solução ótima do jogo recomenda que os jogadores selecionem as 
estratégias A1 e B3. Note que o retorno irá favorecer o jogador B, fazendo 
com que ele ganhe 5 (ou seja, o jogador A irá perder 5 para o jogador B). Isso 
significa que o valor do jogo é de -5. 
Observe que a posição da entrada (ou o ponto) obtida com o critério 
maximin (A1, B3) foi a mesma obtida com o critério minimax(A1, B3). Nesse 
caso, dizemos que A e B estão usando uma solução de ponto de sela. 
 
Considere a seguinte matriz de retorno de para o jogador A, de um jogo 
de soma zero com duas pessoas, para as questões 9 e 10: 
 
9) Determine o valor de p e de q que farão a entrada (A2, B2) ser uma 
solução de ponto de sela. 
 
Solução: 
 
52 
Para o jogador A temos: o mínimo da linha 1 é 1 ou q, o mínimo da linha 
2 é p ou 5 e o mínimo da linha 3 é o 2. Portanto temos que escolher o maior 
dentre essas menores entradas (1 ou q, p ou 5 e 2). Para que o 5 seja a 
menor entrada da linha 2, o valor de p deve ser maior do que 5 (com isso o 5 
será o menor valor da linha 2). Para que a entrada (A2, B2) seja um ponto de 
sela, devemos escolher o 5, dentre os menores valores (o 5 deve ser o maior 
valor). Para qualquer que seja o valor de q iremos escolher o 5 como o maior 
valor (se q for maior do que 1, escolheremos o valor 1 na linha 1, o que fará 
com que o 5 seja escolhido; se q menor do que 1, escolheremos o q na linha 
1 o que também fará com que o 5 seja a entrada escolhida). 
Para o jogador B temos: o máximo da coluna 1 é p ou 6, o máximo da 
coluna 2 é q ou 5 e o máximo da coluna 3 é o 10. Portanto temos que 
escolher o menor dentre essas maiores entradas (p ou 6, q ou 5 e 10). Como 
sabemos que p é maior do que 5 então ele nunca será a entrada escolhida 
(nunca será menor do que 5). Para que o 5 seja a maior entrada da coluna 2, 
o q deve ser menor do que 5 (com isso o 5 será escolhido no lugar do q). 
Assim o menor valor entre p (que é maior do que 5), 5 e 10 será o 5. 
Resposta: Para que a entrada (A2, B2) seja um ponto de sela, é preciso p 
seja maior do que 5 e q seja menor do que 5. 
10) Determine a solução de ponto de sela caso o valor de p seja igual a 3 
e o valor de q seja igual a 2. 
 
Solução: 
Para o jogador A temos: o mínimo da linha 1 é 1, o mínimo da linha 2 é 3 
e o mínimo da linha 3 é 2. Portanto temos que escolher o maior dentre essas 
menores entradas (1, 3 e 2), que é o 3, que corresponde à estratégia A2. 
Para o jogador B temos: o máximo da coluna 1 é 6, o máximo da coluna 
2 é 5 e o máximo da coluna 3 é 10. Portanto temos que escolher o menor 
dentre essas maiores entradas (6, 5 e 10) que é o 5, que corresponde à 
estratégia B2. 
 
53 
Resposta: Como o valor obtido com o critério maximin (3) é diferente do 
valor obtido com o critério minimax (5) então esse jogo não possui solução de 
ponto de sela. 
 
54 
 
Exercícios – Unidade 5 
 
1) Sobre os principais problemas de Pesquisa Operacional que podem 
ser modelados e resolvidos como redes e o algoritmo utilizado para a 
solução, é correto afirmar que: 
a) A árvore geradora mínima determina o caminho mais curto entre duas 
localidades. 
b) O algoritmo (ou método) de caminho mais curto calcula a capacidade 
máxima (em toneladas por ano) de uma tubulação de lama de carvão. 
c) O algoritmo de caminho crítico (CPM – Critical Path Method) auxilia na 
construção de um cronograma (envolvendo as datas das atividades) para um 
projeto de construção civil. 
d) TODAS as alternativas anteriores estão CORRETAS. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
2) Sobre os elementos de uma rede, é INCORRETO afirmar que: 
a) Uma rede consiste de um conjunto de nós (ou vértices) conectados 
por arcos (ou ramos). 
b) Existe um fluxo associado a cada rede, o qual é limitado pela 
capacidade de seus arcos. 
c) Um caminho é uma sequência de arcos distintos ligando dois nós, 
passando por outros nós, independentemente da direção de fluxo de cada 
arco. 
d) Um caminho forma um ciclo ou um loop se formar um caminho de um 
nó para ele mesmo, passando por outros nós. 
e) Uma árvore é uma rede conectada com ciclos, ou seja, ela é um 
subconjunto de todos os nós. 
 
55 
Solução: 
O correto seria: Uma árvore é uma rede conectada SEM ciclos, ou seja, 
ela é um subconjunto de todos os nós. 
 
3) Considere uma rede contendo 5 nós (A, B, C, D e E), cujas ligações 
são mostradas a seguir: 
 
É afirmado que: 
I- É uma rede orientada. 
II- É uma rede conectada. 
III- É uma árvore. 
IV- É uma árvore geradora. 
São corretas as afirmações: 
a) I e II, apenas. 
b) III e IV, apenas. 
c) I, III, apenas. 
d) I, II e III, apenas. 
e) I, II, III e IV. 
Solução: 
Ela não é uma rede conectada, pois o nó B não está conectado à rede 
(todos os nós deveriam estar conectados à rede para ela ser “conectada”). 
 
56 
Ela não é uma árvore geradora, pois o nó B não está presente na árvore 
(a árvore deve ligar todos os nós da rede para ser uma árvore geradora). 
 
4) Considere a rede a seguir, que mostra a distancia em km entre 
diferentes cidades: 
 
Assinale a alternativa que apresenta o comprimento total mais curto 
ligando todos os nós (árvore geradora mínima): 
a) 12 km. 
b) 14 km. 
c) 16 km. 
d) 18 km. 
e) 20 km. 
Solução: 
Etapa k = 0 
0C 
},,,,,,{ TEDCBAOCo  
Etapa k = 1 
}{1 OC  
},,,,,{1 TEDCBAC  
 
57 
Agora devemos entrar na etapa k = 2, que consiste em escolhermos o nó 
não conectado que resulte no menor arco com o nó da etapa anterior (nó O). 
Essa distância é de 2 km, ligando o nó O ao nó A. Assim: 
},{2 AOC  
},,,,{2 TEDCBC  
Além disso, o arco (O, A) de 2 km é uma conexão permanente. 
Agora devemos entrar na etapa k = 3, que consiste em escolhermos o nó 
não conectado que resulte no menor arco com um nó conectado (nó O ou A). 
Essa distância é de 2 km, ligando o nó A ao nó B. Assim: 
},,{3 BAOC  
},,,{3 TEDCC  
Além disso, o arco (A, B) de 2 km é uma conexão permanente. 
Agora devemos entrar na etapa k = 4, que consiste em escolhermos o nó 
não conectado que resulte no menor arco com um nó conectado (nó O ou A 
ou B). Essa distância é de 1 km, ligando o nó B ao nó C. Assim: 
},,,{4 CBAOC  
},,{4 TEDC  
Além disso, o arco (B, C) de 1 km é uma conexão permanente. 
Agora devemos entrar na etapa k = 5, que consiste em escolhermos o nó 
não conectado que resulte no menor arco com um nó conectado (nó O ou A 
ou B ou C). Essa distância é de 3 km, ligando o nó B ao nó E. Assim: 
},,,,{5 ECBAOC  
},{5 TDC  
Além disso, o arco (B, E) de 3 km é uma conexão permanente. 
Agora devemos entrar na etapa k = 6, que consiste em escolhermos o nó 
não conectado que resulte no menor arco com um nó conectado (nó O ou A 
ou B ou C ou E). Essa distância é de 1 km, ligando o nó E ao nó D. Assim: 
 
58 
},,,,,{6 EDCBAOC  
}{6 TC  
Além disso, o arco (E, D) de 1 km é uma conexão permanente. 
Por fim, devemos entrar na etapa k = 7, que consiste em escolhermos o 
nó não conectado (nó T) que resulte no menor arco com um nó conectado 
(nó O ou A ou B ou C ou D ou E). Essa distância é de 5 km, ligando o nó D 
ao nó T. Assim: 
},,,,,,{7 TEDCBAOC  
7C 
Além disso, o arco (D, T) de 5 km é uma conexão permanente. 
As ligações permanentes obtidas em cada etapa: (O, A), (A, B), (B, C), 
(B, E), (E, D) e (D, T) formam a nossa árvore geradora mínima, como 
mostrada a seguir (as conexões permanentes estão destacadas): 
 
O comprimento total mais curto é igual a soma dos comprimentos das 
conexões permanentes (soma dos comprimentos (distância) presente em 
cada arco que forma a árvore geradora mínima). Ou seja, 2 + 2 + 1 + 3 + 1 + 
5 = 14 km. 
 
 
 
 
59 
5) A rede a seguir apresenta as distâncias entre as cidades em km: 
 
Assinale a alternativa que apresente a menor distância (ou seja, o 
comprimento da menor rota) ligando a Cidade 4 à Cidade 8: 
a) A distância mais curta entre as Cidades 4 e 8 é igual a 7 km. 
b) A distância mais curta entre as Cidades 4 e 8 é igual a 8 km. 
c) A distância mais curta entre as Cidades 4 e 8 é igual a 9 km. 
d) A distância mais curta entre as Cidades 4 e 8 é igual a 10 km. 
e) A distância mais curta entre as Cidades 4 e 8 é igual a 11 km. 
Solução: 
Nesse tipo de problema (do caminho mínimo) devemos aplicar o 
algoritmo de Dijkstra (menordistância entre um nó de origem a um nó de 
destino). 
Etapa 0: devemos rotular o nó de origem (nó 4) como um rótulo 
permanente [0, –]. Em seguida devemos fazer i = 1. 
Etapa 1: devemos pegar o nó marcado como permanente na etapa 
anterior (nó 4). Observe que podemos alcançar os nós 5, 6 e 7 a partir do nó 
4 (que é o último nó rotulado como permanente). Assim, devemos somar a 
distância até o nó 4 (que vale 0, pois é o nó de origem) com a distância até 
cada um dos nós (para o nó 5, para o nó 6 e para o nó 7) que podem ser 
alcançados a partir do nó 4. Esses nós devem ser rotulados como 
temporários. A tabela a seguir resume essa etapa: 
 
 
60 
Nó Rótulo Status 
4 [0, –] Permanente 
5 [0 + 3, 4] = [3, 4] Temporário 
6 [0 + 6, 4] = [6, 4] Temporário 
7 [0 + 8, 4] = [8, 4] Temporário 
 
Agora devemos escolher a menor distância entre os rótulos temporários 
(que é o 5u 3), tornando esse nó permanente (o nó 5, destacado na tabela 
anterior, passará a ser permanente na próxima etapa). 
Etapa 2: devemos pegar o nó marcado como permanente na etapa 
anterior (nó 5). Observe que podemos alcançar os nós 6 e 7 a partir do nó 5 
(que é o último nó rotulado como permanente). Assim, devemos somar a 
distância até o nó 5 (que vale 3) com a distância até cada um dos nós (para o 
nó 6 e para o nó 7) que podem ser alcançados a partir do nó 5. Esses nós 
devem ser rotulados como temporários. A tabela a seguir resume essa etapa: 
Nó Rótulo Status 
4 [0, –] Permanente 
5 [3, 4] Permanente 
6 
[3 + 3, 5] = [6, 5] 
ou [6, 4] 
Temporário 
7 [0 + 8, 4] = [8, 4] Temporário 
 
Note que temos duas opções para alcançar o nó 6 (a partir do nó 4 
diretamente, ou a partir do nó 4 passando pelo nó 5). Observe também que o 
rótulo [8, 4] não foi alterado (pois a distância ligando o nó 4 ao nó 7 passando 
pelo nó 5 é igual a 3 + 7 = 10, que é maior do que a distância de 8 ligando o 
nó 4 diretamente ao nó 7). 
 
61 
Devemos escolher a menor distância entre os rótulos (que é o 6u 6), 
tornando esse nó permanente (o nó 6, destacado na tabela anterior, passará 
a ser permanente na próxima etapa). 
Etapa 3: devemos pegar o nó marcado como permanente na etapa 
anterior (nó 6). Observe que podemos alcançar os nós 7 e 8 a partir do nó 6 
(que é o último nó rotulado como permanente). Assim, devemos somar a 
distância até o nó 6 (que vale 6) com a distância até cada um dos nós (para o 
nó 7 e para o nó 8) que podem ser alcançados a partir do nó 6. Esses nós 
devem ser rotulados como temporários. A tabela a seguir resume essa etapa: 
Nó Rótulo Status 
4 [0, –] Permanente 
5 [3, 4] Permanente 
6 [6, 5] ou [6, 4] Permanente 
7 [8, 4] Temporário 
8 [6 + 2, 6] = [8, 6] Temporário 
 
Podemos escolher qualquer um dos dois nós (7 ou 8) que os rótulos não 
serão alterados (pois já apresentam a menor distância possível). Temos que 
a menor distância ligando o nó 4 ao nó 8 é igual a 8 km. Olhando para a 
última tabela, vemos que o nó 8 está ligado ao no 6 (o nó 6 está presente no 
rótulo do no 8). E do nó 6 para o nó 4 a distância é igual a 6 km tanto indo 
diretamente para o nó 4 quanto indo para o nó 4 passando pelo nó 5. Logo, o 
caminho mínimo ligando o nó 4 ao nó 8 pode ser tanto o caminho 4-5-6-8 
quanto o caminho 4-6-8. 
 
 
 
 
 
 
62 
6) Considere a rede a seguir: 
 
Assinale a alternativa que apresente o fluxo máximo para essa rede. 
a) 28 
b) 27 
c) 26 
d) 25 
e) 24 
Solução: 
Iteração 1: 
Iguale as capacidades residuais iniciais às capacidades iniciais, isto é, 
faça ),(),( jiijjiij CCcc  . 
Etapa 1: Faça a1 = ∞ e rotule o nó 1 com rótulo [∞, –]. Faça i = 1. 
Etapa 2: os nós que não foram rotulados e podem ser alcançados do nó 
1 são os nós S1 = {2,3,5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: os fluxos residuais do nó 1 para cada um dos nós de S1 = 
{2,3,5} são {14, 8, 4}. O máximo (o maior valor) corresponde ao arco ligando 
o nó 1 ao nó 3, isto é, o arco (1, 3). Portanto, k = 3. Com isso, devemos 
rotular o nó k = 3 com [14, 1]. Faça i = k = 3 e volte à etapa 2. 
 
63 
Etapa 2: agora, os nós que não foram rotulados e podem ser alcançados 
do nó 3 são os nós S3 = {2,4,5}, que é  , portanto seguiremos para etapa 
3. 
Etapa 3: os fluxos residuais do nó 3 para cada um dos nós de S3 = 
{2,4,5} são {10, 9, 10}. O máximo (o maior valor) corresponde ao arco ligando 
o nó 3 ao nó 2 (o nó de menor índice), isto é, o arco (3, 2). Portanto, k = 2. 
Com isso, devemos rotular o nó k = 2 com [10, 3]. Faça i = k = 2 e volte à 
etapa 2. 
Etapa 2: agora, os nós que não foram rotulados e podem ser alcançados 
do nó 2 são os nós S2 = {4,5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: os fluxos residuais do nó 2 para cada um dos nós de S2 = {4,5} 
são {7, 6}. O máximo (o maior valor) corresponde ao arco ligando o nó 2 ao 
nó 4, isto é, o arco (2, 4). Portanto, k = 4. Com isso, devemos rotular o nó k = 
4 com [7, 2]. Faça i = k = 4 e volte à etapa 2. 
Etapa 2: agora, os nós que não foram rotulados e podem ser alcançados 
do nó 4 são os nós S4 = {5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: os fluxos residuais do nó 4 para cada um dos nós de S4 = {5} 
são {5}. O máximo (o maior valor) corresponde ao arco ligando o nó 4 ao nó 
5, isto é, o arco (4, 5). Portanto, k = 5. Com isso, devemos rotular o nó k = 5 
com [5, 4]. Faça i = k = 5. Como k = n = 5, então o nó sorvedouro foi rotulado 
e uma rota de passagem foi encontrada. Nesse caso, iremos para a etapa 5. 
Etapa 5: Temos N1 = {1,2,3,4,5} (são os nós da rota de passagem 1). O 
fluxo ótimo dessa rota de passagem 1f é igual ao valor mínimo entre os 
rótulos presentes nessa rota, ou seja, 5}5,7,10,14,min{1 f . A figura a 
seguir resume as etapas dessa iteração (destacando a rota 1): 
 
64 
 
Além disso, temos que as capacidades residuais ao longo da rota 1 são: 
)5,9()50,514(),(),( 1311133113  fcfccc 
)10,5()55,510(),(),( 1231322332  fcfccc 
)11,2()56,57(),(),( 1421244224  fcfccc 
)5,0()50,55(),(),( 1541455445  fcfccc 
Devemos fazer essas alterações das capacidades residuais na rede 
original, resultando em: 
 
 
65 
Iteração 2: 
Etapa 2: os nós que não foram rotulados e podem ser alcançados do nó 
1 são os nós S1 = {2,3,5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: O máximo (o maior valor) corresponde ao arco ligando o nó 1 
ao nó 3, isto é, o arco (1, 3). Portanto, k = 3. Com isso, devemos rotular o nó 
k = 3 com [9, 1]. Faça i = k = 3 e volte à etapa 2. 
Etapa 2: Temos S3 = {2,4,5}, que é  , portanto seguiremos para 
etapa 3. 
Etapa 3: O máximo (o maior valor) corresponde ao arco ligando o nó 3 
ao nó 5, isto é, o arco (3, 5). Portanto, k = 5. Com isso, devemos rotular o nó 
k = 5 com [10, 3]. Faça i = k = 3 e volte à etapa 2. Como k = n = 5, então o nó 
sorvedouro foi rotulado e uma rota de passagem foi encontrada. Nesse caso, 
iremos para a etapa 5. 
Etapa 5: Temos N2 = {1,3,5} (são os nós da rota de passagem 2). O fluxo 
ótimo dessa rota de passagem 2f é igual ao valor mínimo entre os rótulos 
presentes nessa rota, ou seja, 9}10,9,min{2 f . A figura a seguir 
resume as etapas dessa iteração (destacando a rota 2): 
 
 
 
66 
Além disso, temos que as capacidades residuais ao longo da rota 2 são: 
)14,0()95,99(),(),( 2312133113  fcfccc 
)9,1()90,910(),(),( 2532355335  fcfccc 
Devemos fazer essas alterações das capacidades residuais na rede 
anterior, resultando em: 
 
Iteração 3: 
Etapa 2: os nós que não foram rotulados e podem ser alcançados do nó 
1 são os nós S1 = {2,5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: O máximo (o maior valor) corresponde ao arco (1, 2). Portanto, 
devemos rotular o nó k = 2 com [8, 1]. Faça i = k = 2 e volte à etapa 2. 
Etapa 2: os nós que não foram rotulados e podem ser alcançados do nó 
2 são os nós S2 = {3,4,5}, que é  , portanto seguiremos para etapa 3. 
Etapa3: O máximo (o maior valor) corresponde ao arco (2, 3). Portanto, 
devemos rotular o nó k = 3 com [10, 2]. Faça i = k = 3 e volte à etapa 2. 
Etapa 2: os nós que não foram rotulados e podem ser alcançados são os 
nós S3 = {4,5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: O máximo (o maior valor) corresponde ao arco (3, 4). Portanto, 
devemos rotular o nó k = 4 com [9, 3]. Faça i = k = 4 e volte à etapa 2. 
 
67 
Etapa 2: os nós que não foram rotulados e podem ser alcançados são os 
nós S4 =  , portanto seguiremos para etapa 4. 
Etapa 4: Rota inversa. O rótulo [9, 3] do nó 4 indica que o nó que foi 
rotulado imediatamente antes foi o nó r = 3. Nesse caso, devemos eliminar o 
rótulo [9, 3] do nó 4, e fazer i = r = 3. Volte para a etapa 2. 
Etapa 2: agora, os nós que não foram rotulados e podem ser alcançados 
do nó 2 são os nós S2 = {5} (pois o nó 4 foi eliminado na etapa da rota 
inversa), que é  , portanto seguiremos para etapa 3. 
Etapa 3: O máximo (o maior valor) corresponde ao arco (3, 5). Portanto, 
devemos rotular o nó k = 5 com [1, 3]. Como k = n = 5, então o nó sorvedouro 
foi rotulado e uma rota de passagem foi encontrada. Nesse caso, iremos para 
a etapa 5. 
Etapa 5: Temos N3 = {1,2,3,5}.O fluxo ótimo dessa rota de passagem 3f 
é igual ao valor mínimo entre os rótulos presentes nessa rota, ou seja, 
1}1,10,8,min{3 f . A figura a seguir resume as etapas dessa iteração 
(destacando a rota 3): 
 
Além disso, temos que as capacidades residuais ao longo da rota 3 são: 
)1,7()10,18(),(),( 3213122112  fcfccc 
 
68 
)6,9()15,110(),(),( 3323233223  fcfccc 
)10,0()19,11(),(),( 3533355335  fcfccc 
Devemos fazer essas alterações das capacidades residuais na rede 
anterior, resultando em: 
 
Iteração 4: 
Etapa 2: os nós que não foram rotulados e podem ser alcançados do nó 
1 são os nós S1 = {2,5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: O máximo (o maior valor) corresponde ao arco (1, 2). Portanto, 
devemos rotular o nó k = 2 com [7, 1]. Faça i = k = 2 e volte à etapa 2. 
Etapa 2: os nós que não foram rotulados e podem ser alcançados são os 
nós S2 = {3,4,5}, que é  , portanto seguiremos para etapa 3. 
Etapa 3: Observe que se fossemos para o nó 3 ou para o nó 4 a 
capacidade residual para o nó 5 é igual a 0 (portanto entraríamos na etapa 4 
da rota inversa). A única ligação possível é através do arco (2,5). Portanto, 
devemos rotular o nó k = 5 com [6, 2]. Como k = n = 5, então o nó sorvedouro 
foi rotulado e uma rota de passagem foi encontrada. Nesse caso, iremos para 
a etapa 5. 
Etapa 5: Temos N4 = {1,2,5}.O fluxo ótimo dessa rota de passagem 4f é 
igual ao valor mínimo entre os rótulos presentes nessa rota, ou seja, 
 
69 
6}6,7,min{4 f . A figura a seguir resume as etapas dessa iteração 
(destacando a rota 4): 
 
Além disso, temos que as capacidades residuais ao longo da rota 4 são: 
)7,1()61,67(),(),( 4214122112  fcfccc 
)6,0()60,66(),(),( 4524255225  fcfccc 
Devemos fazer essas alterações das capacidades residuais na rede 
anterior, resultando em: 
 
 
70 
Iteração 5: 
Temos agora que a única rota possível é através do arco (1,5). Portanto 
temos que aplicar o rótulo [4, 1] ao nó 5. E que 5f = 4, como mostrado a 
seguir. 
 
As capacidades residuais ao longo da rota 5 são: 
)4,0()40,44(),(),( 5515155115  fcfccc 
Devemos fazer essas alterações das capacidades residuais na rede 
anterior, resultando em: 
 
 
71 
Note que não existem mais rotas de passagem (não é possível chegar ao 
nó 5 partindo do nó 1). Logo, podemos ir para a etapa 6. 
Etapa 6: Solução 
O fluxo máximo da rede é dado por (é igual a soma dos fluxos ótimos de 
cada rota de passagem obtido em cada iteração): 
254619554321  fffffF 
O fluxo ótimo de cada arco é calculado como: 
  ),(, jijiijij cCcC  
Em que ),( jiij CC são as capacidades residuais iniciais (dadas na rede 
original do problema) e ),( jiij cc são as capacidades residuais finais (dadas 
na última rede obtida na iteração 5). Lembrando que, Se 0 então o fluxo 
ótimo no arco (i, j) vai de i para j e é igual a  . Caso contrário, se 0 , o 
fluxo ótimo do arco (i, j) vai de j para i e é igual a  . Os fluxos ótimos de 
cada arco são mostrados na tabela a seguir: 
Arco   ),(, jijiijij cCcC  
Fluxo dos 
Arcos 
Direção 
(1,2) (8 – 1, 0 – 7) = (7, – 7) 7 1 -> 2 
(1,3) (14 – 0, 0 – 14) = (14, – 14) 14 1 -> 3 
(1,5) (4 – 4, 0 – 4) = (4, – 4) 4 1 -> 5 
(2,3) (5 – 9, 10 – 6) = (– 4, 4) 4 3 -> 2 
(2,4) (7 – 2, 6 – 11) = (5, – 5) 5 2 -> 4 
(2,5) (6 – 0, 0 – 6) = (6, – 6) 6 2 -> 5 
(3,4) (9 – 9, 7 – 7) = (0, 0) 0 – 
(3,5) (10 – 0, 0 – 10) = (10, – 10) 10 3 -> 5 
(4,5) (5 – 0, 0 – 5) = (5, – 5) 5 5 -> 5 
Note que se fizermos um corte perpendicular na rede original próximo do 
nó 5, teremos um fluxo de 10 + 4 + 6 + 5 = 25. 
 
72 
Considere a rede de projeto a seguir para as questões 7 e 8: 
 
Cada arco representa a duração em dias de uma atividade. 
7) Calcule o caminho crítico. Assinale a alternativa que apresente as 
atividades críticas desse projeto. 
a) Atividades (1, 3), (3, 4), (5, 6) e (6, 7). 
b) Atividades (1, 3), (3, 4), (4, 6) e (6, 7). 
c) Atividades (1, 3), (3, 5), (5, 6) e (6, 7). 
d) Atividades (1, 2), (2, 4), (5, 6) e (6, 7). 
e) Atividades (1, 2), (2, 4) e (4, 7). 
Solução: 
Em primeiro lugar devemos aplicar o forward pass em todos os nós, 
partindo do nó 1. 
Forward Pass 
Nó 1: devemos fazer □1 = 0 
Nó 2: só podemos alcançar o nó 2 a partir do nó 1, portanto □2 = □1 + 
12D = 0 + 2 = 2. Ou seja, a maior distância ligando o nó 1 ao nó 2 é igual a 2. 
Nó 3: só podemos alcançar o nó 3 a partir do nó 1, portanto □3 = □1 + 
13D = 0 + 3 = 3. Ou seja, a maior distância ligando o nó 1 ao nó 3 é igual a 3. 
Nó 4: podemos alcançar o nó 4 a partir do nó 2 e de nó 3, portanto □4 = 
max{ □2 + 24D , □3 + 34D } = max{2 + 2, 3 + 3} = max{4, 6} = 6. Ou seja, a 
maior distância ligando o nó 1 ao nó 4 é igual a 6, passando pelo nó 3. 
 
73 
Nó 5: podemos alcançar o nó 5 a partir do nó 3 e de nó 4, portanto □5 = 
max{ □3 + 35D , □4 + 45D } = max{3 + 2, 6 + 0} = max{5, 6} = 6. Ou seja, a 
maior distância ligando o nó 1 ao nó 5 é igual a 6, passando pelo nó 4. 
Nó 6: podemos alcançar o nó 6 a partir do nó 4 e de nó 5, portanto □6 = 
max{ □4 + 46D , □5 + 56D } = max{6 + 3, 6 + 7} = max{9, 13} = 13. Ou seja, a 
maior distância ligando o nó 1 ao nó 6 é igual a 13, passando pelo nó 5. 
Nó 7: podemos alcançar o nó 7 a partir do nó 4, do nó 5 e de nó 6, 
portanto □7 = max{ □4 + 47D , □5 + 57D , □6 + 67D } = max{6 + 2, 6 + 5, 13 
+ 6} = max{8, 11, 19} = 19. Ou seja, a maior distância ligando o nó 1 ao nó 7 
é igual a 19, passando pelo nó 6. 
Até agora, os cálculos mostram que o tempo mínimo (caminho mais 
longo do nó inicial 1 ao nó final n = 7) para o projeto ser concluído é de 19 
dias. 
Agora devemos aplicar o backward pass em todos os nós, partindo do nó 
n = 7. 
Backward Pass 
Nó 7: devemos fazer 7 = □7 = 19 
Nó 6: o nó 6 só pode alcançar o nó 7, portanto 6 = 7 – 67D =19 – 6 = 
13. Ou seja, o nó final do nó 6 é o nó 7. 
Nó 5: o nó 5 pode alcançar tanto o nó 7 quanto o nó 6, portanto 5 = 
min{ 7 – 57D , 6 – 56D } = min{19 – 5, 13 – 7} = min{14, 6} = 6. Ou seja, o 
nó final do nó 5 é o nó 6. 
Nó 4: o nó 4 pode alcançar tanto o nó 7 quanto o nó 6 quanto o nó 5, 
portanto 4 = min{ 7 – 47D , 6 – 46D , 5 – 45D } = min{19 – 2, 13 – 3, 6 – 
0} = min{17, 10, 6} = 6. Ou seja, o nó final do nó 4 é o nó 5. 
Nó 3: o nó 3 pode alcançar tanto o nó 5 quanto o nó 4, portanto 3 = 
min{ 5 – 35D , 4 – 34D } = min{6 – 2, 6 – 3} = min{4, 3} = 3. Ou seja, o nó 
final do nó 3 é o nó 4. 
 
74 
Nó 2: o nó 2 só pode alcançar o nó 4, portanto 2 = 4 – 24D =6 – 2 = 
4. Ou seja, o nó final do nó 2 é o nó 4. 
Nó 1: o nó 1 pode alcançar tanto o nó 3 quanto o nó 2, portanto 1 = 
min{ 3 – 13D , 2 – 12D } = min{3 – 3, 4– 2} = min{0, 2} = 0. Ou seja, o nó 
final do nó 1 é o nó 3. Como 1 = 0, terminamos os cálculos. 
Esses cálculos do forward pass e do backward pass são mostrados na 
figura a seguir: 
 
Agora devemos aplicar as três condições para a atividade ser crítica. 
Temos que no nó 2 2 4  □2 = 2. Isso significa que o nó 2 não poderá ser 
nem nó inicial e nem nó final de uma atividade crítica (ou seja, todas as 
atividades que passam pelo nó 2, que são as atividades (1, 2) e (2, 4) serão 
não críticas). 
Para a atividade (4,7): 
1. 4 = □4 = 6 
2. 7 = □7 = 19 
3. ij  = □j – □i = 19 – 6 = 13  ijD 2 
Portanto a atividade (4,7) não é uma atividade crítica. 
 
75 
Para a atividade (4,6): 
1. 4 = □4 = 6 
2. 6 = □6 = 13 
3. ij  = □j – □i = 13 – 6 = 7  ijD 3 
Portanto a atividade (4,6) não é uma atividade crítica. 
Para a atividade (3,5): 
1. 3 = □3 = 3 
2. 5 = □5 = 6 
3. ij  = □j – □i = 6 – 3 = 3  ijD 2 
Portanto a atividade (3,5) não é uma atividade crítica. 
As demais atividades são críticas. Caminho crítico: 1-3-4-5-6-7. As 
atividades críticas são (1, 3), (3, 4), (5, 6) e (6, 7). Note que a atividade (4, 5) 
não aparece como atividade crítica, pois ela é uma atividade fictícia (foi criada 
apenas para a representação da rede de projeto). 
A duração total necessária para concluir o projeto (tempo mínimo para a 
conclusão do projeto) é de 19 dias (como mostrado na figura). Podemos obter 
esse valor somando as durações das atividades críticas: 3 + 3 + 7 + 6 = 19 
dias. 
 
8) Assinale a alternativa que apresente a duração mínima desse projeto 
(duração total necessária para concluir o projeto). 
a) 6 dias. 
b) 13 dias. 
c) 17 dias. 
d) 19 dias. 
e) 22 dias. 
 
76 
Solução: 
Vide solução do problema anterior. 
 
9) A rede a seguir apresenta as distâncias entre cada par de nó. Note 
que o arco (4, 5) é direcional (ou seja, só é permitido tráfego no sentido do nó 
4 ao nó 5). Todos os demais arcos permitem o tráfego nos dois sentidos. 
 
Encontre os caminhos mais curtos entre quaisquer dois nós da rede (isto 
é, encontre as matrizes de distâncias e de sequências de nós através do 
algoritmo de Floyd). 
Solução: 
Em primeiro lugar, na etapa 0, devemos construir as matrizes de 
distância D0 e de sequências de nós S0 que são as representações iniciais da 
rede (da rede original), mostradas a seguir: 
 
 
 
 
 
 
 
77 
Matriz D0: 
 1 2 3 4 5 
1 – 5 3 ∞ ∞ 
2 5 – 1 5 2 
3 3 1 – 7 ∞ 
4 ∞ 5 7 – 3 
5 ∞ 2 ∞ ∞ – 
 
Matriz S0: 
 1 2 3 4 5 
1 – 2 3 4 5 
2 1 – 3 4 5 
3 1 2 – 4 5 
4 1 2 3 – 5 
5 1 2 3 4 – 
 
Agora devemos fazer k = 1 e entrar na etapa 1. Na etapa 1, a linha pivô e 
a coluna pivô devem ser a linha 1 e a coluna 1, as quais foram sombreadas 
na matriz D0. Nessa etapa, vemos que não existe caminho mais curto 
passando pelo nó 1 (operação tripla). Note que os únicos nós que podem ser 
acessados pelo nó 1 são os nos 2 e 3 cuja distância entre eles é igual a 1 
(portanto, a operação tripla passando pelo nó 1 daria uma distância maior). 
Portanto não teremos alterações para a próxima etapa. 
 
 
 
 
78 
Matriz D1: 
 1 2 3 4 5 
1 – 5 3 ∞ ∞ 
2 5 – 1 5 2 
3 3 1 – 7 ∞ 
4 ∞ 5 7 – 3 
5 ∞ 2 ∞ ∞ – 
 
Matriz S1: 
 1 2 3 4 5 
1 – 2 3 4 5 
2 1 – 3 4 5 
3 1 2 – 4 5 
4 1 2 3 – 5 
5 1 2 3 4 – 
 
Agora devemos fazer k = 2 e entrar na etapa 2. Na etapa 2, a linha pivô e 
a coluna pivô devem ser a linha 2 e a coluna 2, as quais foram sombreadas 
na matriz D1. Note na rede original que existe um caminho ligando o nó 1 ao 
nó 4 que passa pelo nó 2 (portanto é menor do que infinito). As entradas (1,4) 
e (4,1) estão em destaque na matriz D1. Da mesma forma, existe um caminho 
ligando o nó 1 ao nó 5 que passa pelo nó 2, portanto as entradas (1,5) e (5,1) 
também estão em destaque na matriz D1. Além disso, existe uma caminho 
ligando o nó 3 ao nó 5 que passa pelo nó 2, portanto as entradas (3,5) e (5,3) 
também estão em destaque na matriz D1. Existe também um caminho ligando 
o nó 3 ao nó 4 que passa pelo nó 2, portanto as entradas (3,4) e (4,3) estão 
em destaque na matriz D1. Por fim, existe uma caminho ligando o nó 5 ao nó 
 
79 
4 que passa pelo nó 2, portanto a entrada (5,4) também está em destaque na 
matriz D1. Utilizando a operação tripla: 
14d = ∞ 
10552412 dd 
41d = ∞ 
10552142 dd 
15d = ∞ 
7252512  dd 
51d = ∞ 
7522152 dd 
35d = ∞ 
3212532 dd 
53d = ∞ 
3122352 dd 
34d = 7 
6512432  dd 
43d = 7 
6152342 dd 
54d = ∞ 
7522452 dd 
Essas mudanças aparecerão em D2 e S2, como mostrado a seguir: 
 
 
 
 
 
80 
Matriz D2: 
 1 2 3 4 5 
1 – 5 3 10 7 
2 5 – 1 5 2 
3 3 1 – 6 3 
4 10 5 6 – 3 
5 7 2 3 7 – 
 
Matriz S2: 
 1 2 3 4 5 
1 – 2 3 2 2 
2 1 – 3 4 5 
3 1 2 – 2 2 
4 2 2 2 – 5 
5 2 2 2 2 – 
 
Agora devemos fazer k = 3 e entrar na etapa 3. Na etapa 3, a linha pivô e 
a coluna pivô devem ser a linha 3 e a coluna 3, as quais foram sombreadas 
na matriz D2. Note que existe um caminho menor (do que 5) indo do nó 1 
para o nó 2 passando pelo nó 3, portanto as entradas (1,2) e (2,1) estão em 
destaque na matriz D2. Utilizando a operação tripla: 
12d = 5 
4133213 dd 
21d = 5 
4313123 dd 
Essas mudanças aparecerão em D3 e S3, como mostrado a seguir: 
 
81 
Matriz D3: 
 1 2 3 4 5 
1 – 4 3 10 7 
2 4 – 1 5 2 
3 3 1 – 6 3 
4 10 5 6 – 3 
5 7 2 3 7 – 
 
Matriz S3: 
 1 2 3 4 5 
1 – 3 3 2 2 
2 3 – 3 4 5 
3 1 2 – 2 2 
4 2 2 2 – 5 
5 2 2 2 2 – 
 
Agora devemos fazer k = 4 e entrar na etapa 4. Na etapa 4, a linha pivô e 
a coluna pivô devem ser a linha 4 e a coluna 4, as quais foram sombreadas 
na matriz D3. Nessa etapa, vemos que não existe caminho mais curto 
passando pelo nó 4 (operação tripla). Portanto não teremos alterações para a 
próxima etapa. 
 
 
 
 
 
 
82 
Matriz D4: 
 1 2 3 4 5 
1 – 4 3 10 7 
2 4 – 1 5 2 
3 3 1 – 6 3 
4 10 5 6 – 3 
5 7 2 3 7 – 
 
Matriz S4: 
 1 2 3 4 5 
1 – 3 3 2 2 
2 3 – 3 4 5 
3 1 2 – 2 2 
4 2 2 2 – 5 
5 2 2 2 2 – 
 
Agora devemos fazer k = 5 e entrar na etapa 5. Na etapa 5, a linha pivô e 
a coluna pivô devem ser a linha 5 e a coluna 5, as quais foram sombreadas 
na matriz D4. Nessa etapa, vemos que não existe caminho mais curto 
passando pelo nó 5 (operação tripla). Devemos procurar novas operações 
triplas nessa matriz. Note que a distância entre os nós 1 e 2 é igual a 4 e a 
distância entre os nós 2 e 4 é igual a 5, portanto: 
14d = 10 
9542412  dd 
41d = 10 
9452142 dd 
 
83 
 
Com isso chegamos às matrizes D5 e S5, que apresentam a resposta 
final do problema: 
Matriz D5: 
 1 2 3 4 5 
1 – 4 3 9 7 
2 4 – 1 5 2 
3 3 1 – 6 3 
4 9 5 6 – 3 
5 7 2 3 7 – 
 
Matriz S5: 
 1 2 3 4 5 
1 – 3 3 2 2 
2 3 – 3 4 5 
3 1 2 – 2 2 
4 2 2 2 – 5 
5 2 2 2 2 – 
 
Temos por exemplo que a menor distância ligando o nó 1 ao nó 5 é igual 
a 7 (entrada (1,5) de D5), passando pelo nó 2 (entrada (1,5) de S5). A menor 
distância entre o nó 1 e o nó 4 é igual a 9 (entrada (1,4) de D5). Observe que 
a entrada (1,4) de S5 é igual a 2, o que significa que o caminho é 1->2->4. 
Porém, a (1,2) de S5 é igual a 3, o que significa que o caminho ligando o nó 1 
ao nó 2 é 1->3->2. Portanto o menor caminho ligando o nó 1 ao nó 4 é 1->3-
>2->4 e tem comprimento de 9. 
 
 
84 
10) As fundações de um edifício serão concluídas em quatro seções 
consecutivas (I, II, III e IV). Cada seção possui três atividades: escavar, 
colocar armações e verter concreto. A escavação de uma seção não pode 
começar até que a escavação da seção precedente tenha sido concluída. 
Essa mesma restrição se aplica a verter concreto. Desenvolva a rede para 
esse projeto. 
 
Solução: Temos que as atividades de cada seção são: 
Para a seção I: Escavaçar I (Esc I), Colocar Armações I (Aço I) e Verter 
Concreto I (Conc I). 
Para a seção II: Escavaçar II (Esc II), Colocar Armações II (Aço II) e 
Verter Concreto II (Conc II).Para a seção III: Escavaçar III (Esc III), Colocar Armações III (Aço III) e 
Verter Concreto III (Conc III). 
Para a seção IV: Escavaçar IV (Esc IV), Colocar Armações IV (Aço IV) e 
Verter Concreto IV (Conc IV). 
Temos que a escavação da seção atual deve estar ligada à escavação 
da seção anterior e que o verter concreto da seção atual deve estar ligada ao 
verter concreto da seção anterior. Assim, temos: 
 
 
85 
 
Exercícios – Unidade 6 
 
1) Sobre as características básicas dos problemas de PD é correto 
afirmar que: 
a) O problema é dividido em estados, de forma que cada estado possui 
um número de estágios associado ao início desse estado. 
b) O número de estados de um problema pode ser finito ou infinito. 
c) Os problemas de PD podem ser interpretados como redes, em que 
cada nó representa um estágio. 
d) TODAS as alternativas anteriores estão CORRETAS. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
Solução: 
Na a, o correto seria “cada estágio possui um número de estados 
associado ao início desse estágio” 
Na c, o correto seria “em que cada nó representa um estado” 
2) Sobre a recursividade dos cálculos em PD é correto afirmar que: 
a) Os cálculos em PD são feitos de forma recursiva, em que a solução 
ótima de um subproblema é usada como entrada para o subproblema 
seguinte. 
b) O princípio da otimalidade expressa que as decisões futuras para os 
estágios restantes são uma política ótima independentemente da política 
adotada nos estágios anteriores. 
c) Na recursão progressiva, os cálculos prosseguem do estágio inicial até 
o último estágio. 
d) TODAS as alternativas anteriores estão CORRETAS. 
e) TODAS as alternativas anteriores estão INCORRETAS. 
 
86 
Considere a rede a seguir para os problemas 3 e 4: 
 
Na rede são mostradas as distâncias, em milhas, entre os diferentes nós. 
3) A distância mais curta entre o nó 1 e o nó 7 é igual a: 
a) 15 milhas. 
b) 16 milhas. 
c) 17 milhas 
d) 18 milhas 
e) 19 milhas. 
Solução: 
Estágio 1: nó inicial (nó 1) e nós finais (nós 2, 3 e 4) 
Para o nó 1, os nós finais do estágio são os nós 2, 3 e 4. Temos que a 
distância mais curta é: 
Distância mais curta do nó 1 ao nó 2 = 5 milhas (a partir do nó 1). 
Distância mais curta do nó 1 ao nó 3 = 11 milhas (a partir do nó 2). 
Distância mais curta do nó 1 ao nó 4 = 6 milhas (a partir do nó 1). 
 
 
 
87 
Estágio 2: nós iniciais (nós 2, 3 e 4) e nós finais (nós 5 e 6) 
No estágio 2, temos que os nós iniciais são os nós 2, 3 e 4 (cujas 
entradas foram calculadas no estágio 1) e os nós finais são nós 5 e 6. 
Observe que o nó 5 pode ser alcançado por duas rotas diferentes: (2, 5) e (3, 
5). Devemos considerar essa informação, junto com as distâncias mais curtas 
até os nós 2 e 3 para determinar a distância mais curta até o nó 5: 
13
13211
17125
min 








(a partir do nó 3) 
Temos que a distância entre o nó 1 e o nó 5, passando pelo nó 2, é igual 
a 5 + 12 = 17. E a distância entre o nó 1 e o nó 5, passando pelo nó 3, é igual 
a 11 + 2 = 13. Assim, a menor distância ligando o nó 1 ao nó 5 é igual a 13, 
passando pelo nó 3. 
O nó 6 pode ser alcançado a partir dos nós 2, 3 e 4, assim: 
14
1596
14311
17125
min 













(a partir do nó 3) 
Temos que a distância entre o nó 1 e o nó 6, passando pelo nó 2, é igual 
a 5 + 12 = 17. Temos que a distância entre o nó 1 e o nó 6, passando pelo nó 
3, é igual a 11 + 3 = 14. E a distância entre o nó 1 e o nó 6, passando pelo nó 
4, é igual a 6 + 9 = 15. Assim, a menor distância ligando o nó 1 ao nó 6 é 
igual a 14, passando pelo nó 3. 
Temos então que: 
Distância mais curta do nó 1 ao nó 5 = 13 milhas (a partir do nó 3). 
Distância mais curta do nó 1 ao nó 6 = 14 milhas (a partir do nó 3). 
Estágio 3 nós iniciais (nós 5 e 6) e nó final (nó 7) 
Por fim, na última etapa (estágio 3), temos que o nó de destino pode ser 
alcançado partindo dos nós 5 e 6. A partir dos resultados do estágio anterior, 
temos que a distância mais curta do nó 1 até o nó 5 é igual a 13 e até o nó 6 
é igual a 14 (esses são os nós iniciais do estágio 3). Com isso, temos: 
 
88 
 
17
18414
17413
min 








(a partir do nó 5) 
Temos que a distância entre o nó 1 e o nó 7, passando pelo nó 5, é igual 
a 13 + 4 = 17. E a distância entre o nó 1 e o nó 7, passando pelo nó 6, é igual 
a 14 + 4 = 18. Assim, a menor distância ligando o nó 1 ao nó 7 é igual a 17, 
passando pelo nó 5. 
Temos então que: 
Distância mais curta do nó 1 ao nó 7 = 17 milhas (a partir do nó 5). 
No estágio 3, obtivemos a distância mais curta entre os nós 1 e 7 
(resposta do problema), que é igual a 17 milhas. 
 
4) A rota mais curta entre o nó 1 e o nó 7 é igual a: 
a) 1 -> 2 -> 3 -> 5 -> 7. 
b) 1 -> 3 -> 5 -> 7. 
c) 1 -> 3 -> 6 -> 7. 
d) 1 -> 4 -> 5 -> 7. 
e) 1 -> 4 -> 7. 
Solução: 
Partindo da solução do exercício anterior, para determinar a rota ótima, 
temos que seguir o caminho inverso: o estágio 3 liga o nó 7 ao 5, o estágio 2 
liga o nó 5 ao 3, e o estágio 1 liga o nó 3 ao 1, passando pelo nó 2. Portanto, 
a rota mais curta é 1 -> 2 -> 3 -> 5 -> 7. 
 
 
 
 
 
89 
 
Considere o enunciado a seguir para os problemas 5 e 6: 
Um navio com capacidade para 5 toneladas (W = 5) pode ser carregado 
com um ou mais itens. A tabela a seguir apresenta o peso unitário (wi), em 
toneladas, e a receita unitária (ri), em milhares de dólares, para o item i. 
Item i wi ri 
1 4 70 
2 1 20 
3 2 50 
5) O retorno ótimo (receita ótima) é igual a: 
a) $ 90.00,00. 
b) $ 100.00,00. 
c) $ 110.00,00. 
d) $ 120.00,00. 
e) $ 130.00,00. 
Solução: 
Estágio 3: Como w3 = 2 toneladas por unidade, então o número máximo 
de unidades do item 3 que podem ser carregadas no navio é igual a [W/w3] = 
[5/2] = 2. Isso significa que os valores possíveis de m2 são 0, 1 e 2. Para 
comparar as alternativas do estágio 2, utilizamos a seguinte equação: 
 3
3
33 50
2,1,0
max
)( m
m
xf

 
Devemos escolher a alternativa de maior valor. Além disso, os cálculos 
para cada alternativa consideram o produto entre a receita do item 3 (r3 = 50) 
e o número de itens 3 carregados no navio (m3). A tabela a seguir resume os 
cálculos do estágio 3. 
 
 
90 
 
 350m Solução ótima 
3x 03 m 13 m 23 m )( 33 xf 
*
3m 
0 0 – – 0 0 
1 0 – – 0 0 
2 0 50 – 50 1 
3 0 50 – 50 1 
4 0 50 100 100 2 
5 0 50 100 100 2 
 
Estágio 2: Como w2 = 1 tonelada por unidade, então o número máximo 
de unidades do item 2 que podem ser carregadas no navio é igual a [W/w2] = 
[5/1] = 5. Isso significa que os valores possíveis de m2 são 0,1,2,3,4 e 5. Para 
comparar as alternativas do estágio 2, utilizamos a seguinte equação: 
 )(20
5,4,3,2,1,0
max
)( 2232
2
22 mxfm
m
xf 

 
Novamente devemos escolher a alternativa de maior valor. Além disso, 
os cálculos para cada alternativa consideram o produto entre a receita do 
item 2 (r2 = 20) e o número de itens 2 carregados no navio (m2) somado com 
a solução ótima calculada no estágio anterior )( 223 mxf  . A tabela a seguir 
resume os cálculos do estágio 2. 
 
 
 
 
 
 
 
91 
 
 )(20 2232 mxfm  Solução ótima 
2x
 
02 m
 
12 m
 
22 m
 
32 m
 
42 m
 
52 m
 
)( 22 xf
 
*
2m
 
0 0+0=0 – – – – – 0 0 
1 0+0=0 20+0=20 – – – – 20 1 
2 0+50=50 20+0=20 40+0=40 – – – 50 0 
3 0+50=50 
20+50= 
70 
40+0=40 60+0=60 – – 70 1 
4 
0+100= 
100 
20+50= 
70 
40+50=9
0 
60+0=60 80+0=80 – 100 0 
5 
0+100= 
100 
20+100= 
120 
40+50= 
90 
60+50= 
100 
80+0=80 
100+0= 
100 
120 1 
 
Estágio 1: Como w1 = 4 toneladas por unidade, então o número máximo 
de unidades do item 1 que podem ser carregadas no navio é igual a [W/w1] = 
[5/4] = 1. Isso significa que os valores possíveis de m1 são 0 e 1. Para 
comparar as alternativas do estágio 1, utilizamos a seguinte equação: 
 )4(70
1,0
max
)( 1121
1
11 mxfm
m
xf 

 
Novamente devemos escolher a alternativa demaior valor. Além disso, 
os cálculos para cada alternativa consideram o produto entre a receita do 
item 1 (r1 = 70) e o número de itens 1 carregados no navio (m1) somado com 
a solução ótima calculada no estágio anterior )4( 112 mxf  . A tabela a seguir 
resume os cálculos do estágio 1. 
 
 
 
 
92 
 
 )4(70 1121 mxfm  Solução ótima 
1x 01 m 11 m )( 11 xf 
*
1m 
0 0+0 – 0 0 
1 0+20=20 – 20 0 
2 0+50=50 – 50 0 
3 0+70=70 – 70 0 
4 0+100=100 70+0=70 100 0 
5 0+120=120 70+20=90 120 0 
 
Portanto, o retorno ótimo é )5(1f = $ 120.000. 
 
6) As quantidades de cada item na solução ótima é: 
a) Carregar com uma unidade do item 1. 
b) Carregar com uma unidade do item 1 e uma unidade do item 2. 
c) Carregar com quatro unidades do item 2 e uma unidade do item 3. 
d) Carregar com uma unidade do item 1 e uma unidade do item 3. 
e) Carregar com uma unidade do item 2 e duas unidades do item 3. 
Solução: 
Partindo da solução do exercício anterior, para determinar as 
quantidades de cada item devemos fazer o seguinte: dado que W = 5 
toneladas, partindo do estágio 1, para x1 = 5, temos que a solução ótima é m1 
= 0, o que resulta em x2 = x1 – 4 m1 = 5 – 4x0 = 5. No estágio 2, para x2 = 5, 
temos que m2 = 1, resultando em x3 = x2 – m2 = 5 – 1 = 4. Em seguida, no 
estágio 3, para x3 = 4, temos que m3 = 2. Assim, a solução ótima do problema 
nos diz que a quantidade de itens 1 deve ser igual a 0 (m1 = 0), de itens 2 
deve ser igual a 1 (m2 = 1) e de itens 3 deve ser igual a 2 (m3 = 2). 
 
93 
Considere o enunciado a seguir para os problemas 7 e 8: 
Um empreiteiro de construção civil fez uma estimativa da força de 
trabalho necessária para as próximas 4 semanas: 
Semana 1: 5 operários; 
Semana 2: 7 operários; 
Semana 3: 4 operários; 
Semana 4: 6 operários; 
O excesso de mão-de-obra mantida custa $ 200 por operário por 
semana, e uma nova contratação em qualquer semana resulta em um custo 
fixo de $ 500 mais $ 200 por operário por semana. 
7) O custo mínimo total é igual a: 
a) $ 2.600,00. 
b) $ 2.700,00. 
c) $ 2.800,00. 
d) $ 2.900,00. 
e) $ 3.000,00. 
Solução: 
Podemos resumir os dados desse problema da seguinte forma: 
6,4,7,5 4321  bbbb 
)(2)(1 iiii bxbxC  , i = 1,2,3,4 
1112 ),(25)(   iiiiii xxxxxxC , i = 1,2,3,4 
Para simplificação, os custos C1 e C2 estão em centenas de dólares. 
Estagio 4 (Semana 4): bn = b4 = 6 
A tabela a seguir apresenta os cálculos para esse estágio: 
 
 
 
94 
 )()6( 34241 xxCxC  Solução ótima 
3x 64 x )( 34 xf 
*
4x 
4 2(0)+5+2(2)=9 9 6 
5 2(0)+5+2(1)=7 7 6 
6 2(0)+0=0 0 6 
Observe que como na semana 4 o número mínimo de operários é igual a 
6, e na semana 3 (semana anterior) esse mínimo é de 4, então as 
alternativas (número de operários) para a semana anterior (semana 3) será x3 
= 4,5 e 6 (coluna 1 da tabela). 
 
Estagio 3 (Semana 3): b3 = 4 
A tabela a seguir apresenta os cálculos para esse estágio: 
 )()()4( 3423231 xfxxCxC  Solução ótima 
2x 43 x 53 x 63 x )( 23 xf 
*
3x 
7 2(0)+0+9=9 2(1)+0+7=9 2(2)+0+0=4 4 6 
 
Estagio 2 (Semana 2): b2 = 7 
A tabela a seguir apresenta os cálculos para esse estágio: 
 )()()7( 2312221 xfxxCxC  Solução ótima 
1x 72 x )( 12 xf 
*
2x 
5 2(0)+5+2(2)+4=13 13 7 
6 2(0)+5+2(1)+4=11 11 7 
7 2(0)+0+4=4 4 7 
 
 
 
95 
Estagio 1 (Semana 1): b1 = 5 
A tabela a seguir apresenta os cálculos para esse estágio: 
 )()()5( 1201211 xfxxCxC  Solução ótima 
0x 51 x 61 x 71 x )( 01 xf 
*
1x 
0 
2(0)+5+2(5)+13 
=28 
2(1)+5+2(6)+11 
=30 
2(2)+5+2(7)+4 
=27 
27 7 
A solução ótima mostra que o custo total mínimo é igual a $ 2.700 (ou 
seja, )( 01 xf =2.700). 
 
8) O número de operários em cada semana que minimiza o custo total é: 
a) 5 operários na Semana 1, 7 operários na Semana 2, 4 operários na 
Semana 3 e 6 operários na Semana 4. 
b) 7 operários na Semana 1, 7 operários na Semana 2, 4 operários na 
Semana 3 e 6 operários na Semana 4. 
c) 7 operários na Semana 1, 7 operários na Semana 2, 6 operários na 
Semana 3 e 6 operários na Semana 4. 
d) 6 operários na Semana 1, 7 operários na Semana 2, 5 operários na 
Semana 3 e 6 operários na Semana 4. 
e) 6 operários na Semana 1, 7 operários na Semana 2, 6 operários na 
Semana 3 e 6 operários na Semana 4. 
Solução: 
Partindo da solução do exercício anterior, podemos determinar a solução 
ótima para o número de operários em cada semana da seguinte forma: do 
estágio 1, temos que o valor ótimo de x1 = 7 (7 operários na semana 1). 
Partindo de x1 = 7, no estágio 2 (tabela do estágio 2) temos que x2 = 7 (7 
operários na semana 2). Partindo de x2 = 7, no estágio 3 (tabela do estágio 3) 
temos que x3 = 6 (6 operários na semana 3). Partindo de x3 = 6, no estágio 4 
(tabela do estágio 4) temos que x4 = 6 (6 operários na semana 4). O número 
de operários em cada semana que minimiza o custo total é: 7 operários na 
 
96 
Semana 1, 7 operários na Semana 2, 6 operários na Semana 3 e 6 operários 
na Semana 4. 
 
Considere a rede a seguir para os problemas 9 e 10: 
Na rede são mostradas as distâncias, em milhas, entre os diferentes nós. 
 
9) Determine, através da recursão regressiva, a distância mais curta 
entre o nó 1 e o nó 7. 
Solução: 
Temos que 0)( 44 xf para 74 x (estamos começando pelo último nó, 
ou estado, que é o nó 7). Devemos fazer a seguinte ordem para os cálculos: 
3f -> 2f -> 1f . 
Estágio 3 
Observe que o nó 7 ( 74 x ) está conectado aos nó 5 e 6 ( 3x 5 e 6) 
com uma rota cada (só existe uma rota, portanto não há alternativa a 
escolher). Os resultados do estágio 3 podem ser resumidos na seguinte 
tabela: 
 
 
 
97 
 ),( 43 xxd Solução ótima 
3x 74 x )( 33 xf 
*
4x 
5 4 4 7 
6 4 4 7 
 
Estágio 2 
Dado )( 33 xf do estágio 3 (mostrado na tabela anterior), podemos 
calcular cada uma das alternativas e escolher a solução ótima (a de menor 
valor), como mostra a tabela a seguir: 
 
 )(),( 3332 xfxxd  Solução ótima 
1x 53 x 63 x )( 22 xf 
*
3x 
2 12+4=16 12+4=16 16 5 
3 2+4=6 3+4=7 6 5 
4 – 9+4=13 13 6 
Obs.: La linha de 21 x poderíamos ter escolhido tanto 5
*
3 x quanto 
6*3 x . Por convenção, escolhemos o menor valor. 
 
Estágio 1 
Dado )( 22 xf do estágio 2 (mostrado na tabela anterior), podemos 
calcular cada uma das alternativas e escolher a solução ótima (a de menor 
valor), como mostra a tabela a seguir: 
 
 
 
 
98 
 )(),( 2221 xfxxd  Solução ótima 
1x 22 x 32 x 42 x )( 11 xf 
*
2x 
1 5+16=21 11+6=17 6+13=19 17 3 
Logo, a distância mais curta é de 17 milhas. 
 
10) Determine, através da recursão regressiva, a rota mais curta 
ligando o nó 1 ao nó 7. 
Solução: 
Partindo da solução do exercício anterior, para determinar a rota mais 
curta (rota ótima), temos que, no estágio 1, o nó 1 está ligado ao nó 3 (é 
importante observar que a distância de 11, mostrada na tabela, consiste na 
distância entre o nó 1 e o nó 3, passando pelo nó 2) .Em seguida, a solução 
ótima do estágio 2 liga o nó 3 ao nó 5. Por fim, a solução ótima no estágio 3 
liga o nó 5 ao nó 7. Logo, a rota mais curta é dada por 1 -> 2 -> 3 -> 5 -> 7.