SIMULACIÓN DE SISTEMAS DISCRETOS

DEFINICIÓN GENÉRICA

Por Simulación de Sistemas entendemos el proceso de representar un sistema por medio de un modelo simbólico que puede manipularse por medio de un computador digital para que proporcione resultados numéricos. El computador permitirá evaluar numéricamente un modelo de simulación durante un intervalo de tiempo significativo para los objetivos del estudio, y recoger durante el mismo datos que posibiliten la estimación de las características deseadas del modelo.

En el caso de los sistemas discretos, la simulación se refiere a la modelización en un computador digital de un sistema cuyos cambios de estado tienen lugar de manera discreta como consecuencia de la ocurrencia de agentes del cambio de estado denominados sucesos.

Simular es, pues, duplicar el comportamiento dinámico de algún aspecto de un sistema, real o propuesto, sustituyendo las propiedades esenciales del sistema simulado por las propiedades del sistema que lo simula, el modelo .

Una vez construido, el modelo de simulación actúa como un laboratorio en el que se pueden verificar, comparar y ajustar fácilmente las diferentes alternativas de diseño. Mediante la ejecución del modelo en un ordenador se imitan las acciones del sistema propuesto, permitiendo extraer inferencias sobre las prestaciones del sistema global.

En general las condiciones de utilización de la simulación son las siguientes según Shannon 

1. No existe una formulación matemática completa del problema, o no se han desarrollado aún los métodos analíticos para resolver el modelo matemático.

2. Existen los métodos analíticos, pero las hipótesis simplificadoras, necesarias para su aplicación, desvirtúan las soluciones obtenidas y su interpretación.

3. Los métodos analíticos existen, y en teoría están disponibles, pero los procedimientos numéricos son tan arduos y complejos que la simulación constituye un método más sencillo para obtener una solución.

4. Es deseable observar una historia simulada del proceso dentro de un horizonte temporal dado para poder estimar ciertos parámetros.

5. La simulación constituye la mejor alternativa por la dificultad de realizar experiencias en el contexto real.

6. Es necesario realizar una compresión temporal para estudiar la evolución del sistema a largo plazo.

Un modelo de simulación describe pues el comportamiento dinámico de un sistema en el tiempo. En la terminología que hemos introducido, el sistema está formado por entidades, elementos componentes cuyo comportamiento es seguido a través del sistema. Las entidades pueden pertenecer a diferentes clases, y poseen atributos identificativos que caracterizan su comportamiento, y por ende el del sistema. Las entidades de una clase dada tienen el mismo conjunto de atributos, aunque sus valores no tengan por que ser idénticos, y tenderán a seguir pautas de comportamiento similares en el tiempo. Las entidades pueden intervenir en actividades, solas o conjuntamente con otras entidades.

En un instante determinado el sistema simulado tendrá una configuración dada, definida por las actividades de las entidades y los valores de sus atributos: esta será la caracterización del estado del sistema . El estado cambiará, discretamente, como consecuencia de la ocurrencia de un suceso .

La secuencia de sucesos y los cambios de estado que determinan representan el comportamiento dinámico del sistema .

EJEMPLO

En el caso que nos ocupa podemos definir el estado del sistema como el número de unidades que hay en el sistema en un momento dado. Diremos pues que el sistema se encuentra en el estado n en el instante t si en dicho instante hay n unidades en el sistema, contando las que esperan en la cola a recibir servicio y las que están recibiendo servicio en ese momento.

A partir de esta especificación del estado del sistema es evidente que el sistema cambia de estado cada vez que llega a él una nueva unidad para recibir servicio, o cada vez que una unidad ha terminado de recibir servicio y lo abandona. Diremos entonces que el sistema cambia de estado cada vez que se produce un suceso, y que hay dos tipos de suceso susceptibles de cambiar el estado del sistema, el suceso llegada de una nueva unidad al sistema y el suceso salida de una unidad del sistema.

Si las llegadas son aleatorias según una distribución de Poisson, y los servicios son exponenciales, simular sucesos llegada al sistema consiste en extraer muestras de números aleatorios que sigan la distribución de Poisson que las describe (o, cómo hemos puesto de manifiesto anteriormente, la distribución exponencial asociada que representa los intervalos de tiempo entre llegadas consecutivas), y simular sucesos salida consiste en extraer muestras de números aleatorios que sigan la distribución exponencial que los describe. A partir de dichas muestras un sencillo mecanismo de seguimiento que permite realizar la simulación del sistema de colas propuesto.

En este ejemplo los intervalos de tiempo entre llegadas son:

A1 = 55, A2 = 32, A3 = 24, A4 = 40, A5 = 12, A6 = 29, ...

y las duraciones de los servicios:

S1 = 43, S2 = 36, S3 = 34, ...

de manera que la primera llegada se produce a las 55 unidades de tiempo, como en ese momento la unidad de servicio está libre pasa a recibir servicio directamente,  y su servicio durará 43 unidades de tiempo, por lo que el suceso salida correspondiente se producirá en el instante 98, la segunda llegada se produce 32 unidades de tiempo después de la primera, es decir en el instante 87, como en ese momento la unidad de servicio aún está ocupada sirviendo a la primera llegada, la segunda se instala en la cola a esperar, de donde saldrá en el instante 98 para pasar a recibir servicio, su servicio durará 36 unidades por lo que su suceso salida se producirá en el instante 134, y así sucesivamente.

FORMULACIÓN DEL MODELO

La codificación de un modelo de simulación, de un sistema con sucesos discretos, en términos de un lenguaje de programación, de tipo general o especial para simulación, pone de manifiesto una serie de características comunes a todos ellos, como por ejemplo Fishman 

1. La generación de muestras de números aleatorios uniformemente distribuidos en (0,1).

2. La generación de muestras de variables aleatorias con distribuciones específicas.

3. Los mecanismos de control y flujo del tiempo durante la simulación.

4. La determinación del suceso que ha de ser tratado a continuación del que lo está siendo (técnica next-event).

5. La adición, supresión o actualización de registros en estructuras de datos ad hoc, como por ejemplo listas que representan secuencias de sucesos. 

6. La recolección y el análisis de los datos generados por la simulación.

7. La elaboración de informes sobre los resultados obtenidos. 

8. La detección de condiciones de error.

La existencia de estos y otros factores comunes a la mayor parte de los programas de simulación es lo que ha conducido al desarrollo de los lenguajes de simulación de propósito general, cuyo perfeccionamiento, estandarización y accesibilidad han sido los principales factores del incremento que ha experimentado el uso de la simulación en los últimos años.

Una de las decisiones más importantes que ha de tomar un modelizador o analista para la realización de un estudio de simulación es la selección del lenguaje de computador en que va a programar el

modelo. Algunas de las ventajas de programar el modelo de simulación en un lenguaje de simulación en vez de hacerlo en un lenguaje general como FORTRAN, PASCAL, o C, son las siguientes:

1. Los lenguajes de simulación proporcionan automáticamente muchas, si no todas, 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.

2. 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.

3. Los modelos de simulación son mucho más fácilmente modificables cuando están escritos en un lenguaje de simulación, y por consiguiente se pueden ejecutar con mayor facilidad y flexibilidad los cambios requeridos por los experimentos de simulación.

4. Muchos de los lenguajes de simulación proporcionan una asignación dinámica de memoria durante la ejecución, cosa que no ocurre con todos los lenguajes de propósito general.

5. Facilitan una mejor detección de los errores, especialmente los inherentes a la lógica del proceso de simulación.

Los lenguajes de simulación para la simulación de sistemas discretos se eligen en base a lo atractivo de sus características, aunque hay una de ellas que resulta determinante e impone la naturaleza del lenguaje, es la estrategia, enfoque o visión del mundo inherente al lenguaje, utilizada para la selección del «suceso siguiente» y la gestión del tiempo. Kiviat [41], en un trabajo seminal, clasificó los procedimientos de control de tiempos de los lenguajes de simulación de sucesos discretos, según la estrategia seguida en la selección de sucesos, en:

1. Programación de Sucesos (Event Scheduling). 

2. Exploración de Actividades (Activity Scanning). 

3. Interacción de Procesos (Process Interaction).

La Tabla 11 muestra estrategias que conducen a una  clasificación de los lenguajes de simulación [40,41].

El hecho de que algunos lenguajes, SIMSCRIPT II.5, SLAM, SLAM II y SIMAN aparezcan tanto como lenguajes según una estrategia de programación de sucesos (event scheduling), como de interacción de procesos (process interaction), responde a que su estructura y naturaleza permiten al usuario emplear ambas estrategias, lo que refleja la tendencia creciente a la incorporación de múltiples visiones del mundo en la estructura de un solo lenguaje.

Con cualquiera de estas estrategias, cuando se selecciona el «suceso siguiente» para que sea procesado, se ejecuta la correspondiente «rutina de modelización» (bloque de código), para modelizar los cambios apropiados en el estado del modelo. Los conceptos de suceso condicional, o incondicional, son básicos para las estrategias. Un suceso incondicional es elegible para ser ejecutado cuando se llega al instante de tiempo para el que ha sido programado: depende totalmente del tiempo. Un suceso condicional puede depender de condiciones adicionales distintas del tiempo. Las condiciones se refieren usualmente a valores descriptores del estado de las componentes del sistema, por ejemplo, la desocupación, o el fin de la ocupación de un dispositivo del sistema modelizado. Una característica común a los tres planteamientos es que los programas a que dan lugar tienen una estructura jerárquica de tres niveles [40]:

• Nivel ejecutivo, o del programa de control. 

• Nivel de operaciones (secuencia de sentencias que constituyen el programa de computador que constituyen el modelo propiamente dicho). 

• Nivel de rutinas de detalle, que ejecutan las acciones implicadas por cada una de las operaciones del modelo.

El usuario de un lenguaje de simulación basado en uno de estos planteamientos no necesita conocer con detalle como está programado el ejecutivo, sino como funciona, es decir, lo que hemos llamado visión del mundo del lenguaje correspondiente. El ejecutivo es el que se encarga de identificar cuando tiene que ocurrir el siguiente suceso y que se ejecuten correctamente las operaciones por él implicadas en los momentos adecuados.

La estrategia de programación de sucesos (event scheduling, ES) implica una secuencia de sucesos incondicionales a lo largo del tiempo. Por lo tanto, la visión del mundo de un lenguaje, o modelo expresado en tal lenguaje, que incorpore la estrategia ES consiste en considerar la operación del sistema como una secuencia temporal, ordenada, de sucesos incondicionales, que se implanta de la manera siguiente:

El procedimiento ES de control del tiempo selecciona de la lista de sucesos aquel cuyo tiempo de ocurrencia es el más próximo, resolviendo los empates por las prioridades asignadas o por defecto, actualiza el tiempo del reloj de simulación, igualando su valor al del instante en que ocurre el suceso, y llama a la rutina correspondiente al tratamiento del suceso .

Cualquier verificación de una condición diferente de la del tiempo del reloj debe realizarse dentro de las rutinas de tratamiento de los diferentes sucesos. Los sucesos se eligen y progresan sucesivamente hasta el instante de terminación. En el caso del modelo de colas simple que hemos utilizado en el Capítulo 1 los sucesos primarios que cambian el estado del sistema, en una modelización por programación de sucesos (event scheduling), son el suceso de llegada al sistema de un nuevo cliente, y el de finalización de un servicio, según la descripción que hemos dado en el diagrama de simulación del sistema de colas ilustrado en la Figura 12, descripción cuya lógica, según la metodología de programación de sucesos (event scheduling), se traduce en los diagramas de la Figura 20. La Figura 21, Emshoff [42], ilustra gráficamente el esquema de la rutina ejecutiva para la estrategia de programación de sucesos (event scheduling).

La estrategia de exploración de actividades (activity scanning, AS) elige el suceso siguiente basándose en ambos, el tiempo programado para la ocurrencia del suceso y la verificación de las condiciones. El concepto básico es la actividad, que conceptualmente es una transición de estado del sistema que requiere un período de tiempo. Una actividad se representa habitualmente mediante dos sucesos distintos que marcan respectivamente el principio y el final de la misma.

La visión del mundo que corresponde a un lenguaje, o modelo de simulación programado en un lenguaje, basado en la estrategia.

PUNTOS PARA DESARROLLAR UN PROYECTO DE SIMULACIÓN DE EVENTOS DISCRETOS

Cada una de las estrategias de simulación que hemos propuesto es susceptible de una representación algorítmica genérica, así como las rutinas para el tratamiento de sucesos de la estrategia ES, las rutinas de condición y las de actividades para la estrategia AS, y los segmentos de condición y acción para la estrategia PI.

En la representación algorítmica que vamos a dar se supone que los algoritmos utilizan algún conjunto de procedimientos de gestión de estructuras de datos (por ejemplo listas), para ayudar a la introducción y recuperación de las representaciones de la información sobre los sucesos.

En el planteamiento que vamos a proponer, y para mantener el carácter genérico de la representación, evitaremos suposiciones sobre las estructuras de datos que se pueden utilizar en las implantaciones específicas de las estrategias. La descripción algorítmica que vamos a hacer será, pues, precisa solo en la descripción de los aspectos esenciales de la gestión del tiempo, incluyendo las implicaciones correspondientes a las rutinas de modelización, aunque excluyendo los detalles que no dependen de la estrategia.

El punto de partida para esta representación algorítmica es un análisis de las características que dependen de la estrategia adoptada y de las que dependen del problema específico que se simula. De acuerdo con Kiviat. los lenguajes de simulación ofrecen, en general, las siguientes capacidades y características:

1. Modelización del estado del sistema. 

2. Modelización de la dinámica del sistema. 

3. Herramientas para el muestreo estadístico. 

4. Especificaciones sobre el proceso de recogida de datos.

5. Recogida de datos generados por la simulación. 

6. Análisis de los datos recogidos. 

7. Presentación de resultados. 

8. Monitorización de la simulación y herramientas de depuración del modelo.

9. Procedimientos de inicialización de la simulación. 

10. Herramientas auxiliares complementarias.

Las características 1, 2 y 9 son intrínsecas, dependen de la estrategia elegida y por lo tanto son las que pueden ser objeto de una descripción algorítmica genérica de la estrategia, mientras que las restantes son relativamente independientes de la estrategia. A partir de la identificación de los elementos intrínsecos podemos dar las siguientes descripciones de las estrategia en pseudocódigo.

CONCLUSIÓN

Para finalizasr cada una de las estrategias de simulación que hemos propuesto es susceptible de una representación algorítmica genérica, así como las rutinas para el tratamiento de sucesos de la estrategia ES, manejamos en este capitulo una amplia gama de información en cuanto al uso de los sistemas discretos. Por ejemplo habla en cuestión del análisis de los datos recogidos, la presentación de resultados el monitoreo de la simulación y herramientas de depuración del modelo.


ELABORADO POR:

JONATHAN JESÚS SÁNCHEZ TOLEDO

JUAN CARLOS VELAZQUEZ HERRERA

Bibliografía

 Barcelo,J., (2006)Simulación de sistemas discretos, Madrid,España: Isdefe

Cevallos.,J, (2013)Simulación por eventos discretos. SlideShare.recuperado de http://es.slideshare.net/Jonathan-Cevallos/simulación-discreta