Programación Entera Archivos - Página 4 de 8

Solución del Problema del Vendedor Viajero

El Problema del Vendedor Viajero (conocido también como Travelling Salesman Problem o simplemente TSP) consiste en encontrar el circuito óptimo (en términos del viaje más corto) que deberá seguir un vendedor en un caso con n ciudades, en el que cada ciudad se visita exactamente una vez. Básicamente es una adaptación del Problema de Asignación que considera restricciones adicionales que garantiza la exclusión de subcircuitos en la solución óptima.

Específicamente en el caso de n ciudades se define las variables de decisión de la siguiente forma:

Sea $d_{ij}$ la distancia de la ciudad i a la ciudad j, donde $d_{ij}=\infty$ , el modelo del agente o vendedor viajero corresponde a:

El conjunto de restricciones (1) y (2) definen un modelo de asignación tradicional. Lamentablemente en general, el problema de asignación producirá soluciones de subcircuito más que circuitos completos que abarque las n ciudades.

Para ilustrar los conceptos de circuito y subcircuito en el contexto del Problema del Vendedor Viajero, consideremos un agente de venta que vive en la ciudad 1. Miami (Florida) en Estados Unidos y debe visitar a importantes clientes en las siguientes ciudades: 2. Chicago (Illinois), 3. Houston (Texas), 4. Las Vegas (Nevada) y 5. San Francisco (California). Para mayor claridad se han destacado los estados mencionados anteriormente con un color distintivo.

Un circuito factible sería viajar en el siguiente orden: Miami (FL), Chicago (IL), Houston (TX), Las Vegas (NV), San Francisco (CA), Miami (FL). Es decir, $x_{12}=x_{23}=x_{34}=x_{45}=x_{51}=1$ .

Por otra parte un subcircuito correspondería, por ejemplo, a Miami (FL), San Francisco (CA), Las Vegas (NV), Miami (FL), junto a Houston (TX), Chicago (IL), Houston (TX). Es decir, $x_{15}=x_{54}=x_{41}=x_{32}=x_{23}=1$ , lo que naturalmente no es una solución factible para el problema que se busca resolver.

El modelo del vendedor viajero se caracteriza por su versatilidad para representar otros casos prácticos en optimización. Uno de ellos es el Problema de Secuenciamiento de la Producción como el que se presenta a continuación:

El programa de producción diaria de una empresa de pinturas incluye lotes de color Blanco (B), Amarillo (A), Negro (N) y Rojo (R). Como la empresa utiliza las mismas instalaciones en las cuatro clases de pintura, es necesario hacer una limpieza entre los lotes. La siguiente tabla resume el tiempo de limpieza, en minutos, donde al color de la fila sigue el color de la columna. Por ejemplo, cuando después de la pintura Blanca sigue la Amarilla, el tiempo de limpieza en 10 minutos. Como un color no puede seguir a sí mismo, a los elementos correspondientes se les asigna un tiempo de setup infinito. Se desea determinar la secuencia óptima para la producción diaria de los cuatro colores, que minimice el tiempo total de limpieza necesario.

Se puede hacer una analogía con el problema del vendedor viajero, asumiendo que cada pintura es una “ciudad” y que las “distancias” representan el tiempo de limpieza necesario para cambiar de un lote de pintura al siguiente. En consecuencia, el problema se reduce a determinar el circuito más corto que se inicie en un lote de pintura y pase exactamente una vez por cada uno de los tres lotes restantes, para regresar al punto de partida.

En este contexto dada la cantidad de pinturas, la secuencia óptima se puede encontrar por enumeración exhaustiva de los 6 circuitos posibles $(n-1)!$ , es decir, $(4-1)!=3!=6$ . En el ejemplo dicha secuencia óptima corresponde a Blanco, Amarillo, Rojo, Negro, Blanco, con un tiempo total de setup de 98 minutos. Naturalmente esta estrategia no es eficiente y queda limitada a problemas muy pequeños.

Alternativamente se puede utilizar implementar en Solver el modelo de asignación presentado anteriormente, haciendo uso de los parámetros descritos en el ejemplo del secuenciamiento de la producción de pinturas. A continuación un extracto de los resultados donde se observa que no se alcanza una solución de circuito.

En la actualidad existen programas computacionales que permiten enfrentar estas dificultades que establece el problema del vendedor viajero. Uno de ellos es el software TSPSG (TSP Solver and Generator) que se caracteriza por una interfaz intuitiva y que a continuación se detalla la implementación de nuestro problema (recordar que la Ciudad 1 correspondería al color Blanco, y así sucesivamente).

Una vez ingresado los datos al seleccionar “Solve” el programa se ejecuta entregando los resultados alcanzados que por cierto coincide con aquellos que identificamos por enumeración.

En términos algorítmicos los métodos disponibles para resolver el problema del agente o vendedor viajero tienen su base en las ideas de los algoritmos generales de ramificación y acotamiento (Branch and Bound) o de Plano de Corte, en los cuales abordaremos en próximos artículos.

Cómo enfrentar una Solución Infactible obtenida con el Método Húngaro

En algunos casos los ceros que se producen en los Pasos 1 y 2 del Método Húngaro no producen una solución factible en forma directa, es decir, la asignación alcanzada es infactible. En este caso se necesitan más pasos para alcanzar la asignación óptima (factible). Para ilustrar esta situación consideremos el siguiente ejemplo que consiste en la asignación a costo mínimo de 4 ingenieros a 4 tareas, donde cada ingeniero debe desempeñar exactamente una tarea:

Al aplicar los Pasos 1 y 2 del Método Húngaro se obtiene la siguiente matriz reducida:

Notar que los elementos cero (marcados con color azul) no permiten asignar una tarea por ingeniero. Por ejemplo, si se asigna el ingeniero 1 a la tarea 1, se eliminará la columna 1, y el ingeniero 3 no tendrá elemento cero en las tres columnas restantes. Para solucionar este obstáculo se agrega el siguiente paso al procedimiento:

Paso 2a: Si no se puede asegurar una asignación factible (con todos los elementos cero) con los Pasos 1 y 2.

Trazar la cantidad mínima de líneas horizontales y verticales en la última matriz reducida que cubran todos los elementos cero.
Seleccionar el elemento mínimo no cubierto, restarlo de todo elemento no cubierto y a continuación sumarlo a todo elemento en la intersección de dos líneas.
Si no se puede encontrar una asignación factible entre los elementos cero que resulten, repetir el Paso 2a. En caso contrario, seguir en el Paso 3 para determinar la asignación óptima.

Al aplicar el Paso 2a a la matriz reducida presentada anteriormente, se obtienen las celdas color amarillo según se aprecia a continuación:

La celda de valor mínimo sin fondo amarillo es igual a $1 (destacada con color rojo). Este elemento se resta de todas las celdas sin fondo amarillo y se suma a a las celdas de las intersecciones (destacadas con color azul).

La solución óptima (por cierto factible) se ha marcado con fondo azul: el ingeniero 1 realiza la tarea 1, el ingeniero 2 la tarea 3, el ingeniero 3 la tarea 2 y el ingeniero 4 la tarea 4 . El costo total (valor óptimo) de esta asignación es $1+$10+$5+$5=$21.

El Método Húngaro como Algoritmo de Solución del Modelo de Asignación

Un caso típico de un modelo de asignación es aquel que considera la asignación de trabajadores de distintos niveles de capacitación a puestos de trabajo. Naturalmente un puesto que coincide con los conocimientos de un trabajador cuesta menos que uno en el que el trabajador no es tan hábil. El objetivo del modelo es determinar la asignación de costo mínimo de trabajadores a puestos.

Consideremos un problema con n trabajadores que deben ser asignados a n puestos de trabajo. Sea $x_{ij}$ el costo de asignar al trabajador i al puesto j. Asumamos adicionalmente que cada trabajador debe realizar exactamente un trabajo. Notar que no existe pérdida de generalidad en asumir que la cantidad de trabajadores es igual a la cantidad de puestos, porque siempre se pueden agregar trabajadores o puestos ficticios para obtener esa condición.

El Método Húngaro consta de los siguientes pasos:

Paso 1: En la matriz original de costo, identificar el mínimo de cada fila y restarlo de todos los elementos de la fila.

Paso 2: En la matriz que resulte del Paso 1, identificar el mínimo de cada columna, y restarlo de todos los elementos de la columna.

Paso 3: Identificar la solución óptima como la asignación factible asociada con los elementos cero de la matriz obtenida en el Paso 2.

A continuación presentaremos un ejemplo que muestra la aplicación del Método Húngaro que nos permite decidir la asignación de trabajadores a puestos de trabajo.

Ejemplo Método Húngaro

Un equipo de 3 ingenieros debe ser asignado para la realización de 3 tareas, donde cada ingeniero debe hacer una tarea. Se requiere encontrar la asignación de costo mínimo para lo cual se dispone de los costos asociados a que el ingeniero i realice la tarea j. Por ejemplo, $c_{11}=15$ representa el costo correspondiente a que el ingeniero 1 asuma la tarea 1.

Aplicar el Método Húngaro para encontrar una asignación óptima de los ingenieros a las tareas.

El Paso 1 del Método Húngaro requiere identificar el valor mínimo de cada fila. En el caso de la fila 1 dicho valor es $9 siendo el costo de que el ingeniero realice la tarea 3. En particular si se dispone de un problema de mayor tamaño, hacer uso de Excel facilita los cálculos tal como se muestra en la siguiente imagen:

A continuación se resta el mínimo de cada fila a cada uno de los valores de la fila respectiva, para obtener la matriz reducida:

La aplicación del Paso 2 produce los mínimos de cada columna según se observa en la tabla anterior. Al restar esos valores de las columnas respectivas se obtiene la siguiente matriz reducida:

Las celdas con valor cero y color azul son la solución óptima. En consecuencia el ingeniero 1 realiza la tarea 2, el ingeniero 2 asuma la tarea 1 y el ingeniero 3 la tarea 3. Cada ingeniero realiza exactamente una tarea y el costo total de dicha asignación (valor óptimo) es de $9+$10+$8=$27. Los pasos presentados del Método Húngaro para el ejemplo anterior funcionaron bien debido a que los elementos cero de la matriz anterior permite una asignación factible de ingenieros a tareas (en el sentido que las tareas se asignan de forma única a los ingenieros). No siempre esto es posible lograr una solución factible en la aplicación caso en el cual se requiere pasos adicionales para la aplicación del método.

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″]

Planificación de la Producción y Empaque en el Programa Maestro de Producción

El Plan Maestro de la Producción (PMP) especifica las fechas y las cantidades de producción que corresponden a cada uno de los elementos de la familia de productos (manufactura). En muchas aplicaciones el producto no esta terminado en la medida que no haya sido empacado, es decir, que este en una condición de uso suficiente para su comercialización. El siguiente artículo aborda el problema que enfrenta una empresa que debe programar los niveles de producción y empaque para 4 productos en un horizonte de planificación de 8 meses (4 bimestres), buscando satisfacer una demanda estimada al mínimo costo y haciendo uso de recursos limitados.

Planificación de la Producción

Una firma desea planificar la producción de los próximos 4 bimestres para sus productos finales, representados por los productos A, B, C y D. Esto se hará usando una política óptima de elaboración contra stock para satisfacer las demandas estimadas en cada periodo y cuyos valores se resumen en la siguiente tabla:

En la tabla se entrega igualmente una capacidad máxima de producción por producto, excepto para las labores de empacado. Asuma que estas capacidades son constantes sobre todo el periodo de planificación. En el caso de la sección de empaque esta transforma el producto en un producto empacado, de modo que hay una capacidad global sobre el número total de unidades que pueden ser empacadas en cada periodo y alcanza las 50.000 unidades por bimestre.

Es posible almacenar tanto productos finales como productos finales empacados en una cantidad ilimitada pues la bodega es bastante grande. Sin embargo, hay un costo unitario de mantención de unidades en inventario que se lista en la última columna de la tabla para un producto final empacado y que se asume no cambia en este horizonte de planificación. Asuma que el costo unitario de inventario de un producto final no empacado consiste en restar 4 euros por unidad al valor dado en la tabla para el costo de inventario de uno empacado. El actual inventario es nulo y no hay requerimientos de inventario al final del periodo de planificación.

Cada vez que se emplea la línea de empaque esta debe ser limpiada cuando se planifica empacar cada tipo de producto en un periodo y este proceso de limpieza o esterilización tiene un costo elevado. Dado lo anterior, se espera encontrar una solución donde no necesariamente se empaque de todos los tipos de productos finales en cada periodo. Para representar correctamente esta situación se tomará en cuenta un costo de setup que es independiente del periodo y la cantidad empacada pero si del tipo de producto y está dado por 500.000, 900.000, 800.000 y 900.000 euros para A, B, C y D, respectivamente.

Formule y resuelva computacionalmente un modelo de optimización que permita hallar una política óptima de producción que minimice los costos de inventario y setup, satisfaciendo los requerimientos (estimados) de demanda y las limitaciones en la capacidad de las instalaciones.

Variables de Decisión:

Parámetros: Dada la cantidad de datos del problema propuesto es conveniente trabajar con parámetros, de modo de utilizar una notación más compacta que es equivalente, a saber:

Función Objetivo: Se busca minimizar los costos asociados al proceso de empaque y almacenamiento de productos en inventario (empacados y no empacados) durante el período de planificación. Lo anterior se representa por la siguiente expresión:

Restricciones:

Demanda producto empacado para cada producto i y bimestre t: La demanda de producto empacado de cada uno de los 4 productos en los 4 bimestres se debe satisfacer a través de lo empacado en dicho período y los saldos del mismo (si los hubiere) almacenados en períodos previos.

Balance entre no-empacado y empacados para producto i y bimestre t: De forma similar a las restricciones anteriores, la cantidad de producto a empacar en un período (para cualquiera de las 4 variedades: A, B, B o D) se obtiene como un diferencial entre la producción de producto no empacado más el inventario inicial de producto no empacado menos la cantidad de producto no empacado que se deje en inventario al final del período.

Restricciones Lógicas: La cantidad de producto en un bimestre para un producto en particular no podrá superar las 50.000 unidades en caso que se decida empacar dicho producto en aquel período, en caso contrario no se empaca.

Capacidad de empacado para cada bimestre t: La cantidad de productos A, B, C o D que en total se empaquen en cada período no puede superar la capacidad de empaque de 50.000 unidades por período.

Capacidad de producción en cada familia y bimestre t: Se debe respetar la capacidad de producción de producto no empacado para cada variedad y en cada período del horizonte de planificación.

No negatividad: Las variables de decisión deben adoptar valores no negativos.

La siguiente imagen muestra la solución óptima (celdas amarillas) y valor óptimo (celda celeste) alcanzado a implementar este modelo de Programación Entera Mixta haciendo uso de Premium Solver Pro.

Consideremos el producto A de modo de ejemplificar respecto a la interpretación de los resultados. Se producen 6.000 unidades del producto A y se empacan sólo 5.000 de ellas en el bimestre 1 (con las que se satisface la demanda del bimestre 1), en consecuencia, al final del período se dispone de 1.000 unidades de producto A no empacado. Notar adicionalmente que a excepción del producto D para el resto de los productos no se empaca en todos los períodos.

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

[sociallocker]solver-produccion-y-empaque[/sociallocker]