03 Simulacion de Sistemas Simulacion Montecarlo

  • Published on
    11-Nov-2015

  • View
    12

  • Download
    5

Transcript

  • Red de aprendizaje Modelado

    y

    Simulacin

    Proyectos de

    Simulacin de

    Sistemas

    Generacin

    Valores de

    Variables

    Aleatorias

    Simulacin

    por

    Eventos

    Sistema de Colas con

    Servidores en Serie

    Sistema de Colas con

    Un servidor

    Sistemas de Colas con

    Servidores en Paralelo

    Sistemas de

    Inventarios

    Revisin Peridica

    Sistemas de

    Inventarios Punto

    de Repedido

    Sistemas

    Combinado de:

    Cadena de

    Almacenes

    Sistemas

    Combinado de:

    Sistema de Colas e

    Inventario

    Modelacin

    Montecarlo

  • Simulacin Montecarlo

    En esta parte del curso aprenderemos a disear

    simuladores Montecarlo.

    Recuerda:

    Un diagrama de flujo es la representacin grfica

    de las actividades de un proceso.

  • 1. Proceso (subproceso) , tarea o actividad

    Rectngulo:

    Se usa para denotar

    cualquier clase de

    actividad o proceso.

    Normalmente se debe

    incluir en el rectngulo

    una breve descripcin

    de la actividad.

    Smbolos a utilizar en flujogramas

    Actividad

  • 2. Punto de decisin Rombo:

    Se usa para tomar una

    decisin. La siguiente serie

    de actividades variarn en

    base a esta decisin.

    Por lo general, las salidas

    del rombo se marcarn

    con las correspondientes

    opciones Si - No.

    Smbolos a utilizar en los flujogramas

    Decisin

    SI

    NO

  • 3. Elemento de inicio o fin

    Circulo alargado:

    Se usa para indicar el

    inicio y fin del proceso.

    Normalmente dentro del

    smbolo aparece la palabra

    Inicio o Fin

    Smbolos a utilizar en flujogramas

    INICIO

  • 4. Conector de flujo Circulo pequeo:

    Se usa para indicar que la salida

    de esta parte del diagrama de

    flujo servir como entrada para

    otro diagrama de flujo.

    Con frecuencia este smbolo se

    utiliza cuando no existe suficiente

    espacio para dibujar la totalidad

    del diagrama de flujo en un

    papel.

    Cada salida diferente debe

    designarse con una letra

    diferente.

    Smbolos a utilizar en flujogramas

    A

  • 5. Entrada de datos.

    Rectngulo con la parte

    superior izquierda recortada:

    Se usa para indicar la entrada

    de datos por medio del teclado

    o un archivo con los datos

    correspondientes a la actividad

    a desarrollar por el simulador.

    Por ejemplo, numero de

    replicaciones que efectuar el

    simulador.

    Smbolos a utilizar en flujogramas

  • 6. Documento, formulario, reporte

    Rectngulo con la parte

    inferior en forma de onda:

    Se usa para indicar que la

    salida de una actividad o

    resultado por el programa

    Por ejemplo, informes escritos

    o presentacin de resultados

    impresos o una salida por

    pantalla).

    Smbolos a utilizar en flujogramas

    Documento

  • 6. Seleccin Simple (IF - THEN - ELSE)

    Es una instruccin que se

    utiliza para la bifurcacin

    condicional.

    Formato:

    IF Condicin THEN

    Begin

    Instrucciones - 1;

    End

    ELSE

    Begin

    Instrucciones - 2;

    End;

    Flujogramas bsicos

    Decisin Instrucciones 1

    Instrucciones 2

    Si

    No

  • 7. Ciclo con Entrada controlada (WHILE DO)

    Se utiliza para repetir un

    grupo de instrucciones

    mientras se cumpla una

    condicin.

    Formato:

    WHILE Condicin DO

    Begin

    ......................

    Instrucciones;

    End;

    Flujogramas bsicos

    Decisin

    Instrucciones

    Si No

  • 8. Ciclo con Salida Controlada (REPEAT UNTIL)

    Se utiliza para repetir un

    grupo de instrucciones

    hasta que se cumpla una

    condicin.

    Formato:

    REPEAT

    ....................

    Instrucciones;

    UNTIL Condicin;

    Flujogramas bsicos

    Decisin Si

    No

    Instrucciones

  • 9. Ciclo con Contador (FOR - TO DO) Un ciclo FOR - TO - DO se utiliza para ejecutar un

    bloque de instrucciones un nmero determinado de

    veces.

    Para contar el nmero de veces que se est

    ejecutando el ciclo, existe una variable denominada

    variable de control, que debe ser de tipo ordinal

    (Integer, Char Boolean) y se incrementa o

    decrementa automticamente en cada ejecucin del

    ciclo.

    Contador Creciente:

    FOR i:= Valor - Inic TO Valor - Fin DO

    Begin

    .....................

    Instrucciones;

    End;

    Contador Decreciente:

    FOR i:= Valor - In DOWNTO Valor fin DO Begin

    ...................

    Instrucciones;

    End; ).

    Flujogramas bsicos

    I= a, b

    Instrucciones

    10

    10

  • Se utiliza para implementar un procesamiento con varias opciones de seleccin.

    Formato:

    CASE Expresin OF

    Opcin - 1: Instruc - 1;

    Opcin - 2 : Instruc - 2;

    ..................

    ..................

    ELSE

    Instruccin;

    END;

    Flujogramas bsicos

    10. Diagrama de flujo de CASE OF:

    Escoger

    la opcin I

    Opcin I

    Opcin 1 Opcin Opcin 2

    I=1 I=

    I=2

  • Como generar los valores de un dado?

    El numero de caras que tiene un dado comn

    es 6 y cada una tiene la misma probabilidad de

    salir en un lanzamiento.

    Se le pide hacer un diagrama de flujo que le

    permita simular el lanzamiento de un dado.

  • Como jugar a Craps?

    La serie de tiros para establecer y repetir el Punto se denomina ronda.

    Cada ronda comienza con lo que se llama Tiro de Salida.

    Con este tiro se procura establecer el Punto.

    Un par de dados pueden dar totales desde 2 a 12, pero solamente totales de 3, 4, 5, 6, 8, 9 o 10 son considerados como el Punto.

    Los totales de 2 (los ojos de la serpiente o snake eyes) y 12(vagones o box cars) son considerados Craps.

    Mientras un total de 7 u 11 se le llama Natural.

  • Como jugar a Craps?

    Si durante el Tiro de Salida se obtiene un resultado de Craps o Natural la ronda automticamente llega a su conclusin.

    Sin embargo, si el resultado del lanzamiento es un 3,4, 5, 6, 8, 9 o 10 el Punto queda automticamente establecido y la ronda permanece abierta.

    Una vez establecido el Punto, el juego pasa a lo que se denomina mitad del juego o midgame que es la parte de la ronda donde el tirador contina lanzando los dados hasta que acierte otra vez al Punto o lance un 7 - ambos resultados dan por concluidos la ronda.

    Desarrollar el diagrama de flujo del juego.

  • Como ayudar a Miguel? Miguel un empleado en apuros no sabe que hacer para tratar de reducir sus tardanzas y les pide a ustedes como ingenieros hacer un aplicativo que le ayude a saber a que hora debe levantarse para no llegar tarde este aplicativo involucra sus conocimientos de Simulacin de Sistemas y Algoritmia.

    Para desarrollar este aplicativo le adjunta los siguientes datos de comportamiento:

    El se levanta todos los das entre 6:15 a.m. y 6:30 a.m. Durante 30 das Miguel cronometr el tiempo que empleaba desde el momento en que se levantaba hasta que estaba baado, afeitado y cambiado; los resultados se muestran a continuacin:

    Tiempo Empleado # de observaciones Probabilidad

    (Minutos)

    15 08 8/30

    20 11 11/30

    25 07 7/30

    30 04 4/30

    Miguel tiene una persona que se encarga de atenderlo y esta persona debera levantarse a las 6:20 a.m. sin embargo, esta persona se levanta siempre con algn retraso. Este retraso se distribuye normalmente con media 5 minutos y desviacin estndar de 1.5 minutos y tener listo el desayuno entre 10 a 15 minutos, se sabe adems que si una vez que Miguel est cambiado, y la persona contina durmiendo, ste procede a despertarla para que lo atienda.

    Una vez listos, tanto Miguel como el desayuno, Miguel requiere de 12 a 17 minutos para consumirlo. Luego se dirige a la oficina, empleando un tiempo que se distribuye exponencialmente con una media 50 minutos. Teniendo la muestra de este tiempo de viaje un valor mnimo de 24.57 y un valor mximo de 76.31

    Su hora de entrada es a las 8:00 AM.

    Se pide: Construir un simulador para hallar la probabilidad de que Miguel llegue a tiempo a su oficina y adems cual es la tardanza promedio.

  • Como ayudar a Miguel?

    Para resolver este problema lo primero que tenemos que hacer es trabajar con las variables aleatorias (VA) que se encontramos en el caso que son las siguientes:

    Tiempo de levantarse 6:15 a 6:30. (TLEV) TLEV = UNIF(15,30)

    Tiempo de afeitarse baarse y cambiarse: (TBAC)

    Tiempo Empleado # de observaciones Probabilidad

    (Minutos)

    15 08 8/30

    20 11 11/30

    25 07 7/30

    30 04 4/30 Tiempo de levantarse de la persona encargada. (TLEVP) TLEVP = 20 + Tardanza. (Tardanza = NORM(5,1.5)

    Tiempo de preparacin del desayuno (TPRDES) TPRDES = UNIF (10, 15)

    Tiempo de Tomar el desayuno (TTODES) TTODES = UNIF(12, 17)

    Tiempo empleado para ir ala oficina (TOFIC) TOFIC = EXPO(50)

  • Como ayudar a Miguel?

    Primero trabajaremos con las variables uniformes que son:

    TELEV = UNIF(15,30)

    TPRDES = UNIF (10, 15)

    TTODES = UNIF(12, 17)

    Entonces tendremos lo siguiente:

    X~UNIF (a, b)

    a-b

    1

    12

    a)-(b

    2

    ba

    Moda anza VariMedia

    2

    a b

    a-b

    1

    UNIF (a, b)

    r = random

    La forma de generar esta variable se

    realiza mediante con la siguiente

    expresin:

    x = a + (b a ).r , r [0, 1 ]

    UNIF = a + (b a ).r

    Return

    Diagrama de Flujo

  • Como ayudar a Miguel?

    TBAC # de obs Prob Pacum Intervalos

    (min.)

    15 08 8/30 8/30 [ 0 , 8/30[

    20 11 11/30 19/30 [ 8/30, 19/30[

    25 07 7/30 26/30 [19/30, 26/30[

    30 04 4/30 1 [26/30, 1 ]

    La forma de generar esta VA es generar r [0, 1 ] y luego buscar en que intervalo cayo el valor de r.

    Esto nos conduce al siguiente diagrama de flujo.

    Ahora trabajaremos con la variable discreta: TBAC

    r< 8/30

    r< 19/30

    r< 26/30

    r = random

    DISC

    DISC = 25

    DISC = 15

    DISC = 20

    DISC = 30

    Return

  • Como ayudar a Miguel?

    Para generar este tipo de variable recurriremos al Teorema de Limite Central (TLC):

    es una VA que tiene los siguientes parmetros:

    1

    n

    i

    ir

    Trabajaremos con la variable: TLEVP que esta por una parte constante la VA que es la tardanza entonces: TELEVP = 20 + NORM(5, 1.5)

    )n ,NORM(n :sabe se adems Pero 2

    1

    n

    i

    ir

    2

    11

    )( ,)( nrVarnrEn

    i

    i

    n

    i

    i

    Luego si ri ~ UNIF(0, 1) entonces:

    12)( ,

    2)(

    11

    nrVar

    nrE

    n

    i

    i

    n

    i

    i

    f(x)

    x

  • Como ayudar a Miguel?

    Despejando x tendremos:

    zx

    Para normalizar una VA normal se utiliza la siguiente expresin:

    Donde Z~NORM(0, 1), luego para generar

    X debemos primero generar Z para ello de

    la expresion siguiente:

    tomaremos n=12 y restaremos 6 entonces:

    -x z

    12)( ,

    2)(

    11

    nrVar

    nrE

    n

    i

    i

    n

    i

    i

    1)6( ,0)6(12

    1

    12

    1

    i

    i

    i

    i rVarrE

    Luego: )1,0(612

    1

    NORMri

    i

    Z = 0

    NORM(, )

    z = z - 6

    z = z +r

    r = random

    NORM= + z.

    Return

    i = 1, 12

    10

    10

  • Como ayudar a Miguel?

    1 ,0 ),ln(1 rdonderx

    1

    1

    anza VariMedia

    2

    Para generar una variable aleatoria que se distribuye exponencialmente solo se tiene usar la siguiente expresin:

    Luego:

    EXPO ()

    r = random

    EXPO = - Ln (r)

    Return

    Diagrama de Flujo

    )ln(rx

    TOFIC ~ EXPO(80)

  • Como ayudar a Miguel?

    Una vez que terminamos con las VA involucradas en el problema podremos elaborar el diagrama de flujo del caso.

    Desayuno

    DT = 0

    TT = 0

    Generar TLEV, TBAC y TLEVP

    FIN

    Diagrama de Flujo

    N

    i=1, N

    30

    30

    TPO = TLEV + TBAC

    TLEVP = TPO

    Generar TPRDES

    TELEVP > TPO

    TAUX = TLEVP + TPRDES

    TPO = TAUX

    TPO < TAUX

    Generar TTODES, TOFIC

    TPO = TPO + TTODES+TOFIC

    TPO 120

    TT = TT +TPO - 120

    DT = DT +1

    TARDPROM = TT/DT

    PROBTARD = DT/N

    PROBTARD

    TARDPROM

    SI

    NO

    NO

    SI

    SI

    NO

  • Sistema de colas con un servidor

    La Empresa Creatividad S.A.C. tiene una oficina donde los clientes estn arribando con un tiempo entre llegadas distribuido normalmente con una media de 8 minutos y una desviacin estndar de 2 minutos, segn la muestra tomada se obtiene que los valores van de 4,7 a 11.3 minutos, y el tiempo requerido para atenderlos se distribuye exponencial con una media 9 minutos y con valores entre los 5.1 y 12.5 minutos.

    Esta oficina tiene un solo empleado que atiende a los clientes. Si llega un cliente y el empleado est disponible, se inicia inmediatamente la atencin. Y si el empleado est ocupado, los clientes esperarn a ser atendidos en una cola segn el criterio FIFO.

    Luego de completar la atencin, los clientes salen del rea en estudio.

    Para realizar un estudio de simulacin del sistema se desea saber:

    a.Cul es nmero clientes atendidos?

    b.Cul es la cola mxima que se forma?.

    c. Cunto tiempo pasaron en cola y cuanto en el sistema?.

    d. Los clientes no cumplen con algn requisito con una probabilidad de un 10% al llegar al sistema, los cuales son separados y abandonan la oficina. Cuantos clientes no son atendidos?

  • Representacin grfica del Sistema

    Representacin del Sistema

    Entidades Atributos Actividades

    Cliente Tiempo de arribo Llegar al sistema.(Elemento temporal) % de falta de requisito Abandono por falta requisito.

    Formar Cola. Recibir servicio. Salir del sistema.

    Empleado Tiempo de servicio Atender clientes.(Elemento permanente) Espera de clientes.

    TS (Tiempo de servicio)

    Servidor Salida

    Abandono por falta de requisito

    COLA

    Llegada TLL

    Sistema de colas con un servidor

  • Diseo de un simulador de un sistema de cola simple

    Instantes en que cambia el sistema:

    Llegada de un cliente TLL

    Fin de Servicio TFS

    Para un cliente siempre se cumple TLL < TFS

    Haciendo un pequea corrida en el tiempo T:

    0 t1 t2 t4 t3 t6 t5

    LL FS LL FS LL LL

    T

  • Sistema de colas de un servidor

    Tabla base

    TLL TFS RM Evento

    t1 < t3 t1 Arribo

    t2 < t3 t2 Arribo

    t4 > t3 t3 Fin de Servicio

    t4 < t5 t4 Arribo

    t6 > t5 t5 Fin de Servicio

    0 t1 t2 t4 t3 t6 t5

    LL FS LL FS LL LL

    T

  • Sistema de colas de un servidor

    Diagrama de flujo base

    Tabla base

    TLL TFS RM Evento

    t1 < t3 t1 Arribo

    t2 < t3 t2 Arribo

    t4 > t3 t3 Fin de Servicio

    t4 < t5 t4 Arribo

    t6 > t5 t5 Fin de Servicio

    TLL < TFS

    ARRIBO FIN DE SERVICIO

    RM < TMS

    SI NO

    SI

    NO

  • Sistema de colas de un servidor Diagrama de flujo con entrada de valores de N y de TMS

    TLL < TFS

    ARRIBO FIN DE SERVICIO

    RM < TMS

    SI NO

    SI

    NO

    N, TMS

    I=1, N 10

    10

    N= numero de simulaciones

    TMS= periodo de simulacin

    TLL= tiempo de llegada

    TFS= tiempo de fin de servicios

    RM= reloj maestro

    I= contador del FOR TO DO

  • Sistema de colas de un servidor Calculo de Atendidos Promedio y Abandonos promedio

    Programa Principal

    N= numero de simulaciones

    TMS= periodo de simulacin

    TLL= tiempo de llegada

    TFS= tiempo de fin de servicios

    RM= reloj maestro

    I= contador del FOR TO DO

    TLL < TFS

    ARRIBO FIN DE SERVICIO

    RM < TMS

    SI NO

    SI

    NO

    N, TMS

    I=1, N 10

    10

    TLL= 0, COLA= 0

    TFS= 9999, ES= 0

    RM=0

    ABANPROM= ABANDONO/N

    ATENPROM=ATENDIDOS/N

    REPORTE

    INICIO

    FIN

    TLL= 0, COLA= 0, TFS= 9999, ES= 0, RM=0

    ABANDONO=0, ATENDIDOS=0

  • Evento Arribo

    ARRIBO

    RM = TLL

    ABANDONA

    ES=0

    ES = 1

    Generar TELL

    TFS = RM + TS

    COLA = COLA +1

    TLL = RM + TELL

    RETURN

    NO

    SI

    Generar TS

    Si

    No

    ABANDONO = ABANDONO + 1

  • Evento Fin de Servicio

    FIN DE SERVICIO

    RM = TFS

    ATENDIDOS = ATENDIDOS + 1

    COLA = 0

    COLA = COLA -1

    Generar TS

    TFS = RM + TS

    ES = 0

    TFS = 9999

    RETURN

    NoSi