Slides

Prévia do material em texto

NOTAS DE AULA POII-UFF
Prof. João Carlos C.B. Soares de Mello
PESQUISA OPERACIONAL –
MODELOS ESTOCÁSTICOS (PO II)
• Professor: João Carlos Soares de Mello
• Bibliografia:
Taha, H.A., Pesquisa Operacional, Pearson, 2008
Tavares, L.T.; Oliveira, R.C.; Themido, I.H.; Correia, F.N. 
Investigação Operacional, McGraw-Hill, 1996
Bronson, R. Pesquisa Operacional, McGraw-Hill (Coleção 
Schaum), 1985
Fiani, R. Teoria dos Jogos, Campus-Elsevier, 2006
Revistas: Pesquisa Operacional, Investigação Operacional, 
Gestão & Produção, Produção (www.scielo.org)
Página: www.uff.br/decisao
TÓPICOS
• Otimização em redes (Teoria dos Grafos)
• Tipologia das decisões
• Decisões sob incerteza (jogos contra a natureza)
• Teoria dos jogos
• Decisões sob risco e teoria da utilidade
• Decisões seqüenciais (árvores de decisão)
• Processos multidecisor (Teorema de Arrow e 
métodos ordinais)
TÓPICOS
• Processo de Markov
• Processos de nascimento e morte – Teoria 
das filas
• Gestão de estoques
Teoria dos Grafos
• Pontes de Königsberg
na Prússia (atual 
Kalingrado, na Russia): 
“seria possível percorrer 
todas as quatro seções e 
voltar ao local de 
partida cruzando cada 
ponte uma única vez?”
• Resolvido por Leonhard 
Euler XVIII
Teoria dos Grafos
• Um grafo é uma noção simples e abstrata 
utilizada para representar a idéia de relação entre 
“elementos". Exemplos: ......???
• Matematicamente: G = (V,A), onde V é o 
conjunto de vértices e A é o conjunto de ligações 
entre vértices.
• Grafo não orientado: ligações representadas os 
pares de vértices não possuem uma ordem (i,j) = 
(j,i) = [i,j], aresta
• Grafo orientado (dígrafo): ligações (arcos) 
representadas por partes ordenados (i,j) z (j,i)
Teoria dos Grafos
Grafo não orientado Grafo orientado
V=(1,2,3,4,5,) V=(A,B,C,D,E)
A=([1,2],[1,3],[3,4], A=((A,B),(A,D),(A,C),(B,C),
[3,5],[3,4],[4,5]) (C,E),(D,E),(E,D))
Representação de um Grafo
• Listas de Adjacências: armazena o relacionamento 
entre os vértices em uma estrutura de listas. 
Representação econômica do ponto de vista 
computacional.
Grafos orientados: duas listas origem - destinos e 
destino - origens
Grafo não orientados: uma lista
Representação de um Grafo
• Matriz de adjacências: dois vértices são adjacentes 
se estão unidos por uma aresta ou arco. Matriz 
Mnxn (n total de vértices)
Exemplo:
Representação de um Grafo
• Matriz de adjacências valorada - Matriz de 
Distâncias (custos): valores associados ás 
ligações, matriz D
• Exemplo
Percursos em grafos
• Percurso ou itinerário ou ainda cadeia é uma 
família de ligações sucessivas adjacentes.
• Hamiltonianos: percurso que visita cada vértice 
uma única vez. Problema do Caixeiro Viajante: 
“O Caixeiro Viajante deve sair da sua cidade 
(origem), visitar cada uma das outras (n-1) 
cidades uma única vez e retornar à cidade de 
origem, de forma tal a percorrer uma única 
distância possível”
• Eulerianos: percurso que usa cada ligação 
exatamente uma vez. Problema do Carteiro 
Chinês.: “o carteiro deseja percorrer todas as 
ruas da sua rota um número mínimo de vezes
Problemas estudados em Grafos
• O Problema do Caixeiro Viajante
• O Problema do Carteiro Chinês
• O Problema de Caminho Mínimo
• O Problema de Fluxo Máximo
• O Problema de Fluxo Máximo a custo mínimo
• Árvore Geradora Mínima (AGM)
• Coloração em Grafos
• Roteamento de veículos
• Etc.
O Problema de Caminho 
Mínimo
• Objetivo: minimização do custo de percurso de 
um grafo entre dois vértices, custo este dado pela 
soma dos custos de cada aresta percorrida.
• Existem muitos algoritmos para resolver este 
problema, estudaremos dois: Dijkstra e Floyd
• Algoritmo de Dijkstra: determina o custo ou 
distância mínima entre uma origem e um destino.
• Algoritmo de Floyd: determina os custo ou 
distâncias mínimas entre todos os pares de 
vértices
Algoritmo de Dijkstra
• Para cada vértices usamos a notação: [c,j] X, 
chamada de rótulo
• c custo até o momento, j vértice precedente, X pode 
ser T (temporário) ou P (permanente)
• Início no vértice origem: [0,-]P
• Analisar os vértices adjacentes e colocamos rótulos 
temporários, calculamos a distância até esse ponto, 
caso esteja rotulado escolhemos o de menor distância
• Todos os vértices rotulados, pare, caso contrário, 
escolha o de menor custo rotule como P e repetir o 
passo anterior
Algoritmo de Dijkstra
• Exemplo:
Tipologia das decisões
• Quanto às informações
• Quanto ao número de decisores
• Quanto aos critérios
• Quanto ao objeto
Tipologia das decisões - Quanto 
às informações
• Determinísticas
• Com incerteza
• Com risco
Tipologia das decisões - Quanto 
aos decisores
• Mono decisor
• Multi decisor
• Jogos
Tipologia das decisões - Quanto 
aos critérios
• Mono critério
• Multicritério
Tipologia das decisões - Quanto 
ao objeto
• Escolha (PD )
• Classificação (PE )
• Ordenação (PJ )
• Correta descrição do problema 
(PG)
DECISÕES COM INCERTEZA
• Sem distribuição de probabilidade
• Racionalidade do decisor
• Jogo contra a natureza
• Não usar valor esperado
• Auxiliar o decisor, sem respostas 
prontas
MÉTODOS
• Pessimista (Maxmin). Se algo pode dar 
errado, vai dar errado
• Otimista (Maxmax). Tudo vai dar certo
• Savage (intermediário dos anteriores)
• Custo de oportunidade perdida. Não me 
quero arrepender da decisão tomada.
• Laplace. Valor esperado se as alternativas 
forem equiproporcionais.
4504504504504
4003003003003
4253752252252
4703502701501
DCBA
Cenários de a a d, de estagnação a forte crescimento.
As alternativas representam opções de investimento
MÉTODO OTIMISTA
4504504504504
4003003003003
4253752252252
4703502701501
DCBA
Escolhe-se o maior valor da tabela. O valor 470 
corresponde à alternativa 1.
MÉTODO PESSIMISTA
4504504504504
4003003003003
4253752252252
4703502701501
DCBA
Escolhe-se o menor valor de cada linha. Min1=150, 
Min2=225, Min3=300, Min4=450. Vê-se então qual é 
o maior dos mínimos. Max (150, 225, 300, 450)=450. 
Escolhe-se a opção 4.
MÉTODO DE LAPLACE
4504504504504
4003003003003
4253752252252
4703502701501
DCBA
Esp1=(150+270+350+470)/4=310
Esp2=(225+225+375+425)/4=312,5
Esp3=(300+300+300+400)/4=325
Esp4=450
Consideram-se as 
alternativas 
equiprováveis e 
usa-se o valor 
esperado. Tem 
sérias restrições 
de uso
MÉTODO DE SAVAGE
4504504504504
4003003003003
4253752252252
4703502701501
DCBA
S1=470 DD+150(1+150(1-- DD))
S2=425 DD+225(1+225(1-- DD))
S3=400 S3=400 DD+300(1+300(1-- DD))
S4=450S4=450
Faz uma avaliação de cada Faz uma avaliação de cada 
alternativa ponderando alternativa ponderando 
otimismo e pessimismo. otimismo e pessimismo. 
Adota um coeficiente de Adota um coeficiente de 
otimismo, otimismo, DD subjetivo e subjetivo e 
difdifíícil de determinar. cil de determinar. 
Para Para DD=1 =1 éé o mo méétodo todo 
otimista. Para otimista. Para DD=0 =0 éé o o 
mméétodo pessimista.todo pessimista.
MÉTODO DE SAVAGE
4504504504504
4003003003003
4253752252252
4703502701501
DCBA
470 DD+150(1+150(1-- DD)>450, significa que a alternativa 1 ser)>450, significa que a alternativa 1 seráá
escolhida. Caso contrescolhida. Caso contráário a escolhida serrio a escolhida seráá a alternativa 4.a alternativa 4.
Resolvendo: Resolvendo: 470 D+150-150 D=450
320 320 DD=300 As duas alternativas s=300 As duas alternativas sãão equivalentes para o equivalentes para DD=15/16.` =15/16.` 
ÉÉ preciso um otimismo superior a 93,75% para escolher a preciso um otimismo superior a 93,75% para escolher a 
alternativa 1alternativa 1
ÉÉ necessnecessáário comparar rio comparar 
apenas 1 e 4, japenas1 e 4, jáá que 4 que 4 
domina 2 e 3. Ou seja, na domina 2 e 3. Ou seja, na 
hiphipóótese do decisor achar tese do decisor achar 
que deveria escolher 2 ou 3, que deveria escolher 2 ou 3, 
éé melhor escolher 4.melhor escolher 4.
Dominar significa nunca Dominar significa nunca 
ser pior e ser melhor pelo ser pior e ser melhor pelo 
menos um vezmenos um vez
MÉTODO DE SAVAGE
S1=470 DD+150(1+150(1-- DD))
S2=425 DD+225(1+225(1-- DD))
S3=400 S3=400 DD+300(1+300(1-- DD))
S4=450S4=450
Gráfico do método de Savage
0
100
200
300
400
500
Alfa
S
A avaliação otimista é sempre superior à 
pessimista. Este comentário, que parece 
óbvio, pode não ser válido em situações em 
que otimismo e pessimismo tenham um 
significado diferente, envolvendo valores 
relativos
MÉTODO DO MENOR ARREPENDIMENTO 
(OU DO MENOR CUSTO DE 
OPRTUNIDADE PERDIDA)
4504504504504
4003003003003
4253752252252
4703502701501
DCBA
Verificar qual Verificar qual éé a melhor opa melhor opçãção de cada ceno de cada cenáário. Nos cenrio. Nos cenáários A, B e rios A, B e 
C a melhor alternativa C a melhor alternativa éé a 4, com valor 450. No cena 4, com valor 450. No cenáário D a melhor rio D a melhor 
alternativa alternativa éé a 1 com valor 470. Para cada par (alternativa, cena 1 com valor 470. Para cada par (alternativa, cenáário) rio) 
verificaverifica--se quanto se deixou de ganhar por nse quanto se deixou de ganhar por nãão ter escolhido a o ter escolhido a 
melhor alternativa para aquele cenmelhor alternativa para aquele cenáário. Assim, para cenrio. Assim, para cenáário A tendo rio A tendo 
escolhido a alternativa B o arrependimento escolhido a alternativa B o arrependimento éé 450450--150=300. Constr150=300. Constróóii--
se uma matriz auxiliarse uma matriz auxiliar
200004
701501501503
45752252252
01001803001
DCBA
MÉTODO DO MENOR ARREPENDIMENTO 
(OU DO MENOR CUSTO DE 
OPRTUNIDADE PERDIDA)
Os valores da matriz, agora, sOs valores da matriz, agora, sãão perdas. Quem no perdas. Quem nãão quer sofrer o quer sofrer 
crcrííticas quer, no pior dos caso, ter a menor perda possticas quer, no pior dos caso, ter a menor perda possíível. Para cada vel. Para cada 
alternativa o pior caso alternativa o pior caso éé a pior perda. A menor das piores perdas a pior perda. A menor das piores perdas éé a a 
escolhida. Temescolhida. Tem--se assim um problema se assim um problema minmaxminmax..
200004
701501501503
45752252252
01001803001
DCBA
MÉTODO DO MENOR ARREPENDIMENTO 
(OU DO MENOR CUSTO DE 
OPRTUNIDADE PERDIDA)
Max1=300Max1=300
Max2=225Max2=225
Max3=150Max3=150
Max4=20Max4=20
Min(300,225,150,20)=20. EscolheMin(300,225,150,20)=20. Escolhe--se a alternativa 4.se a alternativa 4.
200004
701501501503
45752252252
01001803001
DCBA
DISCUSSÃO
• Diante dos vários métodos, qual alternativa 
escolher?
• Depende da psicologia do decisor.
• Neste caso há uma rara convergência para 
a alternativa 4. Só o otimista escolheria a 1.
• Savage permite uma análise de 
sensibilidade. Pelo gráfico vê-se que quase 
certamente a 4 seria a escolhida.
EXEMPLO
005000150A3
15403020A2
0-100100050010A1
C5C4C3C2C1
Observar que nenhuma alternativa é dominada
EXEMPLO – MÉTODO 
OTIMISTA
005000150A3
15403020A2
0-100100050010A1
C5C4C3C2C1
Escolhida a A1
EXEMPLO – MÉTODO 
PESSIMISTA
005000150A3
15403020A2
0-100100050010A1
C5C4C3C2C1
Escolhida a A2
EXEMPLO – MÉTODO DE 
LAPLACE
005000150A3
15403020A2
0-100100050010A1
C5C4C3C2C1
Esp A1= (10+500+1000-100)/5=282
Esp A2=(20+30+40+5+1)/5=19,2
Esp A3=(150+500)/5=130
EXEMPLO – MÉTODO DE 
SAVAGE
005000150A3
15403020A2
0-100100050010A1
C5C4C3C2C1
EXEMPLO – MÉTODO DE 
SAVAGE
-200
0
200
400
600
800
1000
1200
A1
A2
A3
EXEMPLO – MÉTODO DE 
MENOR ARREPENDIMENTO
005000150A3
15403020A2
0-100100050010A1
C5C4C3C2C1
155005000A3
00960470130A2
110500140A1
C5C4C3C2C1
QUAL A ESCOLHIDA?
FIM DO PRIMEIRO TÓPICO
EM SEGUIDA: TEORIA DOS 
JOGOS
O que é um jogo
• Situações em que o resultado esperado não 
depende só das nossas decisões.
• Interação estratégica
• Racionalidade
• Xadrez, Bridge, Guerra, Cartel, Combate 
ao Crime, Localização, Política...
• Não são considerados jogos de sorte e 
habilidade puras.
Batalha do Mar de Coral
• II Guerra Mundial, derrota de Guadalcanal para 
os japoneses (1942)
• Transporte de tropas
• Risco: poderio aéreo aliado (americano)
• Duas rotas possíveis
• Dificuldades de reconhecimento aliado
• Fevereiro de 1943: transporte de 6900 soldados 
em uma frota escoltada a alta velocidade naval.
Batalha do Mar de Coral
• Rota Norte: mau tempo
• Rota Sul: bom tempo
• Reconhecimento em uma rota de cada vez
• Rota Norte: dois dias de bombardeio se forem 
descobertos no primeiro dia,1 caso contrário
• Rota Sul: 3 dias de bombardeio se forem 
descobertos no primeiro dia, 2 caso contrário
• O que fazer?
MODELO PARA O MAR DE 
CORAL
Rota Sul Rota Norte
Busca Sul 3 1
Busca Norte 2 2
MODELO PARA O MAR DE 
CORAL
Rota Sul Rota Norte
Busca Sul 3 1
Busca Norte 2 2
Jogo estritamente competitivo, estratégias dominantes
DILEMA DOS PRISIONEIROS
Confessa Não confessa
Confessa (-3,-3) (-1,-5)
Não confessa (-5, -1) (-2,-2)
Cooperação e competição, combate ao crime, 
Equilíbrio de Nash, Ótimo de Pareto, Decisão 
pessimista
DILEMA DOS PRISIONEIROS
Confessa Não confessa
Confessa (-6,-6) (-4,-10)
Não confessa (-10, -4) (-2,-2)
Dificuldade no Equilíbrio de Nash
TEORIA DOS JOGOS
• Lógica situacional de Popper: objetividade 
dos dados, sem subjetividade dos decisores
• Entender situações
• Aprimorar raciocínio
• Cournot (1838), Zermelo e o jogo de 
Xadrez, Borel e o conceito de estratégia, 
von Neumann e Morgenstern 1994, Nash, 
1950
JOGOS COM 3 JOGADORES
• Votação em 2 turnos
• O truelo
Votação em 2 turnos.
Diretor 1 Diretor 2 Diretor 3
I Ap Am
Ap I I
Am Am Ap
Primeiro turno entre Investir e Ampliar
Ação estratégica do diretor 2
O Truelo
• 3 atiradores
• Atirador 1 100%
• Atirador 2 80%
• Atirador 3 20%
TEORIA DA DECISÁO 
RACIONAL
• Preferências do decisor
• Relações binárias: ordem, ordem lata
• Dadas A e B, A P B, B PA ou A I B
• Se A P B e B P C então A P C
• Se A I B e B I C então A I C
• Racionalidade forte e fraca
• Simplicidade, aprendizado, recompensas
IRRACIONALIDADE DE 
GRUPO
• Aumentar programas sociais G
• Manter programas sociais M
• Diminuir programas sociais D
• Conservador: D G M
• Moderado: M D G
• Radical: G M D
• G P M, M P D, D P G
SOLUÇÃO DE JOGOS
• Eliminação sucessiva de estratégias dominadas: a 
racionalidade é conhecimento comum
• Exemplo: Gato e Rato
• Empréstimos bancários: decisões simultâneas
Renova Não renova
Renova 4,4 1,5
Não renova 5,1 3,3
LIMITAÇÃO DO MÉTODO
Não exporta Exporta pouco Exporta muito
Investe 2,1 1,0 0,-1
Não investe 1,0 2,1 -1,2
Não há eliminação de estratégias
EQUILIBRIO DE NASH
• Cada estratégia é a melhor resposta 
possível às estratégias dos demais 
jogadores e isso é verdade para todos os 
jogadores
Não exporta Exporta pouco Exporta muito
Investe L2,1 C 1,0 L0,-1
Não investe 1,0 L2,1 -1,2 C
COMÉRCIO 
INTERNACIONAL
Tarifa protecionista Tarifa simbólica
Tarifa protecionista 800, 800 2300, -700
Tarifa simbólica -700, 2300 1700, 1700
Compara Nash com Pareto
VÁRIOS EQUILIBRIOS DE 
NASH
Campanha agressiva
Campanha agressiva -20, -20 10, -10
Campanha normal -10, 10 0,0
Campanha normal
GUERRA DOS SEXOS
Cinema Jogo
Cinema 2, 1 -1, -2
Jogo -2, -1 1, 2
LOCALIZAÇÃO• Sem custos de transporte: localização 
concentrada
• Com custos de transporte: Localização nos 
extremos
Localização de lojas
• 3 cidades, ABC
• d(A,B)=10, d(A,C)=20, d(B,C)=15
• P(A)=45%, P(B)=35%, P(C)=20%
• Rede I (Grande), rede II (pequena)
• I e II juntas ou equidistantes, I fica com 
65%
• I mais próxima fica com 90%
• I mais distante fica com 40%
• I não fica em C
• Onde localizar?
Localização de lojas
• Jogo estritamente competitivo 
(soma=100%)
• (I,A), (II,A) g(I)=65% (o mesmo para B)
• (I,A), (II,B) 
g(I)=0,9x0,45+0,4x0,35+0,4x0,2=0,625
• (I,A), (II,C) 
g(I)=0,9x0,45+0,9x0,35+0,4x0,2=0,8
• ...
Localização de lojas
II,A II,B II,C
I,A 65 62,5 80
I, B 67,5 65 80
Solução
• As duas em B
• Solução contra intuitiva
• Jogo estável, equilibrio de Nash
determinístico.
Jogos de Soma Zero
• O que um ganha o outro perde
• Guerra (será mesmo), medalhas olímpicas, 
mercados de demanda fixa.
• A soma pode ser constante, não nula.
• Jogos estáveis (exemplo anterior). Já tendo 
jogado antes, os jogadores repetem as 
estratégias.
• Jogos instáveis. Um jogador muda a 
estratégia como resposta à estratégia do 
outro
Jogos de Soma Zero
• Conceito de maxmin e min max: na pior das 
hipóteses ganhar o máximo ou perder o 
mínimo (se perder sempre, para quê jogar?).
• Matriz do segundo jogador é a simétrica da 
transposta do primeiro jogador.
• Estabilidade: se os dois jogadores 
concordam com a solução: 
minmax=maxmin=equilibrio de Nash, 
ponto de sela (rever as lojas).
Jogo instável
II,A II,B II,C
I,A 2 10 1
I, B 3 -1 -2
II,A II,B
I,A 2 10
I, B 3 -1I,A I,B
II,A - 2 -3
II, B -10 1
Jogo instável
• Não tem equilibrio de Nash se for jogado 
uma só vez.
• Resolvido em termos de probabilidades
• O jogo tem que ser jogado várias vezes 
para se obter um equilibrio de Nash em 
estratégias mistas, isto é, com alternância 
aleatória de estratégias, segundo uma 
determinada distribuição de probabilidade
Jogo instável
• Se o jogador II escolhe a sua estratégia A, 
o ganho esperado do jogador I é:
• E1=2p1+3p2 onde pi é a probabilidade do 
jogador I escolher a estratégia i (ele 
controla essa probabilidade, não as 
escolhas do jogador II).
• Se II escolhe a sua B, temos E2=10p1-p2
• A soma das probabilidades é unitária
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Jogo instável
• O jogador I quer maximizar o seu ganho. Mas, 
qual deles?
• Deve minimizar o pior caso, que não sabe qual é.
• Pior caso: min [(2p1+3p2), (10p1-p2)]
• Max E=min [(2p1+3p2), (10p1-p2)]
s.a 
p1+p2=1
p1,p2t 0
Isto é um PPNL (problema de programação não 
linear), não separável, não diferenciável
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Linearização
• Max (2p1+3p2) se este for o menor (podendo ser 
igual).
• Ou, Max (10p1-p2) se o menor for este (podendo 
ser igual)
s.a 
p1+p2=1
p1,p2t 0
São, aparentemente, dois Problemas de 
Programação Linear (PPL). Mas, E sempre será 
igual a uma das expressões.
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Linearização
• Max E onde E=(2p1+3p2) e E< (10p1-p2).
• Ou, Max E onde E=(10p1-p2) e E< (2p1+3p2)
s.a 
p1+p2=1
p1,p2t 0
As restrições de menor podem ser agrupadas 
com as de igual, dando duas restrições de menor 
ou igual.
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Linearização
• Max E 
s.a 
Ed 2p1+3p2
Ed 10p1-p2
p1+p2=1
p1,p2t 0
PPL com 3 variáveis. Pode ser usado o método 
gráfico?
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Linearização
• p2=1-p1 e p1 está entre 0 e 1.
• Max E 
s.a 
Ed 2p1+3(1-p1)
Ed 10p1-(1-p1)
p1d 1
p1t 0
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Linearização
• p2=1-p1 e p1 está entre 0 e 1.
• Max E 
s.a 
Ed -p1+3
Ed 11p1-1
p1d 1
p1t 0
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Gráfico
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
Ponto comum às retas:-p1+3=11p1-1, donde p1=1/3 e 
p2=2/3. E=-1/3 + 3 = 8/3 
p1=1/3p1=1/3p1=1/3p1=1/3
E para o segundo jogador?
 II,A II,B 
I,A 2 10 
I, B 3 -1 
 
p1=1/3p1=1/3p1=1/3p1=1/3
Usar dualidade
JOGOS REPETIDOS
-Jogo possui uma história prévia de 
conhecimento comum.
-Negócios, política, biologia.
-Formação de carteis: o cartel não é estável. 
Exemplo: OPEP e a ética entre ladrões.
-Ganha-se com coordenação, mas mais ainda 
se apenas um trapacear.
COALIZÃO
• Coordenação de quantidades ou preços. O 
caso extremo é o cartel em que se chega ao 
preço do monopólio.
• Pode haver conluios explícitos e tácitos.
• Os explícitos são, normalmente proibidos 
por lei.
• Conluios tácitos: empresas dominantes, 
pontos focais.
REPETIÇÃO
• E se o jogo for realizado outra vez?
• Os jogadores sabem que na segunda vez 
não haverá cooperação.
• Logo, não há incentivo para cooperação na 
primeira.
• Pode-se generalizar para qualquer número 
de repetições finitas.
JOGOS REPETIDOS
• Loja dominante com número finito de unidades.
• Se não valer a pena impedir a concorrência uma 
vez, não valerá nunca. Ou seja, não vale a pena 
ter fama de durona.
• Cartéis existem, obstáculos à concorrência 
existem. O que falha?
• Hipóteses simplificadoras: custos não 
conhecidos, modelagem finita não apropriada.
EQUILIBRIOS ADICIONAIS
• Todo o equilíbrio de Nash em jogo 
simples, também é em jogo repetido.
• Jogos com mais de um equilíbrio de Nash 
podem gerar repetições em que o equilíbrio 
não é nenhum dos originais.
• Situação de ameaças
AMEAÇAS
 Urgente Normal Rápida 
Especial 4,3 0,0 2,5* 
Comum 0,1 2,2* 0,1 
 
Primeiro ano: Especial, urgente
Segundo ano: mantém se o compromisso foi honrado, 
muda para comum normal caso contrário
Qual o novo equilíbrio?
INDUÇÃO À COOPERAÇÃO
• Coerção externa: punições adequadas, 
custo da estrutura.
• Cooperação espontânea: estratégia severa e 
de Talião.
• Probabilidade do jogo acabar.
• Fatores de desconto e somas infinitas.
DECISÕES SEQUENCIAIS
Árvores de decisão e jogos 
sequenciais
DECISÕES SEQUENCIAIS
• Após uma tomada de decisão espera-se um 
acontecimento para toma a próxima 
decisão
• O acontecimento pode ser aleatório (árvore 
de decisão) ou a decisão de outro (jogo 
sequencial)
• Forma matricial e estendida.
EXEMPLO
• Duas empresas, dominante e desafiante.
• Desafiante: entra ou não
• Dominante: acomoda ou luta
• Não entra, (0,10)
• Entra, luta (-1,9)
• Entra acomoda (3,7)
• Sub jogos e solução reversa
Ameaças e promessas: regulação
Credibilidade
Jogos sequencias contra o acaso
• Segundo jogador não é racional
• Podem ser estimadas probabilidades
• Valor esperado ou pessimista
• Indicar se é decisão ou acaso
Exemplo
• Recursos prováveis num terreno
• Companhia oferece 60 pelos direitos
• Opção para investimentos futuros se os atuais forem 
promissores: valor 600
• Exploração própria : 100 de custo inicial, 2000 de lucro 
se houver exploração positiva
• Supor probabilidade de haver o recurso de 60%
• E se houver uma opção de terceirizar após a descoberta 
do recurso?
• E se a empresa tiver outros terrenos para pesquisar?
Métodos ordinais multidecisor
Métodos Ordinais
• Problema: existem n ordenações 
(correspondendo a n critério ou n 
decisores). Como fazer uma ordenação 
justa?
• O que é uma ordenação justa?
Escolha justa-Axiomas de Arrow
• Independente em relação às alternativas 
irrelevantes
• Ordem total (sem intransitividades e sem 
incomparabilidades)
• Unanimidade de Pareto
• Universalidade
• SÓ MÉTODOS DITATORIAIS
Métodos de ditador
• Ditador puro
• Ditadores sucessivos (ou lexicográfico)
• De novo as medalhas
• Bábá x Azar
Método de Borda
• Chevalier de Borda
• Revolução francesa
• Soma de postos
• Nãorespeita a independência em relação 
às alternativas irrelevantes
• Exemplo piorado: Fórmula 1
Exemplo para fazer por Borda
D1 D2 D3
a b b
d a a
e e c
c c d
b d e
a 5
b 7
c 11
d 11
e 11
Borda: retira-se c, d
D1 D2 D3
a b b
e a a
b e e
a 5
b 5
e 8
Borda: retira-se c, d, e
D1 D2 D3
a b b
b a a
a 5
b 4
Dependo do conjunto de análise pode-se ter aPb, bPa
ou aIb. 
Método de Condorcet
• Resolver o paradoxo de Borda
• Considera apenas as alternativas duas a 
duas. 
• Constrói uma matriz binária
• Maria Jean de Caritat, Marquis de
Condorcet
Para o exemplo de Borda: 
comparações pareadas
a 1 x b 2
a 3 x c 0
a 3 x d 0
a 3 x e 0
b 2 x c 1
b 2 x d 1
b 2 x e 1
c 2 x d 1
c 1 x e 2
d 2 x e 1
Para o exemplo de Borda: matriz 
de Condorcet
a b c d e
a 0 1 1 1
b 1 1 1 1
c 0 0 1 0
d 0 0 0 1
e 0 0 1 0
B ganha de todos. É colocado em primeiro e 
retirado da matriz. Destilação descendente.
Para o exemplo de Borda: matriz 
de Condorcet
A ganha de todos. É colocado em segundo e 
retirado da matriz. Destilação descendente.
a c d e
a 1 1 1
c 0 1 0
d 0 0 1
e 0 1 0
Para o exemplo de Borda: matriz 
de Condorcet
c ganha de d que ganha de e que ganha de c. Ciclo 
de intransitividade. Não fornece ordenação. 
Paradoxo de Condorcet.
c d e
c 1 0
d 0 1
e 1 0
Método de Copeland:
a b c d e
a 0 1 1 1
b 1 1 1 1
c 0 0 1 0
d 0 0 0 1
e 0 0 1 0
a=3
b=4
c=1
d=1
e=1
Tirou a intransitividade. Empate é bem diferente de 
intransitividade.
Copeland=Condorcet quando não intrnasitividade.. 
Quando há. É melhor que Borda para resolver.
Tratamento de empates nas 
ordenações: Borda
: D1 D2
a,b a,b,c
c d
d
a 1,5+2
b 1,5+2
c 3+2
d 4+4
Tratamento de empates nas 
ordenações: Condorcet
: Substituir “ganhar” por “não perder”
a b c d
a 1 1 1 1
b 1 1 1 1
c 0 0 1 1
d 0 0 0 1
a,b empatado em primeiro, c em terceiro, d em quarto.
Tratamento de empates nas 
ordenações: Copeland
:
Fazer “linhas menos colunas”
a b c d
a 1 1 1 1
b 1 1 1 1
c 0 0 1 1
d 0 0 0 1
a,b empatado em primeiro, c em terceiro, d em quarto.
a=2, b=2, c=-1, d=-3
Borda no SIAD: Invertido
DECISÕES COM RISCO
Risco e utilidade
Decisão com risco
• É conhecida uma distribuição de 
probabilidade
• Valor médio, com seus problemas; moda
• Decisão eficiente: conceito de risco
• Escolha entre decisões eficientes
• Propensão e aversão ao risco.
Loterias
• Um evento estocástico com apenas dois 
resultados.
• P(A)=1-P(B)
Utilidade
• Verdadeiro valor do ganho
• Definida probabilisticamente. Se definida 
deterministicamente chama-se função de 
valor
• Exemplo: loteria do milhão, área para uma 
fábrica, nota numa matéria, tamanho de 
onda, salário, raspadinha...
Utilidade
• Aversão ao risco: utilidade marginal 
diminui
• Propensão ao risco: utilidade marginal 
aumenta
• Utilidade assintótica
• Teorias psicológicas da utilidade
Utilidade
• Utilidade de von Neumann: Indiferença 
entre obter um ganho e, com 100% de 
probabilidade e participar de uma loteria 
em que o maior valor tem probabilidade p 
e o menor 1-p. Determinar esse p.
• U(e) =pU(max) + (1-p)U(min)
• Se normalizado, U(e) = U(max)
• Críticas conduzem a funções de valor
Funções usadas para modelar a 
utilidade
• Raiz
• Ln[(a+bx)/c]
• Arctg
• tgh
PROCESSOS DE MARKOV
Definições básicas
• Estado de um sistema: situação em que se 
encontra em determinado tempo
• Vetor de estado: indica a probabilidade de cada 
estado, em um determinado instante ou etapa do 
processo
• Processo de Markov: a probabilidade de numa 
etapa o sistema se encontrar em um determinado 
estado, depende apenas do estado anterior (sem 
memória)
• Cadeia de Markov: processo de Markov discreto
Definições básicas
• Probabilidade de transição: a probabilidade de o 
sistema chegar ao estado j na etapa n+1, dado que 
na etapa n estava no estado i.
• Matriz de transição: matriz composta das 
probabilidades de transição
• Propriedades: produto de matrizes de transição é 
uma matriz de transição, produto de uma matriz 
de transição por um vetor de estado é um vetor de 
estado
• Transições sucessivas
Exemplos
• Viajar de várias formas
• Processos periódicos
• Estados absorventes
Matriz regular
• Pelo menos uma potência da matriz não tem nenhum 
valor nulo
• Comportamento estático: vP=v
• Significa tem um autovalor unitário
• O autovetor associado é o vetor de estado no infinito, ou 
vetor fixo.
• Vetor fixo independe do estado inicial:
•
fon
lim S(n) = 
fon
lim S(0). P n = S 
Cada linha da matriz converge para o vetor v
Exemplo: manutenção de uma 
máquina
• Esperar que a máquina quebre
• Trocar no começo do quarto mês
• Trocar no começo do terceiro mês
• Trocar no começo do segundo mês
1 – a máquina inicia o primeiro mês de operação e a substituição
foi planejada.
Q – a máquina inicia o primeiro mês de operação
e a substituição se deveu a quebra da anterior.
2 – a máquina inicia o segundo mês de operação.
3 – a máquina inicia o terceiro mês de operação.
4 – a máquina inicia o quarto mês de operação.
Exemplo: manutenção de uma 
máquina
• Custo de troca programada 500
• Custo de troca por quebra 1500
• Probabilidade de quebrar no mês 1: 0,1
• Probabilidade de quebrar até o mês 2: 0,2
• Probabilidade de quebrar até o mês 3: 0,5
• Probabilidade de quebrar até o mês 4: 1
• DETERMINE A POLÍTICA ÓTIMA
TEORIA DAS FILAS
Fogliatti, MC, Mattos, N.M.C., 
Teoria das Filas, 2007, Interciência
Teoria das Filas
• Surge no início do século XX para centrais 
de telefone.
• Existência de filas: clientes que precisam 
de um serviço.
• Fonte (população), fila, serviço, sistema
Fonte
• Universo onde se encontram a população que 
dará origem aos clientes
• População: finita, infinita. Influência na 
probabilidade de novas chegadas.
• Chegadas simples e em grupo
• Chegadas controláveis e incontroláveis
• Taxa de chegada (cliente por unidade de tempo). 
Pode ser constante ou aleatório. Mede-se o tempo 
entre duas chegadas.
• Clientes podem ser pacientes ou impacientes
Fila
• Simples e múltiplas
• Finita ou infinita
• Disciplina: FIFO (PEPS), FILO (PEUS), 
aleatória, prioridades.
Serviço
• Simples ou em grupo
• Tempo de serviço
• Taxa de serviço (numero de clientes por 
unidade de tempo)
Parâmetros e critérios
• Congestionamento: tempo do cliente é 
pouco valorizado
• Ociosidade: tempo do cliente muito 
valorizado
Parâmetros e critérios
• Comprimento médio da fila Lq
• Número médio de clientes no sistema L
• Tempo médio de espera na fila Wq
• Tempo médio de espera no sistema W
• Taxa de ocupação
• Probabilidade de haver n atendentes 
desocupados...
Parâmetros e critérios
• Pn Probabilidade de haver n elementos no 
sistema
• P (nt k) Probabilidade de haver k ou mais 
elementos no sistema
• P (W>t)
• J taxa de chegada. O seu inverso é o intervalo 
médio de chegada.
• P taxa de serviço e seu inverso é o tempo médio 
de serviço
• U Taxa de ocupação
Distribuições usuais
Exponencial negativa f(t) =a.exp (-at)
Poisson f(x)= (at)x.exp (-at)/x!
Cálculo de valor esperado, variância, CV
Propriedade inversa
Falta de memória: 
P(T>a+b/T>b)=P(T>a+b)/P(T>b)=P(T>a)
Distribuição de chegadas em relação à média
Relação fundamental
• L=OW
• Lq=OWq
• W=wq+1/P
• L=Lq+ O /P
Classificação das filas
• X/Y/Z/W
• Entrada, saída, número de servidores, 
outras propriedades (finita, paciente...)
• M/M/1
Nascimento e morte M/M/1
• Estado zero para 1 com chegada
• Estado 1 para zero com saída, para 2 com 
chegada
• PP1=OP0
• P1 =OP0 /P
• Generalizando: Pn = OnP0 /Pn ou 
• Pn = UnP0 
• Somatório dos P deve ser unitário
• Utilizando convergência chega-se à taxa de 
desocupação e seu valor
Nascimento e morte M/M/1
• O comprimento do sistema é igual ao valor 
médio do estado do sistema, somatório de 
n por Pn.
• L= O/(P - O)
• Para a fila, Lq=L-(1-Po)
Formulário M/M/1
Exemplo
• Caminhões a serem descarregados
• Chegada de 16 por dia
105
124
153
202
501
Tempo (minutos)Funcionário
Exemplo
• Caminhão parado: 3000/h
• Funcionário 1500/h 
• Dia de trabalho com 8h
• Quantos empregados contratar?
Formulário M/M/S
Exemplo
• Verificar o que é melhor para a fila: 
duplicar a velocidade de atendimento ou 
duplicar o número de servidores.
Comprimento Limitado e um 
servidor M/M/1/K
• On= O para n de 0 a k-1
• On=0 caso contrário
• Omédio= O(1-Pk)
• É preciso distinguir entre taxa de ocupação 
e taxa de pressão. A taxa de pressão deste 
caso equivale à de ocupação no caso 
M/M/1
Formulário para M/M/1/K
Exemplo
• Porto com um guindaste móvel de descarga e 
dois berços.
• Porto ocupado implica em desviar navios. Custo 
de 20000 por navio desviado e de 12000 por dia 
por navio parado.
• Chegadas markovianas de 3 navios por dia e 
atendimento de 5 navios por dia.
• Expansão para 3 beços custa 1000 por dia. Vale a 
pena?
Formulário para população finita 
(M/M/1/N)
M/G/1
Exemplo
• Chegada markoviana de 15 clientes por 
hora
• Tempo de atendimento médio de 3 minutos
• a)Com distribuição constante (variância 
nula)
• b)Com distribuição uniforme entre 1 e 5 
minutos
• c)Com distribuição exponencial
GESTÃO DE ESTOQUES
Papel dos estoques
• Haver abastecimento quando a procura é superior à oferta
• Manter o abastecimento quando não há produção
Modelos de gestão de estoques
• Determinísticos ou Estocásticos
• Quanto comprar
• Quando comprar
• Minimização de custos (incluindo perda de 
oportunidade)
• Acumulação de estoques – custos de posse
• Baixo estoque – mau serviço
• Modelos diferentes para vários itens –
classificação ABC
Custos dos estoques
• Aquisição: pagamento ao fornecedor. C1.Q
• Encomenda: custos administrativos, 
geralmente fixos e sub-avaliados. A
• Custo de posse: seguros, aluguel de 
espaço, capital imobilizado, obsolescência 
• Custos de quebra
Modelos determinísticos
• Reposição: instantânea, gradual
• Procura: constante, variável
• Quebra: permitida, não permitida
• Preço: constante, com descontos
Modelos determinísticos
• Reposição instantânea, procura constante, 
quebra não permitida, sem descontos
• Q: Quantidade encomendada
• T: intervalo entre encomendas
• r: procura por unidade de tempo 
(determinada por modelos de previsão, 
aqui suposta conhecida)
• Q=Tr
Modelos determinísticos
• Custo de encomenda: A
• C2: manter uma unidade de artigo numa 
unidade de tempo. Custo de todas as 
unidade, variáveis no tempo, é a integral ao 
longo do período T= C2(Q/2)T
• CT=A+C2(Q/2)T
• Ciclos de tamanho diferente não são 
comparáveis.
Modelos determinísticos
• Custo por unidade de tempo
• K=CT/T=A/T + C2Q/2=Ar/Q + C2Q/2
• Custo mínimo: deriva e iguala a zero
• Q*=(2Ar/C2)1/2
• E os custos de aquisição C1Q?
• A derivada é nula, não interferem nos 
valores ótimos das variáveis de decisão
Análise de sensibilidade
Modelo robusto, curva quase plana no mínimo.; Melhor 
comprar mais que menos. E o JIT,como fica?
Outros casos
• Reposição não instantânea: fazer o gráfico e 
calcular nova integral
• Demanda variável: fazer o gráfico e calcular nova 
integral
• Quebra permitida: incluir o custo de quebra. 
Nova variável é quanto de quebra se permite. 
Problema com derivadas parciais
• Custo de encomenda variável: incluir esse custo 
no custo total e resolver novo problema de 
otimização
Exemplo
• Consumo: 10000/ano
• Custo unitário: 3100 até 2000 unidades, 3000 
entre 2000 e 5000 unidades, 2900 para mais de 
5000 unidades
• Custo fixo 5000
• Custo de posse 600/unidade/ano (na verdade tem 
pequenas variações pelos descontos)
• Calcular o lote ótimo
Modelos Estocásticos
• Encomenda fixa no ponto de encomenda, 
intervalos variáveis
• Intervalos de tempo fixos, quantidade 
variável
• Ambas trabalham com estoques de 
segurança
• Simulação
FIM