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