Pesquisa Operacional AULA 6

Prévia do material em texto

PESQUISA OPERACIONAL 
AULA 6 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Ricardo Zanardini 
 
 
 
 
2 
CONVERSA INICIAL 
Olá! Chegamos à nossa 6ª aula de Pesquisa operacional! 
Ao longo do nosso curso, estudamos diversos temas importantes 
aplicados à tomada de decisões. Nessa aula iniciaremos os nossos estudos 
tratando também de um tema relacionado à tomada de decisões, conhecido 
como teoria dos jogos. 
No entanto, o que difere esse assunto dos demais é que na teoria dos 
jogos, as consequências das decisões tomadas não dependem apenas de uma 
única estratégia ou linha de pensamento, mas sim de estratégias muitas vezes 
distintas ou até mesmo conflitantes. 
Em seguida, veremos o que é simulação e quais são as suas vantagens 
e, finalmente, vamos falar sobre inteligência computacional e como isso 
pode ser extremamente importante para a humanidade. 
O que é teoria dos jogos e para que serve isso? 
Um bom início para a nossa conversa é um trecho do filme “Uma Mente 
Brilhante” (A Beautiful Mind), de 2001, onde o matemático John Nash, 
contrariando uma famosa tese de Adam Smith, nos mostra quais são as 
possibilidades e consequências das decisões que podem ser tomadas quando 
mais do que um indivíduo tem as mesmas ambições. 
Confira um trecho do filme! 
https://www.youtube.com/watch?v=4qmlJvytsBU&feature=youtu.be 
Como você pôde notar, graças a Nash, muitas pessoas, físicas ou 
jurídicas, sabem que as decisões devem ser tomadas para que todos possam 
atingir as suas metas. No entanto, muitos ainda seguem os princípios de Smith 
onde os próprios interesses estão acima do bem de todos. 
Esses conceitos e pensamentos sofreram e sofrem mudanças com o 
passar do tempo. No entanto, os princípios da teoria dos jogos continuam 
servindo de base para eles. 
 
 
3 
A seguir, veja uma produção que nos apresenta de maneira divertida um 
famoso problema conhecido como “dilema do prisioneiro”. 
https://www.youtube.com/watch?v=lFLxpiVH5qc&feature=youtu.be 
O dilema do prisioneiro é a base da teoria dos jogos e para sabermos 
mais sobre esse importante tema, vamos ao nosso texto. 
Teoria dos Jogos 
A teoria dos jogos é um importante campo da pesquisa operacional que 
tem como principal objetivo analisar escolhas dentro de um cenário onde há 
mais do que um participante de modo que as chances de ganho de um dos 
participantes ou a chance de ganhos relativos de mais do que um dos 
participantes seja a melhor possível. 
A princípio, quando se fala em teoria dos jogos, talvez não fique muito 
evidente a importância ou a extensão desses estudos, bem como a relevância 
dos resultados. Por volta de 1930 foi dado início aos primeiros estudos sobre a 
teoria dos jogos. Essa teoria é utilizada quando há uma disputa por objetivos 
definidos e pode ser utilizada em situações estratégicas tais como concorrência 
entre empresas, possibilidades de investimentos, eleições e guerras, além de 
muitas outras situações que envolvem ganhos ou perdas. 
Para que a teoria dos jogos seja utilizada de modo bastante satisfatório, 
é preciso conhecer bem os mecanismos envolvidos, ou seja, conhecer as 
possibilidades reais de ganhos, as regras referentes ao processo e as 
possibilidades dos oponentes, além de pensar nas estratégias que podem ser 
adotadas pelos adversários. 
Na teoria dos jogos, as escolhas feitas pelos envolvidos influenciam nos 
resultados e, nem sempre, para que alguém ganhe os demais devem perder. 
Muitas vezes as melhores decisões podem ser tomadas para que todos ou a 
maior parte dos participantes obtenham ganhos. Como nem sempre há uma 
única solução ótima, pois o cenário da teoria dos jogos é um cenário de 
disputa, a meta é verificar as possibilidades existentes, as consequências das 
decisões a serem tomadas e, é claro, o que efetivamente será feito. 
 
 
4 
Atualmente é possível afirmar que uma das mais importantes áreas de 
aplicação é a dos jogos empresariais. É fundamental que um gestor tenha 
conhecimentos sobre teoria dos jogos para que possa tomar decisões de uma 
forma mais consciente. Pensando nos jogos empresariais, cada empresa é 
classificada como sendo um jogador. As ações são as decisões tomadas, tais 
como definição de preços, estratégias de mercado, investimentos em marketing 
ou em novas tecnologias e assim por diante e as regras são as formas de 
atuação permitidas. 
Um elemento a ser considerado é a maneira de pensar e de agir, pois 
qualquer decisão a ser tomada influencia diretamente ou indiretamente em 
fatores empresariais tais como crescimento, lucro e até mesmo a sobrevivência 
das empresas. 
Duas modalidades são as mais comuns: 
 Escolhas simultâneas – cada jogador toma as decisões sem saber as 
escolhas dos demais jogadores. 
 Escolhas sequenciais – as decisões são tomadas após ações 
realizadas pelos demais jogadores. 
Para os problemas em questão, temos algumas opções de soluções 
para o problema. 
A primeira delas se refere à estratégia dominante. Nesse caso, 
independentemente da escolha dos outros jogadores, é a melhor opção 
possível para o jogador. Na estratégia dominante o jogador não depende das 
decisões dos demais jogadores. A estratégia dominante, individualmente, é a 
melhor, mas nem sempre representa a melhor solução para o grupo de 
jogadores. 
Como é muito comum os jogadores adotarem a estratégia dominante, 
dizemos que é a solução de equilíbrio ou equilíbrio do jogo. Nesse caso não 
há possibilidade de melhorias unilaterais, ou seja, individualmente, é a melhor 
solução. 
 
 
5 
Por outro lado, a melhor solução individual não representa, 
necessariamente, a melhor solução para todos os envolvidos. 
O exemplo a seguir denominado de dilema do prisioneiro, inventado em 
1950 por Merrill Flood e Melvin Dresher e adaptado e divulgado por 
A.W.Tucker, é um clássico problema da teoria dos jogos e ilustra bem as 
possibilidades de solução do problema em decorrência das decisões 
individuais tomadas. 
Vamos supor que dois suspeitos A e B foram detidos pela polícia, mas 
como as provas não são suficientes, é oferecido um acordo para cada um 
deles: 
 Se um suspeito confessar que o crime ocorreu e o outro permanecer em 
silêncio, o que confessou fica livre e o outro cumprirá uma pena de 10 
anos de prisão. 
 Se ambos ficarem em silêncio, pelas provas, cada um cumprirá 1 ano de 
prisão. 
 Se ambos confessarem, cada um cumprirá 5 anos de prisão. 
Como os suspeitos estão em salas separadas, um desconhece a 
decisão do outro. 
A pergunta é a seguinte: como cada suspeito irá reagir ao acordo? 
Ambos vão confessar? Ambos ficarão em silêncio? Apenas um irá confessar e 
o outro cumprirá a pena sozinho? 
Para que possamos analisar melhor as possibilidades e a melhor 
decisão a ser tomada, o primeiro passo é construir uma matriz de resultados 
que é uma forma esquemática de visualização do problema. 
 
 
 
6 
 
Aqui temos as possíveis decisões tomadas pelos suspeitos e as 
respectivas penas a serem cumpridas. Nesse cenário, o melhor para cada 
preso é a redução da pena. As possibilidades são as seguintes: 
 Se A confessar e B confessar, cada suspeito cumprirá 5 anos de prisão. 
 Se A confessar e B calar, A será solto e B cumprirá 10 anos de prisão. 
 Se B confessar e A calar, B será solto e A cumprirá 10 anos de prisão. 
 Se ambos calarem, cada suspeito cumprirá 1 ano de prisão. 
Como os suspeitos estão incomunicáveis entre si, eles não poderão 
entrar em um acordo para decidirem em conjunto o que farão. O raciocínio, 
então, acaba ocorrendo de forma hipotética onde a decisão será tomadaatravés de suposições. 
O suspeito A pode pensar assim: Se B ficar calado e A ficar calado, cada 
um cumprirá 1 ano de prisão, mas se B ficar calado e A confessar, A será solto. 
Nesse caso, confessar é a melhor opção. 
Por outro lado, Se B confessar e A ficar calado, A cumprirá 10 anos de 
prisão e se B confessar e A confessar, A cumprirá 5 anos de prisão. Nesse 
caso, confessar também é a melhor opção. 
Para o suspeito B as possibilidades e consequências são as mesmas. 
Note que em todos os casos confessar é a melhor opção. Podemos 
dizer que confessar é a estratégia dominante, pois apresenta o melhor 
resultado individual independente da escolha do outro suspeito. Tanto o 
suspeito A quanto o suspeito B não precisarão se preocupar com a decisão 
alheia. Pensando nessas possibilidades, confessar é a decisão esperada para 
 
 
7 
ambos e essa decisão é chamada de solução de equilíbrio. Nenhum suspeito 
conseguirá melhorar a situação agindo individualmente. Essa decisão é a 
decisão mais racional a ser tomada por ambos. 
A questão do dilema do prisioneiro é que a solução mais racional não é 
a melhor solução possível para os dois suspeitos. Se ambos ficarem calados, 
cada um cumprirá 1 ano de prisão. Mas para que isso aconteça, surge um 
outro dilema: o dilema da confiança. Será que, mesmo que ambos sejam 
cúmplices, se um suspeito ficar calado o outro também ficará? Ou exatamente 
pelo fato do outro suspeito saber dessa cumplicidade, ele confessará pensando 
na chance de ser solto? Ou seja, mesmo que houvesse a possibilidade de um 
acordo prévio entre os dois suspeitos, será que diante da promessa de ficar 
livre um deles não seria capaz de ceder ao acordo pensando em um benefício 
próprio? 
O dilema do prisioneiro é uma abstração de outros problemas que 
ocorrem em situações do cotidiano onde a escolha por um resultado individual 
melhor, muitas vezes motivada por um esquema de incentivos, implica em uma 
traição mútua. Por outro lado, a colaboração, em diversas situações, pode 
trazer melhores resultados para todos. Segundo John Nash, importante 
matemático norte-americano que contribuiu muito para a teoria dos jogos, o 
melhor resultado é quando todos do grupo fazem o melhor para si... e para o 
grupo. 
Vamos imaginar agora que duas empresas concorrentes têm a 
possibilidade de investir em melhorias no atendimento aos clientes. 
Se apenas uma das empresas realizar os investimentos, irá aumentar o 
número de clientes vindos da empresa concorrente. Estudos mostram que o 
aumento será suficiente para cobrir os custos oriundos das melhorias e 
aumentará os lucros. Se ambas investirem em melhorias, o número de clientes 
de cada empresa não terá mudanças significativas e parte do lucro será 
utilizado para cobrir os custos das melhorias, reduzindo, portanto, o lucro total 
das empresas. 
 
 
 
8 
A tabela a seguir apresenta as estimativas de lucro, em milhões de reais, 
com e sem os respectivos investimentos. 
 
Se ambos investirem, cada empresa terá lucros na ordem de R$ 
10.000.000,00. Se ambas não investirem, o lucro de cada empresa será de R$ 
14.000.000,00. No entanto, se apenas a empresa A fizer o investimento, seu 
lucro será de R$ 19.000.000,00 contra R$ 5.000.000,00 da empresa B. Se a 
Empresa A não investir e a B sim, os lucros serão de R$ 6.000.000,00 e R$ 
18.000.000,00, respectivamente. 
Cada empresa pode imaginar a estratégia da empresa concorrente e 
verificar qual é a melhor alternativa a ser tomada, ou seja, se é interessante 
investir ou não. 
Observando a matriz de resultados, a empresa A tem duas opções. Se a 
empresa B investir em melhorias, a melhor opção para a empresa A é investir 
também. Se a empresa B não investir em melhorias, a melhor alternativa é 
investir em melhorias. 
Em relação à empresa B, as conclusões são similares: se A investir em 
melhorias, é mais conveniente para a empresa B investir e se A não investir, B 
tem maior lucro se fizer os investimentos em melhorias. Logo, a estratégia 
dominante de cada empresa é investir em melhorias, mas é visível que esses 
investimentos, mesmo que sejam melhores para os clientes, não representam 
o melhor para as empresas. Uma solução interessante economicamente para 
as empresas é não realizar os investimentos, mas se essa decisão for tomada 
e a empresa concorrente investir, os prejuízos serão ainda maiores. 
Vamos estudar um pouco mais sobre esta teoria? O seguinte artigo trata 
do uso da Teoria dos jogos para auxiliar a tomada de decisão no setor do gás 
natural. 
http://www.portalabpg.org.br/PDPetro/3/trabalhos/IBP0206_05.pdf 
 
 
9 
E neste artigo, temos um estudo comparativo entre a teoria dos jogos 
cooperativos e uma heurística, ambos aplicados a um problema real de 
alocação de custos. 
http://www.scielo.br/scielo.php?pid=S0101-
74382002000100005&script=sci_arttext 
Trocando Ideias 
Vamos aproveitar o que aprendemos até agora para participarmos do 
fórum dando exemplos e opiniões sobre situações do nosso cotidiano, pessoal 
ou profissional, onde a teoria dos jogos está presente. 
Sua participação é muito importante! 
Está preparado? Vá até o fórum, que está disponível no Ambiente Virtual 
de Aprendizagem e bons estudos! 
Simulação 
Além da teoria dos jogos, uma técnica muito utilizada para prever 
fenômenos ou criar e testar projetos é a simulação. 
Mas o que é simulação? 
A simulação é uma técnica de criar ou recriar situações reais 
através de técnicas matemáticas adequadas. 
Confira antes de prosseguir um texto que explicar de maneira mais 
aprofundada o que é a Simulação. 
Muitas vezes, antes de desempenharmos uma tarefa ou de criarmos 
algo, precisamos desenvolver estudos para que possamos verificar o 
funcionamento dessa tarefa ou sistema com o objetivo de entendermos melhor 
o funcionamento, verificarmos a existência ou não de falhas e de pontos a 
serem melhorados, além de outras questões que podem ser observadas e 
analisadas com isso. E uma forma muito eficaz de fazer isso é recorrer então à 
simulação. 
 
 
10 
Podemos dizer que a simulação é a criação de um modelo destinado a 
reproduzir um problema real onde é possível realizar experimentos ou 
desenvolver modelos matemáticos onde esses experimentos podem ser feitos 
com o auxílio de um computador. 
Em alguns casos, a simulação é analítica. Um modelo matemático é 
utilizado e valores aleatórios ou não são atribuídos às variáveis independentes 
do problema para que possamos determinar o que ocorre com as variáveis 
dependentes do problema, ou seja, que conclusões podem ser obtidas a partir 
desse estudo. 
É importante ressaltar que no caso da simulação, não temos uma 
solução ótima, mas sim um estudo sobre o comportamento que podemos 
esperar do problema real com base nos estudos desenvolvidos com o modelo. 
O processo de simulação tem como objetivo entender melhor o 
funcionamento de um determinado processo, bem como identificar problemas 
ou sugerir alterações. Em muitos casos, a simulação é importante, pois testes 
reais podem gerar grandes prejuízos caso existam falhas no projeto. 
Através da simulação é possível obter resultados muito satisfatórios na 
avaliação de um sistema novo ou até mesmo em relação a sistemas já 
existentes. 
Por questões de facilidade na criação do modelo, o uso da informática 
na simulação é bastante frequente. Dentre vários softwares de simulação 
existentes, um produto bastante utilizado e muito eficiente é o Arena. 
O arena contém todos os recursos necessários para a modelagem de 
processos, animações e análise de resultados. A criação do processo de 
simulação é visual, o que simplifica bastantea modelagem. 
Além da versão de uso comercial, que é uma versão paga, há também a 
versão estudante, que é uma versão gratuita, porém com limitação no número 
de entidades que podem ser utilizadas nos processos de simulação. 
Uma das vantagens do Arena é que, além da criação do modelo e 
obtenção dos dados referentes ao processo de simulação, é possível também 
 
 
11 
criar animação, um importante recurso que facilita muito a visualização do 
processo e também a apresentação do modelo criado. 
Para fazer o download do Arena, o primeiro passo é acessar o link 
http://www.arenasimulation.com. 
 
 
 
Em seguida, ainda na página inicial, devemos clicar no ícone referente 
ao download da versão estudante. 
 
O próximo passo é clicar em “Register”. 
 
 
12 
 
E preencher o seguinte formulário: 
 
 
 
 
13 
Após preencher os campos necessários e clicar em “Submit”, veremos 
uma tela de confirmação do cadastro. 
 
Com o e-mail e senha, basta efetuar o login e fazer o download do 
software. 
 
Se desejar trocar a senha, clique em “My Profile” e faça a alteração. 
Depois de feita a troca, é só clicar em “Submit”. 
 
 
 
14 
Assim que o download estiver concluído, descompacte a pasta e abra o 
arquivo “autorun”. 
 
Na tela inicial, você deverá clicar em “Install Arena”. 
 
O próximo passo é clicar em “Next”. 
 
 
15 
 
Concordando com os termos da licença do software, basta clicar na 
primeira opção e depois em “Next”. 
 
 
Como iremos utilizar a versão estudante, é preciso preencher o campo 
destinado ao número de série com a palavra “STUDENT” e clicar em “Next”. 
 
 
16 
 
É possível instalar o Arena em um diretório padrão ou escolher o local 
onde ele será instalado. 
 
Após realizar esses passos, clique em “Install” para iniciar a instalação. 
 
 
17 
 
 
Após alguns minutos a instalação estará concluída! 
 
Agora é só aproveitar os importantes recursos que esse software de 
simulação nos oferece. 
 
 
18 
Um software muito utilizado na área de simulação é o Arena. É um 
software proprietário, mas é possível utilizar a versão estudante, sem custo 
algum. A diferença entre a versão paga e a versão gratuita é que a versão 
gratuita não pode ser utilizada com fins comerciais e tem um número limitado 
de entidades. 
Para fazer o download do Arena, basta clicar no botão a seguir e 
acompanhar os passos necessários: 
https://www.arenasimulation.com/ 
O próximo vídeo apresenta uma introdução ao Arena utilizando a versão 
estudante. Nesse vídeo é apresentado um modelo simples, mas bastante 
interessante de verificação de qualidade de peças. 
http://youtu.be/Av94qHwpp7I 
Confira agora o vídeo a seguir que nos mostra o uso do simulador 
FlexSim General Purpose em uma linha de produção para uma indústria 
farmacêutica. Isto fará com que você apreenda mais ainda sobre o assunto 
desta aula. 
https://www.youtube.com/watch?v=A4unk7GNXbA&feature=youtu.be 
Inteligência Computacional 
Como você pode notar, praticamente tudo o que estudamos até aqui 
envolve, além dos conhecimentos matemáticos necessários, o uso de 
computadores. 
É importante ressaltar que esse avanço tecnológico faz com que a 
resolução de problemas complexos seja feita de um modo mais rápido e 
eficiente. 
E que atualmente as pesquisas científicas estão cada vez mais focadas 
em criar sistemas inteligentes e mais próximos da forma humana de pensar e 
de tomar decisões. São sistemas inspirados na natureza que tentam, cada vez 
mais, aprimorar formas de aprendizagem, raciocínio e percepção. 
 
 
19 
Esse campo em constante evolução é o que chamamos de Inteligência 
Computacional. 
Veja uma introdução à inteligência artificial. 
Acompanhe com atenção! 
https://www.youtube.com/watch?v=XeTsDjxhZvA&feature=youtu.be 
Para sabermos um pouco mais sobre aplicações da inteligência artificial, 
vamos assistir a esse vídeo. 
https://www.youtube.com/watch?v=7bwgLKjMBVA 
Um estudo sobre Redes Sociais feito através de uma simulação 
utilizando a modelagem computacional e também a inteligência artificial pode 
ser visto a seguir! 
https://www.youtube.com/watch?v=QwNDUt_M1Fc&feature=youtu.be 
 
Já o vídeo a seguir está em espanhol, mas mesmo assim é possível ver 
como a inteligência computacional pode ser utilizada para a identificação do 
câncer de mama. 
https://www.youtube.com/watch?v=K3JTOOOr8ds&feature=youtu.be 
Sugestão de leituras 
Chegamos ao final de mais uma aula. Como, em qualquer situação, 
sempre há algo a mais a ser estudado, a ser aprendido, temos algumas 
sugestões de leitura para sabermos mais: 
Um site muito bacana sobre teoria dos jogos: 
http://www.teoriadosjogos.net/index.asp 
Uma apostila sobre teoria dos jogos: 
http://www.ericolisboa.eng.br/cursos/apostilas/po/cap8.pdf 
 
 
20 
O link a seguir nos leva a um artigo sobre um modelo de simulação 
aplicado ao conceito da produção enxuta no ensino de engenharia de 
produção: 
http://periodicos.utfpr.edu.br/index.php/revistagi/article/viewFile/624/675 
Para conferir mais alguns links sobre os recursos do Arena, clique nos 
tópicos a seguir: 
 Input Analyzer: 
https://www.youtube.com/watch?v=Jsg55gSunkM&feature=youtu.be&list=PL4U
XmHxozBIfNUJq3VwO-vitYHUnmOgBh 
 Animação Gráfica: 
https://www.youtube.com/watch?v=cBhSBFDuApQ&feature=youtu.be&list=PL4
UXmHxozBIfNUJq3VwO-vitYHUnmOgBh 
 Recursos do Modelo: 
https://www.youtube.com/watch?v=FspqGQM9kEw&feature=youtu.be&list=PL4
UXmHxozBIfNUJq3VwO-vitYHUnmOgBh 
 Relatório de Simulação: 
https://www.youtube.com/watch?v=V5Sq5oV_gVY&feature=youtu.be&list=PL4U
XmHxozBIfNUJq3VwO-vitYHUnmOgBh 
Para sabermos mais sobre redes neurais, uma leitura interessante é a 
de uma dissertação sobre redes neurais artificiais: http://www2.ica.ele.puc-
rio.br/Downloads%5C33/ICA-introdu%C3%A7%C3%A3o%20RNs.pdf