03 Simulacion de Sistemas Simulacion Montecarlo

  • Published on
    11-Nov-2015

  • View
    16

  • Download
    6

Embed Size (px)

Transcript

<ul><li><p>Red de aprendizaje Modelado </p><p>y </p><p>Simulacin </p><p>Proyectos de </p><p>Simulacin de </p><p>Sistemas </p><p>Generacin </p><p>Valores de </p><p>Variables </p><p>Aleatorias </p><p>Simulacin </p><p>por </p><p>Eventos </p><p>Sistema de Colas con </p><p>Servidores en Serie </p><p>Sistema de Colas con </p><p>Un servidor </p><p>Sistemas de Colas con </p><p>Servidores en Paralelo </p><p>Sistemas de </p><p>Inventarios </p><p>Revisin Peridica </p><p>Sistemas de </p><p>Inventarios Punto </p><p>de Repedido </p><p>Sistemas </p><p>Combinado de: </p><p>Cadena de </p><p>Almacenes </p><p>Sistemas </p><p>Combinado de: </p><p>Sistema de Colas e </p><p>Inventario </p><p>Modelacin </p><p>Montecarlo </p></li><li><p>Simulacin Montecarlo </p><p>En esta parte del curso aprenderemos a disear </p><p>simuladores Montecarlo. </p><p>Recuerda: </p><p>Un diagrama de flujo es la representacin grfica </p><p>de las actividades de un proceso. </p></li><li><p>1. Proceso (subproceso) , tarea o actividad </p><p>Rectngulo: </p><p> Se usa para denotar </p><p>cualquier clase de </p><p>actividad o proceso. </p><p> Normalmente se debe </p><p>incluir en el rectngulo </p><p>una breve descripcin </p><p>de la actividad. </p><p>Smbolos a utilizar en flujogramas </p><p>Actividad </p></li><li><p>2. Punto de decisin Rombo: </p><p> Se usa para tomar una </p><p>decisin. La siguiente serie </p><p>de actividades variarn en </p><p>base a esta decisin. </p><p> Por lo general, las salidas </p><p>del rombo se marcarn </p><p>con las correspondientes </p><p>opciones Si - No. </p><p>Smbolos a utilizar en los flujogramas </p><p>Decisin </p><p>SI </p><p>NO </p></li><li><p>3. Elemento de inicio o fin </p><p>Circulo alargado: </p><p>Se usa para indicar el </p><p>inicio y fin del proceso. </p><p>Normalmente dentro del </p><p>smbolo aparece la palabra </p><p>Inicio o Fin </p><p>Smbolos a utilizar en flujogramas </p><p>INICIO </p></li><li><p>4. Conector de flujo Circulo pequeo: </p><p>Se usa para indicar que la salida </p><p>de esta parte del diagrama de </p><p>flujo servir como entrada para </p><p>otro diagrama de flujo. </p><p> Con frecuencia este smbolo se </p><p>utiliza cuando no existe suficiente </p><p>espacio para dibujar la totalidad </p><p>del diagrama de flujo en un </p><p>papel. </p><p> Cada salida diferente debe </p><p>designarse con una letra </p><p>diferente. </p><p>Smbolos a utilizar en flujogramas </p><p>A </p></li><li><p>5. Entrada de datos. </p><p>Rectngulo con la parte </p><p>superior izquierda recortada: </p><p> Se usa para indicar la entrada </p><p>de datos por medio del teclado </p><p>o un archivo con los datos </p><p>correspondientes a la actividad </p><p>a desarrollar por el simulador. </p><p>Por ejemplo, numero de </p><p>replicaciones que efectuar el </p><p>simulador. </p><p>Smbolos a utilizar en flujogramas </p></li><li><p>6. Documento, formulario, reporte </p><p>Rectngulo con la parte </p><p>inferior en forma de onda: </p><p> Se usa para indicar que la </p><p>salida de una actividad o </p><p>resultado por el programa </p><p>Por ejemplo, informes escritos </p><p>o presentacin de resultados </p><p>impresos o una salida por </p><p>pantalla). </p><p>Smbolos a utilizar en flujogramas </p><p>Documento </p></li><li><p>6. Seleccin Simple (IF - THEN - ELSE) </p><p>Es una instruccin que se </p><p>utiliza para la bifurcacin </p><p>condicional. </p><p>Formato: </p><p>IF Condicin THEN </p><p> Begin </p><p> Instrucciones - 1; </p><p> End </p><p>ELSE </p><p> Begin </p><p> Instrucciones - 2; </p><p> End; </p><p>Flujogramas bsicos </p><p>Decisin Instrucciones 1 </p><p>Instrucciones 2 </p><p>Si </p><p>No </p></li><li><p>7. Ciclo con Entrada controlada (WHILE DO) </p><p>Se utiliza para repetir un </p><p>grupo de instrucciones </p><p>mientras se cumpla una </p><p>condicin. </p><p>Formato: </p><p>WHILE Condicin DO </p><p> Begin </p><p> ...................... </p><p> Instrucciones; </p><p> End; </p><p>Flujogramas bsicos </p><p>Decisin </p><p>Instrucciones </p><p>Si No </p></li><li><p>8. Ciclo con Salida Controlada (REPEAT UNTIL) </p><p>Se utiliza para repetir un </p><p>grupo de instrucciones </p><p>hasta que se cumpla una </p><p>condicin. </p><p>Formato: </p><p>REPEAT </p><p> .................... </p><p> Instrucciones; </p><p>UNTIL Condicin; </p><p>Flujogramas bsicos </p><p>Decisin Si </p><p>No </p><p>Instrucciones </p></li><li><p>9. Ciclo con Contador (FOR - TO DO) Un ciclo FOR - TO - DO se utiliza para ejecutar un </p><p>bloque de instrucciones un nmero determinado de </p><p>veces. </p><p>Para contar el nmero de veces que se est </p><p>ejecutando el ciclo, existe una variable denominada </p><p>variable de control, que debe ser de tipo ordinal </p><p>(Integer, Char Boolean) y se incrementa o </p><p>decrementa automticamente en cada ejecucin del </p><p>ciclo. </p><p>Contador Creciente: </p><p>FOR i:= Valor - Inic TO Valor - Fin DO </p><p> Begin </p><p> ..................... </p><p> Instrucciones; </p><p> End; </p><p>Contador Decreciente: </p><p>FOR i:= Valor - In DOWNTO Valor fin DO Begin </p><p> ................... </p><p> Instrucciones; </p><p> End; ). </p><p>Flujogramas bsicos </p><p>I= a, b </p><p>Instrucciones </p><p>10 </p><p>10 </p></li><li><p>Se utiliza para implementar un procesamiento con varias opciones de seleccin. </p><p>Formato: </p><p>CASE Expresin OF </p><p>Opcin - 1: Instruc - 1; </p><p>Opcin - 2 : Instruc - 2; </p><p>.................. </p><p>.................. </p><p>ELSE </p><p>Instruccin; </p><p>END; </p><p>Flujogramas bsicos </p><p>10. Diagrama de flujo de CASE OF: </p><p>Escoger </p><p> la opcin I </p><p>Opcin I </p><p>Opcin 1 Opcin Opcin 2 </p><p>I=1 I= </p><p>I=2 </p></li><li><p>Como generar los valores de un dado? </p><p>El numero de caras que tiene un dado comn </p><p>es 6 y cada una tiene la misma probabilidad de </p><p>salir en un lanzamiento. </p><p>Se le pide hacer un diagrama de flujo que le </p><p>permita simular el lanzamiento de un dado. </p></li><li><p>Como jugar a Craps? </p><p>La serie de tiros para establecer y repetir el Punto se denomina ronda. </p><p>Cada ronda comienza con lo que se llama Tiro de Salida. </p><p>Con este tiro se procura establecer el Punto. </p><p>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. </p><p>Los totales de 2 (los ojos de la serpiente o snake eyes) y 12(vagones o box cars) son considerados Craps. </p><p>Mientras un total de 7 u 11 se le llama Natural. </p></li><li><p>Como jugar a Craps? </p><p>Si durante el Tiro de Salida se obtiene un resultado de Craps o Natural la ronda automticamente llega a su conclusin. </p><p>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. </p><p>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. </p><p>Desarrollar el diagrama de flujo del juego. </p></li><li><p>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. </p><p>Para desarrollar este aplicativo le adjunta los siguientes datos de comportamiento: </p><p>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: </p><p>Tiempo Empleado # de observaciones Probabilidad </p><p> (Minutos) </p><p> 15 08 8/30 </p><p> 20 11 11/30 </p><p> 25 07 7/30 </p><p> 30 04 4/30 </p><p>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. </p><p>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 </p><p>Su hora de entrada es a las 8:00 AM. </p><p>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. </p></li><li><p>Como ayudar a Miguel? </p><p>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: </p><p>Tiempo de levantarse 6:15 a 6:30. (TLEV) TLEV = UNIF(15,30) </p><p>Tiempo de afeitarse baarse y cambiarse: (TBAC) </p><p>Tiempo Empleado # de observaciones Probabilidad </p><p> (Minutos) </p><p> 15 08 8/30 </p><p> 20 11 11/30 </p><p> 25 07 7/30 </p><p> 30 04 4/30 Tiempo de levantarse de la persona encargada. (TLEVP) TLEVP = 20 + Tardanza. (Tardanza = NORM(5,1.5) </p><p>Tiempo de preparacin del desayuno (TPRDES) TPRDES = UNIF (10, 15) </p><p>Tiempo de Tomar el desayuno (TTODES) TTODES = UNIF(12, 17) </p><p>Tiempo empleado para ir ala oficina (TOFIC) TOFIC = EXPO(50) </p></li><li><p>Como ayudar a Miguel? </p><p>Primero trabajaremos con las variables uniformes que son: </p><p>TELEV = UNIF(15,30) </p><p>TPRDES = UNIF (10, 15) </p><p>TTODES = UNIF(12, 17) </p><p>Entonces tendremos lo siguiente: </p><p>X~UNIF (a, b) </p><p>a-b</p><p>1 </p><p>12</p><p>a)-(b </p><p>2</p><p>ba</p><p>Moda anza VariMedia </p><p>2</p><p>a b </p><p>a-b</p><p>1 </p><p>UNIF (a, b) </p><p>r = random </p><p>La forma de generar esta variable se </p><p>realiza mediante con la siguiente </p><p>expresin: </p><p> x = a + (b a ).r , r [0, 1 ] </p><p>UNIF = a + (b a ).r </p><p>Return </p><p>Diagrama de Flujo </p></li><li><p>Como ayudar a Miguel? </p><p>TBAC # de obs Prob Pacum Intervalos </p><p> (min.) </p><p> 15 08 8/30 8/30 [ 0 , 8/30[ </p><p> 20 11 11/30 19/30 [ 8/30, 19/30[ </p><p> 25 07 7/30 26/30 [19/30, 26/30[ </p><p> 30 04 4/30 1 [26/30, 1 ] </p><p>La forma de generar esta VA es generar r [0, 1 ] y luego buscar en que intervalo cayo el valor de r. </p><p>Esto nos conduce al siguiente diagrama de flujo. </p><p>Ahora trabajaremos con la variable discreta: TBAC </p><p>r&lt; 8/30 </p><p>r&lt; 19/30 </p><p>r&lt; 26/30 </p><p>r = random </p><p>DISC </p><p>DISC = 25 </p><p>DISC = 15 </p><p>DISC = 20 </p><p>DISC = 30 </p><p>Return </p></li><li><p>Como ayudar a Miguel? </p><p>Para generar este tipo de variable recurriremos al Teorema de Limite Central (TLC): </p><p> es una VA que tiene los siguientes parmetros: </p><p>1</p><p>n</p><p>i</p><p>ir</p><p>Trabajaremos con la variable: TLEVP que esta por una parte constante la VA que es la tardanza entonces: TELEVP = 20 + NORM(5, 1.5) </p><p>)n ,NORM(n :sabe se adems Pero 2</p><p>1</p><p>n</p><p>i</p><p>ir</p><p>2</p><p>11</p><p>)( ,)( nrVarnrEn</p><p>i</p><p>i</p><p>n</p><p>i</p><p>i </p><p>Luego si ri ~ UNIF(0, 1) entonces: </p><p>12)( ,</p><p>2)(</p><p>11</p><p>nrVar</p><p>nrE</p><p>n</p><p>i</p><p>i</p><p>n</p><p>i</p><p>i </p><p>f(x) </p><p>x </p></li><li><p>Como ayudar a Miguel? </p><p>Despejando x tendremos: </p><p> zx </p><p>Para normalizar una VA normal se utiliza la siguiente expresin: </p><p>Donde Z~NORM(0, 1), luego para generar </p><p>X debemos primero generar Z para ello de </p><p>la expresion siguiente: </p><p>tomaremos n=12 y restaremos 6 entonces: </p><p>-x z </p><p>12)( ,</p><p>2)(</p><p>11</p><p>nrVar</p><p>nrE</p><p>n</p><p>i</p><p>i</p><p>n</p><p>i</p><p>i </p><p>1)6( ,0)6(12</p><p>1</p><p>12</p><p>1</p><p> i</p><p>i</p><p>i</p><p>i rVarrE</p><p>Luego: )1,0(612</p><p>1</p><p>NORMri</p><p>i </p><p>Z = 0 </p><p>NORM(, ) </p><p>z = z - 6 </p><p>z = z +r </p><p>r = random </p><p>NORM= + z. </p><p>Return </p><p>i = 1, 12 </p><p>10 </p><p>10 </p></li><li><p>Como ayudar a Miguel? </p><p> 1 ,0 ),ln(1 rdonderx</p><p> 1</p><p> 1</p><p>anza VariMedia </p><p>2 </p><p>Para generar una variable aleatoria que se distribuye exponencialmente solo se tiene usar la siguiente expresin: </p><p>Luego: </p><p>EXPO () </p><p>r = random </p><p>EXPO = - Ln (r) </p><p>Return </p><p>Diagrama de Flujo </p><p>)ln(rx </p><p>TOFIC ~ EXPO(80) </p></li><li><p>Como ayudar a Miguel? </p><p>Una vez que terminamos con las VA involucradas en el problema podremos elaborar el diagrama de flujo del caso. </p><p>Desayuno </p><p>DT = 0 </p><p>TT = 0 </p><p>Generar TLEV, TBAC y TLEVP </p><p>FIN </p><p>Diagrama de Flujo </p><p>N </p><p>i=1, N </p><p>30 </p><p>30 </p><p>TPO = TLEV + TBAC </p><p> TLEVP = TPO </p><p>Generar TPRDES </p><p>TELEVP &gt; TPO </p><p>TAUX = TLEVP + TPRDES </p><p>TPO = TAUX </p><p>TPO &lt; TAUX </p><p>Generar TTODES, TOFIC </p><p>TPO = TPO + TTODES+TOFIC </p><p>TPO 120 </p><p> TT = TT +TPO - 120 </p><p> DT = DT +1 </p><p>TARDPROM = TT/DT </p><p>PROBTARD = DT/N </p><p>PROBTARD </p><p>TARDPROM </p><p>SI </p><p>NO </p><p>NO </p><p>SI </p><p>SI </p><p>NO </p></li><li><p>Sistema de colas con un servidor </p><p>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. </p><p>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. </p><p>Luego de completar la atencin, los clientes salen del rea en estudio. </p><p>Para realizar un estudio de simulacin del sistema se desea saber: </p><p>a.Cul es nmero clientes atendidos? </p><p>b.Cul es la cola mxima que se forma?. </p><p>c. Cunto tiempo pasaron en cola y cuanto en el sistema?. </p><p>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? </p></li><li><p>Representacin grfica del Sistema</p><p>Representacin del Sistema</p><p>Entidades Atributos Actividades</p><p>Cliente Tiempo de arribo Llegar al sistema.(Elemento temporal) % de falta de requisito Abandono por falta requisito.</p><p> Formar Cola. Recibir servicio. Salir del sistema.</p><p>Empleado Tiempo de servicio Atender clientes.(Elemento permanente) Espera de clientes.</p><p>TS (Tiempo de servicio)</p><p>Servidor Salida</p><p>Abandono por falta de requisito</p><p>COLA</p><p>Llegada TLL</p><p>Sistema de colas con un servidor </p></li><li><p>Diseo de un simulador de un sistema de cola simple </p><p>Instantes en que cambia el sistema: </p><p>Llegada de un cliente TLL </p><p>Fin de Servicio TFS </p><p>Para un cliente siempre se cumple TLL &lt; TFS </p><p>Haciendo un pequea corrida en el tiempo T: </p><p>0 t1 t2 t4 t3 t6 t5 </p><p>LL FS LL FS LL LL </p><p>T </p></li><li><p>Sistema de colas de un servidor </p><p>Tabla base </p><p>TLL TFS RM Evento </p><p> t1 &lt; t3 t1 Arribo </p><p> t2 &lt; t3 t2 Arribo </p><p> t4 &gt; t3 t3 Fin de Servicio </p><p> t4 &lt; t5 t4 Arribo </p><p> t6 &gt; t5 t5 Fin de Servicio </p><p>0 t1 t2 t4 t3 t6 t5 </p><p>LL FS LL FS LL LL </p><p>T </p></li><li><p>Sistema de colas de un servidor </p><p>Diagrama de flujo base </p><p>Tabla base </p><p>TLL TFS RM Evento </p><p> t1 &lt; t3 t1 Arribo </p><p> t2 &lt; t3 t2 Arribo </p><p> t4 &gt; t3 t3 Fin de Servicio </p><p> t4 &lt; t5 t4 Arribo </p><p> t6 &gt; t5 t5 Fin de Servicio </p><p>TLL &lt; TFS </p><p>ARRIBO FIN DE SERVICIO </p><p>RM &lt; TMS </p><p>SI NO </p><p>SI </p><p>NO </p></li><li><p>Sistema de colas de un servidor Diagrama de flujo con entrada de valores de N y de TMS </p><p>TLL &lt; TFS </p><p>ARRIBO FIN DE SERVICIO </p><p>RM &lt; TMS </p><p>SI NO </p><p>SI </p><p>NO </p><p>N, TMS </p><p>I=1, N 10 </p><p>10 </p><p>N= numero de simulaciones </p><p>TMS= periodo de simulacin </p><p>TLL= tiempo de llegada </p><p>TFS= tiempo de fin de servicios </p><p>RM= reloj maestro </p><p>I= contador del FOR TO DO </p></li><li><p>Sistema de colas de un servidor Calculo de Atendidos Promedio y Abandonos promedio </p><p>Programa Principal </p><p>N= numero de simulaciones </p><p>TMS= periodo de simulacin </p><p>TLL= tiempo de llegada </p><p>TFS= tiempo de fin de servicios </p><p>RM= reloj maestro </p><p>I= contador del FOR TO DO </p><p>TLL &lt; TFS </p><p>ARRIBO FIN DE SERVICIO </p><p>RM &lt; TMS </p><p>SI NO </p><p>SI </p><p>NO </p><p>N, TMS </p><p>I=1, N 10 </p><p>10 </p><p>TLL= 0, COLA= 0 </p><p>TFS= 9999, ES= 0 </p><p>RM=0 </p><p>ABANPROM= ABANDONO/N </p><p>ATENPROM=ATENDIDOS/N </p><p>REPORTE </p><p>INICIO </p><p>FIN </p><p>TLL= 0, COLA= 0, TFS= 9999, ES= 0, RM=0 </p><p>ABANDONO=0, ATENDIDOS=0 </p></li><li><p>Evento Arribo </p><p>ARRIBO</p><p>RM = TLL</p><p>ABANDONA</p><p>ES=0</p><p>ES = 1</p><p>Generar TELL</p><p>TFS = RM + TS</p><p>COLA = COLA +1</p><p>TLL = RM + TELL</p><p>RETURN</p><p>NO</p><p>SI</p><p>Generar TS</p><p>Si</p><p>No</p><p>ABANDONO = ABANDONO + 1</p></li><li><p>Evento Fin de Servicio </p><p>FIN DE SERVICIO</p><p>RM = TFS</p><p>ATENDIDOS = ATENDIDOS + 1</p><p>COLA = 0</p><p>COLA = COLA -1</p><p>Generar TS</p><p>TFS = RM + TS</p><p>ES = 0</p><p>TFS = 9999</p><p>RETURN</p><p>NoSi</p></li></ul>