TEMA IV - Tema IV Simulación PDF

Preview

Summary

Tema IV Simulación...

Description

TEMA IV LENGUAJES DE SIMULACIÓN SUBTEMAS 4.1 Lenguaje de simulación y simuladores 4.2 Aprendizaje y uso del lenguaje de simulación o un simulador 4.3 Casos prácticos de simulación 4.3.1 Problemas con líneas de espera 4.3.2 Problemas con sistemas de inventario 4.4 Validación de un simulador 4.4.1 Pruebas paramétricas (Validación del modelo, pruebas de hipótesis y pruebas de estimación). 4.4.2 Pruebas no paramétricas

LENGUAJE DE SIMULACION Y SIMULADORES En un principio, los programas de simulación se elaboraban utilizando algún lenguaje de propósito general, como ASSEMBLER, FORTRAN, ALGOL o PL/I. A partir de la década de 1960 hacen su aparición los lenguajes específicos para simulación como GPSS, GASP, SIMSCRIPT, SLAM. En la última década del siglo pasado la aparición de las interfaces gráficas revolucionaron el campo de las aplicaciones en esta área, y ocasionaron el nacimiento de los simuladores. En lo práctico, es importante utilizar la aplicación que mejor se adecúe al tipo de sistema a simular, ya que de la selección del lenguaje o simulador dependerá el tiempo de desarrollo del modelo de simulación. Las opciones van desde las hojas de cálculo, lenguajes de tipo general (como Visual Basic, C++ o Fortan), lenguajes específicos de simulación (como GPSS, SLAM, SIMAN, SIMSCRIPT, GAS y

SSED), hasta simuladores específicamente desarrollados para diferentes objetivos (como SIMPROCESS, ProModel, Witness, Taylor II y Cristal Ball).

APRENDIZAJE Y USO LENGUAJE DE SIMULACIÓN O UN SIMULADOR

Los lenguajes de simulación facilitan enormemente el desarrollo y ejecución de simulaciones de sistemas complejos del mundo real. Los lenguajes de simulación son similares a los lenguajes de programación de alto nivel pero están especialmente preparados para determinadas aplicaciones de la simulación. Así suelen venir acompañados de una metodología de programación apoyada por un sistema de símbolos propios para la descripción del modelo por ejemplo mediante diagramas de flujo u otras herramientas que simplifican notablemente la modelización y facilitan la posterior depuración del modelo. Características de los lenguajes de simulación: 

Los

lenguajes

de

simulación

proporcionan

automáticamente

las

características necesarias para la programación de un modelo de simulación, lo que redunda en una reducción significativa del esfuerzo requerido para programar el modelo. 

Proporcionan un marco de trabajo natural para el uso de modelos de simulación. Los bloques básicos de construcción del lenguaje son mucho más afines a los propósitos de la simulación que los de un lenguaje de tipo general.



Los modelos de simulación son mucho más fácilmente modificables.



Proporcionan muchos de ellos una asignación dinámica de memoria durante la ejecución,



Facilitan una mejor detección de los errores.



Los paquetes de software especialmente diseñados para simulación contienen aplicaciones diversas que facilitan al simulador las tareas de comunicaciones, la depuración de errores sintácticos y de otro tipo de errores, la generación de escenarios, la manipulación “on-line” de los modelos, etc.



Son muy conocidos y en uso actualmente



Aprendizaje lleva cierto tiempo



Simuladores de alto nivel



Muy fáciles de usar por su interface gráfica



Restringidos a las áreas de manufactura y comunicaciones



Flexibilidad restringida puede afectar la validez del modelo

Entre estos lenguajes específicos podemos nombrar los siguientes: MIDAS, DYSAC, DSL , GASP, MIMIC, DYNAMO, GPSS, SIMULA, CSSL( Continuous System Simulation Language) , CSMP, ACSL ( Advanced Conrinuous Simulation Language), DARE-P and DARE-Interactive, C-Simscript, SLAM, SIMAN, SIMNON, SIMSCRIPT-II-5, ADA, GASP IV, SDL. Muchos de estos lenguajes dependen fuertemente de los lenguajes de propósito general como es el caso de SLAM o SIMAN que dependen de Fortran para las subrutinas. Por otro lado, el GPSS es un caso especial de un lenguaje de simulación de propósito especial, altamente estructurado que está orientado a la transacción, un caso especial de una orientación basada en procesos más general. El GPSS fue diseñado para la simulación simple de sistemas de colas tales como trabajos de taller. A diferencia de los otros lenguajes de simulación, GPSS tiene varias implementaciones incluyendo GPSS/H y GPSS/PC, ambos de los cuales serán discutidos más adelante. El SIMAN V, SIMSCRIPT II.5, y el SLAM son lenguajes de simulación de alto nivel que tienen constructor especialmente diseñados para

facilitar la construcción de modelos. Estos lenguajes proveen al analista de simulación con una opción orientación basada en procesos o basada en eventos, o un modelo usando una mezcla de las dos orientaciones. A diferencia del FORTRAN, estos tres lenguajes proveen la administración de la lista de eventos futuros, generador interno de variables aleatorias, y rutinas internas para la obtención de estadísticas (estas características para las implementaciones del GPSS mencionadas previamente.) Se pueden lograr cálculos complejos en ambas implementaciones del GPSS y estos tres lenguajes. El SIMAN, SIMSCRIPT II.5, y el SLAMSYSTEM proveen la capacidad de realizar simulación continua (esto es, para modelar sistemas que tengan continuamente cambios en sus variables de estado) pero este tema no está dentro del alance de este libro. El SIMAN está escrito en C, aunque las primeras versiones del lenguaje fue escrito en FORTRAN. El SIMAN V puede ser acezado directamente, o a través del medio ambiente del ARENA, El SLAMSYSTEM contiene al lenguaje de simulación SLAM II. El SLAM II está basado en el FORTRAN y contiene al lenguaje GASP como un subconjunto. El GASP es un conjunto de subrutinas en FORTRAN para facilitar las simulaciones orientadas al objeto escritas en FORTRAN. El SIMSCRIPT II.5 por otro lado, contiene un subconjunto de un completo lenguaje científico de simulación comparable con el FORTRAN, C o C++. El MODSIM III es un descendiente del lenguaje que la compañía de productos CACI originalmente diseñado por la armada de los Estados Unidos. Hereda mucha de su sintaxis del MODULA-2 y del ADA, ciertas características del ADA y sus conceptos de simulación del SIMSCRIPT y el SIMULA. Algunas de las características de la simulación orientada al objeto fueron originalmente vistas en el SIMULA y el SMALLTALK.

CASOS PRACTICOS DE SIMULACIÓN

Un caso práctico de una simulación podemos decir en esta parte, la simulación del Método de Monte Carlo.

ALGORITMOS El algoritmo de Simulación Monte Carlo Crudo o Puro está fundamentado en la generación de números aleatorios por el método de Transformación Inversa, el cual se basa en las distribuciones acumuladas de frecuencias: 

Determinar la/s V.A. y sus distribuciones acumuladas(F)



Generar un número aleatorio uniforme Î (0,1).



Determinar el valor de la V.A. para el número aleatorio generado de

acuerdo a las clases que tengamos. 

Calcular media, desviación estándar error y realizar el histograma.



Analizar resultados para distintos tamaños de muestra.

Otra opción para trabajar con Monte Carlo, cuando la variable aleatoria no es directamente el resultado de la simulación o tenemos relaciones entre variables es la siguiente:  Diseñar el modelo lógico de decisión  Especificar distribuciones de probabilidad para las variables aleatorias relevantes  Incluir posibles dependencias entre variables.  Muestrear valores de las variables aleatorias.  Calcular el resultado del modelo según los valores del muestreo (iteración) y registrar el resultado  Repetir el proceso hasta tener una muestra estadísticamente representativa  Obtener la distribución de frecuencias del resultado de las iteraciones

 Calcular media, desvío.  Analizar los resultados Las principales características a tener en cuenta para la implementación o utilización del algoritmo son: 

El sistema debe ser descripto por 1 o más funciones de

distribución de probabilidad (fdp) 

Generador de números aleatorios: como se generan los números

aleatorios es importante para evitar que se produzca correlación entre los valores muéstrales. 

Establecer límites y reglas de muestreo para las fdp: conocemos

que valores pueden adoptar las variables. 

Definir Scoring: Cuando un valor aleatorio tiene o no sentido para

el modelo a simular. 

Estimación Error: Con que error trabajamos, cuanto error

podemos aceptar para que una corrida sea válida? 

Técnicas de reducción de varianza.



Paralelización y vectorización: En aplicaciones con muchas

variables se estudia trabajar con varios procesadores paralelos para realizar la simulación. EJEMPLO PRACTICO I Tenemos la siguiente distribución de probabilidades para una demanda aleatoria y queremos ver qué sucede con el promedio de la demanda en varias iteraciones: Utilizando la distribución acumulada(F(x) es la probabilidad que la variable aleatoria tome valores menores o iguales a (x) podemos determinar cuál es el valor obtenido de unidades cuando se genera un número aleatorio a partir de una distribución continua uniforme. Este método de generación de variable aleatoria se llama Transformación Inversa.

Generando los valores aleatorios vamos a ver como se obtiene el valor de la demanda para cada día, interesándonos en este caso como es el orden de aparición de los valores. Se busca el número aleatorio generado en la tabla de probabilidades acumuladas, una vez encontrado ( si no es el valor exacto, éste debe ser menor que el de la fila seleccionada pero mayor que el de la fila anterior), de esa fila tomada como solución se toma el valor de las unidades (Cuando trabajamos en Excel debemos tomar el límite inferior del intervalo para buscar en las acumuladas, para poder emplear la función BUSCARV(), para 42 sería 0, para 43 0,100001 y así sucesivamente). Ejemplo: Supongamos que el número aleatorio generado sea 0,52, ¿a qué valor de unidades corresponde? Nos fijamos en la columna de frecuencias acumuladas, ese valor exacto no aparece, el siguiente mayor es 0,70 y corresponde a 48 unidades. Se puede apreciar mejor en el gráfico, trazando una recta desde el eje de la frecuencia hasta que interseca con la línea de la función acumulada, luego se baja a la coordenada de unidades y se obtiene el valor correspondiente; en este caso 48. Cuando trabajamos con variables discretas la función acumulada tiene un intervalo o salto para cada variable ( para casos prácticos hay que definir los intervalos y luego con una función de búsqueda hallar el valor). Para funciones continuas se puede hallar la inversa de la función acumulada. De esta forma logramos a partir de la distribución de densidad calcular los valores de la variable aleatoria dada.

En la siguiente tabla, vemos como a medida que aumenta el número de simulaciones, el valor simulado se acerca al valor original de la media y desviación estándar, además de la disminución del error típico.

PROBLEMAS CON LINEA DE ESPERA Simulación de una línea de espera con una fila y un servidor Un sistema de colas estará definido cuando tengamos la siguiente información acerca de este: • Distribución de probabilidad de los tiempos de servicio. • Distribución de probabilidad de los tiempos entre llegadas. • Numero de servidores. • Numero de filas. • Conexiones entre servidores y filas. • Disciplinas y restricciones de los servidores y filas (en caso de que existan). Para este primer ejemplo se utilizara el modelo de líneas de espera que se muestra en la figura siguiente. Como se puede apreciar, es un modelo bastante simple donde la disciplina de atención es FIFO (primero en llegar, primero en salir).

Tanto el tiempo de servicio como el tiempo entre llegadas siguen una distribución exponencial aunque con parámetros diferentes, para el caso del tiempo entre llegadas tenemos λ=15 y para el tiempo de servicio tenemos λ=10. Aplicando el método de la transformada inversa a la distribución exponencial (consultar Dyner etc. al, 2008), tenemos que:

Donde corresponde a una observación de una variable exponencial, ri es un número aleatorio entre cero y uno y λ es la media de la distribución. Para la implementación del sistema descrito en Excel, abra una nueva hoja de cálculo y configúrela como se muestra en la figura.

En la celda B8 escriba la formula =ALEATORIO() y arrastre hasta la celda B23. Repita este procedimiento para la columna G. En el paso anterior, se definió los números aleatorios a partir de los cuales se generaran las observaciones de variables aleatorias de la simulación. Ahora, en la celda C8 escribe la formula =-LN(1-B8)/$B$4, y arrastre hasta la celda C23.

Como se puede apreciar, esta es la formula descrita anteriormente para obtener observaciones de una variable exponencial. En este caso, se están generando observaciones para la variable aleatoria de tiempos entre llegadas. En la celda D8 escribe la formula =C8, lo anterior significa que como es la primera llegada al sistema, su tiempo de llegada (en el instante de tiempo en el que llego al sistema), será igual a su tiempo entre llegadas. Sin embargo, para la celda D9 la formula correspondiente es =C9+D8, ahora arrastre la formula de D9 hasta D23; esta fórmula significa que después de que llega el primer cliente, el instante de tiempo en el que cualquier otro cliente llega al sistema será el instante de tiempo en

el

que

entro

el penúltimo cliente

sumado

el

tiempo

entre

llegadas

del último cliente, es decir, si el penúltimo cliente entro al sistema en el instante t=4, y el tiempo entre llegadas del último cliente es dt=2, entonces este ultimo cliente entrara realmente al sistema en t=6. La formula correspondiente a la celda E8 es =D8, esto significa que, al ser primer cliente, el instante en el que llega al sistema será el mismo instante en el que comienza el servicio; más adelante se presenta las formulas correspondientes al resto de clientes del sistema en esta columna. Ahora en la celda F8 escriba la formula =E8-D8 y arrástrela hasta la celda F23, esto corresponde al tiempo de espera del cliente antes de comenzar a ser atendido, note que D8 nunca será mayor que E8 ya que el valor mínimo que puede tomar el tiempo de comienzo del servicio es el tiempo de llegada, es decir, cuando un cliente llega al sistema y no tiene que hacer fila. En la celda H8 escribe la formula =-LN(1-G7)/$B$5, y arrástrela hasta la celda H23, esta fórmula indica cuanto tiempo tardara el servidor atendiendo al cliente actual. Ahora en la celda I8 escriba la formula =E8+H8, esta fórmula indica el instante de tiempo en el que servidor termina de atender al cliente actual y corresponde a la suma entre el instante que comienza el servicio y la cantidad de tiempo que este toma.

Retomemos ahora la columna E, nótese que esta solo está definida en su posición E8, esto porque primero se requería definir otros valores antes de poder determinar el instante en el que empieza realmente el servicio. En un sistema como el aquí presentado se pueden tener dos casos para el tiempo de comienzo del servicio, en primer lugar puede que el servidor se encuentre desocupado, en este caso el tiempo de comienzo del servicio será igual al tiempo de llegada al sistema y no habrá tiempo de espera. Sin embargo, si el servidor se encuentra ocupado, el tiempo de comienzo del servicio será igual al máximo entre el instante en que el servidor termine de atender al cliente actual y el tiempo de llegada al sistema; por si el tiempo de fin del servicio del cliente actual es igual a tfs=12 pero el tiempo de llegada del próximo cliente es tll=14, el tiempo de comienzo del servicio del próximo cliente será t=14 y el servidor tendrá un ocio dt=2; por otro lado, si tfs=13 para el cliente actual y el próximo cliente tiene un tll=10, el servidor no tendrá ocio y el próximo cliente deberá esperar un intervalo de tiempo dt=3. De lo anterior se concluye que la fórmula para la celda E9 debe ser =MAX(D9;I8), ahora arrastre esta fórmula hasta la celda E23. Hasta este punto se tiene una simulación de un sistema de líneas de espera con una fila y un servidor, si se desea generar nuevas observaciones presione la tecla F9; como tarea al lector se deja el cálculo de: • Tiempo promedio en el sistema • Tiempo promedio de espera (sin incluir ceros) • Tiempo promedio de espera (incluyendo ceros) • Tiempo promedio de servicio • Tiempo promedio de ocio Adicionalmente se plantea al lector elaborar, una simulación en Excel que represente el sistema que se muestra en la figura siguiente, donde p es la probabilidad de que un cliente se dirija a S1 o a S2. Tanto el tiempo entre llegadas

como los tiempos de servicio, se distribuyen exponencial con los parametros que se muestran a continuación.

Tiempo entre llegadas: λ=8 Tiempo de servicio S1: λ=13 Tiempo de servicio S2: λ=18 Probabilidad p: 0.63 VALIDACIÓN DE UN SIMULADOR Aquí vamos a mostrar cómo se valido el correcto funcionamiento de un simulador con demanda y tiempo de espera, determinanticos. Para

ver

más

detalladamente

sigue

el

enlace

propuesto: https://www.dropbox.com/s/d1i7ft47b6ubu1t/validacion %20simulador.pdf?m PRUEBAS PARAMETRICAS (VALIDACIÓN DEL MODELO, PRUEBAS DE HIPOTESIS Y PRUEBAS DE ESTIMACIÓN) Validación del modelo Etapas en el desarrollo de un simulador. Recordemos que las etapas nombradas para desarrollar un simulador son: 1) Identificación del problema 2) Delimitación del sistema 3) Formulación del modelo 4) Preparación de datos

5) Construcción del modelo 6) Validación 7) Diseño de experimentos 8) Ejecución de experimentos 9) Interpretación (Inferencia) 10) Documentación IV) Etapa IV: Preparación de datos, o bien obtención de datos. Consiste en la identificación y captación de los datos que requiere el modelo, de acuerdo a la formulación que se haya hecho en las etapas anteriores del diseño. Los datos son para: ·

Las relaciones funcionales, ya sea para determinar la forma de éstas, completar su forma o expresión, o para precisar algún parámetro que en ella se tenga.

·

Las variables estocásticas, que de ellas se deberá determinar su función de distribución de probabilidades, tanto para variables continuas como discretas.

·

Las relaciones funcionales podrían ser, rectas obtenidas por regresión lineal o ajuste de curvas.

·

En las relaciones funcionales se debe fijar todos los parámetros que tenga; a menos que se haya dejado como una variable de entrada al simulador. Los datos a usar pueden ser: 

Datos empíricos



Datos obtenidos con distribuciones teóricas.

El usar datos empíricos es en general más conveniente, pero puede implicar que el modelo quede influido por factores que se dieron en el tiempo de gestación de ellos y no vuelvan a repetirse. V. Construcción del modelo Es llevar el modelo que se tiene del simulador a un lenguaje de programación disponible en el computador a usar o en las configuraciones disponibles, y que debe conocer su programación. Luego que se tiene el programa fuente del modelo, escrito en el lenguaje elegido, probarlo y depurarlo desde el punto de vista computacional, hasta obtener una versión satisfactoria. VI. Validación Es esta etapa se trata de establecer, y si es posible aumentar, el nivel aceptable de confiabilidad de las inferencias efectuadas sobre el sistema real. La val...