Minientrada archivos - Página 6 de 8 - Gestión de Operaciones

Problema de Asignación en Programación Entera resuelto con Solver

Cuando necesitamos asignar recursos escasos a determinadas funciones y dichos recursos no son fraccionables, la utilización de modelos de Programación Entera resultan ser de utilidad para la toma de decisiones. En este contexto los problemas de asignación de personal a determinadas tareas es una aplicación típica de la Programación Entera que a continuación desarrollaremos a través de un ejemplo.

Problema de Asignación

Consideremos una empresa que dispone de 5 ingenieros que deben desarrollar 7 proyectos. La tabla a continuación resume el tiempo que demora cada ingeniero (en horas) en completar un determinado proyecto. El problema consiste en determinar una asignación óptima que permita realizar cada uno de los proyectos con la limitante que por motivos estratégicos cada ingeniero debe desarrollar al menos un proyecto y en ningún caso hacer más de 2 proyectos. Por supuesto se busca que el tiempo requerido para realizar los 7 proyectos sea el menor posible.

Una alternativa sería buscar intuitivamente una asignación que cumpla con los requisitos de la empresa y tenga un bajo tiempo asociado. Sin embargo, este tipo de estrategias de resolución queda claramente acotada a problemas de tamaño menor y ni siquiera en ese tipo de situaciones nos asegura la mejor solución posible. Por ello definiremos el siguiente modelo de optimización de Programación Entera:

1. Variables de Decisión: Utilizamos las siguientes variables de decisión binarias

2. Función Objetivo: Minimizar el tiempo total requerido para completar los proyectos

Donde Tij (parámetros) es el tiempo (en horas) requerido por el ingeniero i en realizar el proyecto j. Por ejemplo T(A,P5)=7.

3. Restricciones:

Cada proyecto debe ser realizado por un solo ingeniero:

Cada ingeniero debe ser al menos un proyecto y no puede hacer más de 2:

El siguiente tutorial muestra cómo resolver este problema de asignación con Solver de Excel:

Se puede observar que para efectos de Solver, las variables de decisión binarias se deben definir como una restricción adicional. También puede resultar que luego de resolver Solver no encuentre inmediatamente la mejor solución posible. Para enfrentar esta situación se puede «volver a resolver» sobre la solución que el programa nos haya proporcionado hasta el momento para verificar si se puede lograr algo mejor. Esta situación es la que sucedió en el tutorial y a continuación se muestra la solución óptima (final) encontrada por Solver.

En total se requieren 56 horas para realizar los 7 proyectos. El ingeniero A realiza el P7, el ingeniero B el P3 y P5, el ingeniero C el P6, el ingeniero D el P2 y P4 y el ingeniero E el P1. Notar que cada proyecto es realizado por un ingeniero y cada ingeniero al menos realiza un proyecto, pero no más de 2 proyectos.

Probabilidad de terminar un Proyecto en un tiempo determinado con PERT

Cuando se utiliza el método PERT (Program Evaluation and Review Technique) uno de los principales objetivos es considerar la incertidumbre en el tiempo de duración de cada una de las actividades de modo de poder estimar la probabilidad de completar el proyecto en un tiempo determinado. Este tipo de análisis resulta de bastante utilidad en aplicaciones prácticas dado que se entiende que en todo Proyecto existen imprevistos o circunstancias que pueden afectar la duración de una actividad y su impacto se puede traspasar al inicio o termino de otras actividades.

Probabilidad de completar un Proyecto en un tiempo determinado utilizando PERT

Para introducir este concepto consideraremos nuevamente nuestro ejemplo de un proyecto que consta de 9 actividades y que contempla las siguientes secuencias y tiempos estimados para cada uno de sus 3 escenarios:

Luego de obtener la duración del proyecto utilizando la Metodología de PERT y el software WINQSB, se determina que el tiempo estimado para completar el proyecto es de 21,5 semanas y las actividades de la ruta crítica son D-F-G. El paso siguiente es determinar la sumatoria de las varianzas de las actividades que pertenecen a la ruta crítica. La varianza se obtiene como:

Donde b es el tiempo pesimista y a es el tiempo optimista. La siguiente tabla muestra el cálculo de la varianza redondeando a 5 decimales (decisión arbitraria para efectos de desarrollar el ejemplo). Se ha marcado con verde las actividades de la ruta crítica para las cuales en la celda H13 se ha calculado la suma de sus varianzas.

Consideremos ahora que para este proyecto nos interesa calcular la probabilidad de poder terminarlo en 23 semanas o menos. Para ello desarrollamos el siguiente procedimiento que nos indica que dicha probabilidad es un 86,86%:

Esta probabilidad también se puede obtener con la función de Excel: =DISTR.NORM.ESTAND(1,12)

El siguiente tutorial muestra cómo calcular la probabilidad de terminar el proyecto en 23 semanas o menos utilizando WINQSB. Notar que el resultado es levemente diferente sólo por efecto de aproximación:

Cómo obtener la duración de un Proyecto con PERT y WINQSB

A diferencia del Método de Ruta Crítica o CPM la metodología de PERT (Program Evaluation and Review Technique) considera que el tiempo de duración de las actividades que comprenden un proyecto es estocástico.

Este supuesto implica que para cada actividad tendremos distintos escenarios de ocurrencia sobre el tiempo requerido para llevarla a cabo. Estos escenarios se denominan usualmente como Optimista (a) (el menor tiempo posible), Más Probable (m) y Pesimista (b) (el mayor tiempo en el peor de los casos).

Cada uno de estos escenarios descritos se pondera en 1/6, 2/3 y 1/6, respectivamente para obtener el Tiempo Esperado $t_{e}$ de cada actividad: $t_{e}=(1/6*a+2/3*m+1/6*b)$ y luego obtener el tiempo de duración del proyecto (notar que la suma de las probabilidades de ocurrencia de cada escenario es igual a 1 o un 100%).

Duración de un Proyecto con PERT

En la siguiente tabla se muestra cómo calcular el tiempo esperado para cada actividad de un Proyecto, por ejemplo, el tiempo esperado de la actividad A es de 6 semanas ((1/6)*5+(2/3)*6+(1/6)*7) según se aprecia en la fórmula:

Para poder determinar la duración de un proyecto utilizando PERT consideramos los tiempos esperados para cada actividad y seguimos un procedimiento similar al del Método de la Ruta Crítica o CPM. Otra alternativa equivalente es utilizar un software especializado como WINQSB para obtener la duración del proyecto según se muestra en el siguiente tutorial:

El tiempo estimado para completar el proyecto es de 21,5 semanas y la ruta crítica esta determinada por la secuencia D-F-G. Se puede comprobar que si aplicamos el método de la ruta crítica con los tiempos esperados de cada actividad como tiempo determinista, se obtienen los mismos resultados.

Cómo resolver un modelo de Programación Lineal con el Método Simplex

Existen algunas herramientas en Internet que permiten resolver modelos de Programación Lineal utilizando el Método Simplex. Este tipo de aplicaciones resultan de bastante utilidad para los estudiantes de ingeniería que desean verificar si los resultados que obtienen en la aplicación manual del método resultan ser correctos.

En esta oportunidad revisaremos la interfaz para resolver modelos de Programación Lineal con el Método Simplex disponible en el sitio web ProgramacionLineal.net. Para ello utilizaremos un modelo lineal en 2 variables que previamente resolvimos gráficamente con el complemento Solver de Excel y el software Geogebra.

Cómo resolver un modelo de Programación Lineal con el Método Simplex

El siguiente tutorial muestra cómo implementamos este modelo de optimización con la herramienta de resolución del Método Simplex:

La última tabla del Método Simplex luego de la resolución con esta aplicación y eliminando la columna p (no es necesaria) es la siguiente:

La Solución Óptima (que corresponde a una solución básica factible óptima) es x=100 e y=350 (x e y son las variables básicas de las filas 1 y 3 respectivamente). El valor óptimo es V(P)=3.100. Notar que la solución óptima corresponde al vértice C de la representación gráfica del problema propuesto que se muestra a continuación:

Importante: Las variables s1 y s3 son variables no básicas en la actual solución óptima y por tanto su valor es cero. La variable s2 es la variable básica de la fila 2 y toma el valor de 400. Notar que las variables s1, s2 y s3 son inicialmente las variables de holgura necesarias para llevar el modelo de Programación Lineal a su forma estándar.

Cómo calcular la Capacidad de un Proceso con Actividades en Paralelo

En un Proceso Productivo con actividades en paralelo el cálculo de su capacidad, es decir, cuántas unidades se fabrican en promedio en un determinado período de tiempo ( se puede definir arbitrariamente en unidades fabricadas por segundos, minutos, horas, etc) depende, entre otros aspectos, de la configuración del proceso, la duración de cada actividad y los recursos involucrados en cada una (personal, maquinaria, etc).

Para una mejor comprensión de los conceptos consideremos un ejemplo sencillo que corresponde a un proceso productivo para la fabricación de un mueble. Asumamos que en cada actividad trabaja un trabajador:

Capacidad de un Proceso con Actividades en Paralelo

Un mueble se termina en la medida que pasa por las actividades de Pulir, Ensamblar y Pintar (en ese orden) y resulta evidente que existen 2 caminos que permiten cumplir esa secuencia.

Las actividades Ensamblar están en paralelo, es decir, los trabajadores de estas actividades puedes estar operando en forma simultanea en un mismo instante en el tiempo. Dicho de otra forma, el trabajador que Ensambla en la línea de abajo no necesita esperar a que el trabajador que Ensambla en la línea de arriba se desocupe para comenzar a trabajar (y viceversa).

Para calcular la capacidad del proceso de producción de muebles debemos calcular la capacidad de cada uno de las actividades en forma individual.

La etapa Pulir tiene una capacidad de 12[u/hora] (también es correcto decir que la capacidad de Pulir es de 1/5[u/min]); la etapa Ensamblar de la línea de arriba tiene una capacidad de 7,5[u/hora] y la etapa Ensamblar de la línea de abajo tiene una capacidad de 6[u/hora]. Finalmente el trabajador de la etapa Pintar tiene una capacidad de 10[u/hora].

Los 2 trabajadores de las etapas Ensamblar tienen una capacidad conjunta de 13,5[u/hora] (es la suma de la capacidad individual de cada uno, es decir, 7,5+6[u/hora]). Luego la capacidad del proceso es de 10[u/hora] y el Cuello de Botella es la actividad Pintar.

¿Cuál sería la capacidad ahora si el trabajador de la etapa Ensamblar de la primera línea en vez de demorar 8 min ahora demora 20 min?.

En este caso la capacidad de las etapas Ensamblar en paralelo sería 9[u/hora] (3+6[u/hora]) y por tanto las actividades en paralelo ahora serían el cuello de botella, teniendo el proceso una capacidad de 9[u/hora].

Recomendamos revisar el artículo Cálculo de la Capacidad de Producción en un Proceso Flexible con una Carta Gantt donde a través de esta herramienta frecuentemente utilizada en la Gestión de Proyectos se puede corroborar de forma intuitiva el cálculo de la capacidad de un proceso productivo.