GEO Tutoriales, Autor en Gestión de Operaciones

Conformación de Equipos de Trabajo a través de la Programación Entera

La Programación Entera provee una alternativa metodológica para enfrentar los Problemas de Asignación en donde una serie de recursos (mano de obra, horas máquinas, materia prima, etc) se deben asignar a uno o más fines (conformar equipos de trabajo, producción, etc). El siguiente artículo aborda el problema que enfrenta una consultora que debe formar 2 equipos de expertos del área de operaciones en base a 8 ingenieros industriales. Estos 2 equipos los puede escoger de entre 5 equipos de profesionales que trabajan en la consultora. Los datos del problema se muestran en la siguiente tabla:

Cada equipo tiene que estar compuesto por al menos 3 y a lo más 5 expertos. Si el profesional j es asignado al equipo i, la compañía le debe pagar una remuneración rij. Si en la tabla aparece un guion (—), significa que el experto no puede ser asignado a ese equipo: por ejemplo, el profesional 3 no puede pertenecer al equipo 2 ni al 4. Se espera que el equipo i genere un ingreso di.

Se requiere formular y resolver computacionalmente un modelo de optimización que permita determinar la conformación de los equipos, alcanzando la utilidad máxima y cumpliendo las condiciones anteriormente expuestas. Definir claramente las variables de decisión, función objetivo y restricciones.

Variables de Decisión:

Función Objetivo:

Restricciones:

Sólo 2 equipos se seleccionan:

Cada equipo está formado solamente por entre 3 y 5 expertos:

A continuación se presenta un extracto de la implementación computacional del problema de conformación de equipos de trabajo con Solver. Notar que aquellas combinaciones infactibles en términos de asignación de ingenieros a equipos ha sido marcado con color rojo y en particular se le ha asignado un costo significativamente mayor en comparación a aquellas asignaciones factibles. De esta forma se espera que estos casos no sean seleccionados (por cierto también se puede seleccionar paso a paso sólo las celdas factibles al momento de definir las variables de decisión en Solver, omitiendo las situaciones infactibles).

La solución óptima consiste en seleccionar el equipo 1 y 5. En la tercera tabla (filas 16 a 21) se muestra la asignación de ingenieros a dichos equipos (por supuesto aquellos equipos que no se conforman, es decir, equipos 2, 3 y 4 no tienen ingenieros asignados). El equipo 1 se compone de los ingenieros 1, 3 y 4; por otra parte el equipo 5 se compone de los ingenieros 1, 3 y 10. Notar que no existe incentivo económico a conformar equipos con un mayor número de integrantes. Finalmente el valor óptimo (utilidad máxima) es de $16.550.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google+ o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre “Descarga el Archivo” se mostrará abajo una vez que nos hayas recomendado).

[l2g name=»Descarga el Archivo» id=»4545″]

Problema de Producción y Ensamblaje resuelto con el Método Simplex

El siguiente problema de Programación Lineal fue enviado por uno de nuestros lectores desde Puerto Rico. Consiste en determinar la política óptima de producción y ensamblaje de una empresa que se dedica a fabricar componentes para computadoras. A continuación los detalles de dicho problema el cual luego de su formulación (definición de las variables de decisión, función objetivo y restricciones) será resuelto a través del Método Simplex:

Problema de Producción y Ensamblaje

Una pequeña compañía fábrica tres componentes electrónicos de computadoras. Componente A requiere 2 horas de fabricación, 1 hora de ensamblaje y 1 hora de finalización; Componente B requiere 3 horas de fabricación, 1 hora de ensamblaje y 1 hora de finalización; y el Componente C requiere 2 horas de fabricación, 2 horas de ensamblaje y 1 hora de finalización. La compañía tiene a lo sumo 1.000 horas de labor en la fabricación, 800 horas de labor en el ensamblaje y 100 horas de finalización disponibles cada semana. Las ganancias de cada componente A, B y C, son $7, $8 y $10, respectivamente.

¿Cuántos componentes de cada tipo debe la compañía fabricar cada semana de manera que pueda maximizar sus ganancias? ¿Cuál es la ganancia máxima?. Resuelva el problema de Programación Lineal utilizando el Método Simplex.

Sea $x_{1}, x_{2}, x_{3}$ la cantidad de unidades a producir semanalmente del Componente A, B y C, respectivamente, un modelo de Programación Lineal que permite abordar el problema anterior es:

De modo de resolver el modelo a través del Método Simplex llevamos el mismo al formato estándar, agregando $x_{4}, x_{5}, x_{5}$ como variables de holgura de las restricciones 1, 2 y 3, respectivamente (fabricación, ensamblaje y finalización).

Lo que da origen a la siguiente tabla inicial del método:

Por el criterio del costo reducido más negativo ingresa a la base la variable $x_{3}$ . Luego calculamos el mínimo cuociente en dicha columna obteniendo: $Min \begin{Bmatrix}{\frac{1.000}{2}, \frac{800}{2}, \frac{100}{1}}\end{Bmatrix}=100$ , el pivote está en la fila 3 y en consecuencia $x_{6}$ deja la base. Se realiza entonces una iteración:

Notar que luego de una iteración las variables no básicas $x_{1}, x_{2}, x_{6}$ tienen costos reducidos mayores a cero, además las variables básicas cumplen con las condiciones de no negatividad, a saber, $x_{3}=100, x_{4}=800, x_{5}=600$ , lo que corresponde a una solución básica factible óptima. En consecuencia se propone producir exclusivamente 100 unidades del Componente C lo que reporta un valor óptimo (ganancia máxima) de $1.000.

Sondeo de Opiniones o Juicio Informado para Pronósticos de Ventas

El sondeo de opiniones o juicio informado corresponde a una Técnica Cualitativa de Pronóstico de Ventas (o pronóstico/proyección de demanda). En este caso se consulta por un determinado pronóstico que pueden hacer un grupo de expertos en forma individual o en forma colectiva. Este tipo de pronóstico es bastante frecuente en las publicaciones sobre estrategias de empresas, en relación por ejemplo a pronosticar la tasa de crecimiento de la economía en los próximos años.

Al interior de las empresas este método se puede utilizar realizando una consulta escalonada y secuencial a las personas que pueden realizar algún aporte en la proyección deseada, siguiendo la jerarquía de la organización, desde los niveles más bajos a los niveles más altos. De esta forma los primeros consultados serán aquellos que están en contacto con el entorno relevante (clientes, distribuidores, proveedores, asociaciones gremiales, etc), los que podrán aportar su estimación su estimación del tema que se pretende pronosticar.

Con estas consultas realizadas, serán los jefes de los encuestados anteriores los que aporten su estimación, analizando las respuestas de sus subalternos, y entregando la suya propia, la que se supone más experimentada y fundamentada (por cierto esto no siempre es una premisa válida tal como representa el siguiente cómic).

Las consultas siguen en forma en forma ascendente, llegando al nivel superior donde se elaboran las políticas, objetivos y estrategias de la empresa. Los ejecutivos de este nivel serán finalmente responsables del pronóstico que se elabore, considerando que conocen la percepción de sus subalternos. Esta forma de elaborar un pronóstico puede tener un efecto motivacional importante, en la medida que el personal de los niveles inferiores se siente tomado en cuenta por la dirección de la empresa, independiente de si la percepción de cada uno de ellos resulta similar o no al pronóstico final realizado.

Un ejemplo del proceso anterior es el de una empresa distribuidora que para efectos de determinar el nivel de ventas del próximo período consulta a los vendedores (los que en general tenderán a hacer estimaciones conservadoras, de forma que en el futuro les sea fácil cumplirlas), luego a los supervisores, jefe de ventas, gerente comercial y finalmente gerente general. Esta información se puede procesar por producto, cliente, sector geográfico, vendedor, etc, de forma que al transcurrir el tiempo se puedan verificar los avances en el logro de los niveles estimados.

Otra forma que puede tomar este sondeo es consultar directamente a los clientes sobre las necesidades de productos que estos estiman tendrán y por ende se proponen comprar durante un determinado período de tiempo; este método es útil para empresas con pocos clientes, lo cual es típico de los clientes industriales.

En las empresas manufactureras se generan verdaderas cadenas de suministro, en que es muy importante conocer las necesidades de las últimas empresas de la cadena, de forma que las empresas que están al comienzo de la cadena puedan efectuar sus pronósticos y producir la cantidad requerida por las empresas del final de la cadena. El traspaso de esta información requiere cooperación, reserva y un buen grado de confianza entre las empresas (factores que permiten mitigar lo que se conoce como Efecto Látigo).

Método de la Esquina Noroeste (Algoritmo de Transporte en Programación Lineal)

El Método de la Esquina Noroeste (o esquina superior izquierda) es una heurística que se aplica a una estructura especial de problemas de Programación Lineal llamada Modelo de Transporte, la cual permite asegurar que exista una solución básica factible inicial (no artificial). Otros métodos para la obtención de una solución básica de inicio son el Método de Costo Mínimo y Método de Aproximación de Vogel. En general, el Método de Vogel produce la mejor solución básica de inicio y el de la Esquina Noroeste la peor, sin embargo, el Método de la Esquina Noroeste implica el mínimo de cálculos.

El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la esquina noroeste, o superior izquierda, de la tabla (variable $x_{11}$ ). A continuación una descripción de los pasos:

Paso 1: Asignar todo lo posible a la celda seleccionada y ajustar las cantidades asociadas de oferta y demanda restando la cantidad asignada.

Paso 2: Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tachar sólo uno (la fila o columna) y dejar una oferta (demanda) cero en la fila (columna) que no se tachó.

Paso 3: Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a la de abajo si se tachó un reglón. Seguir con el Paso 1.

Método de la Esquina Noroeste

Para ilustrar la aplicación del Método de la Esquina Noroeste consideremos el siguiente problema balanceado de transporte que considera 3 silos productos (oferta) que satisfacen las necesidades de 4 molinos (demanda). El algoritmo de transporte se basa en la hipótesis que el modelo está balanceado, es decir, que la demanda total es igual a la oferta total (si el modelo no está balanceado siempre se podrá aumentar con una fuente ficticia o un destino ficticio para restaurar el equilibrio o balance).

Los costos unitarios de transporte desde el silo i al molino j $c_{ij}$ se representan en la esquina superior derecha de cada cuadro. Por ejemplo el costo unitario de enviar una unidad de producto desde el silo 1 al molino 1 es de $10. Adicionalmente los silos 1, 2 y 3 tienen capacidad u oferta de 15, 25 y 10 unidades, respectivamente. Por otra parte los molinos 1, 2, 3 y 4 tienen requerimientos o demanda de 5, 15, 15 y 15 unidades, respectivamente. El modelo esta balanceado (suma oferta = suma demanda = 50 unidades).

Al aplicar el Método de la Esquina Noroeste al ejemplo anterior se obtienen los siguientes resultados. Las flechas indican el orden en el que se generan las cantidades asignadas:

La cantidad asignada a la celda $x_{11}$ son 5 unidades, dado que si bien el silo 1 tiene capacidad de 15 unidades, el molino 1 sólo necesita (demanda) 5 unidades (no se realizan más asignaciones a la columna 1 correspondiente al molino 1).
A continuación nos movemos a la derecha y asignamos lo máximo posible (10 unidades remanentes) a la celda $x_{12}$ (con lo cual se completa la capacidad del silo 1 y en consecuencia no es posible seguir realizando asignaciones en la fila 1).
Luego asignamos 5 unidades a la celda $x_{22}$ lo cual es por cierto menor que la capacidad del silo 2 pero lo suficiente para satisfacer los requerimientos del molino 2 (ahora no es posible generar asignaciones adicionales a la columna 2).
Nos movemos a la derecha y se asignan 15 unidades del silo 2 al molino 3 ( $x_{23}=15$ ) lo que cubre inmediatamente los requerimientos del molino 3 (no es necesario asignar más en la columna 3).
Nuevamente nos movemos a la derecha y asignamos lo máximo posible (5 unidades que es la capacidad remanente del silo 2, es decir, $x_{24}=5$ ) con lo cual el silo 2 opera a máxima capacidad (ahora ya no es posible nuevas asignaciones en la fila 2).
Finalmente se asignan 10 unidades del silo 3 al molino 4 ( $x_{34}=10$ ) cubriendo la demanda de dicho molino (y la capacidad del correspondiente silo).

En consecuencia la solución básica factible inicial es: $x_{11}=5, x_{12}=10, x_{22}=5, x_{23}=15, x_{24}=5, x_{34}=10$ que reporta un costo del programa (valor en la función objetivo) de: Z=5(10)+10(2)+5(7)+15*(9)+5(20)+10*(18)=$520. Notar que si se implementa computacionalmente el problema anterior haciendo uso de Solver de Excel y utilizando como motor de resolución Simplex_LP se alcanza la siguiente solución óptima (celdas amarillas) con costo mínimo (valor óptimo) de $435.

Cómo detectar que un Problema de Programación Lineal es infactible con el Método Simplex de 2 Fases

Un problema infactible en Programación Lineal es una situación que se detecta cuando en la aplicación del Método Simplex de 2 Fases el valor óptimo del problema de la Fase 1 es distinto a cero (para continuar a la Fase 2 se requiere que el valor óptimo de la Fase 1 sea cero). Cabe recordar que un problema infactible es aquel cuyo dominio de soluciones factibles es vacío.

Consideremos el siguiente modelo de Programación Lineal en 2 variables que nos permitirá representar dicha situación:

Agregamos las siguientes variables al modelo para aplicar el Método Simplex de 2 Fases: $x_{3} (holgura), x_{4} (exceso), x_{5} (auxiliar)$ .

Definiendo el problema inicial de la Fase 1:

A continuación llevamos el costo reducido de la variable $x_{5}$ a cero, multiplicando por -1 la fila 2 y sumando ésta a la fila 3:

Para favorecer la rapidez de convergencia del método $x_{2}$ entra a la base. Luego calculamos el criterio del mínimo cuociente: $Min \begin{Bmatrix}{\frac{2}{1}, \frac{12}{4}}\end{Bmatrix}=2$ por tanto $x_{3}$ deja la base. Actualizamos la tabla:

Notar que todas las variables no básicas $x_{1}, x_{3}, x_{4}$ tienen costos reducidos mayores o iguales a cero. Adicionalmente las variables básicas $x_{2}, x_{5}$ cumplen con las condiciones de no negatividad. En consecuencia hemos finalizado la Fase 1 del Método Simplex de 2 Fases, sin embargo, el valor de la función objetivo es distinto de cero (en el ejemplo es -4) lo que determina que el problema es infactible.

La siguiente representación gráfica del problema anterior se puede realizar con Geogebra. El área achurada color rojo corresponde a la intersección de los conjuntos de factibilidad definido por la restricción 1 y las de no negatividad. Por otra parte el área achurada color azul es la intersección de los conjuntos de factibilidad definido por la restricción 2 y las de no negatividad. Luego resulta evidente que la intersección de dichos conjuntos (rojo y azul) es vacío, por tanto no existen valores que puedan adoptar las variables de decisión y satisfacer de forma simultanea todas las restricciones del problema.