simulacion c sharp - a

PONTIFICIA UNIVERSIDAD CATLICA DE CHILE ESCUELA DE INGENIERA DEPARTAMENTO DE CIENCIA DE LA COMPUTACIN Curso: IIC 1102 INTRODUCCIN A LA PROG. ORIENTADA A OBJETO Profesor: Rodrigo Sandoval U.

Simulacin Computacional con C#

1 2

INTRODUCCIN ............................................................................................................................................... 1 MODELO DE SIMULACIN............................................................................................................................ 2 2.1 PARMETROS DE LA SIMULACIN .................................................................................................................. 2 2.2 DATOS O INPUT DE LA SIMULACIN ................................................................................................................ 2 2.2.1 Generacin de Nmeros Aleatorios ....................................................................................................... 2 2.2.2 Carga de Datos Reales desde Archivos.................................................................................................. 4 2.3 EJECUCIN DE LA SIMULACIN....................................................................................................................... 5 2.3.1 El Manejo del Tiempo ............................................................................................................................ 5 2.3.2 Colas en C# ............................................................................................................................................ 7

3

EJEMPLOS .......................................................................................................................................................... 9 3.1 SIMULACIN DE CADENA DE CORREO ............................................................................................................ 9 3.2 LLEGADA DE CLIENTES A CAJA EN EL BANCO .............................................................................................. 10 3.2.1 Solucin 1.0.......................................................................................................................................... 11 3.2.2 Solucin 2.0.......................................................................................................................................... 13 3.2.3 Solucin 3.0.......................................................................................................................................... 15 3.3 SIMULACIN DE LAS COLAS EN UN SUPERMERCADO .................................................................................... 17 3.3.1 Definicin del Problema ...................................................................................................................... 17 3.3.2 Caractersticas del Modelo .................................................................................................................. 17 3.3.3 Mediciones Requeridas ........................................................................................................................ 17 3.3.4 Solucin................................................................................................................................................ 18 3.4 SIMULACIN DE UNA PLAZA DE PEAJE.......................................................................................................... 24 3.4.1 Definicin del Problema ...................................................................................................................... 24 3.4.2 Solucin................................................................................................................................................ 26

Material preparado por Rodrigo Sandoval U en Agosto 2005, ([email protected]) basado en los apuntes de clase del curso IIC1102, ao 2003, de M. Nussbaum, Marcos Seplveda, et.al.


Rodrigo Sandoval U.

1 IntroduccinLa simulacin mediante programas de computador permite el estudio detallado de sistemas complejos, sobre los que resulta costoso, difcil o peligroso llevar a cabo estudios reales. La simulacin se basa en analizar el comportamiento de un modelo derivado de una situacin real, de la forma ms equivalente posible, para obtener resultados de la medicin del comportamiento de este modelo y as sacar conclusiones. En otras palabras, un modelo de simulacin intenta recrear de la mejor manera posible las caractersticas del sistema representado y se comporta de manera similar a como lo hara en la realidad. La idea es que la ejecucin de la simulacin produzca resultados en la forma de valores estadsticos, o simplemente permita monitorear el desempeo del sistema durante su funcionamiento.

Modelo de Simulacin Los modelos de simulacin distinguen en general cuatro elementos esenciales: A. Parmetros de Funcionamiento. Estos datos, muchas veces valores numricos fijos para una simulacin, determinan ciertas condiciones de la ejecucin, que tambin se define como el escenario a analizar. Siempre ser posible cambiar los valores de estos parmetros y como consecuencia, observar el comportamiento del modelo con esas nuevas condiciones y eventualmente sacar conclusiones al comparar los resultados de un escenario con los de otro. B. Datos o Input de la Simulacin. Para representar situaciones del modelo real, se cuenta con datos de diverso tipo que alimentarn la simulacin completando el escenario a implementar con este modelo. Estos datos generalmente son de tres tipos: datos fijos, conceptualizados como promedios constantes; datos aleatorios que le dan un factor de variabilidad y ofrecen un escenario con elementos impredecibles al modelo; y datos reales, que fueron medidos en una situacin equivalente en la vida real, y que le aportarn el factor realista directo al modelo. C. Ejecucin de la Simulacin. Consiste en realizar la simulacin propiamente tal, por medio de la ejecucin iterativa de pasos que emulan el comportamiento de la situacin modelada. Entre los elementos que se consideran en esta ejecucin, posiblemente el ms importante es el manejo del tiempo, en el cual el modelo es capaz de identificar los eventos que ocurren en un instante relevante de tiempo, y ejecutarlos como parte de la simulacin. D. Resultados de la Simulacin. Datos medidos durante la ejecucin que permiten obtener una visin del desempeo del modelo y por ende, sacar conclusiones de la situacin simulada. Tomando un ejemplo clsico, la simulacin de autos en una interseccin de calles, un parmetro de entrada sera la duracin de la luz roja y de la verde; datos o input sera la llegada de vehculos en momentos de la simulacin; la ejecucin considerara el tiempo que toma que los autos se vayan acumulando en roja y luego salgan en verde; y resultados posibles se consideran el tiempo de espera, o la probabilidad de que un auto no alcance a cruzar en verde.

IIC 1102

Pgina: 1


Rodrigo Sandoval U.

2 Modelo de Simulacin2.1 Parmetros de la SimulacinEn estos modelos es de mucha utilidad el uso de parmetros, que permitan de manera simple cambiar las caractersticas del ambiente o del sistema mismo, de modo que sea posible observar los cambios que se producen en su operacin. Definen un escenario especfico en el cual se realizar la simulacin. Normalmente son valores numricos, que se mantienen constantes durante la simulacin completa. El hecho de mantener estos valores paramtricos, permite a quien analiza la simulacin variarlos y poder probar distintos escenarios de simulacin. Por ejemplo, parmetros de una simulacin podran ser la duracin de un semforo en una interseccin, la capacidad de carga de un camin o de otro medio de transporte, la capacidad de atencin de una caja de banco o de tienda, valores monetarios o tarifas.

2.2

Datos o Input de la Simulacin

Los datos que alimentan el modelo de simulacin pueden ser fijos que usualmente son ms bien considerados como parmetros de la simulacin o bien generarse en forma aleatoria de acuerdo a ciertas condiciones de distribucin de estos valores casi siempre numricos, y finalmente es posible contar con mediciones reales tomadas en terreno, las cuales al quedar almacenadas en archivos, por ejemplo, permiten su recuperacin durante el proceso de la simulacin, para constituir una fuente realista de la situacin modelada.

2.2.1 Generacin de Nmeros AleatoriosLa generacin de valores aleatorios le da un grado de incerteza al comportamiento del modelo. Si bien es posible determinar que ciertos valores que alimentan el modelo se comportan de acuerdo a diferentes tipos de distribuciones estadsticas, en el gran porcentaje de los casos, el uso de la distribucin uniforme en la cual todos los nmeros de un rango tienen la misma posibilidad de salir es suficiente para soportar diferentes modelos. Para producir estos datos es necesario contar con herramientas que generen nmeros aleatorios en ciertos intervalos y con cierta distribucin especificada en el modelo. En C# la generacin de nmeros aleatorios est resuelta por una clase llamada Random, cuyo principal propsito es generar nmeros aleatorios dentro de un rango especificado. Un programa que utilice Random para la generacin de nmeros, depende de dos principales declaraciones: el constructor y el mtodo Next(). 2.2.1.1 Constructor de Random

Existen diferentes versiones del constructor, las cuales por sobrecarga reciben distintos parmetros. El constructor simple no recibe parmetros: Random num = new Random(); El constructor con semilla permite su inicializacin estableciendo una semilla de aleatoriedad, de manera que no se repitan las secuencias de nmeros entregados. Para darle un grado de variabilidad a esta generacin de nmeros, se recomienda el uso de una semilla que en cada llamado al programa tenga un valor diferente. El usar un nmero fijo o constante, es equivalente funcionalmente al constructor sin parmetros: la secuencia de nmeros aleatorios ser idntica en cada ejecucin desde cero del programa. Para la semilla, hay dos alternativas: utilizar un nmero entregado por el usuario, que se espere vaya variando en cada ejecucin, o utilizar un valor del reloj del computador, el cual se obtiene del uso de DateTime.Now objeto que se detalla ms adelante en este documento. Este objeto tiene un campo llamado Millisecond, el cual indica la parte de milisegundos (de 0 a 999) de la hora actual. Random num = new Random(DateTime.Now.Millisecond);

IIC 1102

Pgina: 2


Rodrigo Sandoval U.

2.2.1.2

Generacin de nmeros con Next

El mtodo Next() tiene varias versiones, las cuales por sobrecarga de mtodos ofrecen comportamientos levemente diferentes y tiles en situaciones distintas. Las dos versiones principales son las siguientes, y ambas incluyen un valor que representa el lmite superior no incluido del rango de valores posibles: int numero1 = num.Next(11); // numero1 tendr un valor entre 0 y 10

int numero2 = num.Next(5,11); // numero2 tendr un valor entre 5 y 10 2.2.1.3 Ejemplo Bsico de Random

A continuacin, un ejemplo de un programa que genera 10 nmeros aleatorios entre 1 y 10.using System; class MainApp { static void Main() { Random rn = new Random(DateTime.Now.Millisecond); for(int n=0; n 1 minuto TimeSpan tick = new TimeSpan(0, 1, 0); // 0 horas, 1 minuto, 0 segundos . . . while(reloj 0) { if(ProdsPrimerCliente(caja) < 3) cobrados = ProdsPrimerCliente(caja); else cobrados = 3; Cobrar(caja,cobrados); if(ProdsPrimerCliente(caja) == 0) SacarCaja(caja); } } } } class Estadistica { private int LargoTotal; private int LargoMax; public Estadistica() { LargoTotal = 0; LargoMax = 0; } num_clientes;

IIC 1102

Pgina: 21


Rodrigo Sandoval U.

public int LargoT { get { return LargoTotal; } set { LargoTotal = value; } } public int LargoM { get { return LargoMax; } set { LargoMax = value; } } }

class CMain { public static void Main() { DateTime dt = new DateTime(DateTime.Now.Year,DateTime.Now.Month,DateTime.Now.Day, 9,0,0,0); int NumClientes = 0, EsperaTotal = 0, EsperaMax = 0; int cajas = 0; Console.WriteLine("SIMULACION DE SUPERMERCADO"); Console.Write("Indique la cantidad de cajas atendiendo: "); cajas = int.Parse(Console.ReadLine()); Queue Clientes = new Queue(); Cajas Cajas = new Cajas(cajas,10); Estadistica [] estadistica = new Estadistica[cajas]; for(int i = 0; i < Estadistica.Length; i++) estadistica[i] = new Estadistica(); try { StreamReader sr = new StreamReader("clientes.txt"); Console.WriteLine("Leyendo datos de entrada"); NumClientes = int.Parse(sr.ReadLine()); string str; System.Random rn = new System.Random(System.DateTime.Now.Millisecond); for(int i = 0; (str = sr.ReadLine()) != null; i++) { string[] hh_mm = str.Split(' '); Cliente cr = new Cliente (int.Parse(hh_mm[0]), int.Parse(hh_mm[1])); cr.registro_compra = rn.Next(0,99); Clientes.Enqueue(cr); } sr.Close(); } catch(Exception e) { Console.WriteLine("No se abre archivo clientes.txt: {0}",e.Message); return; } while(Clientes.Count > 0 || Cajas.QuedanClientes()) { if(Clientes.Count == 0) break; CRegistro cli = (CRegistro)Clientes.Peek(); while(cli.HoraRegistro == dt) { int prodsCajas = Cajas.ProductosEnCaja(Cajas.MejorCaja()); int colaCaja = Cajas.ColaCaja(Cajas.MejorCaja()); EsperaTotal += prodsCajas; if(prodsCajas > EsperaMax) EsperaMax = prodsCajas; Estadistica[Cajas.MejorCaja()].LargoT += colaCaja; if(colaCaja > Estadistica[Cajas.MejorCaja()].LargoM) Estadistica[Cajas.MejorCaja()].LargoM = colaCaja; if(Clientes.Count == 0) break; cli = (CRegistro)Clientes.Dequeue(); Cajas.Insertar(cli.registro_compra); } Cajas.Atender();

IIC 1102

Pgina: 22


Rodrigo Sandoval U.

DateTime d = dt.AddMinutes(1); dt = d; } Console.WriteLine("\n\n\t\t-=Estadistica=-\n\n"); int valor = (EsperaTotal / 3) / NumClientes; int min = valor; int seg = ((valor-min)*60); Console.WriteLine("\tTiempo de espera Promedio (mm:ss) -> {0}:{1}",min,seg); valor = (EsperaMax / 3); min = (int)valor; seg = (int) ((valor-min)*60); Console.WriteLine("\tTiempo de Espera Maximo

(mm:ss) -> {0}:{1}",min,seg);

Console.WriteLine("\tLargo de la Cola en las Cajas (Promedio/Maximo):"); for(int i=0 ; i 29:0 Tiempo de Espera Maximo (mm:ss) -> 52:0 Largo de la Cola en las Cajas (Promedio/Maximo): Caja n0: 44 / 2 Con 2 cajas: -=Estadistica=-

Tiempo de espera Promedio (mm:ss) -> 29:0 Tiempo de Espera Maximo (mm:ss) -> 57:0 Largo de la Cola en las Cajas (Promedio/Maximo): Caja n0: 6 / 2 Caja n1: 50 / 3 Con 4 cajas: -=Estadistica=-

Tiempo de espera Promedio (mm:ss) -> 26:0 Tiempo de Espera Maximo (mm:ss) -> 46:0 Largo de la Cola en las Cajas (Promedio/Maximo): Caja n0: 12 / 4 Caja n1: 12 / 3 Caja n2: 12 / 4 Caja n3: 15 / 4 Modificaciones propuestas

IIC 1102

Pgina: 23


Rodrigo Sandoval U.

Como se puede ver en los ejemplos de ejecucin, la simulacin arroja algunos valores estadsticos que pueden ser de utilidad para el administrador del supermercado: tiempos de espera de los clientes y largos de cola en las cajas. Sin embargo, la experimentacin es an algo engorrosa, pues cada vez que se quieren ver los resultados para una determinada configuracin, es necesario ejecutar de nuevo el programa y registrar los resultados. Una posible modificacin al programa planteado es hacer que por s mismo busque la mejor configuracin, de acuerdo a parmetros dados por el usuario. Por ejemplo, Cuntas cajas son necesarias para que los clientes no deban esperar ms de 1 minuto?. Para lograr esto, el cuerpo de la simulacin se debe convertir en un mtodo o funcin que reciba como argumento el nmero de cajas y retorne el tiempo de espera promedio (actualmente se enva por la consola). El algoritmo principal (Main) har llamados sucesivos a esta nueva funcin (mediante un ciclo), pasndole como argumento distintos valores para el nmero de cajas en forma incremental (primero 2, luego 3, etc.), hasta que se llegue al tiempo de espera propuesto por el usuario (1 minuto). Otra caracterstica que podra resultar muy til es permitir la simulacin por perodos distintos al da completo. Por ejemplo, es bien sabido que las horas de mayor saturacin en el supermercado se dan al final de la tarde. Sera til que el administrador del supermercado pudiera determinar cuntas cajas requiere para cada perodo del da en forma independiente. Actualmente los datos de las horas de muy alta y muy baja afluencia estn alterando los promedios arrojados. Para lograr esto el programa debera pedir un rango de horas y ejecutar la simulacin nicamente con los datos de entrada que correspondan con el rango especificado. Adems, dependiendo de la hora del da el nmero de productos que llevan los clientes podra variar. Para lograr esto bastara con cambiar la generacin aleatoria de la cantidad de productos para que dependiera de la hora en la que se est comprando. Finalmente, podra ser interesante lograr que la hora de llegada de los clientes se genere en forma aleatoria, de modo que podamos suprimir el archivo de entrada y lo nico que deba dar el usuario es el nmero de clientes y la cantidad de cajas que debern emplearse para la simulacin. La planificacin y la implementacin de estas modificaciones se dejan como ejercicio al estudiante.

3.4

Simulacin de una Plaza de Peaje

Este ejemplo en particular se present como trabajo personal dentro de un curso. Cada alumno, contando slo con ejemplos como los anteriores y la explicacin que se indica a continuacin. Este ejemplo se centra en implementar una plaza de peaje de la carretera, donde se tienen distintas casetas abiertas para atencin y en el tiempo van llegando autos a ser atendidos. Una plaza de peaje est compuesta de distintas casetas que atienden a los autos que llegan por cada lado de la carretera. Los autos deben pagar una tarifa que depende de la hora, y segn esa tarifa, la tasa de atencin de la caseta puede aumentar o disminuir. El propsito del programa es determinar la cantidad ptima de casetas abiertas y atendiendo para dar un servicio adecuado a los vehculos al menor costo. Esta particularidad le impone un factor especial al ejemplo, ya que ms que slo ejecutar una simulacin del funcionamiento de la plaza de peaje, se toman los datos obtenidos de una simulacin completa y se usan para cambiar los parmetros que determinan el escenario de la siguiente simulacin (en particular la cantidad de casetas abiertas). De tal manera, se evalan diferentes escenarios y se determina cul de ellos ofrece la mejor relacin costo/ingreso. Este proceso informal de optimizacin se refleja en el algoritmo principal (Main).

3.4.1 Definicin del ProblemaEn detalle el funcionamiento de la simulacin considera lo siguiente:

IIC 1102

Pgina: 24


Rodrigo Sandoval U.

3.4.1.1

El Tiempo de Simulacin El periodo a simular consta de dos horas, desde las 17:00 a las 19:00 de un da viernes. Cada unidad de tiempo de simulacin es de 1 minuto. A las 18:00 - la mitad del tiempo de simulacin - se cambia la tarifa de peaje, con lo cual tambin cambia la tasa de atencin. Estos dos valores se explican ms adelante. Las Casetas Hay un total de 20 casetas construidas, de las cuales en una simulacin dada, el total de ellas o slo una parte estarn atendiendo (al menos dos casetas siempre, una para cada direccin). De las abiertas, la mitad est atendiendo a los autos que llegan por el sur y las otras a los que llegan por el norte. La cantidad de casetas que atienden a cada lado tambin es fijo para cada simulacin, pero es el parmetro a ir ajustando para determinar la cantidad ptima. El costo fijo de atencin por caseta es de $50.000 por cada periodo de simulacin, lo que permite calcular los costos. En cada caseta siempre habr una cola que tiene 0 ms autos. Cada auto que llegue a la plaza de peaje, por cualquier direccin, seleccionar la caseta cuya cola sea la ms corta, o bien la primera si todas son iguales. Tarifa de peaje: en la primera hora la tarifa es de $1.200 por vehculo, y en la segunda hora es de $2.000. La tasa de atencin en la caseta es de: o 2 autos por minuto cuando la tarifa es baja (ya que se cuenta el tiempo para dar vuelto en monedas). o 4 autos por minuto cuando la tarifa es alta (ya que no se requiere dar vuelto en monedas). o En cualquiera de los dos casos se atender a la cantidad de autos correspondiente a la tasa del horario actual, y si quedan menos autos, slo se atender a los que haya. Los Vehculos Existe un registro de los autos que llegan por el sur y por el norte respectivamente, identificando la hora (en hh y mm) y la cantidad de autos que llegan en ese minuto. Los del norte vienen en el archivo norte.txt y los del sur en sur.txt. Estos archivos asumen conocidos y para este ejemplo se pueden inventar datos. En cada archivo se registra una lnea por minuto de datos, la cual tiene en orden: hh mm cantidadautos. Si en un minuto dado no se registraron autos (cantidadautos=0), esa lnea no viene en el archivo. En la correccin de la tarea se pueden utilizar otros archivos, por lo que no asuma que esos sern siempre los archivos. El Proceso de Optimizacin

3.4.1.2

3.4.1.3

3.4.1.4

El proceso de optimizacin no se enfoca en las tcnicas formales de optimizacin matemtica, ya que ese enfoque no forma parte de este documento. Sin embargo, se busca lograr un punto denominad ptimo por medio de la evaluacin de los resultados tomando distintos escenarios de simulacin. Al comparar progresivamente los escenarios en torno a los costos e ingresos, se puede llegar a una combinacin ideal de casetas abiertas que logren un nivel aceptable de tasa de atencin por vehculo. Para ello, el procedimiento (algoritmo) es el siguiente: Se comienza con el mnimo: 1 caseta abierta para los vehculos del norte y 1 para los del sur. Se efecta la simulacin completa y se miden los siguientes datos que deben mostrarse en pantalla.

IIC 1102

Pgina: 25


Rodrigo Sandoval U.

o Cantidad de cajas abiertas por cada lado. o Cantidad de autos atendidos por cada lado. o $ ingreso (cobro de peaje). o $ costos (casetas x costo fijo). o Mxima espera en minutos. Se aumenta en uno la cantidad de casetas abiertas por cada lado y se vuelve a simular. Las condiciones de trmino del proceso de optimizacin (que a su vez ejecuta varias simulaciones) son: o El Tiempo Mximo de espera por atencin debe ser menor que un valor en minutos dado por el usuario al comienzo de todo el proceso. o Se analiza si la utilidad (ingresos-costos) disminuye o aumenta. Dentro de la restriccin de Tiempo de Espera Mxima, se busca el menor costo posible (el mnimo de casetas abiertas). o El mximo de casetas es el de la cantidad construida: 20 en total (10 para cada lado).

3.4.2 SolucinCdigo Fuenteusing System; using System.IO; using System.Collections;

//-----------------------------------------------------------------------------------// Clase: Auto // Representa un auto cuyos datos relevantes son nicamente los de la hora de llegada //-----------------------------------------------------------------------------------class Auto { DateTime horallegada; // Atributo relevante: la hora de llegada. public Auto(int hh, int mm) { // Transforma la hora y minutos de llegada en un tipo DateTime horallegada = new DateTime(DateTime.Now.Year, DateTime.Now.Month, DateTime.Now.Day, hh, mm, 0, 0); } public DateTime HoraLlegada { get { return(horallegada); } } public int Hora { get { return(horallegada.Hour); } } public int Minutos { get { return(horallegada.Minute); } } // Al imprimir una instancia de Auto, se imprime la hora de llegada public override string ToString() { return(horallegada.ToString()); } }

//-----------------------------------------------------------------------------------// Clase: Caseta // Hereda de Queue, por lo cual la misma caseta representa una cola de vehculos que // se atienden en dicha caseta. Adems, registra el tiempo mximo de espera durante // toda la operacin de la caseta, contabiliza los autos atendidos, y va sumando // el cobro de peajes segn tarifa por auto atendido. //-----------------------------------------------------------------------------------class Caseta : Queue { int maxespera = 0; int procesados = 0; int ingresos = 0; // AtenderPrimero(): toma al primero de la cola, y si est en la // lo atiende, registrando su tiempo de espera public int AtenderPrimero(DateTime lahora, int valorpeaje) { if(Count

simulacion c sharp - a

Documents