excel Archivos - Página 10 de 19 - Gestión de Operaciones

Problema de la Mochila en Programación Entera resuelto con OpenSolver

El Problema de la Mochila (conocido también como Knapsack Problem o simplemente KP) es un problema clásico de la Investigación de Operaciones y en particular de la Programación Entera. Consiste en un excursionista que debe preparar su mochila, la cual tiene una capacidad limitada y por tanto no le permite llevar todos los artículos que quisiera tener en la excursión. Cada artículo que el excursionista puede incluir en la mochila le reporta una determinada utilidad. Luego el problema consiste en seleccionar un subconjunto de objetos de forma tal que se maximice la utilidad que el excursionista obtiene, pero sin sobrepasar la capacidad de acarrear objetos.

En este contexto existen varias aplicaciones que guardan una similitud conceptual con el Problema de la Mochila y en consecuencia nos podemos beneficiar de la formulación y resolución de un modelo de optimización matemática para dicho propósito. Consideremos el siguiente ejemplo:

Problema de la Mochila

Un armador tiene un carguero con capacidad de hasta 700 toneladas. El carguero transporta contenedores de diferentes pesos para una determinada ruta. En la ruta actual el carguero puede transportar algunos de los siguientes contenedores:

El analista de la empresa del armador desea determinar el envío (conjunto de contenedores) que maximiza la carga transportada. Para ello se propone el siguiente modelo de Programación Entera:

Variables de Decisión:

Función Objetivo: Consiste en maximizar la carga que transportará el carguero.

Restricciones: El peso de la carga transportada no puede exceder la capacidad máxima del carguero.

Al implementar computacionalmente el problema anterior haciendo uso de OpenSolver se alcanzan los siguientes resultados:

La solución óptima consiste en transportar los contenedores C1, C2, C3, C4, C8, C9 y C10, con un valor óptimo de 700 (toneladas), es decir, se utiliza la capacidad completa del carguero. Notar que otra solución óptima consiste en transportar los contenedores C1, C3, C4, C5, C6, C7, C8 y C9 lo que reporta un similar valor en la función objetivo.

¿Quieres tener el archivo Excel con la resolución en OpenSolver de este problema?. Recomiéndanos en Facebook o Google+ utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo.

[sociallocker]Problema Mochila[/sociallocker]

Ejemplo de Gráfica de Control P o de Proporciones en el Control Estadístico de Procesos

La gráfica de control de proporciones o gráfica p corresponde a una herramienta del Control Estadístico de Procesos (CEP) utilizada particularmente en la evaluación del cumplimiento de determinadas características del producto que son fáciles de evaluar (con frecuencia mediante inspección visual) asumiendo sólo 2 valores posibles: “cumple” o “no cumple”, “aprobado” o “no aprobado”, etc. Utilizar datos de atributos requiere de muestras relativamente grandes para obtener resultados estadísticos válidos. En el siguiente artículo de describe el procedimiento para la confección de una gráfica p utilizando distintos niveles de significancia estadística al momento de definir los límites de control.

Ejemplo Gráfica de Control P

Todos los días se tomaban muestras de las formas llenas, de un departamento en particular, en una compañía de seguros para revisar la calidad del desempeño de ese departamento. Con el fin de establecer una norma tentativa para el departamento, se tomó una muestra de 300 unidades al día (n=300) durante 10 días, obteniendo los siguientes resultados:

Desarrolle una gráfica de proporciones o gráfica p utilizando un intervalo de confianza de un 90% para las 10 muestras recolectadas. ¿Qué comentarios puede hacer sobre el proceso?. ¿Qué sucede ahora si los límites de control se definen a un σ del promedio de defectos?.

En primer lugar calculamos el promedio de unidades defectuosas para cada una de las muestras (celdas color celeste). Por ejemplo la muestra 1 presenta 10 defectos (de un total de 300 unidades inspeccionadas), en consecuencia el porcentaje de defectos de dicha muestra corresponde aproximadamente a un 3,33% (10/300). Luego se obtiene el promedio de unidades defectuosas del total de las muestras (celda amarilla) correspondiente a un 3,03% (se obtiene de [3,33%+2,67%+3,00%+…+2,67%]/10).

A continuación se procede con la estimación de la desviación estándar (Sp):

De la tabla de la distribución normal estándar un intervalo de confianza de un 90% equivale a definir los límites de control a 1,645*Sp. Con esto podemos calcular el Límite de Control superior (LCS) y Límite de Control Inferior (LCI) respectivamente (notar que los resultados han sido aproximados).

LCS = 3,03% + 1,645*0,9896% = 4,66%
LCI = 3,03% – 1,645*0,9896% = 1,40%

A continuación y con la ayuda de Excel se procede a graficar los límites de control (líneas verdes y violeta), el promedio de unidades defectuosas de cada una de las muestras (línea azul) y el promedio de defectos total (línea roja). El proceso se encuentra bajo control estadístico. Los promedios de defectuosos se encuentran dentro de los límites de control estadístico.

Si en cambio los límites de control se definen a un σ del promedio de defectos será necesario recalcular los límites de control estadístico obteniendo los siguientes resultados (aproximados):

LCS = 3,03% + 0,9896% = 4,02%
LCI = 3,03% – 0,9896% = 2,04%

Al estrechar los límites de control el proceso ya no se encuentra bajo control estadístico. La muestra n° 4 presenta un porcentaje de defectuosos mayor al LCS.

Cómo determinar la Duración Óptima de un Proyecto a través del Análisis de Crashing

La Programación Lineal como hemos analizado anteriormente provee una forma eficiente para enfrentar el problema de cómo reducir la duración de un proyecto de la forma más económica posible (Análisis de Crashing) en el contexto de la aplicación del Método de Ruta Crítica (CPM) para la gestión de proyectos. Adicionalmente en algunas situaciones se suele enfrentar costos de penalización en la medida que el proyecto se entregue más tarde de lo comprometido o estimado, como también incentivos por entregas anticipadas que no vayan en desmedro de la calidad del proyecto.

Consideremos el siguiente ejemplo para el cálculo de la Duración Óptima de un Proyecto (el tiempo está medido en días y el costo en dólares):

Por ejemplo la Actividad F tiene una duración normal de 4 días a un costo de 600 dólares y se puede comenzar una vez terminadas las Actividades B y E (predecesores). Si se desea apurar (hacer “crash”) en la Actividad F, el menor tiempo que se puede adoptar es de 2 días (es decir, la reducción máxima es 2 días), donde por cada día que se reduce la duración de dicha actividad se incurre en un costo adicional de 175 dólares. De esta forma, por ejemplo, si se quisiera reducir la duración de la Actividad F de 4 a 3 días, el costo sería de 775 dólares (600+175).

Asuma que la fecha de entrega del proyecto es el día 10. La compañía debe pagar 170 dólares por cada día de atraso. Encuentre el número óptimo de días que debe durar el proyecto a través del análisis de crashing y el costo total del proyecto (incluyendo posibles multas por atraso).

Indique claramente las actividades donde realice crashing. Dibuje el diagrama del proyecto de la alternativa que se propone (el proyecto con el costo más bajo), representando el nombre de cada actividad al interior de los respectivos nodos. Para cada actividad calcule los siguientes indicadores: IC, TC, IL, TL. Luego obtenga explícitamente la holgura de cada actividad y la(s) ruta(s) crítica(s) del proyecto.

A continuación se define un modelo de optimización lineal propuesto para abordar el problema:

Variables de Decisión:

Parámetros:

Función Objetivo: Consiste en minimizar el costo de terminar el proyecto en K días, donde 3.175 corresponde al costo en dólares de desarrollar el proyecto con las actividades en tiempo normal y la expresión en la sumatoria es el costo incremental de disminuir la duración del proyecto.

Restricciones:

Cada actividad se puede reducir (de ser posible) dentro del límite máximo de reducción permisible:

Relaciones de predecesores entre las actividades y el tiempo de inicio y reducción:

Definición del tiempo objetivo para el proyecto:

No negatividad de las variables de decisión:

Una vez definido el modelo de Programación Lineal se implementa computacionalmente haciendo uso de Solver de Excel. Para ello será necesario sensibilizar los resultados del modelo para valores del parámetro K en el intervalo de [10,15] días (el lector puede corroborar que la duración del proyecto si cada actividad mantiene su duración normal es de 15 días). La solución óptima se resume a continuación:

El tiempo óptimo para completar el proyecto corresponde a 12 días, con un costo total (incurriendo multas por atraso) de 3.890 dólares. El gráfico a continuación muestra el valor de la función objetivo (costo total) para distintos valores de duración del proyecto.

A continuación desarrollamos el diagrama del proyecto donde se observa que existen 2 rutas críticas: A-B-F y A-C-E-F, con una duración de 12 días. Notar que la única actividad que no es crítica con holgura positiva (de 1 día) es la Actividad D.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?

[sociallocker]Crashing Óptimo[/sociallocker]

Cálculo de Índice de Habilidad Cp e Índice de Capacidad Cpk en el Control Estadístico de Procesos

Al planear los aspectos de calidad de la manufactura, nada es más importante que asegurarse de antemano de que el proceso productivo será capaz de mantener las tolerancias. La habilidad del proceso proporciona una predicción cuantitativa de qué tan adecuado es un proceso. La habilidad del proceso es la variación medida, inherente del producto que se obtiene en ese proceso. En este contexto, la habilidad permite entre otras cosas establecer limites de especificación realistas.

La fórmula para el cálculo de la habilidad del proceso que más se usa es: Habilidad del Proceso = +- 3σ (un total de 6σ) donde σ es la desviación estándar del proceso cuando se encuentra bajo control estadístico. Adicionalmente si el proceso esta centrado en la especificación nominal y sigue una distribución de probabilidad normal, 99,73% de la producción estará a menos de 3σ de la especificación nominal.

En este contexto la tasa de habilidad de un proceso Cp se refiere a la variación en un proceso alrededor del valor promedio, obteniéndose a través de la siguiente fórmula (notar que se usa 6S como estimación de 6σ):

Un proceso que cumple bien con los límites de especificación (rango de especificación = +- 3σ) tiene un Cp=1. Lo crítico de muchas aplicaciones y la realidad de que el promedio del proceso no permanecerá en el punto medio del rango de especificación sugiere que Cp debe ser al menos 1,33.

En este contexto es útil tener un índice de habilidad que refleje ambas variaciones y la localización del promedio del proceso. Tal índice es Cpk o índice de capacidad del proceso, el cual refleja la proximidad de la media actual del proceso al Límite de Especificación Superior (LES) o al Límite de Especificación Inferior (LEI).

Si el promedio actual es igual al punto medio del rango de especificación, entonces Cpk=Cp.

Adicionalmente si un proceso se encuentra en control estadístico, la siguiente relación se cumple para usar S como una estimación de σ (desviación estándar):

A continuación se presenta el calculo de los índices Cp y Cpk aplicado a los datos del ejemplo de las Gráficas de Promedios y Rangos en el Control Estadístico de Procesos. El resumen de los datos se observa en la siguiente tabla:

Luego se procede a la estimación de S (recordar que cada muestra tiene 4 observaciones, en consecuencia n=4 y d2=2,059).

Notar que el parámetro d2=2,059 se puede obtener de la siguiente tabla:

El cálculo de Cp y Cpk esta dado por:

La media del proceso (999,6 OHMS) se encuentra prácticamente centrada respecto a la especificación nominal (1.000 OHMS). Esto se corrobora en la similitud de los indicadores Cp y Cpk. No obstante lo anterior la habilidad del proceso es relativamente baja (se recomienda al menos Cp≥1,33) lo que permite anticipar que un porcentaje significativo de resistores podrían estar fuera de los límites de especificación.

Existen un importante número de herramientas que permiten el cálculo sencillo de estos indicadores de desempeño. Al respecto recomendamos a nuestros usuarios leer el artículo Cómo Calcular Cp y Cpk con el Complemento SPC for Excel que muestra cómo utilizar el complemento SPC de Excel para simplificar este tipo de operaciones.

Ejemplo de Gráfica de Promedios y Gráfica de Rangos en el Control Estadístico de Procesos

El Control Estadístico de Procesos (CEP) es una metodología que da la confianza estadística de que un componente está dentro de una tolerancia sin tener la necesidad de medir cada componente. Como su nombre lo sugiere es un control del proceso (no del producto) y es un indicador más que una solución. En este contexto la importancia del Control Estadístico de Procesos radica en los siguientes aspectos:

Se utiliza como apoyo al proceso de Control de Gestión.
Consiste en la aplicación de métodos estadísticos a la medición y análisis de la variación en cualquier proceso.
Permite diagnosticar el estado del proceso: Se dice que el proceso está bajo control estadístico (estable) si no presenta señales de que existe alguna causa asignable de variación y en consecuencia representa un proceso predecible. Una causa asignable es detectable y posible de eliminar con una justificación económica.

Las principales herramientas del Control Estadístico de Procesos lo constituyen las cartas de control (de promedios y rangos), las cuales se aplican en el monitoreo de las características de calidad de un producto y detecta cuando el proceso esta fuera de control. A continuación presentaremos un ejemplo que permite la evaluación de si un proceso se encuentra bajo control estadístico mediante la elaboración e interpretación de las gráficas de control de promedios y rangos.

Gráfica de Promedios y Gráfica de Rangos

Una máquina automatizada a alta velocidad fabrica resistores para circuitos electrónicos. La máquina está programada para producir un lote muy numeroso de resistores de 1000 OHMS cada uno, siendo éste el valor ideal para cada resistor y admitiéndose una variación sobre dicho valor de ± 25 OHMS.

Con el fin de ajustar la máquina y crear una gráfica de control para utilizarla a lo largo de todo el proceso, se tomaron 15 muestras con cuatro resistores cada una. La lista completa de muestras y sus valores medidos es la siguiente:

¿Se encuentran el proceso bajo control estadístico?. Grafique los datos en una gráfica de control de promedio (X) y de rango (R) con los limites de control. Para el cálculo del promedio muestral considere los resultados aproximados a un decimal. Comente e interprete los resultados.

En primer lugar necesitamos calcular los límites de control estadístico para las gráficas de promedio y rango. Para ello se deben considerar las siguientes fórmulas y parámetros:

Con esta información procedemos a calcular el promedio y rango de cada una de las 15 muestras. Por ejemplo el promedio de la muestra 1 se obtiene de X1=(1010+991+985+986)/4=993 y el rango R1=1010-985=25 (la diferencia en magnitud de la mayor y menor observación de la muestra). Se replica el procedimiento para el resto de las muestras lo cual se facilita haciendo uso de una planilla Excel según se observa a continuación:

Finalmente se obtienen los límites de control estadístico los cuales se resumen en la siguiente tabla:

A continuación se grafican los resultados de cada una de las muestras (celdas color amarillo de la planilla anterior) en contrastes con los límites de control.

El proceso se encuentra bajo control estadístico. Tanto en la gráfica de promedios y rangos los resultados de las muestras están dentro de los límites de control. Recomendamos a nuestros usuarios revisar el artículo Gráfico de Promedios y Gráfico de Rangos en el Control Estadístico de Procesos con Minitab 17.
En la gráfica de promedios se observa una dispersión aleatoria respecto a la media del proceso aun cuando llama la atención de la media de las muestras 4 y 5.
En la gráfica de rangos se observa un leve tendencia creciente a contar de la muestra 9. Si bien las observaciones se mantienen dentro de los límites de control, esta situación se debe tener bajo alerta dado que muestra un aumento en la variabilidad.