93
PESQUISA OPERACIONAL Slide 1 de 93 home O P PERACIONAL ESQUISA Mário Sérgio Leite Anand Cheela Alves Jales de Queiroz

Pesquisa Operacional

Embed Size (px)

Citation preview

Page 1: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 1 de 93home

OP PERACIONAL

ESQUISA

Mário Sérgio LeiteAnand Cheela Alves Jales de Queiroz

Page 2: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 2 de 93home

AGENDA1. Introdução a Pesquisa Operacional

1.1 Aspectos Históricos1.2 Definição de Pesquisa Operacional

2. Programação Matemática2.1 Programação Linear

2.1.1 Caso Portman-Johansson2.2 Fluxos em Redes

2.2.1 Caso Caminho Mínimo Casa-Ufersa3. Modelos Estocásticos

3.1 Teoria dos Jogos3.1.1 Caso do Dilema do Prisioneiro3.1.2 Aplicação: Tese de Pós-graduação

3.2 Teoria de Filas3.2.1 Aplicação: Artigo

4. Análise de Demanda4.1 Aplicação: Artigo

5. Processos Decisórios5.1 Caso do Terreno com (ou sem) Petróleo

6. Modelagem6.1 Definição de Modelagem6.2 Tipos de Modelagem6.3 Arena

7. Referências

Page 3: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 3 de 93home

Introdução àPesquisa Operacional

Page 4: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 4 de 93home

2ª Guerra Mundial

Imagem retirada do filme “O Resgate do Soldado Ryan”

Page 5: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 5 de 93home

Aspectos históricosNa 2ª Guerra Mundial, a Pesquisa Operacional surgiu para resolver problemas

- de natureza logística, - de natureza tática e - de estratégia militar.

Os problemas eram complexos, com necessidade de envolvimento de técnicas matemáticas complexas.

Com o fim do conflito, houve a transferência do conhecimento adquirido para a área civil.

Page 6: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 6 de 93home

Mas afinal, o que é

Pesquisa Operacional?

Page 7: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 7 de 93home

Definição de PO

É uma abordagem científica para a tomada de decisões.

É ciência devido as técnicas matemáticas e recursos com-putacionais (objetividade) e é arte porque depende mui-to da criatividade e experiência de quem aplica os con-ceitos de PO (subjetividade).

Introdução à Engenharia de Produção, BATALHA.

Page 8: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 8 de 93home

Definição de PO

- Se um dado combustível é obtido de uma mistura de produto de preços variados, qual a composição de menos custo com poder calorífico suficiente?

- Se existem vários caminhos que ligam duas cidades, qual é a que propicia o mínimo de gasto de combustível?

- Se o espaço para armazenamento é limitado, de quanto deve ser o pedido de material para atender a demanda de um certo período?

Introdução a Pesquisa Operacional, MORAES.

Exemplos de Problemas de Tomada de Decisão:

Page 9: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 9 de 93home

ProgramaçãoMatemática

Page 10: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 10 de 93home

Um modelo de programação matemática representa alternativas ou escolhas desse problema como variáveis de decisão e procura por valores dessas variáveis de decisão que minimizam ou maximizam funções dessas variáveis, chamadas funções objetivos, sujeito a restrições sobre os possíveis valores dessas variáveis de decisão. Abaixo os sub-itens:

- Programação Linear- Programação Discreta- Programação Não-linear- Fluxo de Redes- Programação Multi-objetivos

Programação Matemática

Introdução à Engenharia de Produção, BATALHA

Page 11: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 11 de 93home

Programação Linear e Fluxo de Redes

Page 12: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 12 de 93home

Prog. Linear e Fluxo de Redes

Os problemas de Programação Linear (PL) buscam a distribuição eficiente de recursos limitados para atender um determinado objetivo, em geral, maximizar lucros ou minimizar custos. Em se tratando de PL, esse objetivo é expresso através de uma função linear, denominada de "Função Objetivo".

Programação Linear

Page 13: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 13 de 93home

Prog. Linear e Fluxo de RedesPara a resolução de problemas de Programação Linear, usa-se gráficos, comando solver do excel, LINDO, etc

Linear Interactive and Discrete Optimizer

Page 14: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 14 de 93home

CasoPortman-Johansson

Page 15: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 15 de 93home

Considere que você está saindo com duas mulheres:

Natalie Portman Scarlett Johansson

Page 16: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 16 de 93home

Restrições :

- Uma não pode saber da outra. Para isso , você tem que levá-las a lugares diferentes em dias diferentes. (restrição operacional)

- O dinheiro é limitado, portanto você não pode sair todos os dias. (restrição logística/ matemática)

- O tempo é limitado, portanto deve haver um planejamento do tempo gasto com cada uma. (restrição logística/matemática)

Exemplo 1: Caso Portman-Johansson

Page 17: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 17 de 93home

Natalie Portman

-É chique, só gosta de restaurantes caros (de Tenda pra cima), num encontro com ela você vai gastar R$180,00.

-É calma, sossegada, um encontro com ela dura 2 horas.

x1

Page 18: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 18 de 93home

Scarlett Johansson

-É mais simples, gosta de lugares mais baratos (como o sebosão), num encontro com ela você vai gastar R$100,00.

-É agitada, gosta de fazer muitas coisas na noite, um encontro com ela dura 4horas.

x2

Page 19: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 19 de 93home

Quantas vezes você vai poder sair com Natalie numa semana? E com Scarlett?

Exemplo 1: Caso Portman-Johansson

Você pode gastar R$ 800,00 por semana com elas.

Você tem 20 horas livres para sair com elas na semana.

Page 20: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 20 de 93home

Chamemos assim:

x1 a quantidade de vezes que você sai com Natalie Portman.

x2 a quantidade de vezes que você sai com Scarlett Johansson.

Exemplo 1: Caso Portman-Johansson

Page 21: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 21 de 93home

Portanto teremos:

Resumindo:

- Se você sai x1 vezes com Natalie por semana e cada noite com ela custa R$180,00, então sair com Natalie custará 180 x1. Com Scarlett será 100 x2. A mesma lógica se aplica ao tempo.

{ 800100180 21 xx2042 21 xx

Exemplo 1: Caso Portman-Johansson

Page 22: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 22 de 93home

Exemplo 1: Caso Portman-Johansson

{ 800100180 21 xx2042 21 xx

Esse sistema de equação elaborado no slide passado são as restrições do modelo.

Como iremos resolver esse problema? Existem vários métodos para resolver problemas de programação linear (gráficos, solver, lindo, etc) porém iremos simplificar elaborando três alternativas de solução:

ALTERNATIVA 1: x1 = 2 e x2 = 4; ALTERNATIVA 2: x1 = 3 e x2 = 3; ALTERNATIVA 3: x1 = 3 e x2 = 2.

Page 23: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 23 de 93home

Vamos testar as alternativas!Lembre-se que o limite é R$ 800,00 e 20horas.

Alternativa 3 - x1 = 3 e x2 = 2:180 x 3 + 100 x 2 = R$740,002 x 3 + 4 x 2 = 14horas

Alternativa 2 - x1 = 3 e x2 = 3:180 x 3 + 100 x 3 = R$840,00 2 x 3 + 4 x 3 = 18 horas

Alternativa 1 - x1 = 2 e x2 = 4:180 x 2 + 100 x 4 = R$760,002 x 2 + 4 x 4 = 20 horas

OK!

OK!

Errado!

Exemplo 1: Caso Portman-Johansson

Page 24: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 24 de 93home

Qual é o seu objetivo? Segue abaixo dois objetivos diferentes:

1- Sair o máximo de vezes com as duas. Matematicamente teremos: MAX( x1 + x2 ).

2- Sair o máximo de vezes com as duas mas com notável preferência por Natalie Portman. Matematicamente teremos: MAX( 3x1 + x2 ).

Exemplo 1: Caso Portman-Johansson

Page 25: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 25 de 93home

Seguindo o Objetivo 1, analisamos as duas alternativas válidas:

Alternativa 1 : x1 = 2 e x2 = 4: x1 + x2 = 6

Alternativa 3 : x1 = 3 e x2 = 2: x1 + x2 = 5

Portanto, se o objetivo for sair o máximo possível com as duas, sem preferências, você deve sair duas vezes com Natalie Portman e quatro vezes com Scarlett Johansson em uma semana.

Objetivo 1: MAX( x1 + x2 )

Exemplo 1: Caso Portman-Johansson

Page 26: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 26 de 93home

Seguindo o Objetivo 2, analisamos as duas alternativas válidas:

Alternativa 1 : x1 = 2 e x2 = 4: 3x1 + x2 = 10

Alternativa 3 : x1 = 3 e x2 = 2: 3x1 + x2 = 11

Portanto, se o objetivo for sair o máximo possível com as duas, mas com uma clara preferência por Portman, você deve sair três vezes com Natalie Portman e duas vezes com Scarlett Johansson em uma semana.

Objetivo 2: MAX( 3x1 + x2 )

Exemplo 1: Caso Portman-Johansson

Page 27: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 27 de 93home

Exemplo 1: Caso Portman-Johansson

Modelo com o 1º objetivo:

Função objetivo: MAX( x1 + x2 )

Restrições:

Condições de não-negatividade: x1, x2 ≥ 0

800100180 21 xx2042 21 xx

Modelo com o 2º objetivo:

Função objetivo: MAX( 3x1 + x2 )

Restrições:

Condições de não-negatividade: x1, x2 ≥ 0

800100180 21 xx2042 21 xx

LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões: modelagem em Excel. São Paulo: Campus, 2006. (Adaptado)

Page 28: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 28 de 93home

Modelos de programação em redes têm sido utilizados com sucesso em diversos programas como fluxos em uma rede ou grafo. Exemplos:

- Problema de Caminho Mínimo- Problema de Caminho Máximo- Problema de Árvore Geradora Mínima- Problema de Fluxo Máximo- Problema de Fluxo de Custo Mínimo

Prog. Linear e Fluxo de Redes

Introdução à Engenharia de Produção, BATALHA

Fluxo de Redes

Page 29: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 29 de 93home

Caminho mínimoCasa-Ufersa

Caso

Page 30: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 30 de 93home

Page 31: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 31 de 93home

Page 32: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 32 de 93home

Page 33: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 33 de 93home

Page 34: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 34 de 93home

S2

S1

S16

S5

S4

S3

S24

S9

S8 S17S11

S28

S10

S7

S6

S13S14

S15S23

S22

S21S20

S19S18

E1

E2 E4

E5

E6

E7

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

S25

3’10’’

S26 S27

S12

E91’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

S27

1’

18’’

Caso Caminho Mínimo Casa-UfersaRede de Caminhos Possíveis

X

1’15’’

37’’

12’’

41’’ 15’’

50’’

25’’

4’33’’1’32’’

Page 35: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 35 de 93home

S1 – A:22’’, F:38’’

S2 – A:30’’, F:35’’S3 – A:27’’, F:49’’

S5 – A:40’’, F:45’’S4 – A:18’’, F:48’’

S8 – A:40’’, F:1’15’’

S6 – A:32’’, F:43’’

S7 – A:34’’, F:50’’

S10 – A:30’’, F:24’’

Semáforos

S9 – A:29’’, F:50’’

S11 – A:30’’, F:47’’

S13 – A:22’’, F:48’’

S14 – A:22’’, F:48’’S15 – A:24’’, F:1’5’’S16 – A:30’’, F:43’’S17 – A:33’’, F:31’’

S18 – A:33’’, F:31’’S19 – A:33’’, F:31’’S20 – A:32’’, F:31’’

S12 – A:32’’, F:55’’

S25 – A:23’’, F:01’

S26 – A:30’’, F:26’’

S21 – A:30’’, F:39’’S22 – A:38’’, F:28’’S23 – A:21’’, F:48’’

S27 – A:28’’, F:44’’

S24 – A:38’’, F:34’’

S28 – A:29’’, F:46’’

Caso Caminho Mínimo Casa-Ufersa

Page 36: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 36 de 93home

Semáforos

Para diminuir a complexidade do problema, vamos supor que o tempo gasto em cada sinal seja 70% do tempo em que o mesmo esteja fechado. Também reduziremos os tempos dos sinais seriados. Com isso, temos:

S1 – 27’’

S2 – 25’’S3 – 34’’

S5 – 32’’S4 – 34’’

S8 – 52’’

S6 – 30’

S7 – 35’’

S10 – 17’’S9 – 35’’

S11 – 33’’

S13 – 34’’

S14 – 17’’S15 – 46’’S16 – 30’’S17 – 22’’

S18 – 9’’S19 – 13’’S20 – 17’’

S12 – 39’’

S25 – 42’’

S26 – 18’’

S21 – 27’’S22 – 20’’S23 – 34’’

S27 – 31’’

S24 – 24’’

S28 - 32’’

Caso Caminho Mínimo Casa-Ufersa

Page 37: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 37 de 93home

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

39’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

Rede de Caminhos Possíveis com os tempos dos sinais

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Page 38: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 38 de 93home

Elaborando alternativas

Com os tempos dos caminhos e com os tempos dos sinais, vamos elaborar algumas alternativas de caminhos para escolhermos o caminho de menor tempo.

Caso Caminho Mínimo Casa-Ufersa

Page 39: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 39 de 93home

Alternativa I:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

17’4’’

15’’

Avançar

Caso Caminho Mínimo Casa-Ufersa

Page 40: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 40 de 93home

Alternativa II:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

17’33’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 41: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 41 de 93home

Alternativa III:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

16’46’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 42: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 42 de 93home

Alternativa IV:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

17’15’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 43: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 43 de 93home

Alternativa V:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

17’38’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 44: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 44 de 93home

Alternativa VI:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

18’17’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 45: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 45 de 93home

Alternativa VII:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

18’40’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 46: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 46 de 93home

Alternativa VIII:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

17’53’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 47: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 47 de 93home

Alternativa IX:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

20’14’’

15’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 48: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 48 de 93home

Alternativa X:

25’’

27’’

30’’

32’’

34’’

34’’

24’’

35’’

52’’ 22’’

33’’

32’’

17’’

35’’

30’’

34’’17’’

46’’34’’

20’’

27’’17’’

13’’9’’

1’23’’

2’32’’

3’21’’

2’47’’

2’14’’

50’’

1’10’’

1’14’’

2’05’’

2’38’’

C

U

42’’

3’10’’

18’’ 31’’

1’23’’16’’

26’’

42’’

27’’

19’’ 1’12’’

5’

17’’

1’

18’’

X

1’15’’

37’’

12’’

41’’

50’’

25’’

4’33’’1’32’’

20’26’’

15’’

39’’

Caso Caminho Mínimo Casa-Ufersa

Avançar

Page 49: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 49 de 93home

Menor tempo:Alternativa III16’46’’

Ver Maior tempo:Alternativa X20’26’’

Ver

Caso Caminho Mínimo Casa-Ufersa

Page 50: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 50 de 93home

Modelos Estocásticos

Page 51: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 51 de 93home

Modelo matemático cujas variáveis respondem a uma distribuição específica. Tais modelos não oferecem soluções únicas, mas apresentam uma distribuição de soluções associadas a uma probabilidade, segundo uma determinada distribuição de probabilidades.

Exemplos: Teoria dos Jogos, cadeias de Markov, teoria de filas, etc

Modelos Estocásticos

O que é um Modelo Estocástico?

Site do Ministério da Agricultura, Pecuária e Abastecimento

Page 52: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 52 de 93home

X

A Estratégia de uma emissora depende muitas vezes da estratégia da outra

Page 53: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 53 de 93home

Modelos EstocásticosTeoria dos Jogos

A teoria dos jogos é uma teoria matemática criada para se modelar fenômenos que podem ser observados quando dois ou mais “agentes de decisão” interagem entre si.

Uma Introdução à Teoria dos Jogos, SARTINI, GARVUGIO, BORTOLOSSI, SANTOS e BARRETO.

“Diz-se, portanto, que aquele que conhece o inimigo e conhece a si mesmo não ficará em perigo diante de centenas de batalhas. Aquele que não conhece o inimigo mas conhece a si mesmo às vezes vence, às vezes perde. Aquele que não conhece o inimigo nem a si mesmo invariavelmente perde todas as batalhas.” Sun Tzu em “A arte da guerra”.

Page 54: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 54 de 93home

Teoria dos Jogos

Caso do Dilema do Prisioneiro

Thiago e Samuel são presos por um crime. A polícia tem provas insufici-entes para os condenar, mas, separando os prisioneiros, oferece a ambos o mesmo acordo: se um dos prisioneiros, confessando, testemunhar con-tra o outro e esse outro permanecer em silêncio, o que confessou sai livre enquanto o cúmplice silencioso cumpre 10 anos de sentença. Se ambos ficaram em silêncio, a polícia só pode condená-los a 1 ano de cadeia cada um. Se ambos traírem o comparsa, cada um leva 5 anos de cadeia. Cada um faz a sua decisão sem saber que decisão o outro vai tomar, e nenhum tem certeza da decisão do outro.

Modelos Estocásticos

“Dilema do Prisioneiro” por Merrill Flood e Melvin Dresher, 1950. (Adaptado)

Page 55: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 55 de 93home

Teoria dos Jogos

Caso do Dilema do Prisioneiro

Modelos Estocásticos

“Dilema do Prisioneiro” por Merrill Flood e Melvin Dresher, 1950

Confessar

Confessar

Negar

Negar

THIAGO

SAMUEL(-5,-5)

(-10,0)

(0,-10)

(-1,-1)

Nesta matriz, os números de cada célula representam, respectiva-mente, os payoffs de Thiago e Samuel para as escolhas de Thiago e Samuel correspondentes a célula.

Page 56: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 56 de 93home

Teoria dos Jogos

Modelos Estocásticos

TESE DE PÓS-GRADUAÇÃO:

APLICAÇÃO DA TEORIA DOS JOGOS COOPERATIVOS PARA A ALOCAÇÃO DOS CUSTOS DE TRANSMISSÃO EM MERCADOS ELÉTRICOS

Autor:Max Rodrigues Junqueira

Page 57: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 57 de 93home

TESE DE PÓS-GRADUAÇÃO:

As relações entre empresas transmissoras de energia e consumidores podem ser estudadas por teoria dos jogos.

No artigo são apresentados vários métodos de tarifas de transmissão de energia, entre as quais a que usamos no Brasil. Depois é apresen-tada a metodologia proposta: Aumann-Shapley. Nessa metologia de cobrança são aplicados conceitos de teoria de jogos cooperativos.

No final, conclui-se que através do esquema Aumman-Shapley conse-gue-se fazer uma análise mais consistente e imparcial dos custos por uso da rede de cada usuário.

Teoria dos Jogos

Modelos Estocásticos

Page 58: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 58 de 93home

Teoria das Filas

Modelos Estocásticos

A teoria das filas é um ramo da probabilidade que estuda a formação de filas, através de análises matemáticas precisas e propriedades mensuráveis das filas.

Fila representa os clientes que estão esperando pelo serviço, juntamente com os que estão sendo atendidos pelos servidores.

Wikipedia.org

“A fila que anda é a outra, mas não adianta trocar de fila pois a fila que anda é a outra.”

Lei de Murphy.

Page 59: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 59 de 93home

Teoria das Filas

Modelos Estocásticos

O que é fila? “É quando se tem um recurso e em um determinado momento a demanda é maior do que a oferta.”

Prof. David em entrevista

Page 60: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 60 de 93home

Teoria das Filas

Modelos Estocásticos

A fila pode ser física ou não!

Exemplos: supermercado, banco, cantina, elevador, aviões aguar-dando pouso, centrais de atendimento telefônico, posto de lava-gem de carros, sequência de tarefas em uma máquina, semáforo, etc.

A existência de fila em um equipamento pode implicar em espera por peças que necessitam ser processadas, o que ocasiona um aumento nos tempos de produção.

Page 61: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 61 de 93home

Teoria das Filas

Modelos Estocásticos

Devemos projetar Sistemas Balanceados!

Um sistema ou processo está balanceado quando se encontra adequadamente dimensionado.

Para dimensionar adequadamente é necessário dedicar especial atenção aos gargalos, ou seja, os pontos onde ocorrem filas.

Geralmente estamos interessados em dimensionar, analisamos:- Qual a quantidade correta de equipamentos;- Qual o melhor layout e o melhor fluxo dentro do sistema

que está sendo analisado.

Page 62: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 62 de 93home

Teoria das Filas

Modelos Estocásticos

ARTIGO:

TENDÊNCIAS PARA O AUTO-ATENDIMENTOBANCÁRIO BRASILEIRO: UM ENFOQUEESTRATÉGICO BASEADO NA TEORIADAS FILAS

Autores:Eder Oliveira Abensur

Adalberto A. FischmannIsral Brunstein

Linda Lee Ho

Page 63: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 63 de 93home

Teoria das Filas

Modelos Estocásticos

ARTIGO:

Foi feito um estudo de Planejamento Estratégico e de Teoria das Filas para dar suporte para a gestão de serviços bancários. Foram analisa-dos dois grandes bancos: Bradesco e Itaú.Inicialmente foram analisadas as características da demanda desses bancos e como essa demanda iria se comportar num futuro próximo. Depois com os conhecimentos de teoria das filas aliada a ferramentas estatísticas foram elaborados modelos.Esses modelos mostravam características de atendimento, caracterís-ticas de ATMs, etcO banco que mais se aproximou as características do modelo propos-to foi o Bradesco.

Page 64: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 64 de 93home

Análise de Demanda

Page 65: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 65 de 93home

Análise da Demanda

Como é que vou planejar a capacidade da minha planta produtiva para dez anos, para um ano ou para um mês? Devo trabalhar com quantos turnos: um, dois ou três? Devo comprar mais máquinas para ampliar a produção?

Page 66: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 66 de 93home

Análise da Demanda

Quantos caixas eletrônicos devo comprar para o meu banco para que não haja uma fila grande e para que os mesmos não passem muito tempo ociosos?

Page 67: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 67 de 93home

Análise da DemandaA resposta para essas perguntas é Análise da Demanda.

Uma das principais tarefas de um Engenheiro de Produção é alinhar a capacidade produtiva de uma corporação à sua demanda.

demandacapacidade produtiva

demandacapacidade produtiva

Page 68: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 68 de 93home

Análise da DemandaO que é demanda?É a disposição dos clientes a consumirem bens e serviços ofertados por uma organização.(LUSTOSA et al., 2008)

O que é previsão de demanda?São estimativas de como vai se comportar o mercado demandante no futuro, ou seja, o potencial de compra que o mercado tem em relação aos bens e serviços ofertados por uma organização.(CORRÊA; CORRÊA, 2010)

Page 69: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 69 de 93home

Análise da DemandaDados de variáveis que expliquem as

vendas

Dados históricos de vendas

Informações que expliquem o

comportamento atípico

Tratamento estatístico dos dados de vendas e

outras variáveis

Informações da conjuntura econômica

Decisões da área comercial

Informações de clientes

Informações de concorrentes

Tratamento das informações disponíveis

Sist

ema

Gen

éric

o d

e P

revi

são

de

Dem

and

a, C

OR

RÊA

, 20

10

.

PREVISÃO DE DEMANDA

Page 70: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 70 de 93home

Análise da Demanda

Retirado do Material do Prof. Engº. Ms. Abraão Freires Saraiva Júnior

Page 71: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 71 de 93home

Análise da Demanda

Retirado do Material do Prof. Engº. Ms. Abraão Freires Saraiva Júnior

Page 72: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 72 de 93home

Análise da DemandaARTIGO:

A DEMANDA POR ENERGIA ELÉTRICA NO NORDESTE APÓS O RACIONAMENTO DE 2001-2002: PREVISÕES DE LONGO PRAZO.

Autores:Marcelo Lettieri Siqueira

Herbetes de Hollanda Cordeiro JúniorIvan Castelar

Page 73: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 73 de 93home

ARTIGO:

O artigo propõe uma metodologia para incorporar os efeitos do racionamento de 2001-2002 nas previsões da demanda por energia elétrica para as três principais classes de consumo (residencial, comercial e industrial) do Nordeste brasileiro. Para modelar a recuperação da demanda por energia, no período pós-racionamento, foi adotada a hipótese de que o consumo converge para a sua tendência de longo prazo.

Análise da Demanda

Page 74: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 74 de 93home

Processos Decisórios

Page 75: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 75 de 93home

Processos Decisórios

Com sistemas de análise e apoio à decisão garante-se mais eficiência e eficácia e consegue-se assim ir ao en-contro da otimização dos payoffs ganhando pró-atividade em vez de reati-vidade de uma forma trans-versal.

Page 76: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 76 de 93home

Processos Decisórios

Alexandre é proprietário de um terreno que pode ter pe-tróleo em seu subsolo. Um geólogo relatou que existe uma probabilidade de 35% de chance de haver petróleo.

Em virtude disso, a Petrobras ofereceu R$200mil para comprar o terreno. Porém Alexandre está considerando a possibilidade de abrir uma nova empresa e através dessa explorar o petroleo do próprio terreno. Para isso ele terá que gastar R$500mil. Se ele conseguir explorar o pe-tróleo, terá lucro de R$8milhões.

Caso do Terreno com (ou sem) Petróleo

HILLIER, 2005, capítulo 15 exemplo-protótipo. (adaptado)

Page 77: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 77 de 93home

Processos DecisóriosCaso do Terreno com (ou sem) Petróleo

Condição do Terreno

Alternativa

Prêmio

Petróleo Seco

Perfurar em busca de petróleo

Vender o terreno R$ 200mil R$ 200mil

R$ 8milhões R$ - 500mil

Chance da condição 35% 65%

Page 78: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 78 de 93home

Modelagem

Page 79: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 79 de 93home

Modelagem

Sistema

Modelo = representaçãoModelagem e simulação de eventos discretos, Chwif e Medina, 2006

Page 80: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 80 de 93home

Modelagem

Um modelo é uma representação das relações dos componentes de um sistema, sendo considerada como uma abstração, no sentido em que tende a se aproximar do verdadeiro comportamento do sistema.Modelagem e simulação de eventos discretos, Chwif e Medina, 2006

Lembrando que um sistema é um agrupamento de partes que operam juntas, visando um objetivo comum.Forrester, 1968.

Page 81: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 81 de 93home

Modelo é uma representação simplificada / idealizada, que visa obter informações sobre o sistema real com economia de tempo e recursos

Dedução: uso de técnicas dependentes do modelo formulado, rigor matemático e precisão, uso de computadores

Formulação: liberdade, arbitrariedade e coerência

Interpretação: julgamento humano, reavaliação do modelo

Sistema Real

Modelo

Solução Real

Solução do Modelo

Formulação/

Dedução/

Interpretação/

modelagem

análise

inferência

Avaliação/julgamento

Modelagem

Modelagem e simulação de eventos discretos, Chwif e Medina, 2006Introdução à Engenharia de Produção, Mário Batalha

Page 82: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 82 de 93home

Modelagem

Tipos:

- Modelos Simbólicos

- Modelos Analíticos

- Modelos de Simulação

Page 83: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 83 de 93home

Modelagem

Modelos simbólicos:

- Símbolos gráficos (fluxogramas, Layouts, etc)

- Muito utilizado para a comunicação e documentação

- Limitações:- Modelos estáticos- Não fornece elementos

quantitativos- Não entra no detalhe do sistema

Modelagem e simulação de eventos discretos, Chwif e Medina, 2006

Page 84: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 84 de 93home

Fluxograma do processo de atendimento de emergências de uma central do corpo de bombeiros

Page 85: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 85 de 93home

ModelagemModelos analítico:

- Forte modelagem matemática (Modelos de Programação Linear, Teoria de Filas, etc)

- Limitações:- Modelos, na grande maioria,

estáticos- A complexidade do modelo pode

impossibilitar a busca de soluções analíticas diretas

- Vantagens: solução exata, rápida e, às vezes, ótima

Modelagem e simulação de eventos discretos, Chwif e Medina, 2006

Page 86: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 86 de 93home

Modelo de Simulação

-Captura o comportamento do sistema real- Permite a análise pela pergunta: “e se...?”- Capaz de representar sistemas complexos

de natureza dinâmica e aleatória- Limitações:

- Pode ser de construção difícil- Não há garantia do ótimo

Modelagem

Modelagem e simulação de eventos discretos, Chwif e Medina, 2006

Page 87: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 87 de 93home

Simulação Computacional

Page 88: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 88 de 93home

Simulação Não-computacional

Page 89: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 89 de 93homeModelagem e simulação de eventos discretos, Chwif e Medina, 2006

Page 90: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 90 de 93home

Counter-Strike é uma simulação?

Sim, pois é um programa de computador que tenta reproduzir “o real”. CS trabalha utilizando recursos de estatística, calculando, por exemplo, a probabilidade de aparecer um inimigo ou a probabilidade de um tiro acertar o inimigo. Prof. David... na entrevista

Page 91: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 91 de 93home

Modelagem

Page 92: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 92 de 93home

- BATALHA, Introdução à Engenharia de Produção.- MORAES, Introdução a Pesquisa Operacional.- LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões: modelagem em Excel. São Paulo: Campus, 2006.- Site do Ministério da Agricultura, Pecuária e Abastecimento (http://www.agritempo.gov.br/modules.php?name=Encyclopedia&op=content&tid=133). Acessado em 31/10/2011.- SARTINI, GARVUGIO, BORTOLOSSI, SANTOS e BARRETO; Uma Introdução à Teoria dos Jogos.- SUN TZU, A arte da guerra.- FLOOD e DRESHER, “Dilema do Prisioneiro”, 1950.- Wikipedia.org (“pt.wikipedia.org/wiki/Teoria_das_filas”). Acessado em 31/10/2011.- Planejamento e Controle da Produção. CORRÊA, 2010HILLIER, Pesquisa Operacional, 2005.CHWIFT e MEDINA, Modelagem e simulação de eventos discretos, Chwif e Medina, 2006.

Referências

Page 93: Pesquisa Operacional

PESQUISA OPERACIONAL Slide 93 de 93home

Críticas, Dúvidas,

Sugestões?