Según lo descrito en el artículo Solución del Problema del Vendedor Viajero, una de las situaciones potenciales a la que nos podemos enfrentar es que la solución de asignación obtenida represente un subcircuito, lo cual naturalmente no da respuesta a la problemática que el modelo de agente viajero desea abordar. En este contexto existen diversas estrategias algorítmicas que permiten enfrentar esta situación entre las cuales destaca el Algoritmo de Plano de Corte.
La idea del Algoritmo del Plano de Corte es agregar un conjunto de restricciones que, cuando se incorporan al Problema de Asignación garanticen evitar la formación de un subcircuito. Consideremos un problema con n ciudades, asociar una variable continua con las ciudades 2,3,…,n. A continuación definir un conjunto de restricciones adicionales de la siguiente forma:
Estas restricciones al añadirse al Modelo de Asignación, eliminarán todas las soluciones de subcircuito de forma automática, pero no eliminarán alguna solución de circuito.
A modo de ejemplo consideremos nuevamente el problema de secuenciamiento de la producción donde nos interesa determinar el orden en el cual se deben producir 4 colores de pintura.
A continuación se define un modelo de optimización haciendo uso del lenguaje de programación matemática AMPL. Para ello se puede utilizar un editor de texto como Bloc de Notas o WordPad. La siguiente imagen muestra la sintaxis utilizada en la definición del modelo del ejemplo propuesto donde se incorpora las restricciones que evitan los subcircuitos. Notar que es importante guardar el archivo con el formato adecuado (.mod) para lo cual simplemente en el caso de utilizar Bloc de Notas seleccionamos «Archivo», seguido de «Guardar como …» y luego en «Nombre» se ingresa un nombre arbitrario seguido de .mod (por ejemplo, modelo.mod).
El siguiente paso es generar un nuevo archivo con los datos o parámetros del problema. Básicamente aquellos que resumen el tiempo (en minutos) necesarios para la limpieza al realizar un cambio de colores, según se describe al inicio de este artículo. Notar que para evitar aquellas asignaciones infactibles (como que a un color le precede el mismo en la secuencia) se asignan «constantes grandes» a los elementos en la diagonal. El archivo se procesa y guarda de forma similar al caso del modelo pero con la extensión .dat (por ejemplo, matriz.dat).
Finalmente será necesario construir un tercer archivo con extensión .run que provee de instrucciones adicionales para efectos de la resolución computacional y que facilita la interpretación de los resultados (por ejemplo, solucion.run).
Una vez definido el modelo, datos y archivo run, podemos utilizar un solver de Programación Entera Mixta de los disponibles en el Servidor NEOS. En particular recomendamos utilizar el solver XpressMP donde se deberá adjuntar los archivos con extensión .mod, .dat y .run (respectivamente) según se muestra a continuación (recordar que el nombre asignado al archivo es arbitrario, no así su extensión).
Luego seleccionamos «Submit to NEOS» y los resultados se mostraran en el navegador de Internet, además de recibir un informe de respuestas en la dirección de correo electrónico que ingresamos. La siguiente imagen muestra un extracto de dichos resultados:
Notar que XpressMP encuentra como recorrido óptimo la secuencia 1-2-4-3-1, es decir, corresponde a producir en el siguiente orden: Blanco, Amarillo, Rojo, Negro, con un tiempo total de setup de 98 minutos.
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 la distancia de la ciudad i a la ciudad j, donde , 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, .
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, , 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 , es decir, . 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.
El siguiente artículo desarrolla un ejemplo de la Planificación de Requerimientos de Materiales o MRP para una empresa de manufactura que se dedica a las operaciones de ensamblaje, como lo que se podría observar en un sistema productivo Flow Shop. En particular consideraremos una empresa que produce carros de golf, la cual ha recibido una orden de 100 carros para la semana 6, 100 para la semana 8 y 100 para la semana 9. La información sobre la producción de los carros de golf se presenta en la tabla a continuación. Las partes en la primera columna alineadas a la izquierda se hacen con las partes centradas.
Notar que la empresa utiliza distintas políticas de lotificación lo que vuelve más complejo el desarrollo del MRP. Se propone la siguiente abreviación para las mismas: LxL: Lote a Lote; C.T.M: Costo Total Mínimo; C.U.M: Costo Unitario Mínimo; EOQ: Cantidad Económica de Pedido). Para cada ítem el costo de emitir un pedido es de $400 (independiente del tamaño del pedido) y el costo unitario semanal de almacenamiento de inventario es de $1. En base a la información anterior se solicita:
Realizar el Bill of Materials (BOM) para el carro de golf.
El BOM o lista de materiales es un registro donde figuran todos los componentes de un articulo, las relaciones padre – componente y las cantidades de uso derivadas de los diseños de ingeniería y de procesos. Una forma tradicional de representar la información del BOM es a través del árbol estructural del producto el cual se presenta a continuación:
Cada carro de golf requiere de un «Top» y una «Base». Adicionalmente cada «Top» necesita de 4 «Supports» y 1 «Cover». Análogamente cada «Base» necesita 1 «Motor», 1 «Body» y 2 «Seats». Finalmente cada «Body» necesita 1 «Frames», 1 «Controls» y 4 «Wheel Assemblies». Por cierto la información es consistente con lo detallado en la tabla inicial pero la representación gráfica de la lista de materiales facilita su rápida interpretación.
Con esta información desarrollamos el MRP del carro de golf, siendo el producto final el que establece las necesidades brutas de 100 unidades en las semanas 6, 8 y 9, según lo indicado en los datos del problema. En este sentido al no disponer de inventario inicial del carro de golf (terminado) las necesidades brutas de los períodos indicados son al mismo tiempo necesidades netas. Por ello se requiere entradas de pedidos planeados de 100 unidades en las semanas 6, 8 y 9 para lo cual la emisión (expedición) de las mismas debe ser con una semana de antelación dado el tiempo de reposición o lead time de una semana.
En el caso del ítem «Top» las necesidades brutas corresponden al mismo período en el cual se emiten los pedidos planeados del carro de golf. Ahora bien, se dispone de 40 unidades de inventario inicial de «Top» lo que se traduce a que el requerimiento neto de este producto de demanda dependiente sea de 60 unidades en la semana 5. En consecuencia se requiere la entrada de un pedido planeado de 60 unidades de «Top» en la semana 5, el cual se emite en la semana 4 (lead time de 1 semana).
De forma análoga se puede completar la información correspondiente para la «Base» que al igual que «Top» utiliza la política de lotificación lote a lote, por tanto se satisface de forma exacta el requerimiento neto positivo de cada período (si lo hubiere).
En el caso del ítem «Supports» se utiliza el método de Costo Unitario Mínimo. Descontando de las necesidades brutas el inventario inicial, los requerimientos netos de dicho componente son 40, 400 y 400 en las semanas 4, 6 y 7, respectivamente. Con ello se aplica el Costo Unitario Mínimo agrupando las necesidades: por ejemplo, un pedido de 40 unidades para satisfacer la necesidad neta exacta de la semana 4 no genera costos de inventario (C.Inv) pero sí un costo de emisión (C.Em) de $400 (el costo unitario es $400/40=$10). En el caso de consolidar las necesidades de la semana 4 y 6 se deberá hacer un pedido de 440 unidades. En este caso el costo de emisión (que es independiente del tamaño de pedido) seguirá siendo $400 y el costo de inventario es de $800 (al final se la semana 4 y 5 quedaran 440-40 unidades en inventario, con un costo unitario de almacenamiento semanal de $1, es decir, 400*$1+400*$1=$800). El costo unitario en este caso es ($800+$400)/440=2,727 (aprox). Finalmente se analiza la alternativa de realizar un pedido único de 840 unidades (para cubrir los requerimientos netos de las semanas 4, 6 y 7). El costo de emisión es de $400 y el de almacenamiento es $2.000 (800*$1+800*$1+400*$1), con un costo unitario de ($2.000+$400)/840=$2,857 (aprox).
En consecuencia el Costo Unitario Mínimo se alcanza agrupando las necesidades netas de la semana 4 a la 6 y se deberá realizar un pedido de 440 unidades. Luego se requerirá un pedido de 400 unidades el cual satisface el requerimiento neto de la semana 7.
Para el producto «Cover», sus necesidades brutas dependen de la emisión de pedidos planeados del «Top» en una razón 1 a 1. Como el ítem «Cover» utiliza la política lote a lote, los pedidos satisfacen las necesidades netas exactas (notar que no se dispone de inventario inicial) y en cada caso son emitidos con una semana de antelación dado el tiempo de reposición.
Un «Motor» es necesario para cada «Base» (según se detalla en el BOM) y este producto utiliza al igual que «Supports» la política de Costo Unitario Mínimo. No obstante se dispone en este caso de un inventario inicial suficiente (300 unidades) para cubrir los requerimientos brutos en las semanas 4, 6 y 7.
El ítem «Body» al igual que el «Motor» depende de la «Base». Este producto («Body») utiliza la política de Tamaño Fijo de Pedido de Q=300 unidades, es decir, cada vez que se necesite se emite un pedido de esa magnitud. Adicionalmente se dispone de un inventario inicial de 50 unidades de «Body» por lo cual la necesidad neta es de 30 unidades en la semana 4 (80-50). Por ello se emite un pedido de 300 unidades (en la semana 3) el cual se recibe al inicio de la semana 4, en consecuencia, el saldo disponible proyectado al final de la semana 4 es de 270 unidades (que de hecho es suficiente para cubrir las necesidades brutas de las semanas 6 y 7).
Por cada «Base» se necesitan 2 «Seats», luego las necesidades brutas de este último ítem es de 160, 200 y 200 (semanas 4, 6 y 7, respectivamente). Este producto utiliza la lotificación de Costo Total Mínimo la cual se detalla a continuación.
Notar que para la semana 4 es sólo necesario 40 unidades (dado el inventario inicial de 120 unidades). Naturalmente un pedido de este tamaño no genera costos de almacenamiento pero si el costo fijo de pedido de $400. Por otra parte un pedido de 24o unidades que cubre las necesidades netas de la semana 4 a la 6 tiene un costo de emisión de $400 y un costo de inventario de $400 (200*$1+200*$1). En este caso el diferencial en valor absoluto entre el costo de preparación de pedido y de inventario es de $0 que es el primer Costo Total Mínimo. Luego se realiza un pedido adicional de 200 unidades para enfrentar los requerimientos de la semana 7.
Continuando el desarrollo del MRP del carro de golf, los ítems «Frames» y «Controls», ambos dependen del «Body» en una relación 1 a 1. En cada caso es suficiente con un único pedido de la magnitud que establece el Tamaño Fijo de Pedido.
Finalmente se requieren 4 «Wheels» por cada «Body» lo que determina el requerimiento bruto de 1.200 unidades de «Wheels» en la semana 3. Como se dispone de un inventario inicial de 240 unidades y no hay más requerimientos después de la semana 3, es suficiente con un pedido único de 960 que se emite en la semana 2.
La siguiente tabla resumen muestra el resultado final de la Planificación de Requerimientos de Materiales (MRP):
Las técnicas de tipo cualitativo para efectuar pronósticos de ventas (demanda) se basa en el juicio de un grupo de personas conocedoras, con experiencia y expertas en la materia, lo que les permite dar su opinión y pronosticar el futuro en relación a un tema determinado; esta opinión puede consistir en la entrega de valores o rango de valores sobre el futuro. Estas técnicas se utilizan cuando no existen datos numéricos que permitan el uso de técnicas cuantitativas o cuando estos datos son poco confiables. Esta situación se presenta generalmente cuando se requiere planificar a largo plazo basándose en algún pronóstico, donde la exactitud necesaria es mediana, a diferencia de la planificación de corto plazo donde la exactitud necesaria es más alta, y de preferencia se usan técnicas cuantitativas.
A continuación un breve listado de las principales técnicas cualitativas para pronóstico de ventas. Para acceder a información detallada de cada una de ellas selecciona el enlace de interés:
El diseño de procesos como también la planeación de la capacidad de las instalaciones corresponden a decisiones estratégicas (largo plazo) que suelen ser apoyadas en algún nivel a través de la utilización de métodos de pronósticos cualitativos. El nivel administrativo alto es quien participa activamente de dichas decisiones dada su trascendencia y en consecuencia el efecto que tendrán éstas en las operaciones cotidianas de la empresa.
El siguiente cuadro propone una clasificación aproximada de los métodos de pronósticos más idóneos según el ámbito de las decisiones que se deben tomar. Por cierto su interpretación debe ser flexible, por ejemplo, los métodos cualitativos de proyección de demanda pueden ser utilizados también como complemento a métodos de naturaleza cuantitativa en la planificación táctica (mediano plazo).
Finalmente la selección de la técnica de pronóstico a utilizar se ve influida por diversos factores: la precisión deseada del pronóstico, la disponibilidad de personal calificado, el costo del procedimiento, validez y disponibilidad de datos históricos y los períodos futuros a proyectarse. En este contexto se debe procurar que el método seleccionado sea preciso, como también factible de ser sensibilizado.
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.
con las ciudades 2,3,…,n. A continuación definir un conjunto de restricciones adicionales de la siguiente forma:
la distancia de la ciudad i a la ciudad j, donde 
, el modelo del agente o vendedor viajero corresponde a:
.
, lo que naturalmente no es una solución factible para el problema que se busca resolver.
, es decir, 
. 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.
