Simulação estocástica discreta - fenix.tecnico.ulisboa.pt · Exemplos (3) • Mais outra simulação para o mesmo input: 200 400 600 800 1000 5 10 15 20. LEEC@IST Simulação estocástica

LEEC@IST Simulação estocástica discreta : 1/31

Simulação estocásticadiscreta

Apoio ao projecto


Introdução (1)Existem diversos tipos de simulação de sistemas:• Simulação analógica: com modelos físicos, por exemplo, o

modelo reduzido de uma ponte.• Simulação digital: realizada em computador.

– Modelos possíveis:• Modelos contínuos: equações diferenciais que descrevem a

evolução de grandezas contínuas.• Modelos discretos: fenómenos que podem ser descritos por

eventos e suas sequências.– Classificação:

• Estocástica: as grandezas em causa seguem leis aleatórias, por exemplo, o tempo que decorre entre eventos.

• Determinista: as grandezas em causa seguem leis deterministas.


Introdução (2)• No seguimento, vamos ilustrar uma técnica de simulação

digital, discreta e estocástica.• Problema: Simulação de um troço de auto-estrada.

– Simular o tráfego num troço de estrada com portagem, sónum dos sentidos.

– Os veículos entram no troço em causa com uma cadênciaaleatória no final do qual chegam a uma portagem (apenascom um portageiro), ficam em fila até ao pagamento e, concluído este, saem do troço.

– Pretende-se estudar a evolução do número de veículos nafila, em função de leis aleatórias:

• tempo entre chegadas;• tempo de travessia;• tempo de pagamento.


Introdução (3)• A técnica adoptada é a de sequenciamento de

eventos pendentes (SEP):1. Identificar os eventos que afectam o sistema a modelar.

– É necessário caracterizar os eventos, entre outros:– É essencial categorizar os eventos, por forma a

distingui-los.– É essencial um atributo de tempo, que marca o

instante em que se dá o evento.2. Definir as leis aleatórias que regem o acontecimento dos

eventos.


Introdução (4)3. Definir procedimentos para simular a observação das

variáveis aleatórias em causa.4. Simular os eventos.

– O núcleo do simulador é a cadeia de acontecimentospendentes (CAP), na qual se encontram todos oseventos (futuros). Durante a simulação podem:

– Retirar-se eventos da CAP.– Colocar-se novos eventos na CAP.


Identificação de eventos (1)

• Na simulação de um troço de auto-estrada existemos seguintes eventos:– Chegada: chegada de um veículo ao troço em estudo

(entrada na auto-estrada).– Portagem: chegada de um veículo à portagem no final do

troço (ou fica na fila da portagem ou entra em pagamento).– Partida: saída do veículo da portagem após pagamento.


Identificação de eventos (2)• Na simulação de um troço de auto-estrada não há outros

atributos para além do atributo de tempo.• Em simulações mais complicadas pode ser necessário

considerar outros atributos.– Poderia ser necessário associar cada evento ao veículo em

causa se se pretendesse estudar o tempo total de permanência dos carros no troço incluindo a portagem.


Identificação de eventos (3)

EvChegada EvPortagem EvPartida

<<abstract>Evento

• Diagrama de classes dos eventos do sistema (sem representação de atributos e métodos):


Leis aleatórias (1)

• Na simulação de um troço de auto-estrada há queconsiderar as seguintes leis aleatórias:– Chegadas: admite-se que o tempo entre chegadas

consecutivas é uma variável aleatória com distribuição exponencial de valor médio chegada.

– Travessias: admite-se que o tempo que um veículo leva a atravessar o troço é uma variável aleatória com distribuição exponencial de valor médio travessia.

– Pagamentos: admite-se que o tempo que cada veículo leva a pagar (tempo entre o início do pagamento, depois de ficar em primeiro lugar na fila, e a saída) é uma variável aleatória com distribuição exponencial de valor médio pagamento.


Leis aleatórias (2)

• Uma variável aleatória com distribuição exponencialde valor médio m tem a seguinte distribuição:

1-exp{-t/m}

1 2 3 4 5 6

0.2

0.4

0.6

0.8Por exemplo, para m=2:


Observação de variáveisaleatórias (1)

• A geração de uma observação de uma variável aleatória exponencial é feita por intermédio da inversa da função de distribuição: -m log(1-y)

1 2 3 4 5 6

0.2

0.4

0.6

0.8Por exemplo, para m=2:



public static double expRandom(double m) {Random random = new Random();double next = random.nextDouble();return -m*Math.log(1.0-next);

}

• Se Y~U(0,1) então -m log(1-Y)~Exp(m)



• Para uma variável aleatória com distribuição exponencial de valor médio 2:

for (int i=0; i<5; i++) {System.out.println(expRandom(2));

}

No terminal é impresso:3.6116265627007620.54540568692719220.96950464897071713.76352123373708560.04546112270038736


Simulação dos eventos –CAP (1)

• Para se entender a utilidade da CAP, considere-se o problema da simulação de tráfego em estudo na situação em que:– há veículos já no troço,– há veículos na fila, e– está um veículo a pagar a portagem.

• Como deverá continuar a simulação a partir desta situação?



• A simulação é apenas um ciclo em que em cada passo se simula o acontecimento de um evento.

– Põe-se então a questão: qual será o próximo evento a simular?

– A resposta é simples: vai-se buscar à CAP o próximo evento, onde por próximo se entende o evento com o atributo tempo de menor valor.

– Põe-se então outra questão: como alimentar a CAP de novos eventos?

– A resposta a esta questão já é mais complicada…



• Na CAP devem estar os eventos que já sabemos que terão de ser simulados no futuro (e que ainda não foram simulados por ainda não ter chegado a vez deles).

– De cada vez que se simula uma chegada ao troço deve-se colocar na CAP:

1. A próxima chegada: basta guardar na CAP o evento new EvChegada(tempo+expRandom(chegada))

2. O fim da travessia do veículo cuja travessia se está a simular: basta guardar na CAP o evento new EvPortagem(tempo+expRandom(travessia))

em que tempo é um atributo que contém o tempo de simulação do evento corrente (o tempo corrente), neste caso um evento de chegada.



– De cada vez que se simula um fim de travessia do troço há que examinar se o portageiro está ocupado.

1. Se estiver ocupado há que colocar mais um veículo na fila de espera.

2. Caso contrário começa a fase de pagamento. Pode-se então calcular o evento de fim de pagamento e, portanto, deve-se colocar na CAP o evento new EvPartida(tempo+expRandom(pagamento))

– Finalmente, de cada vez que se simula uma saída, ou seja, fim de pagamento, há que examinar a fila de espera. Se esta não estiver vazia há que retirar um elemento da fila (o primeiro) e planificar o fim de pagamento desse veículo guardando na CAP o evento new EvPartida(tempo+expRandom(pagamento))



• Na realidade, não é necessária a fila de portagem, sendo apenas necessário guardar o número de carros na fila…


Simulação (1)• A classe SimuladorTrafego pode então ser

definida como se segue (definição parcial):

public class SimuladorTrafego {

private static double tempoSimulacao, tempoCorrente;

private static Evento eventoCorrente;

static CAP cap;static int numCarrosFilaPortagem;

//...}


Simulação (2)• A classe Evento pode então ser definida como se

segue (definição parcial):

public abstract class Evento {

protected static double chegada, travessia, pagamento;

protected double tempo;

public abstract void simulaEvento();

//...}


Simulação (3)• Supondo existe acesso à cap e ao método expRandom, o método simulaEvento relativo àchegada ao troço de auto-estrada é definido como se segue:

• Nota: estudar com cuidado de que forma deve ser dado o acesso à cap e ao método expRandom!

cap.adicionarEvCAP(new EvChegada(tempo+expRandom(chegada)));

cap.adicionarEvCAP(new EvPortagem(tempo+expRandom(travessia)));


Simulação (4)• Supondo que existe acesso à cap, ao numCarrosFilaPortagem e ao método expRandom, o método simulaEvento relativo àchegada à portagem é definido como se segue:

• Nota: estudar com cuidado de que forma deve ser dado o acesso à cap, numCarrosFilaPortagem, e ao método expRandom!

if (numCarrosFilaPortagem==0)cap.adicionarEvCAP(

new EvPartida(tempo+expRandom(pagamento)));numCarrosFilaPortagem++;


Simulação (5)• Supondo que existe acesso à cap, ao numCarrosFilaPortagem e ao método expRandom, o método simulaEvento relativo àsaída da portagem é definido como se segue:

• Nota: estudar com cuidado de que forma deve ser dado o acesso à cap, numCarrosFilaPortagem, e ao método expRandom!

numCarrosFilaPortagem--;if (numCarrosFilaPortagem>0)

cap.adicionarEvCAP(new EvPartida(tempo+expRandom(pagamento)));


Simulação (6)• A CAP é uma classe com dois métodos:

– public void adicionarEvCAP(Evento ev)adiciona o evento recebido como parâmetro à CAP.

– public Evento proximoEvCAP(Evento ev)remove o primeiro evento da CAP e devolve-o.


Simulação (7)• O simulador é o método main da classeSimuladorTrafego e consiste basicamente num ciclo, onde em cada passo se simula o próximo evento na CAP.

• O simulador tem como input:− chegada− travessia− pagamento− tempoSimulacao


Simulação (8)

public static void main(String[] args) {// TODO: ler input e actualizar atributos de:// chegada, travessia, pagamento e tempoSimulacao//inicializaçãonumCarrosFilaPortagem = 0;cap = new CAP();eventoCorrente = new EvChegada(expRandom(chegada));tempoCorrente = eventoCorrente.tempo;//ciclo de simulaçãowhile (tempoCorrente<tempoSimulacao) {

//TODO: simular eventoCorrenteeventoCorrente = cap.proximoEvCAP();tempoCorrente = eventoCorrente.tempo;

}}


Exemplos (1)• É obtido o seguinte gráfico para o comprimento da

fila de espera da portagem executando oSimuladorTrafego com:– chegada=1 – travessia=50 – pagamento=0.9

– tempoSimulacao=1000

200 400 600 800 1000

5

10

15

20

25


Exemplos (2)

• Outra simulação para o mesmo input:

200 400 600 800 1000

2.5

5

7.5

10

12.5

15

17.5


Exemplos (3)

• Mais outra simulação para o mesmo input:

200 400 600 800 1000

5

10

15

20


Exemplos (4)• Aumentado apenas pagamento para 2:

200 400 600 800 1000

100

200

300

400


Exemplos (5)• Diminuindo apenas pagamento para 0.7:

200 400 600 800 1000

1

2

3

4

5

6

7

Documents

Simulação estocástica discreta - fenix.tecnico.ulisboa.pt · Exemplos (3) • Mais outra simulação para o mesmo input: 200 400 600 800 1000 5 10 15 20. LEEC@IST Simulação estocástica