Apostila de Pesquisa Operacional - Parte II.pdf

Embed Size (px)

Text of Apostila de Pesquisa Operacional - Parte II.pdf

  • 1

    UNIVERSIDADE SO FRANCISCO

    DISCIPLINA

    PESQUISA OPERACIONAIOL

    Parte II

    Adalberto Nobiato Crespo 2015 Verso 4.0

  • 2

    Sumrio

    PROCESSOS ESTOCSTICOS ......................................................................................................... 3

    1 Processos Estocsticos ................................................................................................................... 3

    1.1 Classificao de Processos Estocsticos ................................................................................. 3

    Questes para Estudo ........................................................................................................................... 4

    2 Processos Markovianos .................................................................................................................. 5

    3 Conceitos Fundamentais .............................................................................................................. 11

    3.1 Cadeias de Markov................................................................................................................ 11

    3.2 Probabilidade de Transio ................................................................................................... 12

    3.3 Probabilidade de Transio de Passo 1 ................................................................................. 12

    3.4 Probabilidade de Transio de Passo n ................................................................................. 12

    3.5 Distribuio Inicial de Probabilidades .................................................................................. 14

    3.6 Distribuio de Probabilidades aps n Passos ................................................................... 16

    3.7 Classificao dos Estados de Uma Cadeia de Markov ......................................................... 20

    3.8 Classificao de Matrizes Estocsticas ................................................................................. 26

    Primeira Lista de Exerccios - Cadeias de Markov ......................................................................... 28

    4 Aspectos Fundamentais sobre Filas ............................................................................................. 34

    4.1 Conceito de Fila .................................................................................................................... 34

    4.2 Dimensionamento de Filas .................................................................................................... 35

    4.3 Aspectos Histricos............................................................................................................... 36

    5 Fundamentos Bsicos de Filas ..................................................................................................... 37

    5.1 - Elementos de Uma Fila .......................................................................................................... 37

    5.2 Caractersticas de Uma Fila .................................................................................................. 38

    5.3 Distribuio do Tempo de Atendimento ............................................................................... 41

    5.4 Dinmica de uma Fila ........................................................................................................... 42

    5.5 Conceitos Bsicos de Fila .................................................................................................... 47

    5.5.1 Variveis Aleatrias Fundamentais ....................................................................................... 48

    5.5.2 - Postulados Bsicos.................................................................................................................. 53

    Segunda Lista de Exerccios ............................................................................................................ 54

    6 O Sistema de uma Fila e um Atendente ....................................................................................... 55

    6.1 Equaes do Modelo ................................................................................................................. 55

    Terceira Lista de Exerccios ............................................................................................................ 57

    Quarta Lista de Exerccios .............................................................................................................. 59

  • 3

    PROCESSOS ESTOCSTICOS

    1 Processos Estocsticos

    Um Processo Estocstico definido como uma coleo de variveis aleatrias Xt

    indexadas por um parmetro t pertencente a um conjunto T. Normalmente, T um

    conjunto de nmeros inteiros no negativos e Xt representa uma caracterstica

    qualquer mensurvel de interesse e que varia com o tempo t.

    Exemplo 1:

    Xt: Nvel de estoque de um produto no fim de cada semana t.

    t = 1, 2, 3...

    X1 = 20 significa que na semana 1 o estoque era de 20 unidades.

    X2 = 13 significa que na semana 2 o estoque era de 13 unidades.

    X5 = 28 significa que na semana 5 o estoque era de 20 unidades.

    Processos Estocsticos so de interesse para descrever o procedimento de um sistema

    operando em algum perodo de tempo. Com isso, a varivel aleatria Xt representa o

    estado do sistema no parmetro t.

    O parmetro t representa o estado e o valor da varivel Xt representa o

    comportamento do sistema no estado t.

    Por exemplo, interessante para uma empresa observar o comportamento do estoque

    de um determinado produto, durante 6 meses. Esta observao serve para a

    programao dos estoques nos prximos perodos.

    Portanto, a varivel Xt definida em um conjunto de estados denominado Espao de

    Estados.

    1.1 Classificao de Processos Estocsticos

    Os Processos Estocsticos podem ser classificados como:

    a) Em relao ao Estado

    Estado Discreto: Xt definida sobre um conjunto enumervel finito.

    Estado Contnuo: Xt caso contrrio

    b) Em relao ao Tempo t (parmetro)

    Tempo Discreto: t finito e enumervel

    Tempo Contnuo: t caso contrrio

  • 4

    Exemplos:

    1 Nmero de usurios em uma fila de banco em um determinado instante t.

    Estado discreto e Tempo contnuo

    2 ndice pluviomtrico dirio.

    Estado contnuo e Tempo discreto

    3 Nmero de dias chuvosos.

    Estado Discreto e Tempo discreto

    Questes para Estudo

    1 Suponha que Xt representa o nvel de estoque de um produto e t representa a semana de observao do estoque.

    Qual a probabilidade do estoque ser zero no final desta semana, dado que na

    semana anterior o estoque era de 10 unidades?

    Matematicamente temos a equao: ?10|0 anterioratual XXP Fazendo: semana atual =1

    semana anterior = 0

    Ento teremos a seguinte equao: ?10|0 01 XXP Pode se tambm estar interessado na seguinte questo:

    ?3,6...15,12,11|0 0178910 XXXXXXP

    Onde: 10=semana atual; 9 = semana anterior; e assim por diante.

    O valor desta probabilidade serve para tomada de decises sobre o estoque do

    produto em questo.

    2 Suponha que Xt representa o comportamento do tempo numa cidade de praia durante o vero.

    Qual a probabilidade do tempo estar com sol nesta semana, dado que na semana

    anterior o tempo esteve com chuva.

    Matematicamente temos a equao: ?| chuvaXsolXP anterioratual Fazendo: semana atual =1

    semana anterior = 0

    Ento teremos a seguinte equao: ?| 01 chuvaXsolXP Pode se tambm estar interessado na seguinte questo:

    ?,,| 1234 solXchuvaXchuvaXsolXP

    Onde: 4 = semana atual; 3 = semana anterior; e assim por diante.

    O valor desta probabilidade serve para tomada de decises sobre os eventos que

    podero ser promovidos na cidade de praia, no perodo em questo.

  • 5

    Existem vrios "tipos" de Processos Estocsticos, porm neste curso ser abordado

    apenas um tipo de Processo Estocstico denominado Processo Markoviano.

    2 Processos Markovianos

    Um Processo Estocstico dito ser um Processo Markoviano se:

    kkkkkkkkkkkk yXyXPyXyXyXyXyXyXP |,...,,| 110011221111

    Onde k = 0, 1, 2, 3 ...

    Essa expresso pode ser traduzida como: a probabilidade condicional de qualquer

    evento futuro, dado qualquer evento passado e o estado presente Xk = yk,

    independente do evento passado e depende somente do estado presente.

    Em termos mais resumidos: Um processo Estocstico dito ser um Processo

    Markoviano se o estado futuro depende apenas do estado presente e no depende dos

    estados passados.

    Este tipo de Processo Estocstico tambm denominado de processo sem Memria,

    uma vez que o passado desprezado.

    As probabilidades condicionais kkkk yXyXP |11 so denominadas

    Probabilidades de Transio e representam a probabilidade do estado Xk+1 ser yk+1

    no instante k+1 dado que no instante k o estado Xk yk.

    Exemplo 2: No ano de 1993, o estado do uso da terra em uma cidade de 50

    quilmetros quadrados de rea ra:

    Tabela 1 Estado do uso da Terra em 1993

    I Uso Residencial 30%

    II Uso Comercial 20%

    III Uso Industrial 50%

    Os valores da tabela 1 podem ser dispostos em um vetor T, denominado

    Vetor de Estados:

    T = [ I II III ].

    As probabilidades de cada Estado podem tambm serem dispostas em

    um vetor , denomi