TAREA MODELOS ESTOCASTICOS Simulación por computador de cadenas de Markov en tiempo discreto y continuo Tabla contenidos CAPÍTULO1: INTRODUCCIÓN____________________ página 2 CAPÍTULO 2: PROBLEMAS_____________ ________ página 3−5 • Diseño de las vigas del puente grúa • Diseño de la caja reductora CAPÍTULO 3: PROBLEMAS_____________ ________ página 6−10 CAPÍTULO 4: DESARROLLO ANALÍTICO________ página 11−19 CAPÍTULO 5: SIMULACIÓN COMPUTACIONAL_ _ página 20−26 CAPÍTULO 6: ANÁLISIS RESULTADOS _ ________ página 27−5

Capítulo Introducción 1 En este trabajo el grupo de alumnos se dispondrá a vertir todos los conocimientos que han adquirido en el ramo de modelos estocásticos durante el actual semestre, de manera tal de resolver los problemas dispuestos por el profesor para que el alumnado demuestre lo aprendido. Los alumnos, especificamente harán uso de los contenidos primordiales de las interrogaciones 2 y 3 , más concretamente, de la teoría y práctica aprendida en torno a los temas de modelamiento de cadenas de markov tanto en tiempo discreto como en tiempo continuo, siendo ambas teorías los pilares fundamentales del curso de modelación estocástica. Además los alumnos deberán de exponer en el trabajo conociminetos de simulación, la cual es materia de final de semestrey que se expuso a medida en que se desarrlollaba el informe, en conjunto con un avanzado entendimiento de herramientas computacionales tales como C o pascal. Para este trabajo en específico, los alumnos decidieron utilizar el lenguaje C, debido a una mayor profundidad de contenidos sabidos de este lenguaje que de cualquier otro capaz de utilizarse para esta tarea. La disposición de los cuatro integrantes de este grupo hacia el proyecto ha sido buena, ya que se ve con agrado el poder profundizar conocimientos en semanas previas a lo que será el examen y así poder rendir de la mejor manera en lo que es la parte final de este curso. Sin más que acotar, se le invita al lector seguir con atención y agrado las siguientes páginas en las que quedaron expuestas el esfuerzo y conocimientos de los alumnos.

1

Capítulo Problemas 2 Cadena de Markov en tiempo discreto. Empresa ELECTRONICA S.A. El problema consiste en que esta empresa productora de medidores electrónicos necesita realizar un inventario de manejo de insumos. La producción diaria está sujeta a la demanda diaria de medidores las cuales se consideran por medio de llegada de órdenes de compra que arriban de acuerdo a un proceso de Poisson con tasa 2 [órdenes/hora] en la que se piden uno (probabilidad 0.8) o dos (probabilidad 0.2) medidores. Ordenes pueden ser recibidas desde las 9: 00 AM a las 4: 00 PM y los medidores son despachados en el mismo día antes de las 6 : 00 PM. A las 8:00 PM se revisa la cantidad de transductores que hay en bodega y comienza la política de reposición que es la siguiente: Si hay más de 20 no se pide reposición. Si es mayor que 10 pero menor o igual que 20 se piden 20 transductores. Si es menor o igual que 10 se piden 50 transductores. Lo que nos interesa en este caso es poder saber en cada día cuanto marcará el inventario para esto partimos desde un X0 = 35 transductores. Cadena de Markov en tiempo continuo Empresa Manufacturera de tarjetas de crédito La idea es considerar que esta es la única empresa que puede arreglar máquinas de tarjetas de crédito en el mundo por lo que cualquier máquina que falle debe ser enviada hacia acá. Se toma como base que en el mundo existen solamente 10 máquinas creadoreas de tarjetas de crédito y este número se mantendrá por los próximos 2 años. El tiempo de duracioón de una máquina, es decir, hasta que falle distribuye en forma exponencial con media de 5 días ( = 0.2). En la empresa hay un sólo mecánico capacitado para arreglar el cual comenzará a arreglar cuando se encuentren 3 máquinas en espera y continuará hasta que no queden máquinas por arreglar. El tiempo que demora en arreglar una máquina distribuye en forma exponencial con media de 20 horas (ð =1.2). En el caso en que la cantidad de máquinas por arreglar supere las 5 máquinas la empresa contrata otro técnico, el cual trabajara hasta que se llegue nuevamente a 5 máquinas, el segundo técnico trabaja de la misma manera que el primero. Metodología de trabajo Tiempo discreto Se buscará una relación de recurrencia para la variable de estado, probabilidades de de transición en una etapa, clases de estado, clasificación de estados y periodicidad.

2

Por medio del algún programa computacional estimar un tiempo esperado hasta que la empresa no logre satisfacer la demanda requerida. Por medio del algún programa computacional estimar la probabilidad de que en el largo plazo hayan 10 o menos transductores en bodega. Por medio del algún programa computacional estimar la proporción de días en el largo plazo de que hayan mas de 40 transductores en bodega. Tiempo continuo Poder calcular mediante la ayuda de un computador en un horizonte de largo plazo el número medio de máquinas en el taller de reparaciones en instante cualquiera de tiempo, Su tiempo medio de permanencia en el taller de una máquina cualquiera, la fracción del tiempo en que el técnico no está reparando y en el que está reparando. Por ayuda de un computador calcular las soluciones de las ecuaciones de equilibrio. Por simulación estocástica las medidas que se piden en el primer punto y comparación de resultados. El desarrollo de cada una de las simulaciones y estimaciones que se piden en ambos problemas se realizó mediante el programa computacional Visual C++. En el cual se provoca un juego de iteraciones para lograr el largo plazo requerido en los problemas.

Capítulo Marco Teórico 3 Cadena de Markov en tiempo discreto Empresa ELECTRONICA S.A. El desarrollo de problemas de tiempo discreto requieren de ciertas condiciones para considerarse como cadenas de markov, y un proceso estocástico (Xn, n=0,1,2,....) se denomina una cadena de markov en tiempo discreto si cumple con las propiedades markovianas y de estacionareidad, las cuales se explicarán en las próximas lineas. Se sabe que para conocer la distribución de Xn+1 se necesita conocer Xn. Razonando, se ve que Xn depende a su vez de Xn−1. Además, Xn−1 depende de Xn−2, etc. Luego, se concluye que Xn+1 depende no solo de Xn, sino que indirectamente depende también de Xn−1, Xn−2,...,X1,X0. El proceso estocástico (Xn, n=0,1,2,......) está conformado por una familia de variables aleatorias independientes entre sí. Sin embargo, la dependencia entre estas variables aleatorias es tal que, si yo conozco el valor de Xn, los valores de X0, X1, X2, ....Xn−1i son irrelevantes para estudiar el valor de Xn+1. Se observa que esto no quiere decir que Xn+1 sea independiente de X0, X1,..,Xn−1, sino que lo que ocurre es que estas variables influyen en Xn+1 solo a través de Xn. Más exactamente, si se denomina el periodo n+1 como el futuro, el periodo n como el presente, y los periodos 0,1,2,....,n−1 como el pasado, se dirá entonces que el pasado influye sobre el futuro pero sólo a través del presente. Esta propiedad es la denominada markoviana, que por definición formal puede quedar expresada como: Sea Xn una v.a. que toma valores enteros: Entonces se dice que el proceso (Xn, n=0,1,2,...)cumple con la propiedad markoviana si:

3

Por otra parte el proceso (Xn, n=0,1,2,...) cumple con la propiedad de estacionareidad si la propiedad Pr( Xn+1=j/Xn=i) depende sólo de i y de j, pero no de n. En este caso, definimos como Pi,j a esta probabilidad, y se denomina probabilidad de transición en una etapa. La propiedad de estacionareidad establece que los mecanismos probabilísticos que definen la evolución del proceso no cambian con el tiempo. Las probabilidades Pi,j pueden agruparse en una matriz P, denominada matriz de probabilidades de transición en una etapa, que tendrá tantas filas y columnas como estados tenga el proceso. En las cadenas de markov en tiempo discreto se pueden estudiar los procesos en el largo plazo, dentro de lo que se puede analizar es si estos tienen distribución límite o no, lo cual se expresa a travás de fórmula como . En la medida que esto ocurra, podemos concluir que, pasado mucho tiempo, la distribución de probabiliadades del proceso no cambia de una etapa a otra. En el largo plazo los estados del proceso se pueden clasificar de diversas maneras, de forma tal que estas clasificaciones formalizan las existencia de las distribuciones límites. Un estado se denominará transiente si F(i,i)<1, o sea , si un estado parte en i, la probabilidad de que regrese al mismo estado es menor que uno. También los estados se denominarán recurrentes si F(i,i)=1, y si su valor esperado de tiempo es menor a infinito (E(T(i,i)< ) se denominará recurrente positivo, en caso contrario, se denominará recurrente nulo. En el caso de un estado recurrente nulo, existe la seguridad de que, si el proceso parte en el estado i, volverá a ese estado alguna vez, sin embargo, el tiempo promedio de retorno será infinito. Existe un ámbito importante en el estudio de los estados en el largo tiempo, y eso es su comunicación, debido a que los determina a estos según clases. Por convención se dice que un estado siempre se comunica consigo mismo, ya que:

(esto es, se comunica através de un camino de largo 0) Las clases de estados que se comunican son disjuntas entre sí y cubren todo el conjunto de estados, esdecir, generan una partición del conjunto. Si una cadena de markov contiene una sola clase de estados (todos los estados se comunican entre sí), se dirá que es irreducible. La existencia de una distribución límite depende esencialmente del comportamiento en el largo plazo (n grande) de las probabilidades Pi,j(n). Para analizar estas probabilidades necesitamos el concepto de estado periódico: Un estado es periódico si, partiendo de este estado, sólo es posible volver a él en un número de etapas que sea múltiplo de un cierto número entero mayor que uno. En otras palabras, el estado j es periódico si existe un número entero K , tal que Pi.j(n)>0 sólo para valores de n en el conjunto (K, 2K, 3K, 4K,). Cabe mencionar que un periodo se puede definir de la siguiente forma: El período d del estado j corresponde al máximo común divisor de los n para los que Pi,j (n)>0. Si d>1, diremos que el estado es periódico con periodo d. SI d=1 se dirá que el estado es aperiódico. Además se puede decir que el estado es aperiódico si no es posible volver a él (en este caso, el estado es aperiódico por la imposibilidad de chequear la condición de periodicidad).

Cadena de Markov en tiempo continuo Empresa Manufacturera Esta parte tiene similitudes con las cadenas de markov en tiempo dicreto en que requieren características 4

similares para su validez, pero difieren en que para markov continuo interesa extender el modelo a cadenas para el caso de un sistema en todo instante de tiempo, por ejemplo, sea (X(t), t ) un proceso estocástico, en que X(t) representa el estado (discreto) de un sistema; es decir, esta variable aleatoria solo puede tomar valores enteros(eventualmente negativos), se dirá que el proceso es de estado discreto y tiempo continuo. Luego para extender la propiedad markoviana del modelo discreto al continuo se dirá que el proceso (X(t), t ) cumple con la propiedad markoviana si:

Es decir, si se considera el instante t como el instante presente, y t+s como un instante futuro cualquiera, y si se conoce toda la trayectoria del proceso en el continuo , entonces la distribución de probabilidades de X(t+s), depende sólo de la última información disponible (esto es, de X(t)). Se dirá que el proceso cumple con la propiedad de estacionareidad si la probabilidad Pr(X(t+s)=j/X(t)=I) depende sólo de i,j y s, pero no de t. Se observa que esta probabilidad de transición en s unidades de tiempo es equivalente a la probabilidad de transición en m etapas de Pi,j(m) del modelo discreto. Luego se pude definir una exacta definición sobre cadenas de markov en tiempo continuo: El proceso estocástico (X(t), t ) es una cadena de markov en tiempo continuo si cumple con la propiedad markoviana y la propiedad de estacionareidad definidas anteriormente. Teoría de Simulación En el desarrollo del modelo computacional en lenguaje C se consideraron ciertos aspectos de simulación para conseguir el objetivo de modelación. Lo anterior hace referencia a la generación de instancias de una variable aleatoria, que se puede explicar de manera generalizada mediante el siguiente desarrollo: Si se quieren generar instancias de una variable aleatoria X con una distribución de probabilidades F. Se sabe que:

Sea R una v.a. con distribución de probabilidades uniforme en . Entonces:

en que 0 y por lo tanto, dado que 0 , para todo x, se puede escribir:

Con lo que se establece la siguiente igualdad: 5

F(x)= Ahora bien, F() es siempre una función monótona no decreciente y, por lo tanto, el evento es quivalente al evento Equivalencia de los dos eventos implica:

De lo anterior se observa que F−1 (R ) es una función de una v.a., y por lo tanto también es aleatoria., luego de las ecuaciones anteriores se puede obtener como implicancia la siguiente ecuación:

y por lo tanto, las variables aleatorias X y F−1( R ) tienen la misma distribución de probabilidades. El método para generar instancias de X (denominado de la transformada invesa), opera de la siguiente forma: • Generar una instancia de R1 de R, en que R~U(0,1) • Sea X1=F−1(R1); entonces X1 es una instancia de X. Se nota que F−1( R ) es una variable aleatoria distinta de X, pero que comparte su distribución de probabilidades. Por lo tanto, generar una instancia de F−1( R ) es equivalnte a generar una instancia de X. Para generar una secuencia X1, X2,,Xn de instancias de X, se debe generar una secuencia R1,R2,,Rn. Para que las instancias (Xi) sean independientes entre sí, se debe asegurar de que las instancias (Ri) también lo sean. Luego se demuestra que la generación de instancias de una v.a. con cualquier distribución se reduce al problema de generar instancias de una v.a.~U(0,1). Capítulo 4

Desarrollo Analítico

Cadena de Markov en tiempo discreto Empresa ELECTRONICA S.A. Para el caso del tiempo discreto la cantidad a pedir de transductores depende directamente de las órdenes recibidas durante las horas de atención y cuantos pedidos hay en cada orden. El tiempo de atención, la hora del inventario, el momento en que se considera el estado siguiente están mayormente explicados en la siguiente línea del tiempo. A continuación se definirán las variables aleatorias a utilizar. Nn : Número de órdenes recibidas durante el día desde las 9:00 hrs. Hasta las 16:00 hrs. Xn : Número de transductores contabilizados a las 8:30 hrs. Yn : Número de transductores a reposición luego del inventario obtenido a las 20:00 hrs. 6

Se obtendrá la relación de recurrencia dependiendo de intervalos en que se encuentre la variable Xn ya que la relación con Xn+1 no vará en forma lineal, sino en forma escalonada. Matriz de Probabilidades Para poder calcular la matriz de probabilidades en forma general, se necesita analizar una serie de casos relevantes para el desarrollo, es decir, existen una serie de estados en que la probabilidad de transición hacia otros estados no es constante. Los casos relevantes de la matriz de probabilidades fueron tomadas con respecto a la cantidad total de pedidos recibidos durante el día y la respectiva cantidad con que se inicio este. En una forma recursiva se pudo obtener fórmulas para la transición desde un estado a otro: • Para ir de un estado al mismo se necesita que no hayan pedidos durante el día o que si los pedidos fueron 20 y quedo al final del día con un número de medidores mayor que 10 y menor o igual que 20, se le sumarían 20 medidores que son los que se piden a reponer y se llegaría nuevamente al estado inicial del día anterior, esto se da solamente en los estados X(31) al estado X(40) porque para los estados anteriores al restar 20 quedo con menos de 10 llegando así al estado X(50) y para los mayores al restar 20 quedo con la misma cantidad, este es el caso de ir de i a j con i=j. • Para ir de un estado de menor cantidad a una de mayor cantidad de medidores, la única manera es que al número inicial que se tiene se le resten los números de pedidos quedando al final del día con un número de medidores mayor que 10 y menor o igual que 20, se le sumarían 20 medidores que son los que se piden a reponer, pero esto se daría con estados Xn+1 mayores o iguales de X(31) y menores que X(40), en otro caso no se puede llegar • Para ir de un estado de mayor cantidad a menor cantidad de medidores simplemente es necesario que hayan la cantidad de pedidos correspondientes a la resta entre el estado mayor y el menor, por ejemplo del estado X(25) al X(23) basta con hacer 2 pedidos, y existe un caso especial en que se necesite llegar a un estado que se encuentre entre X(31) a X(40) para estos casos basta con pedir lo anterior mas 20 y se vuelve a este estado por ejemplo desde el estado X(45) al estado X(35) puedo llegar pidiendo 10 a 30. • Existe un caso especial que es el caso del estado X(50) para llegar al estado X(50) basta con tener un número de pedidos igual al número de medidores menos 10, que tengo al inicio del día o mayor que este, por ejemplo si tengo 25 medidores es necesario que tenga un número de pedidos mayor o igual que 15, y para el caso de llegar del estado 50 al 50 necesito que no hayan pedidos o que hayan 40 o más pedidos durante el día. Todo esto se da a causa de que si al final del día tengo 10 o menos números de medidores entonces para comenzar el día siguiente se reponen hasta 50 medidores. Generalizando en fórmulas para cada caso se tiene: Para ir del estado Xn a Xn+1 P ( Xn=i / Xn+1=j )

para 31 0 para otro caso

7

para

para otro caso

para

para otro caso caso especial:

•

Estas son las ecuaciones para lograr sacar cualquier valor de la matriz de probabilidades, pero como se ve a primera vista no hay valores numéricos sino más bien están dadas como probabilidades dependientes de N(t) que se ha definido como el número de pedidos recibidos durante el día. La matriz de probabilidades corresponde a una matriz de 30 30 por lo que hacer el grafo sería muy tedioso e innecesario, puesto que con la simple matriz se podrá observar que todos los estados están comunicados entre sí ya que aunque existen algunas probabilidades iguales a cero de alguna manera indirecta, es decir pasando por otro estado anteriormente se pude llegar desde cualquier estado a cualquier estado y como desde un estado cualquiera puedo llegar al mismo estado con una probabilidad distinta de cero el sistema es aperiódico, por consiguiente se existe un solo estado presente recurrente positivo aperiódico e irreducible. Tomando lo anteriormente descrito como cierto se puede concluir que al estar todos los estados comunicados entre sí no importa el estado inicial en que se encuentre, siempre se podrá llegar a cualquiera por lo que se puede considerar que existe una distribución estacionaria. Como es un estado recurrente positivo irreducible la y además el por lo que:

Por lo que existe una distribución límite dado a largo tiempo distinto de cero. El valor N(t) está subdividido en dos partes, cuando la orden de pedido es de 1 sólo medidor en que el grupo lo ha definido como en N1(t) y en el caso de que la orden de pedido se requira 2 medidores se ha definido de 8

igual manera como N2(t). Y estas probabilidades se han dividido a su vez en dos situaciones distintas. El caso en que el valor n de la expresión P{N(t)=n} sea par. Para este caso:

El caso en que el valor n de la expresión P{N(t)=n} sea impar. Para este caso:

El proceso de llegada de órdenes transformada a un número total de pedidos N(t) como se dijo anteriormente fue dividido en dos casos N1(t) y N2(t) para los cuales se les han dado una nueva tasa de llegada que se le podría considerar una ponderación de las probabilidades de que llegue cad una. La tasa de llegada de un pedido corresponde a la tasa de llegada de N1(t) que es igual a

Mientras que la tasa de llegada de dos pedidos corresponde a la tasa de llegada de N2(t) que es igual a

Estas dos tasas de llegada de pedidos también corresponden a una distribución Poisson de sus respectivas tasas, el tiempo que se considera para obtener las probabilidades es de 7 hrs que corresponde al tiempo que se extiende la atención de público desde las 9:00 horas hasta las 14:00 horas, en consecuencia las probabilidades correspondientes a

Para que pueda ser explicado de mejor manera el problema que se plantea se hará un breve esquema de lo que sucede al llegar una orden a la empresa, se asume que cada vez que llega un posible comprador este siempre hace una orden de uno o dos pedidos en forma aleatoria, nunca llega y se va sin pedir nada. En el problema se pidió el cálculo del tiempo esperado hasta que no se logra satisfacer la demanda diaria por 9

primera vez. Este requerimiento se entendió como: En que n es el estado en que se encuentra, es decir, si se encuentra en el estado X(25) en que hay 25 transductores, la probabilidad de que no haya podido satisfacer la demanda, es que la demanda haya sido mayor que 25. Mientras que la esperanza del tiempo puede ser calculado como . En conclusión lo requerido se obtuvo como. Para el tercer ítem de la pregunta de tiempo discreto se necesita la probabilidad de que en cualquier día en el largo plazo existan 10 o menos transductores la cual fue asumida como la probabilidad de que en el estado Xn+1 se encuentre en el estado 50, por lo tanto: = y esta corresponde a su vez a por lo que calculado manualmente, daría una serie de sumatorias que son casi imposibles de resolverlas a mano por lo que se ocupa el programa computacional bajo iteraciones para calcular este problema , pero siempre bajo esta teoría. Cadena de Markov en tiempo continuo. Empresa Manufacturera de tarjetas de crédito En el grafo se muestra claramente cuales son las tasa de salida y de entrada a cada estado. Cada estado contiene un intervalo (i , j) en el que se representa: i : Número de máquinas en reparaciones o en espera a reparar (máquinas en el sistema) j : Cantidad de técnicos reparando. ð ð Tasa de falla de una máquina cualquiera y necesite reparación. En este problema se da la media igual a 5 días, por lo que la tasa es igual a . ð ð Tasa de reparación de un técnico en acción. En este problema se da la media igual a 20 horas ( =0.833 días), por lo que la tasa es igual a =1.2 Los estados X (1,0); X (2,0) no tienen tasa de muerte puesto que aun el técnico no se ha puesto a trabajar en las reparaciones, él está esperando que hayan tres máquinas en espera de reparación. Grafo de probabilidades de salida y entrada de cada estado Ecuaciones de Equilibrio Las ecuaciones de equilibrio se reemplazan de la tabla anterior y se ocupa la ecuación general explicada en el márco teórico para su constitución.

10

Además hay que agregar que la suma de las probabilidades tiene que ser uno.

Con las ecuaciones anterirores y sabiendo que la suma de las probabilidades es uno. Se resuelven mediante calculadora y los datos se pasan a excel: En que las tasas medias fueron calculadas multiplicando las probabilidades de estar en cada estado por su tasa respectiva y luego sumando todas las tasas medias obtenidas, incurriendo así en una tasa media total de y luego obteniendo el valor promedio de máquinas calculado multiplicando las probabilidades de encontrarse en el estado por el número de máquinas en el estado y luego sumando todos estos valores promedios se obtiene un valor promedio total de máquinas Nm=3.739045 Ya obtenidos estos dos datos podemos ocupar la ecuación de Little que está enunciada a continuación: L = Número promedio de máquinas en el sistema. = Tasa media de entrada de máquinas al sistema. W = Tiempo de permanencia de una máquina cualquiera en el sistema. Obteniendo así: Que representa el tiempo esperado de permanencia de una máquina en el taller. Capítulo 5

Simulación Computacional

Cadena de Markov en tiempo continuo Empresa Manufacturera de tarjetas de crédito Análisis y supuestos del algoritmo para las fracciones de tiempo Para simular las variables de desempeño pedidas se realizó un programa en lenguaje C++. La simulación de los tiempos exponenciales se realizó con el método explicado en el marco teórico. Con lo 11

cual resulta que la función necesaria para obtener tiempos entre eventos exponenciales con cierta tasa esta dada por: Es decir queda determinado en C++ mediante una función implementada que ocupa la función uniforme que viene incorporada en las librerías por defecto. El algoritmo utilizado para buscar las probabilidades de estado se explicará a continuación: • Se realiza una modelación en el tiempo, que puede ser de 1 año, 2 años, etc. • Esta modelación en el tiempo comienza cuando el sistema está en el estado (0,0). Es decir todas las máquinas están funcionando. Este estado de inicio no tiene influencia en los resultados mayormente ya que se está trabajando a largo plazo y existe una distribución límite y estacionaria. Claro que puede traer pequeñas diferencias porcentuales con respecto a los resultados correctos. • Se inventó en el programa una variable llamada estado la cual determina en todo momento en que estado se encuentra el sistema. • Dentro de la iteración se pregunta: ¿El sistema está en el estado (i,j)? • Si está en (0,0); (1,0); (2,0) se calcula un tiempo de nacimiento con sus respectiva tasa y se pasa al estado contiguo con probabilidad 1. • Si el sistema se encuentra en otro estado (i,j) distinto a los anteriores se calcula un tiempo de nacimiento y un tiempo de muerte (ambos con su tasa, que depende del estado). • Si el tiempo de muerte es menor que el tiempo de nacimiento se pasa al estado contiguo menor (ej: (3,1) (2,1)) • Si el tiempo de nacimiento es menor que el tiempo de muerte se pasa al estado contiguo mayor (ej: (3,1) (4,1)) • Las transiciones están determinadas en las tablas expuestas en el capitulo 2. (no se incluyen en la explicación del algoritmo) • Se guarda en un vector la cantidad de tiempo en que se permanece en cada estado. • Este vector se actualiza cada vez que se vuelve a entrar al estado. Con lo cual se contabiliza todo el tiempo de permanencia en el estado en el transcurso de l tiempo de iteración a largo plazo. • Al final de la iteración en el tiempo se calculan las probabilidades como: la suma de todos los tiempos de permanencia en cada estado por separado y se dividen por el tiempo total de iteración. Es decir se calcula como:

Con esto se encuentran las probabilidades en el largo plazo (dependiendo del tiempo de modelación que se estime necesario) Fracción de tiempo en inventario La fracción de tiempo que el técnico permanente pasa dedicado a los inventarios es la suma de:

Que se calcula con las probabilidades obtenidas por el computador y se suman manualmente, o directamente mediante el computador al realizar la suma de los primeros 3 valores del vector tiempo para cada estado. Dividiendo esta suma por el tiempo total de modelación de la siguiente manera (notación del vector en el algoritmo = suma [ ])

12

Fracción de tiempo del empleado reparando La fracción de tiempo que el técnico permanente pasa dedicado a reparar se calcula sumando los restantes vectores de tiempo para cada estado:

también se calcula como:

Análisis y supuestos del algoritmo para promedio de máquinas El algoritmo realizado para encontrar el número de máquinas promedio en el taller en un instante cualquiera es el siguiente. • Se realiza un estudio en un tiempo aleatorio a largo plazo (cualquier instante), es decir se toma un tiempo aleatorio entre 1 y 2 años. • Luego de este estudio se verifica el estado final del sistema. • Se guarda en un vector el valor que indica la cantidad de máquinas encontradas en el sistema al finalizar el estudio aleatorio. • Se realizan iteraciones para repetir este proceso una razonable cantidad de veces para así obtener un resultado aproximado de la variable de desempeño. • El promedio de máquinas se calcula de la siguiente manera:

Análisis y supuestos para el algoritmo que resuelve el tiempo medio de espera de una máquina en el sistema Este algoritmo es bastante más complejo y se hacen algunas suposiciones. Se supone que las máquinas entran a una cola y la primera en llegar es la primera en salir (hay un orden de reparación) Además se conoce que la función exponencial se caracteriza por su propiedad de pérdida de memoria. El siguiente algoritmo se basa en esta propiedad específica. Como sólo se necesita el estado actual para obtener información sobre el pasado se realizan los siguientes pasos.

13

• Se obtiene un estudio en forma aleatoria en un tiempo entre 1 y 2 años. Se toma como estado inicial el (0,0). • Al finalizar el estudio se toma el valor del estado final y se prosigue con el algoritmo. • Con el estado actual se realiza la suposición de que la última máquina acaba de llegar (pérdida de memoria) • Se calcula el tiempo que transcurre hasta que se logra salir del sistema. • Esto se realiza sumando tiempos de llegada y tiempos de salida. Cada vez que ocurre un evento de salida (reparación) se incrementa un contador. Cuando el contador llegue a un valor igual a la cantidad de máquinas del estado final del estudio anterior (1−2años) se finaliza la iteración y se obtiene el tiempo transcurrido hasta que la última máquina (con respecto al estado final del estudio) deja el sistema. • Este proceso se realiza un gran número de veces • Existen casos especiales en las iteraciones. Si luego del estudio el sistema se encuentra en el estado cero (ninguna máquina en reparación) el programa no cuenta estos datos. Ya que falla la suposición de que acaba de llegar una máquina. • Si luego del estudio se encuentra el estado actual = (1,1) no se puede suponer que la máquina acaba de llegar. Ya que el estado (1,1) proviene sólo de (2,1) y no de (0,0). Es decir no puede llegar una máquina y quedar en el estado (1,1). Por lo tanto hay que agregarle a este caso un tiempo de espera de reparación, más tiempos de llegada de máquinas al sistema. • Finalmente se guardan en un vector todos los tiempos obtenidos. Este vector tendrá el largo de la cantidad de iteraciones que se seleccionó hacer. • El resultado se obtiene de la siguiente forma:

Con esto queda demostrado el algoritmo a usar en el segundo problema (Markov continuo) El cual se pasará a lenguaje computacional en C++. En el anexo se adjunta el programa en lenguaje C++, con sus respectivos comentarios indicando los pasos del algoritmo utilizado para cada variable de desempeño. Cadena de Markov en tiempo discreto Empresa ELECTRONICA S.A. Análisis y supuestos de algoritmo para media de días hasta que no se satisface la demanda diaria por primera vez. Para calcular la cantidad de días promedio hasta que no se satisface por primera vez la demanda se realiza el siguiente algoritmo. • Se realizan un número razonable de iteraciones generales. Cada iteración contiene los siguientes pasos. Se comienza con X0 = 35 medidores a la venta. • Se calcula la cantidad de pedidos de medidores durante un día cualquiera. Esto considerando las probabilidades de realizar 2 pedidos o 1 pedido. Y tomando el tiempo entre llegadas de órdenes como una variable aleatoria exponencial a tasa 2 [ordenes/hora]. El tiempo en que pueden llegar órdenes es de 7 horas. • Al final de cada día (luego de las 7 horas de recibir órdenes) se calcula la cantidad de medidores que quedan y se toman las decisiones apropiadas para el día siguiente. (reposición). Además se incrementa el contador de días transcurridos. • Cuando el sistema encuentre que la cantidad de pedidos en un día fue mayor que la cantidad de cajas en venta. Es decir Xn − ordenes < 0 (Xn = cantidad de medidores en el día n). El sistema detiene el contador de días y acaba con la primera iteración, guardando en un vector el número de días hasta que no se pudo 14

satisfacer la demanda. • Este proceso se realiza la cantidad de veces determinada en el número de iteraciones que se escogió realizar para resolver el problema. Finalmente se utiliza el vector de días encontrado (el largo del vector será igual al número de iteraciones escogidas). De la siguiente forma se encuentra la variable pedida:

Análisis y supuestos de algoritmo para la probabilidad de que la existencia de transductores sea menor o igual a 10 Para encontrar esta probabilidad se implementó el siguiente algoritmo: • Se escoge una cantidad de iteraciones generales. Cada una de estas iteraciones contiene los pasos que se describen a continuación: • Se realiza un estudio escogiendo como cantidad inicial de trasductores igual a 35 en bodega. Este número no tendrá mayores implicancias ya que el estudio durará entre 1 y 2 años (escogido aleatoriamente para cumplir la condición en un instante cualquiera a largo plazo). Por lo cual se puede considerar como un estudio a largo plazo que no dependerá de la condición inicial (además es una cadena irreductible con distribución estacionaria). Claro está que los resultados no serán perfectos. • Se calcula la cantidad de pedidos de medidores durante un día cualquiera. Esto considerando las probabilidades de realizar 2 pedidos o 1 pedido. Y tomando el tiempo entre llegadas de órdenes como una variable aleatoria exponencial a tasa 2 [ordenes/hora]. El tiempo en que pueden llegar órdenes es de 7 horas. • Al final de cada día (luego de las 7 horas de recibir órdenes) se calcula la cantidad de medidores que quedan y se toman las decisiones apropiadas para el día siguiente. (reposición). Además se incrementa el contador de días transcurridos. • Al finalizar la simulación en el tiempo (1 a 2 años) se calcula la cantidad de transductores que quedan (del último día de simulación: instante cualquiera). Y se verifica si esta cantidad es mayor o menor que 10. Si es menor o igual a 10 se incrementa un contador. Si es mayor el programa continúa con la siguiente iteración general sin hacer nada. • Al finalizar la cantidad de iteraciones generales seleccionada, el contador estará incrementado en la cantidad de veces que el programa encontró que el número de transductores era menor o igual a 10. Por lo tanto para obtener la probabilidad requerida se resuelve el siguiente cálculo:

Análisis y supuestos de algoritmo para la probabilidad de que la existencia de transductores sea mayor a 40 después de la reposición Para encontrar esta probabilidad se implementó el siguiente algoritmo: • Se escoge una cantidad de iteraciones generales. Cada una de estas iteraciones contiene los pasos que se describen a continuación: • Se realiza un estudio escogiendo como cantidad inicial de trasductores igual a 35 en bodega. Este número no tendrá mayores implicancias ya que el estudio durará entre 1 y 2 años (escogido aleatoriamente para 15

cumplir la condición en un instante cualquiera a largo plazo). Por lo cual se puede considerar como un estudio a largo plazo que no dependerá de la condición inicial (además es una cadena irreductible con distribución estacionaria). Claro está que los resultados no serán perfectos. • Se calcula la cantidad de pedidos de medidores durante un día cualquiera. Esto considerando las probabilidades de realizar 2 pedidos o 1 pedido. Y tomando el tiempo entre llegadas de órdenes como una variable aleatoria exponencial a tasa 2 [ordenes/hora]. El tiempo en que pueden llegar órdenes es de 7 horas. • Al final de cada día (luego de las 7 horas de recibir órdenes) se calcula la cantidad de medidores que quedan y se toman las decisiones apropiadas para el día siguiente. (reposición) Además se incrementa el contador de días transcurridos. • Al finalizar la simulación en el tiempo (1 a 2 años) se calcula la cantidad de transductores que quedan luego de la reposición (del último día de simulación: instante cualquiera). Y se verifica si esta cantidad es mayor o menor que 40. Si es mayor que 40 se incrementa un contador. Si es menor el programa continúa con la siguiente iteración general sin hacer nada. • Al finalizar la cantidad de iteraciones generales seleccionada, el contador estará incrementado en la cantidad de veces que el programa encontró que el número de transductores era mayor que 40. Por lo tanto para obtener la probabilidad requerida se resuelve el siguiente cálculo:

Intuitivamente se puede pensar que la probabilidad de encontrar más de 40 transductores al inicio de un día es un poco mayor que encontrar 10 o menos transductores al final del día. Ya que esta segunda probabilidad está incluida en la primera. (Ya que al haber 10 o menos transductores se reponen hasta llegar a 50 transductores, que es mayor que 40) Con esto queda demostrado el algoritmo a usar en el primer problema (Markov discreto) El cual se pasará a lenguaje computacional en C++. En el anexo se adjunta el programa en lenguaje C++, con sus respectivos comentarios indicando los pasos del algoritmo utilizado para cada variable de desempeño.

Capítulo Análisis de resultados 6 Cadena de Markov en tiempo discreto Empresa ELECTRONICA S.A. Resultados tiempo esperado En este problema obtener los resultados en forma analítica es un proceso muy largo y complejo. Por lo tanto sólo se obtuvo resultados por medio del computador. Los resultados del tiempo esperado, utilizando el algoritmo implementado para ello que utiliza iteraciones, son: Porcentajes de Error con respecto a 42 días

16

Se puede apreciar en la tabla que los valores rondan los 42 días aproximadamente. La tabla fue confeccionada utilizando distintas cantidades de iteraciones y por supuesto mientras más iteraciones se realicen más exacto es el resultado. Por lo tanto escogeremos como resultado ideal a 42 días (resultado de 50.000 iteraciones) A continuación se muestran gráficos que muestran de mejor manera los resultados. Un gráfico que muestra como se forma la recta de valores entre los días y las iteraciones y un gráfico que muestra el porcentaje de error tomando como resultado correcto los 42 días. En los gráficos se puede observar claramente que luego de las 500 iteraciones se puede llegar a un resultado razonable de la investigación. Esto hay que tomarlo muy en cuenta a la hora de simular un proceso, ya que mientras más iteraciones se realicen en la vida real (estudios reales) el costo se incrementa. Según estos resultados con 500 iteraciones basta para encontrar una solución acorde al problema. En cambio si sólo se realizaran 10 o 100 iteraciones se llegaría a un resultado bastante alejado y sobreestimado de alrededor de 46 días (10% error). El cual podría traer consecuencias a la hora de implementar la solución para la empresa. La empresa encuentra que por primera vez la demanda no se satisface luego de 42 días. Por lo cual para evitar estas pérdidas podría implementar un sistema de resguardo, dejando una cierta cantidad de transductores de reserva cada cierto intervalo de tiempo (menor a 42 días) para evitar las pérdidas de venta por falta de insumos. Resultados probabilidad de que existan menos de 11 transductores al final del día Los resultados de la probabilidad de que existan menos de 11 transductores, utilizando el algoritmo implementado para ello que utiliza iteraciones, son: Porcentajes de Error con respecto a 50000 iteraciones Se puede apreciar en la tabla que los valores rondan la probabilidad de 0.23 aproximadamente. La tabla fue confeccionada utilizando distintas cantidades de iteraciones y por supuesto mientras más iteraciones se realicen más exacto es el resultado. Por lo tanto escogeremos como resultado ideal a 0.23156 (resultado de 50.000 iteraciones) Que puede pensarse como infinito. A continuación se muestran gráficos que muestran de mejor manera los resultados. Un gráfico que muestra como se forma un recta aproximada por el número de iteraciones. También se muestra un gráfico que describe el porcentaje de error con respecto a las 50000 iteraciones. En los gráficos se puede apreciar que se llega a un resultado razonablemente exacto luego de las 1000 iteraciones. Ya que con menos iteraciones (10, 100 o 500) los porcentajes de error son considerablemente altos, en un orden desde 10% hasta 30%. Luego de las 1000 iteraciones el rango de la probabilidad se mantiene más o menos estables con algunos saltos en las 5000 y las 10000 iteraciones, regularizándose en las 25000 y 50000 iteraciones. El orden de la 17

probabilidad esta más o menos en 0.23. Esto es un indicativo para la empresa, que le lleva a concluir que un quinto de las reposiciones será del tipo de llegar hasta 50 transductores para el siguiente día. Ya que al tener menos de 11 transductores la empresa repone hasta llegar a 50 para comenzar las ventas al siguiente día. Con esto la empresa sabe cuales serán aproximadamente sus costos de reposición en parte del sistema. Resultados probabilidad de que existan más de 40 transductores al primcipio del día Los resultados de la probabilidad de que existan más de 40 transductores, utilizando el algoritmo implementado para ello que utiliza iteraciones, están dados por las siguientes tablas: Porcentajes de Error con respecto a 50000 iteraciones Se puede apreciar en la tabla que los valores rondan la probabilidad de 0.24 aproximadamente. La tabla fue confeccionada utilizando distintas cantidades de iteraciones y por supuesto mientras más iteraciones se realicen más exacto es el resultado. Por lo tanto escogeremos como resultado ideal a 0.23706 (resultado de 50.000 iteraciones) Que puede pensarse como infinito. A continuación se muestran gráficos que muestran de mejor manera los resultados. Un gráfico que muestra como se forma una recta aproximada por el número de iteraciones. También se muestra un gráfico que describe el porcentaje de error con respecto a las 50000 iteraciones. En los gráficos se puede apreciar que se llega a un resultado razonablemente exacto luego de las 1000 iteraciones. Ya que con menos iteraciones (10, 100 o 500) los porcentajes de error son considerablemente altos, en un orden desde 10% hasta 30%. Esta sobreestimación se debe a que se eligió un punto de partida fijo y que con el pasar de las iteraciones se hace despreciable su influencia. Luego de las 1000 iteraciones el rango de la probabilidad se mantiene más o menos estables con algún salto en las 10000 iteraciones. El orden de la probabilidad esta más o menos en 0.24. Se puede concluir que la suposición hecha en el capitulo 5 es apoyada por estos resultados. Ya que se aprecia que en todo momento la probabilidad de >40 siempre es mayor o en algunos casos igual a la probabilidad < 11, por lo cual se comprueba que los resultados obtenidos por medio de la simulación computacional esta de acuerdo al análisis analítico. La diferencia de probabilidades es pequeña (aprox. 0.005) Esta diferencia representa los casos en que habrán más de 40 transductores en la mañana y los pedidos fueron tan pocos que al final de ese día quedaron nuevamente más de 40. Queda claro que la probabilidad de que existan menos de 10 pedidos es pequeña (además al principio del día se debía cumplir que existieran más de 40, lo cual demuestra porque la diferencia de probabilidades es tan pequeña) Esta diferencia de probabilidades se muestra en la siguiente tabla de datos: Aquí se aprecia lo dicho con anterioridad, y además se reafirma que los datos comienzan a ser bastante correctos luego de las 1000 iteraciones, ya que aquí comienza a apreciarse una diferencia de probabilidades del orden de 0.005. 18

Esta probabilidad se puede expresar analíticamente como:

Con esto se finaliza el análisis de los resultados obtenidos de la simulación estocástica de las variables aleatorias involucradas en el problema. Cadena de Markov en tiempo continuo Empresa Manufacturera de tarjetas de crédito Por medio del algoritmo implementado para la solución de las fracciones de tiempo o probabilidades se encontraron los siguientes resultados de las probabilidades de cada estado. Las probabilidades calculadas vía desarrollo analítico fueron calculadas en el capítulo 4 y está expresadas en una tabla. En este capitulo sólo se mostrarán las diferencias porcentuales de las probabilidades y del las fracciones de tiempo. En esta tabla se tabulan todas las probabilidades para cada estado en estudios sucesivos de ½ año, 1 año, 2 años, etc En esta tabla se muestran los porcentajes de error con respecto a la tabla desarrollada en forma analítica en el capitulo 4 de este informe. Se aprecia claramente que mientras más años se simule la situación más cerca de los resultados correctos se está. Pero resulta ilógico realizar una simulación que dure 10000 años. Esto sólo se realizó para comprobar la efectividad del algoritmo implementado. Ahora se compararan las dos fracciones de tiempo pedidas (su fórmula para el cálculo está explicitada en el capítulo 5) Variable Desempeño/Año Fracción tiempo inventario Fracción tiempo reparando

Calculados Analíticamente 0,087768 0,912225

19