BITÁCORA: TEORÍA DE LINEAS DE ESPERA O COLA

domingo, 23 de octubre de 2011 - Publicado por Diana Marcela Polo en 23:56

Cada clase de Investigación de Operaciones se distingue por abarcar temáticas con numerables aplicaciones. En la semana del 17 al 21 de Octubre analizamos las características de una cola o linea de espera y comprobamos las diferentes situaciones en las que estas pueden ser estudiadas.


Cola o línea de espera:
  • Número de clientes que esperan ser atendidos
  • Turnos para la prestación de un servicio o ejecución de un trabajo
Una cola o linea de espera lleva un respectivo orden y admite un numero máximo permisible de clientes. Las colas pueden ser finitas o  infinitas.

La percepción del servicio de una cola puede explicarse a través del siguiente diagrama:



Donde el significado de las variables asociadas es el siguiente:

T= Tiempo  de un elemento en el sistema.
S= Tiempo en cola.

La percepción del servicio empieza desde el momento en que los clientes que requieren de un servicio determinado se generan a través del tiempo en una fuente de entrada (Entradas), estos clientes entran al sistema de colas y se unen a una cola. En determinado momento se selecciona un miembro de la cola, para proporcionarle el servicio. Una vez se lleva a cabo el servicio requerido por el cliente, este sale del sistema de colas.

Generalmente los modelos de colas, hacen la suposición de todos los tiempos de legadas y todos los tiempos de servicio so independientes e idénticamente distribuidos, por convención utilizan la notación de Kendall, así:

  


Donde:
M= Distribución exponencial (markoviana)   
D= Distribución degnerada (tiempos constantes
Ek= Distribución Erlang (parámetro de forma= k)
G=  Distribución general (Permite cualquier distribución arbitraria;  aquella que mejor se ajuste a los datos asociados).



                     
Se requiere cierta notación para describir los resultados del estado estable. Cuando un sistema de colas acaba de iniciar su operación, el estado del sistema, es decir el número de clientes en el sistema, se encuentra bastante afectado por el estado inicial y del tiempo que ha pasado desde el inicio. Se dice entonces que el sistema se encuentra en condición transitoria. Después que ha pasado un tiempo suficiente, el estado del sistema se vuelve, en esencia  independiente el estado inicial y del tiempo transcurrido, así se puede decir que el sistema ha alcanzado su condición de estado estable.    

La notación siguiente supone que el sistema se encuentra en la condición de estado estable:

L= Número de clientes en el sistema.
Lq = Número de clientes esperando en la cola.
W = Tiempo medio en el sistema (tiempo en el ciclo)
Wq = Tiempo medio en la cola.

                                      


Tipos de colas:


Colas Markovianas: Se basan en los procesos de muerte y nacimiento.



Muerte = Cliente sale del sistemas  -->  n = n -1 

Nacimiento = Cliente que entra al sistema .--> n = n + 1



Supuestos:





Una cola Markoviana es una cadena de Markov en tiempo continuo, donde el número de estados está representado por el número de clientes en el sistema en el instante t.
    





En el caso del estado “0”, hay “0” clientes, del uno, solo uno, y así sucesivamente.



Balance = Lo que entra debe ser igual a lo que sale.



                                                    Estado (0)





                                                        Entonces: 













El tamaño de una cola esta dado por:







Esta clase fue desarrollada a partir del análisis del articulo: "Teoría de colas de espera: Modelo integral de aplicación para la toma de decisiones", a continuación presentamos un resumen que resalta lo mas importante del mismo:


La teoría de colas es un método en la investigación de operaciones que se basa en el estudio de las líneas de espera de diferentes tipos. Para aplicarla, tienen en cuenta los factores subjetivos y objetivos en los problemas, además de las evaluaciones  dadas para su solución.

Hay tres formas de resolverlos:
  • Análisis subjetivo: Cuando se toman las decisiones ‘al ojo’, sin usar ningún tipo de cálculo. 
  • Método matemático: Mediante modelos descriptivos y estadísticos (puede ser para casos infinitos o finitos).
  • Técnica de simulación: Se utiliza cuando no se puede hallar una solución por medio del 2do.

Para el caso de los factores objetivos, se utilizan los modelos matemáticos, los cuales analizan  los 4 tipos de colas que se pueden dar:



1 cola: 1 servidor (consulta con especialista).

1 cola: Varios servidores en paralelo (cajas en un banco).

Varias colas: Múltiples servidores (peaje).

Servidores en serie antes de salir del sistema (fila que le toca a uno hacer en Aduana para ir de Colombia a EE.UU.)
Al ya saber qué tipo es, se tienen en cuenta ciertas consideraciones como de dónde son las personas en la cola, ingreso en el sistema (individual o grupal), disciplina de la cola, entre otros. Por último, ven las diferentes restricciones (llegadas aleatorias o individuales, espacio, atención primero en llegar primero en salir, y muchas más).

No obstante, hay veces que los aspectos subjetivos valen más que los objetivos, entre ellos vemos:

  • Percepción del servicio: Difiere entre el tiempo real (cuánto ha pasado en la cola en realidad) y el  subjetivo (cómo lo siente el cliente) que dependerá  de aspectos como la personalidad del cliente, distractores mientras espera, comodidad ambiental y percepción de ineficiencia en el servicio. Demostrando nuevamente que “el tiempo es relativo”.
  • Aspectos sociales y culturales: Interpretación de cada uno en el momento. Ej: Para algunos “el tiempo es oro”, mientras otros lo lo ven distinto.
  • Eficiencia y satisfacción: Hay que saber cuán satisfecho está el cliente con el servicio y no solo pensar en lo que la eficiencia (“hacer lo mismo con menos”) numérica me indica.

La conjunción de todo lo visto, según el caso que se presente, busca como resultado minimizar los costos, aunque nunca se llegue a la máxima solución óptima; poniendo el caso de los supermercados, si tienen todas las cajas abiertas al público a las 7 am, daría un sobrecosto de personal al haber horas ociosas, demostrando así una mala planeación. Solo se podrá llegar a la probabilidad más cercana de obtener una calidad total si se tiene un equilibrio entre aspectos subjetivos positivos del cliente, servidores y  datos satisfactorios tomados de factores objetivos.  




Vídeo Clase de Investigación de Operaciones 2 ;19-OCT-2011


Modelos para Determinar Tamaños de Lote

miércoles, 19 de octubre de 2011 - Publicado por Diana Marcela Polo en 23:08
Consiste en el análisis de varios productos ubicados en lotes de diferentes                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                tamaños (capacidad) con diversos niveles, además de esto se comenta  acerca de la programación dependiente de la secuencia en las configuraciones. Comúnmente es usado un modelo de programación mixto el cual no es práctico para encontrar pequeñas instancias del problema, MIP está basado en la heurística, la cual por medio de 2 límites se comprueba su exactitud para la obtención de una solución óptima. Cabe resaltar que existe una proporción entre la calidad del programa y el tiempo de cálculo de la heurística.


Los Problemas de  tamaños de lotes y  la programación han sido un área de investigación activa a partir del estudio seminal de Wagner y Whithin (1958) . Desde entonces ha habido una cantidad considerable de investigaciones con el fin de incorporar otras características importantes. 
Las características mas notables en los modelos de tamaños de lotes y su programación  son la aplicación de un horizonte de planificación, una dependencia temporal que tienen los parámetros del modelo, el número de productos, las etapas de producción, la estructura.productiva y la capacidad de las restricciones.


Los modelos de tamaño de lotes y su programación están dividíos en 2 tipos: cubeta pequeña y grandes problemas de la cuchara. Los problemas de la cubeta pequeña rompen el horizonte de planificación en periodos de tiempo pequeños, en consecuencia si una instalación se lleva a cabo, el intervalo de tiempo solo debe ser dedicado a este. En otras palabras, las configuraciones que se realicen y los ciclos de producción forman parte de un número entero de intervalos de tiempo, este modelo es aplicable a los problema de programación (MLDLSP) en el cual el  tamaño de lote es proporcional de niveles múltiples y la programación de problemas (MLPLSP) Ambos modelos permiten tamaños de lotes simultáneos y la programación, pero limitar el número de productos a ser fabricados en un período. 

Este estudio trata de los modelos deterministicos dinámicos con un horizonte de planeación finito, en lo referente a la producción de diferentes productos en serie, máquinas dispuestas con capacidad. Cuando el tamaño de los lotes se considera eficiente se dice que el problema es difícil, por lo tanto se requiere que su modelado sea por medio de  programación entera mixta (MIP). 
Los tamaños de lotes  simultáneos y la programación dependen de la secuencia de los costos de instalación y los tiempos de preparación que se producen durante la producción.Por lo tanto, como el TSP (Traveling Salesman Problem), el CLSP (…) con dependientes secuencia configuraciones también pertenece a un conjunto de problemas que son llamados NP-hard. Esto significa que es muy difícil de resolver de manera óptima los casos gran parte del problema. De hecho, el tiempo de solución aumenta exponencialmente, ya sea el número de variables y aumentar las restricciones. La introducción de multi-nivel de producción hace que el problema aún más complicado. Por lo tanto, es necesario encontrar soluciones razonables heurístico para casos medianos y grandes. También es importante desarrollar una baja computable ligado con el fin de probar la exactitud de la heurística. 



Ambos modelos tiene la ventaja de fijar los tamaños de lotes y horarios simultáneamente, pero con la desventaja que no pueden hacer tantos productos en un periodo de tiempo, lo que el modelo de multinivel para establecer el tamaño de lote  (MLCLSP: Multilevel Capacitated Lotsizing Problem)  sí tiene. Por ello se creó un problema de programación integral mixta (MIP por sus siglas en inglés) que combina lo mejor de ‘ambos mundos’ del que se hablará más adelante.
Los modelos CLSP y TSP son muy difíciles de resolver en casos largos del problema de una manera óptima. Por ello, se llegó a la conclusión que para la resolución de éstos, podíamos obtener una respuesta mediante soluciones heurísticas, lo que es más fácil por medio de un límite inferior calculable que midiera la exactitud  de la heurística.
Como sabemos hay ciertas dudas sobre algunos temas que explicaremos en el siguiente orden:
  • Cotas inferiores.
  •   Heurísticas.
  •   Experimento numéricos.



Desarrollo de la Heurística
Rolling-horizon heuristics, más conocido como  heurística horizonte rodante, suele utilizarse en lotsizing (modelo de tamaño del lote dinámico) el cual es una generalización de la orden de la cantidad económica que el modelo tiene en cuenta, para que la demanda del producto varíe con el tiempo. y en los problemas de programación. Donde las demandas son gradualmente reveladas durante el horizonte de planificación al igual que los tipos de piezas que se asignarán a las máquinas de manera continua a medida que llegan nuevas órdenes. Aquí el enfoque de rodadura toma un papel importante ya que  se guían mediante parámetros perfectamente conocidos.
El enfoque adoptado inicialmente descompone el modelo en una sucesión  de pequeños precios mínimos. Todos con un número asequible de variables binarias. Cada enfoque rodadura horizonte descompone la planificación
horizonte en tres secciones  para una iteración dada k: 
1.)  La primera iteración se compone de los (k - 1) primeros períodos. Aquí las decisiones han sido parcial por las anteriores iteraciones de acuerdo a una estrategia de congelación ya seleccionada.
2.)  La segunda incluye el K – esimo periodo.
3.)  Y la tercera y última incluye los últimos periodos desde el periodo k +1 para x periodo. El proceso se detiene cuando ya no hay sección final hay que tener cuidado  porque la ultima iteración define las variables de decisión sobre el horizonte.








Conclusión:
En conclusión, todas las heurísticas tienen un pro y un contra dependiendo del tipo de problema que se quiera resolver. Demostrando así que aún no hay una solución óptima para cualquier problema (pequeño, mediano o grande), por medio de una heurística en general. 

Referencias:
- http://translate.google.com/translatehl=es&langpair=en|es&rurl=
translate.google.com.co&u=http://scialert.net/fulltext/%3Fdoi%3Djas.2009.296.303#67520_ja <
-http://knol.google.com/k/jairo-rafael-coronado-h/modelos-para-determinar-tama%C3%B1os-de-lote/fsr3rs45g58n/6#

¡Entrevista a José Jiménez!

domingo, 9 de octubre de 2011 - Publicado por Diana Marcela Polo en 19:10

A lo largo de la historia, Cartagena de Indias ha sido una ciudad muy importante siendo reconocida por sus hermosas playas, Castillo San Felipe de Barajas y murallas que el mismo rey de España una vez preguntó si podría verse desde allá. Actualmente algunos de los sectores en los que se destaca son: petroquímico plástico, turismo, logística para el comercio exterior, agroindustria y diseño de construcción y reparación de embarcaciones navales. Gracias a este último, la ciudad es preferida por muchas embarcaciones a nivel nacional e internacional, mas no significa que  no lo haya venido siendo desde hace mucho, puesto que desde fundada, ha sido reconocida como un puerto importante en todo el continente Americano.

Actualmente uno de los mayores terminales marítimos es la Sociedad Portuaria, la cual en los últimos años  ha venido implementando diversas herramientas operativas para ser más competitiva, lucrativa y productiva. Entre ellos podemos destacar la investigación de operaciones junto con softwares para la toma de decisiones.
Para saber más sobre el tema le hicimos una entrevista a José Jiménez, superintendente de la SPRC. Seguidamente mostramos un poco de su vida:

Estudió administración marítima en la escuela naval y luego ciencias náuticas. Adicionalmente hizo la maestría con la UTB y durante 8 años se fue a navegar Latinoamérica, Europa y Asia. Tiene 23 años de experiencia en el tramo portuario, marítimo y logístico. En el presente controla las operaciones terrestres y marítimas de CONTECAR, además de ser catedrático del programa de logística de la UTB.

Pudimos darnos cuenta, por medio de las explicaciones que nos dio él, que la mayoría de los problemas de transporte en el sector de manga, donde se encuentra la Sociedad Portuaria, no es a causa de ésta, ya que continuamente hay flujo de tractomulas. ¡Sin más preámbulos la entrevista!




REFERENCIAS

http://cisne.puertocartagena.com/opadmco.nsf/vstRefLinkDoc/72F387B7240ACAC1052573B5004DC5A3

General Algebraic Modelling System (GAMS)

domingo, 2 de octubre de 2011 - Publicado por Diana Marcela Polo en 14:11
El nombre GAMS se deriva de las iníciales de General Algebraic Modelling System, que como su propio nombre indica es un lenguaje de modelización, más que un programa para resolver problemas de optimización. La ventaja que presenta este programa, es que junto al módulo de modelización (base) incorpora diferentes solver (algoritmos de resolución de problemas) tanto de programación no lineal, como lineal y entera.

El lenguaje GAMS posee diferentes versiones (estudiante, profesional, workstation, mainframe, etc.) que se diferencian básicamente en las posibilidades de resolución de problemas de diferente tamaño, así por ejemplo, en la versión básica de estudiante existen una serie de limitaciones en cuanto al tamaño del problema que admite un máximo de 1000 elementos distintos de cero en los problemas lineales y no lineales, y de 20 variables enteras. Estas limitaciones no son importantes para los ejercicios prácticos que se desarrollan en las clases.

Una de las grandes ventajas de GAMS es la facilidad de migrar a versiones superiores ya que el formato general es idéntico tanto en un PC como en un supercomputador en paralelo. Otra de las ventajas es también la capacidad de resolver diferentes versiones de un mismo modelo, tanto como problema no lineal, lineal y entero, y el poder usar diferentes solvers.
De entre ellos podemos citar los siguientes:

Problemas
Solver
NLP
CONOPT, MINOS, etc.
LP
OSL, CPLEX, MINOS, BDMLP, XA, etc.
MIP
OSL, ZOOM, CPLEX, XA; etc.
MINLP
DICOPT

Además, dentro de cada uno de estos solver, se pueden elegir diferentes opciones. Por ejemplo, para resolver los problemas lineales con la librería OSL, podemos elegir los siguientes algoritmos:                           




Características del Sistema GAMS


Los modelos pueden ser desarrollados y documentados de forma simultánea puesto que GAMS permite al usuario incluir un texto explicativo, como parte de la definición de cualquier símbolo o una ecuación.





ESPECIALISTAS EN SOLUCIÓN……




Tipos de modelos

GAMS puede modelar diferentes tipos de problemas lo que quiere decir que es muy fácil cambiar de un tipo de modelo a otro sin muchas complicaciones. Tanto es, que se puede utilizar la misma información, índices, parámetros, variables, ecuaciones, y restricciones en diferentes modelos, ¡todo al mismo tiempo!


Algunos de los modelos que se pueden hacer con GAMS son:


LP: Programación Lineal.

MIP: Programación Entera Mixta.

NLP: Programación No Lineal.

MCP: Problemas de Complementariedad Mixta.

MPEC: Programación Matemátia con Restricciones de equilibrio.

CNS: Sistemas No Lineales Restringidos

DNLP: Programación No Lineal con Derivadas Discontinuas.

MINLP: Programación No Lineal Entera Mixta.

QCP: Programación con Restricciones Cuadráticas.

MIQCP: Programación Entera Mixta con Restricciones Cuadráticas.



Esta tabla muestra que tipo de solver es capaz de hacer alguno de estos 10 tipos de modelos básicos:


          Matriz tomada de: http://www.gams.com/modtype/index.htm



Documentación en línea

En la página de GAMS, www.GAMS.com  , si lo desean pueden descargar la documentación sobre GAMS.
En la siguiente tabla se encuentran los diferentes links para descargar la información que se desea.

DOCUMENTO
link
Tutorial GAMS
GAMS-Guía de Usuario
Notas de instalación para Windows
Notas de instalación para Unix y Mac
Notas sobre la versión
Nota: los documentos se encuentran en Ingles.

A continuación se muestra una lista de Solvers con los que cuenta GAMS:



 APORTES REALIZADOS POR PERSONAS QUE TRABAJAN CON GAMS




Al trabajar con GAMS podemos ver que es muy fácil escribir texto y que este texto será ignorado por GAMS, si le decimos que es un comentario y eso lo indicamos con un asterisco (*) en el inicio de la línea. Este símbolo es de hecho nuestra primera instrucción en GAMS. Los comentarios son útiles para documentar los procedimientos que se siguen, y es una buena práctica utilizar frecuentemente comentarios aclaratorios. Si nos olvidamos de añadir un asterisco, entonces GAMS detecta un error y nos lo dice. (Ver la figura adjunta en la que añadimos otros comentarios). 
En este caso el usuario se le olvido el asterisco en la última línea. GAMS  dice que detecta errores y le informa qué tipo de error es probable que se este cometiendo, al dar click en el mensaje de error se envía a la línea donde se ha detectado el error, a fin de que el usuario intente depurarlo. 


GAMS a contribuido a la solución de diferentes problemas asociados a la economía, Rob Dellink es el autor de un importante libro, que deja en claro  la actividad económica, mediante los diferentes modelos aplicados.

Ramón Sala-Garrido; GAMS Documentation in Spanish

Ejercicios Resueltos con GAMS
              >>>    http://www.uv.es/~sala/gams/Lineal01.pdf


Implementación de GAMS para la solución de un modelo:

Subasta combinatoria

En algunas subastas los elementos aparecen agrupados por paquetes no necesariamente disyuntos y la oferta que hace el posible comprador por cada paquete no es la suma de los precios de sus elementos, puede ser mayor o menor.


                                  
En Gams:



La solución es:        x = (1,1,1,0,0,0),     z = 21     





Video guía sobre cómo manejar GAMS






GAMS Timeline



En el siguiente link  podrás encontrar  una gran variedad de presentaciones de GAMS, sobre diversas temáticas para complementar la línea de tiempo.