Processos Markovianos de Decisão

Processos de Markov

Um processo de Markov consiste num conjunto de objectos e num conjunto de estados tais que

i) Em qualquer instante cada objecto deve estar num estado (objectos distintos não estão necessariamente em estados diferentes),

ii) A probabilidade de que um objecto passe de um estado para outro (que pode ser o mesmo que o inicial) num período de tempo depende apenas desses dois estados.

O número inteiro de períodos de tempo passados desde o início do processo é o estágio do processo. Esse número pode ser finito ou infinito.

Se o número de estados é finito ou infinito numerável, o processo Markov é uma cadeia de Markov.

Uma cadeia de Markov com um número finito de estados diz-se uma cadeia de Markov finita.

Designaremos a probabilidade de passar do estado para o estado num certo período de tempo por .

Para uma cadeia de Markov de estados (sendo um número inteiro fixo), a matriz (quadrada de ordem ) é a matriz de transição ou

estocástica associada ao processo.Como primeiras propriedades de temos:

i) A soma de todos os elementos de cada linha da matriz é 1,

ii) Toda a matriz estocástica tem 1 como valor próprio (possivelmente com multiplicidade superior a 1) e nenhum dos seus valores próprios excede 1 em valor absoluto.

Seja um vector com coordenadas (neste caso uma linha com elementos.

Recorde-se que os valores próprios de verificam a igualdade

sendo um valor próprio e, como (sendo I a matriz identidade de ordem , eles determinam-se resolvendo a equação

.

Resulta, imediatamente, da segunda propriedade de vista atrás que existe um vector , tal que

1

que se designa por ponto fixo de .

Exemplo

Os dados de um censo dividem as famílias em populações economicamente estáveis e economicamente em depressão. Depois de um período de 10 anos, a probabilidade de que uma família estável assim permaneça é de , enquanto que a probabilidade de ela ficar em depressão é . A probabilidade de que uma família em depressão se torne estável é de , enquanto a probabilidade de que ela assim permaneça é de .

Designando por

1 – estabilidade económica2 – depressão económica

temos que

ou seja

E, ainda,

é solução da equação: basta notar que Então, recorrendo à regra de Ruffini:

0Conclui-se que o outro valor próprio é . Por outro lado,

2

, portanto

um sistema indeterminado. Mas, como ( e são probabilidades e é um vector de estado) podemos obter

. Assim o ponto fixo de é .

Potências de Matrizes Estocásticas

Designe-se a -ésima potência de uma matriz por . Se é

estocástica, então representa a probabilidade de que um objecto passe do estado para o estado em períodos de tempo. é também uma matriz estocástica.

Designe-se a proporção de objectos no estado no final do -ésimo período de tempo por e ponha-se

como sendo o vector de distribuição para o final do -ésimo período de tempo. Da mesma forma

representa a proporção de objectos em cada estada no início do processo. está relacionado com pela equação

.

Assim, é a matriz estocástica correspondente a uma cadeia de Markov em que o período unitário corresponde à soma de períodos.

Matrizes Ergódicas

3

Uma matriz estocástica é ergódica se existe ; isto é: se cada tem limite quando ; designaremos a matriz limite, necessariamente estocástica, por . As componentes de são dadas por

e representam as proporções aproximadas de objectos nos diversos estados de uma cadeia de Markov após um grande número de períodos de tempo.

Vejamos os resultados seguintes:

- Uma matriz estocástica é ergódica se e somente se um único valor próprio tem módulo ou se tem multiplicidade e existem vectores

próprios linearmente independentes associados a este valor próprio,

- Se todo o valor próprio de uma matriz gera vectores próprios (à esquerda) linearmente independentes em número igual à sua multiplicidade, então existe uma matriz não singular, cujas linhas são os vectores próprios de , tal que é uma matriz diagonal. Os elementos da diagonal de são os valores próprios de , repetidos de acordo com a multiplicidade.

Adoptamos a conversão de posicionar os vectores próprios correspondentes a acima de todos os vectores próprios de . Então, para uma matriz diagonável, ergódica com de multiplicidade , a matriz limite pode ser calculada por

.

A matriz diagonal tem elementos e elementos na diagonal principal.

Matrizes Regulares

Uma matriz estocástica é regular se uma das suas potências contém somente elementos positivos.

4

Assim,

- Se uma matriz é regular, então é um valor próprio de multiplicidade e todos os outros elementos satisfazem a ,

- Uma matriz regular é ergódica.

Se é regular, com matriz limite , então todas as linhas de são idênticas entre si e idênticas a um vector próprio associado com e tendo a soma das suas componentes unitária. Designe-se este vector próprio por . Assim se é regular, qualquer que seja a distribuição inicial ,

.

Exemplos

1. Formule o processo seguinte como uma Cadeia de Markov. O fabricante do creme dental HI-GLO domina normalmente 60% o mercado de uma certa cidade. Dados do ano anterior mostram que 88% dos utilizadores de HI-GLO lhe permanecem leais, enquanto 12% mudam para outros concorrentes. Além disso, 85% dos utilizadores dos concorrentes permanecem-lhes leais, enquanto os outros 15% mudam para HI-GLO. Considerando-se que essa tendência é permanente, determine a participação de HI-GLO no mercado

- Daqui a 5 anos,

- A longo prazo.

Considerando como estado

1- Consumo de creme dental HI-GLO

2- Consumo dos cremes dentais concorrentes

então

vindo a matriz estocástica correspondente

5

O vector de distribuição de probabilidade de inicial é .

Como

concluímos que, após 5 anos, a participação de HI-GLO no mercado cairá para 56,48%.

Por outro lado, como cada componente da primeira potência de (evidentemente igual a ) é positiva, é regular e, portanto, ergódica. Daí a existência do limite quando tende para infinito. O vector próprio

correspondente a é dado por =

. Conjuntamente um somos conduzidos a

.

Portanto e

.

Com o tempo, a participação de HI-GLO no mercado estabilizar-se-à em

(aproximadamente 55,56%).

2. Resolva o problema anterior no caso de HI-GLO controlar normalmente 90% do mercado.

6

e, após 5 anos, a participação de HI-GLO no mercado será de aproximadamente 63%.

Como é regular, a distribuição limite mantém-se e o valor próprio de

associado a é .

3. Formule o processo seguinte como uma cadeia de Markov. O programa de treino de supervisores de produção de uma determinada companhia consiste em 2 fases. A fase 1, que envolve 3 semanas de aula teórica, é seguida de fase 2, que envolve três semanas de aprendizagem prática sob a direcção de supervisores treinados. Pelas experiências anteriores, a companhia espera que apenas 60% dos candidatos da fase teórica sejam graduadas na fase prática, com os 40% restantes a completarem o programa de treino na totalidade. Dos que fazem a fase prática, 70% são graduados como supervisores, 10% voltam a repeti-la e 20% são dispensados. Quantos supervisores pode a companhia esperar formar do seu programa normal de treino se existem 45 pessoas na fase teórica e 21 na fase prática?

Consideramos um período de tempo como sendo de 3 semanas e definimos os estados de 1 a 4 como as condições de ser

1- eliminado2- um aprendiz teórico3- um aprendiz prático4- supervisor

Considerando que os candidatos eliminados não voltam ao programa de treino e que os supervisores permanecem supervisores, as probabilidades de transição são dadas pela matriz estocástica

.

Existem pessoas no programa inicial de treino, de modo que o

vector de probabilidade inicial é .

Como nem todas as entradas de são positivas não podemos concluir de imediato que ela é regular. Mas, em vez de calcular potências superiores de na tentativa de obter uma com entradas todas positivas, vamos calcular os valores próprios de , resolvendo a sua equação característica:

7

(raiz dupla) .

Determinemos os vectores próprios associados ao valor próprio :

ou seja: .

Portanto, existem dois vectores próprios linearmente independentes associados a (que tem multiplicidade 2). Portanto é ergódica embora não seja regular.

Determinemos agora os vectores próprios associados a :

ou seja:

. Por exemplo, com , obtemos .

E, finalmente, os vectores próprios associados a :

8

.Então temos

e, com , obtemos .

Então é diagonalizável como vimos e, pondo e

obtemos sucessivamente:

- ,

-

9

-

.

Então 6621 .

Portanto, eventualmente, 43,43% dos candidatos normalmente em treino (ou seja: aproximadamente 29 pessoas) serão eliminadas do programa e 56,57% (ou seja: aproximadamente 37 pessoas) tornar-se-ão supervisores.

4. Resolva um problema em tudo idêntico ao anterior excepto que se supõe que todos os 66 formandos estão na fase de aprendizagem teórica do programa de treino.

Agora e, portanto,

.

Assim, das 66 pessoas em treino (aproximadamente 35 pessoas) serão

eliminadas definitivamente do programa, permanecendo 31 pessoas eventualmente como supervisores.

10

Comparando estes resultados com os do Problema anterior, vemos que as distribuições iniciais, situação usual sempre que uma matriz estocástica é ergódica mas não regular.

5. Construa o diagrama de transição para a cadeia de Markov dos problemas 3. e 4. . Um diagrama de transição de estados é uma malha orientada na qual os nós representam os estados e os arcos as possíveis transições. Assim, tendo em conta as denominações dos estados vistos em 3. e 4. temos

0,4 0,6 1

1

0,2 0,1

em que o número em cada arco é a probabilidade de transição.

6. A matriz estocástica é regular? É ergódica? Calcule

se existe.

Como tem todas as

entradas positivas, é regular e, portanto, ergódica. Logo existe. Fazendo

, como obtemos e

.

7. Uma costureira trabalha exclusivamente numa fase do processo de fabrico de uma determinada confecção de roupas. Esta fase necessita de exactamente

11

1

2

3

4

meia hora por peça de roupa para se completar. A cada 30 minutos um estafeta passa pela mesa da costureira, apanha todas as peças de roupa que já estejam prontas e deixa novas peças de roupa para serem costuradas. O número de peças de roupa que o estafeta transporta é incerto: 30% das vezes o estafeta não tem peças para a costureira; 50% das vezes o estafeta tem apenas 1 peça para a costureira; 20% das vezes tem 2 peças para a costureira. Entretanto, o estafeta é instruído para nunca deixar na costureira mais do que três peças inacabadas de roupa (As peças inacabadas que não podem ser deixadas com a costureira, como resultado desta programação, são levadas a outra costureira para processamento). Determine a percentagem de vezes em que a costureira fica ociosa, considerando que todas as peças de roupa que se encontram na sua mesa no fim do expediente permanecem lá para serem processadas de forma útil.

Podemos modelar este processo como uma cadeia de Markov de três estados, considerando os estados como o número de peças de roupa inacabadas na mesa da costureira no instante em que o estafeta passa. Designamos os estados 1, 2 e 3, respectivamente, representando 0, 1 e 2 peças inacabadas de roupa; os estágios são os intervalos de meia hora entre cada passagem.

Se a costureira tem uma peça de roupa inacabada no começo de um estágio (no momento em que o estafeta passa) e se deixa uma peça (com probabilidade 0,5) então uma peça estará completada (pronta) no início do estágio seguinte, ficando a costureira novamente com uma peça inacabada, daí .

Se a costureira tem duas peças inacabadas de roupa no começo de um estágio e se o estafeta passa 1 ou 2 peças (com a probabilidade de ) então o estafeta deixará apenas uma peça e no começo do período seguinte estará com duas peças inacabadas, já que uma terá sido processada durante o período. Portanto, . Considerando todas as outras probabilidades do mesmo modo, temos a matriz estocástica

.

tem todas as

entradas positivas. Portanto é regular e, em consequência, ergódica. O vector próprio associado a com a soma de todas as coordenadas positiva, determina-se fazendo

12

. Mas,

e, assim, e

.

Assim, e, como é regular, temos também que

.

Com o tempo a costureira começa um estágio no estado 1 (sem nenhuma

peça inacabada) das vezes. O mensageiro passa e, com probabilidade

não deixa peça alguma para processar, deixando portanto a costureira ociosa. Então a costureira fica ociosa

Ou seja: aproximadamente 14% do tempo.

8. Verifique que, para a matriz estocástica definida no exemplo dos censos, representa a probabilidade de passagem do estado para o estado em 2

períodos de tempo.

Existem duas maneiras para uma família permanecer estável após vinte anos como se ilustra no esquema seguinte:

ou seja:

Estável Estável

Em depressão Estável

Estável

0,92

Após 10 anos Após 20 anos

0,08

0,92

0,03

13

- Ela permanece estável durante os primeiros 10 anos e durante os 10 seguintes ou permanece em depressão após os 10 primeiros anos e então torna a estabilizar-se depois de outros 10. A probabilidade de que uma família permaneça estável durante um período de tempo é 0,92; daí, a probabilidade de que ela permaneça estável durante dois períodos de tempo seja (0,92) (0,92); A probabilidade de que uma família estável caia em depressão após 10 anos é 0,08; a probabilidade de que, em seguida, se torne estável é 0,03; assim a probabilidade de que ambos os acontecimentos se dêem na mesma família é (0,08) (0,03). Então, a probabilidade de que uma família estável permaneça estável após dois períodos de tempo é

que é exactamente o elemento (1,1) de .

A figura seguinte

descreve os modos como uma família em depressão se pode tornar estável após 2 períodos de tempo. A probabilidade de que ela continue em depressão durante o primeiro período de tempo e então se torne estável no seguinte é (0,97) (0,03). A probabilidade de que ela se torne estável após o primeiro período de tempo e assim permaneça no período seguinte é (0,03) (0,92). Logo a probabilidade de que uma das situações ocorra é

que é exactamente o elemento (2,1) de . As outras situações ocorrem de modo semelhante.

9. Exemplo de um modelo de manutenção

Um processo de produção contém uma máquina que se deteriora com rapidez diminuindo tanto em qualidade como em rendimento a sua produção, quando sujeita a uma utilização pesada. Assim é inspeccionada periodicamente, digamos, diariamente (ao fim do dia de trabalho). Em cada inspecção, observa-se a situação da máquina e classifica-se em um de quatro estados possíveis:

Estável Estável

Em depressão Estável

Em depressão

0,03

0,97

0,92

0,03

14

Estado Situação0 Boa como nova1 Operacional (desgastes menores)2 Operacional (desgastes importantes)3 Inoperacional (produção de qualidade inaceitável)

Designemos por o estado observado da máquina após a inspecção, no final do dia . È razoável supor que o estado do sistema evolui de acordo com algumas “leis de movimento” probabilísticas, de modo que a sucessão de estados se pode conceber como um processo estocástico. Supor-se-á ainda que o processo estocástico é uma cadeia de Markov com um número de estados finito, com uma “matriz de transição” dada por

Estado 0 1 2 3

0 0

1 0

2 0 0

3 0 0 0 1

A partir desta matriz de transição, é evidente que uma vez que a máquina se torna inoperacional (isto é: entra no estado 3) permanece inoperacional. Portanto, provavelmente a análise deste processo estocástico é desinteressante porque o estado 3 é um estado absorvente e, a partir de algum momento, a máquina entrará neste estado e ali permanecerá; quer dizer, depois de um certo tempo, será sempre igual 3. É óbvio que, de um ponto de vista prático, este modelo é intolerável porque uma máquina que está inoperacional não pode continuar a permanecer no processo de produção e deve ser substituída (ou reparada). Esta acção de substituição altera o comportamento do sistema, de modo que agora o sistema evolui no tempo de acordo com o efeito conjunto das leis probabilísticas do movimento e a acção de substituição da máquina inoperacional. Note-se que a acção de substituir uma máquina inoperacional se pode conceber como definidora de uma política de manutenção.

Quando uma máquina se torna inoperacional e se substitui, a máquina substituta é “tão boa como nova”; quer dizer, a máquina volta, por assim dizer, ao estado 0, no momento da inspecção regular no final do dia seguinte. De um ponto de vista prático, pode-se imaginar o processo de substituição como necessitando de 1 dia para se completar, de modo que se perde a produção deste período de tempo.

Os custos em que se incorre enquanto o sistema evolui contêm várias componentes. Quando o sistema se encontra no estado 0,1 ou 2 podem produzir-se artigos defeituosos no dia seguinte e os custos esperados são dados por

15

Estado Custo esperado devido à produção de artigos defeituosos

0 01 1 000€2 3 000€

Se se substitui a máquina, incorre-se num custo de substituição de 4 000€, a que se deve juntar um custo de produção perdida (utilidade perdida) de 2 000€. De modo que, o custo total em que se incorre, sempre que o sistema está no estado 3, é de 6 000€.

O processo estocástico que resulta do sistema com a política de manutenção delineada atrás, isto é: substituir uma máquina inoperacional, é ainda uma cadeia de Markov com um número de estados finito, mas com uma matriz de transição dada agora por

Estado 0 1 2 3

0 0

1 0

2 0 0

3 1 0 0 0

Pode ter interesse avaliar o custo desta política de manutenção.Se o custo médio esperado (a longo prazo) por dia, ou então, o custo médio

real (a longo prazo) forem medidas apropriadas podemos recorrer aos resultados vistos atrás.

Assim, notando que

tem as entradas todas positivas concluímos que é regular. Para calcular fazemos

16

2x 2x o que conduz a

o que conjuntamente com

leva a .

Como consequência o custo médio esperado (a longo prazo) por dia é dado por

,

que representa o custo desta política de manutenção.

Modelos Markovianos de Decisão

Acabámos de ver, no último exemplo apresentado, um modelo de manutenção para uma máquina em que se apresentou uma política de manutenção; quer dizer, quando uma máquina se torna inoperacional, substiui-se, em alternativa, a máquina deixa-se tal e qual como está. Por outras palavras, toma-se a decisão de levar a cabo a acção de substituir a máquina, quando se encontra no estado 3, e toma-se a decisão de levar a cabo a acção de deixar a máquina tal e qual como está, quando se encontra nos estados 0, 1 ou 2. Mesmo quando estas duas acções são as únicas permitidas, podem implementar-se outras políticas; por exemplo, quando a máquina se torna inoperacional, ou mesmo, se acha que está operacional mas com desgastes importantes (isto é: a máquina está no estado 2 ou 3), substitui-se; caso contrário, deixa-se a máquina tal e qual como está. Como é evidente, esta política gera uma matriz de transição diferente:

Estado 0 1 2 3

0 0

1 0

2 1 0 0 03 1 0 0 0

Para se tornar mais realista o exemplo da manutenção da máquina, suponha-se que se permite uma terceira opção: a reparação. Quando se repara

17

uma máquina, regressa-se ao estado 1 (operacional – desgastes menores), no instante da inspecção regular no fim do dia seguinte. De um ponto de vista prático, à semelhança da substituição, pode imaginar-se o processo de reparação como se requeresse 1 dia para ser efectuado, perdendo-se em consequência a produção durante este período. A reparação da máquina não se considera como uma decisão viável quando a máquina se torna inoperacional.

Ao imaginar este sistema dinâmico, torna-se evidente que o sistema evolui no tempo de acordo com o efeito conjunto das leis probabilísticas do “movimento” e a sucessão de decisões que se tomam (acções implementadas). Em particular, inspecciona-se a máquina no final de cada dia e regista-se o seu estado. Deve-se tomar então uma decisão em relação à acção que se deve levar a cabo, ou seja:

Decisão Acção1 Não fazer nada2 Reparar (O sistema regressa ao estado 1)3 Substituir (O sistema regressa ao estado 0)

Para o modelo original geral, supor-se-á que se observa um sistema no instante e se classifica em um de um número finito de estados denominados . Designaremos por a sucessão de estados observados. Depois de cada observação, toma-se uma de (finito) decisões (acções) possíveis, denominadas (O número de decisões possíveis pode depender do estado do sistema).

Designaremos por a sucessão de decisões reais que se tomam.

Uma política, designada por , é uma regra para tomar decisões em cada instante do tempo. Em princípio, uma política poderia utilizar toda a informação observada no passado até ao instante , quer dizer, a “História” completa do sistema que consta de e . No entanto, para a maior parte dos problemas que se encontram na prática, é suficiente restringir a nossa consideração àquelas políticas que dependem apenas do estado observado do sistema no instante , e às decisões possíveis de que se dispõe (caracteristicamente markoviana).

Em consequência, uma política pode imaginar-se como uma regra que prescreve a decisão quando o sistema se encontra no estado . Portanto, fica completamente caracterizado pelos valores

.

Note-se que esta descrição supõe que sempre que o sistema se encontre no estado , a decisão que deve tomar-se é a mesma para todos os valores de . As políticas que têm esta propriedade chamam-se políticas estacionárias.

No exemplo que temos estado a seguir as políticas de interesse são:

18

Política Descrição VerbalSubstitua-se no estado 3 1 1 1 3Substitua-se no estado 3 e repare-se no estado 2 1 1 2 3

Substitua-se nos estados 2, 3 1 1 3 3Substitua-se nos estados 1, 2 e 3 1 3 3 3

- é a política referida no exemplo 9. atrás,

- é a política acabada de referir agora.

Recorde-se, melhor, saliente-se que cada política conduz a uma diferente matriz de transição.

Já se salientou que um sistema evolui no tempo de acordo com o efeito conjunto das leis probabilísticas do movimento e a sucessão de decisões que se devem tomar; a sua trajectória depende do estado inicial . Supor-se-á que sempre que o sistema se encontre no estado e se toma a decisão , o sistema evolui para um novo estado , com probabilidade de transição conhecida , para todo o e . Portanto, se se segue uma dada política , o processo estocástico resultante é uma cadeia de Markov com uma matriz de transição conhecida (que depende da política escolhida). Salvo indicação em contrário, por razões técnicas, supor-se-á que a cadeia de Markov associada com cada matriz de transição é irredutível.

Como exemplo de cadeia de Markov redutível temos a dada pela matriz

A que corresponde o diagrama de transição

19

redutível a duas cadeias Markov.No nosso exemplo temos as matrizes de transição seguintes:

Estado 0 1 2 3 Estado 0 1 2 3

0 0

1 1

2 2

3 3

Estado 0 1 2 3 Estado 0 1 2 3

0 0

1 1

2 2

1 2 3 4

32

21

87

81

20

3 3

Em Resumo:Dada uma distribuição sobre os estados iniciais do sistema, e uma

política , um sistema evolui no tempo de acordo com o efeito conjunto das leis probabilísticas do movimento e a sucessão de decisões que se tomem (acções empreendidas). Em particular, quando o sistema se encontra no estado e se toma a decisão , então a probabilidade de que o sistema se encontre no estado , no período observado seguinte, é dada por . Isto conduz a uma sucessão de estados observados e a uma sucessão de decisões tomadas . Esta sucessão de estados observados e a sucessão de decisões tomadas chama-se processo markoviano de decisão. Usa-se o termo markoviano devido às hipóteses estabelecidas com respeito às leis probabilísticas do movimento.

Descreveram-se (isto é: exemplificou-se) quatro políticas de manutenção mas não se avaliaram as suas propriedades. Falta dar resposta a perguntas como

“Qual é a melhor?”Para prosseguir por este caminho, é necessário introduzir uma estrutura de

custos. Quando o sistema se encontra no estado e se toma uma decisão , seguindo a política , incorre-se num custo conhecido. Este custo

pode representar (e de facto representa mesmo) mais um custo esperado do que um custo real. Por exemplo, no problema da manutenção, o custo de deixar uma máquina tal e qual como está depende da variável aleatória, número de artigos defeituosos produzidos no período seguinte. O valor esperado (ou média) desta função de custo, tomado relativamente à distribuição do número de artigos defeituosos, conduzirá ao custo desejado . É importante salientar que este custo depende apenas do estado em que se encontra o sistema e da decisão tomada, ou seja:

= custo (esperado) conhecido em que se incorre durante a transição seguinte, se o sistema se encontra no estado e se toma a decisão .

Para as quatro políticas de manutenção, podem obter-se custos a partir da informação seguinte:

Decisão

Custo

Estado

Custo esperado devido à

produção de ar. def.

Custo de manutenção

Custo (utilidade

perdida) da produção perdida

Custo Total por

dia

1. Deixe-se a máquina tal e

01

01000€

00

00

01000€

21

qual como está 23

3000€x

00

00

3000€

2. Repare-se 0, 1, 2,3

00

2000 20002000

4000

3. Substitua-se 0, 1, 2, 3 0 4000 2000 6000

*Já que, por hipótese, não se pode deixar a máquina na condição de inoperacional ou repará-la quando fica inoperacional imputa-se um custo infinito. Um modo alternativo seria omitir estas decisões do conjunto de decisões possíveis, quando a máquina se encontra no estado 3.

Note-se que o custo em que se incorre quando se toma a decisão de substituir é independente do estado do sistema. Isto é evidente, porque não se tem produção alguma durante o dia seguinte, quando se opta por esta acção. Em suma, o custo total esperado por dia resume-se como se segue:

(em milhares de euro) Decisão

Estado1 2 3

0 0 4 6

1 1 4 6

2 3 4 6

3 6

Para comparar as políticas é necessário estabelecer uma medida apropriada do custo. Uma dessas medidas associadas com uma política é o custo médio esperado (a longo prazo) por unidade de tempo, e é a que utilizaremos. Ou seja: para qualquer política pode calcular-se o custo médio esperado (a longo prazo) por unidade de tempo, , a partir da expressão

em que , para cada , e representa a distribuição de estado estacionário do estado do sistema, governado pela política que se está a avaliar. Claro que, pretende-se achar a política que minimize . Utilizando este critério, é evidente que não é relevante a distribuição assumida para os

22

estados iniciais, porque o efeito a longo prazo do custo da decisão inicial é desprezável. No exemplo da manutenção, é necessário calcular para cada uma das quatro políticas tomadas como interessantes e, de seguida, usar estes resultados para obter . Procedendo tal como mostrámos (exemplificámos) atrás para agora, também, para e obtemos:

Política

É evidente que a política é a melhor. Entre as quatro políticas consideradas, a política que exige a substituição da máquina quando se encontra no estado 3 (inoperacional) e a sua reparação quando se encontra no estado 2 é a melhor (estado 2: operacional - desgastes importantes), e o custo médio esperado (a longo prazo) por dia é 1 667 euro.

A técnica que acabamos de descrever é simplesmente uma enumeração exaustiva de um conjunto de políticas possíveis. É evidente que a enumeração directa se torna incómoda quando o número de políticas é grande e, em consequência, necessitam-se algoritmos para determinar políticas óptimas. Vamos ver, de seguida, alguns desses algoritmos.

Programação linear e políticas óptimas

Na secção anterior definimos uma política. Salientar-se que uma política se pode imaginar como uma regra que prescreve a decisão , quando o sistema se encontra no estado . Portanto, caracteriza-se pelos valores

Alternativamente, pode-se caracterizar atribuindo os valores ou a na matriz

Decisão, …

23

Estado

em que cada linha deve conter um único , com os restantes elementos iguais a (isto é: a soma dos elementos de cada linha deve ser ). Quando um elemento

, interpreta-se como sendo requerida a decisão quando o sistema se encontra no estado . No exemplo do modelo de manutenção, pode caracterizar-se a política por intermédio da matriz

Decisão,

Estado ;

ou seja: substituir a máquina quando se encontra no estado 3, reparar a máquina quando se encontra no estado 2 e deixá-la tal e qual como está quando se encontra nos estados ou .

Esta interpretação dos fornece a motivação para uma formulação em termos de programação linear.

Com alguma sorte, o custo esperado de uma política pode exprimir-se como uma função linear dos , ou uma variável relacionada, sujeita a restrições lineares. Mas (e isto não é necessariamente bom) os são inteiros ( ou ) e são exigidas variáveis contínuas para uma formulação em termos de programação linear. Pode-se lidar com esta situação alargando a interpretação de uma política (melhor dizendo: generalizando).

A definição anterior exige que se tome a mesma decisão cada vez que o sistema se encontre no estado . A nova interpretação (agora proposta) de uma política exigirá a determinação de uma distribuição de probabilidade para a decisão que se deve tomar, quando o sistema se encontre no estado . Portanto, agora deverá imaginar-se como

.

A uma política deste tipo dá-se o nome de política aleatória, enquanto que a uma política que exige ou se pode chamar política determinística. Ainda assim as políticas aleatórias podem caracterizar-se através da matriz

Decisão, …

24

Estado

em que a soma de cada linha é igual a , mas agora

Note-se que cada linha é a distribuição de probabilidade que se deve usar quando o sistema se encontra no estado . Por exemplo, suponha-se que se vai usar uma nova política, , no modelo de manutenção, que é uma política aleatória e que está definida pela matriz

Decisão,

Estado .

Esta política solicita que se observe o estado da máquina no final do dia. Se se encontra no estado ou , deixa-se tal e qual como está. Se se encontra no

estado 2, deixa-se tal e qual como está com probabilidade , repara-se com

probabilidade e substitui-se com probabilidade . Provavelmente, pode-se

usar um artifício aleatório com estas probabilidades (possivelmente uma tabela de números aleatórios) para tomar a decisão real. Por fim, se se encontra a

máquina no estado 3, repara-se com probabilidade e substitui-se com

probabilidade .

A formulação em termos de programação linear expressa-se melhor em termos de uma variável , que está relacionada com de modo seguinte:

- Seja a probabilidade estacionária de que o sistema no estado e que se tome a decisão :

e .

Então,

25

Note-se que

e, portanto,

.

Existem várias restrições relativas a :

1. pelo que

2. Como vimos, (recordar que ) de modo que

( de indica que a probabilidade de

transição considerada depende da decisão ) para .

3. e .

O custo médio esperado, a longo prazo, por unidade de tempo vem dado por

Assim, o problema é determinar os de modo que:

26

Trata-se de um problema de programação linear que se pode resolver através do método do simplex.

Obtidos os , os , que verdadeiramente nos interessam, obtêm facilmente a partir de

.

A solução tem algumas propriedades interessantes:

- Conterá variáveis básicas ; tem-se uma restrição redundante,

- Pode demonstrar-se que para pelo menos um , para cada ,

- Portanto, deduz-se que para um único , para cada . Quer dizer que ou ,

- Por outras palavras a política óptima é determinística e não aleatória. Por fim, como se têm restrições funções e variáveis originais, os problemas “práticos” tendem a ser grandes neste modo de formulação, de modo que é possível que não se possam obter soluções, mesmo recorrendo ao método do simplex.

Exemplo

Como exemplo, pode formular-se deste modo o problema da manutenção da máquina; Assim,

27

, ,

É possível resolver este problema aplicando o método do simplex. Trata-se de um problema de programação linear.

Todos os resultam nulos excepto

e .

Estes valores são precisamente as probabilidades de estado estacionário para a política , provando-se assim que se trata da política óptima. Os

correspondentes vêm

,

e todos os restantes . Esta política requere que

- Se deixe a máquina tal e qual como está, se se encontra no estado 0 ou 1,

- Se repare quando se encontre no estado 2,

- Se substitua quando se encontre no estado 3.

28