investigación de operaciones Archivos - Página 4 de 26

Qué son las Líneas de Espera (Teoría de Colas)

En el artículo Qué es la Ley de Little y su aplicación en el análisis de Líneas de Espera describimos algunos elementos básicos asociados al estudio de líneas de espera como la población de referencia (finita o infinita), distribución de los tiempos entre llegadas (usualmente se distribuyen de forma exponencial, satisfaciendo la Propiedad de Falta de Memoria o Amnesia de la Distribución Exponencial), disciplina del servicio (FIFO, Prioridad, etc), entre otros elementos. A continuación buscaremos ahondar en dichos fundamentos buscando responder ¿Qué son las Líneas de Espera?.

En dicho contexto considere la siguiente pregunta: Un pequeño almacén tiene un solo vendedor que atiende en promedio a 12 clientes por hora (es decir su capacidad es µ=12[/c/h]), atendiendo de un cliente a la vez. La llegada de los clientes al almacén es a una tasa promedio de 10 clientes por hora (λ=10[/c/h]). ¿Hay filas en el almacen? (clientes esperando por su atención). Probablemente muchas personas respondan que no, pero la respuesta correcta es: depende.

Un ejemplo que permite evidenciar lo anterior es el siguiente. Un proceso como el que se describió en la pregunta anterior (almacén) que recibe 12 clientes por hora (λ). La columna Arrival Time detalla el minuto en el cual el cliente llega al almacén (asumamos que estamos evaluando desde las 07:00 a las 08:00, es decir, el primer cliente llega a las 07:00, el segundo a las 07:07 y así sucesivamente). Finalmente la columna Service Time detalla el tiempo que el vendedor se demora en atender al cliente (al calcular el promedio de los valores de dicha columna se observa que es 4,083 minutos, es decir, µ=14,69[/c/h] aproximadamente). Luego la utilización promedio del servidor (vendedor) es ρ=λ/µ=0,8167< 1. Los detalles de este procedimiento se puede consultar en el artículo Cómo calcular la Utilización de un servidor, Tiempo de Espera y Tiempo de Flujo de una Línea de Espera.

No obstante si analizamos en detalle del proceso de espera anterior podemos observar lo siguiente:

Los clientes 3, 4, 5, 6, 7, 8 y 9 debieron esperar antes de ser atendidos por el vendedor aun cuando la utilización (promedio) del mismo es menor a 1. En el gráfico de barras adicionalmente se observa la cantidad de clientes en el sistema para un instante del tiempo dado (esto considerando tanto el cliente que eventualmente pueda estar siendo atendido más los que eventualmente están esperando por su atención). Por ejemplo a las 07:31 se esta atendiendo al cliente 5 y están esperando en fila los clientes 6, 7 y 8 (es decir, hay 4 clientes en el sistema). Luego la conclusión que podemos generalizar en este caso es:

Si existe variabilidad en las llegadas de los clientes al sistema y/o en las atenciones (tiempos de servicio), entonces hay colas o filas (aunque de largo finito). Esto a pesar de que λ<µ, o sea, de que ρ< 1. Si λ>µ el sistema es inestable (se generan colas infinitas).Dicho de otra modo la existencia de colas o filas en un sistema se deben a la variabilidad y no al hecho de que λ>µ (ρ> 1).

Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA

El software TORA es una excelente herramienta para resolver de forma intuitiva distintos modelos y aplicaciones de la Investigación Operativa. TORA está incluido en un CD (Compact Disc) adjunto al libro Investigación de Operaciones de Hamdy Taha y es compatible aún con las últimas versiones disponibles de Windows. Al respecto en el siguiente artículo se muestra su uso en un computador con sistema operativo Windows 7 Home Premium de 64 bits. para abordar la pregunta Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA. Adicionalmente el libro de Investigación de Operaciones de Hamdy Taha puede ser adquirido en sus versiones en español e inglés a precios convenientes desde distintos portales de comercio electrónico como Amazon.

Luego de su instalación y previo a su utilización es necesario realizar un ajuste a la resolución de pantalla seleccionando alguno de las 2 opciones recomendadas: 800×600 o 1024×786 pixeles (en realidad en este último caso 1024×768 como se podrá observar abajo). Para ello se debe ir al Panel de Control.

A continuación seleccionamos la resolución 1024×768 pixeles y Aplicar.

Luego se despliega una ventana que nos solicita confirmar nuestra selección anterior. En este caso debemos Conservar Cambios.

Una vez que el cambio en la resolución de pantalla ha sido ejecutado abrimos el programa TORA y se procede seleccionando el botón Click Here.

Una vez en el menú principal podemos seleccionar un importante número de funcionalidades relativas a la Investigación Operativa que se tratan en el libro de Hamdy Taha y donde TORA resulta ser un excelente complemento para el aprendizaje de los estudiantes. En esta oportunidad mostraremos cómo resolver un modelo de Programación Lineal por ello seleccionamos la opción Linear Programming.

En el menú que se despliega ingresamos el nombre o título del problema, la cantidad de variables y restricciones (aquellas adicionales a las de no negatividad).

En este tutorial utilizaremos el mismo ejemplo que implementamos en el artículo Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial, un problema que tiene 2 variables de decisión y 5 restricciones (donde 2 de ellas son las de no negatividad).

Luego se completan los parámetros de la grilla con la información relativa al ejemplo que nos interesa resolver tal como se observa en la siguiente imagen:

Una vez ingresados los datos del problema se selecciona Solve Menu, Solve Problem y Graphical.

En la ventana a continuación se nos pide confirmar la cantidad de decimales. En este caso mantendremos los valores que ofrece el programa por defecto y seleccionamos Go To Output Screen.

Finalmente llegamos a la interfaz que permite realizar una representación gráfica del modelo lineal. Para graficar las restricciones se debe seleccionar cada una de ellas de forma individual y finalmente marcar la función objetivo que mostrará el desplazamiento de la curva de nivel que permite alcanzar la solución óptima y valor óptimo (visible en la esquina inferior izquierda de la siguiente imagen). En próximos artículos seguiremos mostrando funcionalidades adicionales de TORA, hasta entonces.

Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial

Los modelos de Programación Lineal han sido motivo de amplio estudio en nuestro Blog y en esta oportunidad queremos presentar a nuestros usuarios una herramienta computacional sencilla e intuitiva llamada IORTutorial (Interactive Operations Research Tutorial) la cual nos permite resolver gráficamente modelos de Programación Lineal con 2 variables de decisión, además de proporcionar informes de sensibilidad para complementar la interpretación de los resultados alcanzados.

Para ello consideremos el ejemplo descrito en el artículo Cálculo del Intervalo de Variación del Lado Derecho que conserva la Base Óptima que permitirá al lector contrastar los resultados alcanzados en dicho ejemplo con el procedimiento alternativo que presentamos a continuación a través del uso de IORTutorial. El ejemplo en cuestión que considera 2 variables de decisión y 5 restricciones (considerando las 2 de no negatividad) es el siguiente:

La implementación computacional se muestra en el siguiente tutorial disponible en nuestro canal de Youtube que detalla Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial:

Cabe destacar que los resultados que se observan en el Informe de Sensibilidad (o Análisis de Sensibilidad) son equivalentes a los obtenidos en la resolución con Solver de Excel como se muestra en la imagen a continuación:

Problema de Explotación de Minas y Transporte de Carbón a Puertos

Es frecuente reconocer en los problemas de optimización que representan una estructura productiva, un componente de costo fijo asociado a la utilización de un recurso (dentro de un intervalo de producción relevante) y un costo variable que que asume proporcional al nivel de actividad que represente la unidad productiva (por ejemplo, lo que se refiere a costos de producción, costos de transporte en una red logística, entre otros). Por ejemplo, el Problema de Inclusión de Costos Fijos en Programación Entera representa una situación muy sencilla de lo anteriormente descrito.

En este contexto a continuación se presenta un problema de operación de minas de carbón que su simple utilización tiene asociado un costo fijo, además de incurrir en costos variables por concepto de producción y transporte a distintos puertos demandantes, que adicionalmente tienen requerimientos particulares sobre la calidad del producto recepcionado.

Problema de Explotación de Minas y Transporte

La compañía ABC puede explotar hasta tres minas de carbón y debe realizar envíos a tres puertos. El costo por tonelada de producción (en dólares), el costo fijo de operación en dólares (en caso de ser utilizada), los contenidos de una cierta clase de ceniza y de sulfuro por tonelada y las capacidades de producción (en toneladas de carbón) se resumen en la siguiente tabla:

Por su parte, las toneladas demandadas que deben ser enviadas a cada puerto, conjuntamente con los costos de transporte (en dólares por tonelada) se dan en la siguiente tabla:

Formule y resuelva un modelo de optimización que permita determinar la eventual operación de cada mina y sus niveles de producción, de modo de satisfacer los requerimientos de demanda y que las cantidades enviadas a cada puerto contenga a los más un 4,5% de ceniza y a lo más un 3% de sulfuro.

Variables de Decisión:

Parámetros:

Función Objetivo: Se desea minimizar los costos asociados a la explotación de las minas, el costo de producción del carbón y los costos de transporte del carbón enviado desde las minas a los puertos.

Restricciones:

Capacidad de Producción de las Minas: cada mina puede operar a su capacidad máxima de producción para abastecer los requerimientos de los distintos puertos en caso en que se decida realizar funciones de explotación en la misma.

Demanda de Carbón los Puertos: cada puerto debe recibir la cantidad de toneladas de carbón que demanda.

Máximo Porcentaje de Ceniza admitido por cada Puerto: cada puerto esta dispuesto a recibir como máximo un 4,5% de ceniza en los envíos de carbón que recibe desde las minas. En este caso se expresa dicha condición de forma general a través de parámetros.

Máximo Porcentaje de Sulfuro admitido por cada Puerto: similar al caso anterior pero estableciendo un límite máximo al porcentaje de sulfuro que admite cada puerto (en el ejemplo un 3%).

No Negatividad: las toneladas producidas en las minas y transportadas a los puertos naturalmente deben satisfacer las condiciones de no negatividad.

A continuación de presenta un extracto de la implementación computacional del modelo anterior haciendo uso de Solver de Excel junto a un tutorial de nuestro canal de Youtube con los detalles de la resolución:

Se puede observar que sólo se utilizan las minas 1 y 3. La mina 1 envía 35, 45 y 30 toneladas al Puerto 1, 2 y 3, respectivamente. En el caso de la mina 3, ésta envía 35, 35 y 30 toneladas a los Puertos 1, 2 y 3, respectivamente. La demanda en toneladas de carbón es satisfecha en los puertos y se respeta adicionalmente la capacidad máxima de producción de las minas. Adicionalmente se puede observar en color verde el porcentaje de ceniza o sulfuro (según sea el caso) que recibe cada puerto lo cual satisface las condiciones expuestas. Finalmente el valor óptimo, es decir, el costo mínimo asociado al plan de producción y transporte descrito es de 14.550 dólares.

¿Quieres tener el archivo Excel con la implementación computacional de este problema?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

¿Cómo elegir los invitados de una Boda o Matrimonio con un modelo de Programación Entera?

Elegir los invitados a una boda (matrimonio) no es asunto fácil. Se debe respetar un presupuesto, cumplir compromisos familiares, compatibilizar los invitados de las distintas familias, incluir amigos y compañeros de trabajo y evitar incompatibilidades entre los invitados. El siguiente problema corresponde a una aproximación simplificada a la situación anterior a través de un modelo de Programación Entera. Por cierto las condiciones a incorporar en un problema de esta naturaleza pueden considerar aspectos adicionales como los comentados anteriormente.

Asuma que usted trabaja en una consultora matrimonial y su tarea es seleccionar los invitados para una boda. Tanto la novia como el novio están muy complicados porque tienen amigos que no pueden estar juntos. Los novios han asignado a cada invitado un valor en unidades matrimoniales (u.m) según lo siguiente:

Existen ciertas incompatibilidades que se deben considerar en la planificación que usted como consultor propondrá:

Juan Pérez no asistirá al menos que Luis Toro asista.
Juan Pérez no asistirá si tanto Pedro Soto y María González asisten.
Pedro Soto no asistirá si Gloria Pérez asiste.
Pedro Soto sólo asistirá si María González y Luis Toro asisten.

Formule y resuelva un modelo de Programación Entera que permita determinar a qué personas invitar de modo de lograr la mayor puntuación en unidades matrimoniales.

Variables de Decisión:

Con i=1,2,3,4,5 que representan a Juan Pérez, Pedro Soto, María González, Luis Toro y Gloria Pérez, respectivamente.

Función Objetivo:

Se desea encontrar la selección de invitados a la boda que permita maximizar la puntuación en u.m.

Restricciones:

Juan Pérez no asistirá al menos que Luis Toro asista: $X_{1}\leqslant X_{4}$
Juan Pérez no asistirá si tanto Pedro Soto y María González asisten: $2-(X_{2}+X_{3})\geq X_{1}$
Pedro Soto no asistirá si Gloria Pérez asiste: $X_{2}+X_{5}\leq 1$
Pedro Soto sólo asistirá si María González y Luis Toro asisten: $X_{2}\leqslant X_{3}$ y $X_{2}\leqslant X_{4}$ . En este conjunto de restricciones se entiende que si María González y Luis Toro asisten, Pedro Soto podría asistir. Si al menos uno de los 2 falta (María o Luis) entonces Pedro no asiste.

Al implementar el modelo anterior en Solver de Excel se alcanza un valor óptimo de 800 u.m el cual corresponde a invitar a Pedro Soto, María González y Luis Toro (solución óptima).