Aplicación a problemas de
mediana complejidad
Estos problemas agrupan una gran cantidad de variantes.
Problemas de El objetivo es recorrer una conjunto de puntos (nodos) al menor
costo, tocando todos los nodos en su recorrido.
Ruteo
Algunas variantes son:
Ruteo con capacidad limitada
Ruteo con capacidad y ventana de tiempo
El Agente Viajero
Un vendedor de libros que vive en Ciudad Capital (Ciudad 1), debe
visitar una vez al mes a cinco clientes que están en la Ciudades 2, 3, 4
y 5 respectivamente.
La red de caminos y sus distancias, se muestran a continuación.
El objetivo es minimizar la distancia total de viaje del vendedor.
Ejemplo
5 5
𝑀𝑖𝑛 𝑍 = 𝑑𝑖𝑗 𝑋𝑖𝑗
𝑖=1 𝑗 =1
8
𝑗 =5
22 16
𝑋𝑖𝑗 = 1 𝑐𝑜𝑛 𝑖 = 1, 2, … , 5
12 13 11 𝑗 =1
15 𝑗 =5
18 19 𝑋𝑖𝑗 = 1 𝑐𝑜𝑛 𝑗 = 1, 2, … , 5
𝑖 =1
21
𝑋𝑖𝑗 = 0, 1
Parámetros
𝑑𝑖𝑗 = 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎 𝑒𝑛𝑡𝑟𝑒 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑖 𝑦 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑗 Variables:
1, 𝑠𝑖 𝑠𝑒 𝑙𝑙𝑒𝑔𝑎 𝑑𝑒 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑖 𝑎 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑗
𝑋𝑖𝑗 =
0, 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Problema de asignación de turnos
Las enfermeras de un hospital llegan cada 4 horas y trabajan en
turnos de 8 horas continuas. La administración ha decidido definir
6 cambios de turno al día para minimizar las distracciones y los
problemas de comunicación que ocurren en los cambios de turno.
El hospital ha realizado un análisis del trabajo requerido durante
cada uno de los seis períodos del día. Las características de cada
período se ven en la tabla.
Las enfermeras que empiezan a trabajar en los períodos 2, 3 y 4
ganan US$ 40 al día, y aquellas que comienzan en los períodos 1, 5
y 6 ganan US$ 50 al día. ¿Cuántas enfermeras deben empezar a
trabajar en cada turno para minimizar los costos por salarios?
Programación de Máquinas
.- Cómo equilibrar la línea de producción. En un trabajo fabril es necesario realizar cinco operaciones, A, B,
C, D y E, cada una de las cuales se puede llevar a cabo ya sea en la máquina 1 o en la máquina 2. El tiempo
que se requiere para cada operación en cada una de las máquinas mencionadas se presenta en la siguiente
tabla.
Formule y resuelva una PLE para asignar los trabajos a las máquinas, de modo que si T1 es el tiempo total
en el que se ocupa la máquina 1 y T2 dicho tiempo en la máquina 2, entonces Max (T1, T2) se minimiza.
Set Covering
Se desea construir el menor número de estaciones de bomberos que
cubra un territorio de 6 ciudades: Ciudad1, Ciudad2, Ciudad3, Ciudad4,
Ciudad5, y Ciudad6. Las estaciones se podrían construir en cualquiera
de las ciudades, pero garantizando siempre que todas las ciudades
dispongan al menos de una estación a una de distancia máxima de 15
minutos. La Tabla 1 muestra los tiempos en minutos para ir de una
ciudad a otra y la Tabla 2 muestra el costo asociado a construir una
estación
Plan Agregado con PL
La planeación agregada es un proceso para determinar una estrategia
de forma anticipada que permita satisfacer los requerimientos
(demanda) del sistema, al mismo tiempo que optimiza los recursos del
mismo; cuyo desarrollo se lleva a cabo en el corto y mediano plazo.
Horizonte de tiempo ➔ 6 a 18 meses
Factores:
• Mano de obra: Costo de tiempo normal.
• Contratación: Costos asociados a la búsqueda de mano de obra, a la contratación misma
y a las actividades de inducción.
• Despidos: Costos legales (compensaciones e indemnizaciones) de despedir empleados.
• Horas extras.
• Subcontratación (Outsourcing).
• Inventario: Costos de mantenimiento de inventario, incluso costos de oportunidad por
lucro cesante.
• Quiebres de stock (faltantes).
• Costos de financiamiento del plan.
Restricciones
Todos los sistemas objeto de planeación agregada se encuentran sujetos a restricciones y
de diversos tipos, tales como:
• Restricciones de demanda: [Link]: Requerimientos por periodo.
• Restricciones laborales: [Link]: Máximo número de horas extras posibles.
• Restricciones de espacio: [Link]: Máxima capacidad de almacenamiento.
• Restricciones de la cadena de valor: [Link]: Capacidad máxima del proveedor.
• Restricciones de eficiencia: [Link]: Curva de aprendiza en empleados nuevos.
Variables de decisión:
XNi = Cantidad de unidades a producir en tiempo normal en el período i
XHi = Cantidad de unidades a producir en tiempo extra en el período i
Ii = Unidades en inventario en el período i
Fi = Unidades faltantes en el período i
Si = Unidades a subcontratar en el período i
NCi = Cantidad de trabajadores contratados en el período i
NDi = Cantidad de trabajadores despedidos en el período i
Función Objetivo
Está formada por la sumatoria de cada una de las variables de decisión por el costo
unitario de su utilización.
Restricciones
1. Restricciones de demanda: cómo se abastecerá la demanda de cada período (suma de
unidades en tiempo normal y extra + Inventario del período anterior – Inventario del
período – Faltantes de periodo anterior + Faltantes del período + Unidades
subcontratadas)
2. Restricciones de capacidad: capacidad de las bodegas (inventarios), límite de faltantes,
límite de horas extras, límite de subcontratación.
3. Restricciones dadas por las políticas: stock de seguridad, faltantes, etc.
4. Otras restricciones.
