Solucionador de Problemas de Asignación

¿Qué es el problema de asignación?

El problema de asignación es un problema fundamental de optimización combinatoria: dados n agentes y n tareas con una matriz de costos C, encontrar una asignación uno a uno que minimice el costo total.

El algoritmo húngaro (método Kuhn-Munkres, 1955) resuelve en O(n³). Reduce iterativamente la matriz mediante sustracción de filas y columnas, luego encuentra la asignación óptima mediante caminos aumentantes.

Para matrices rectangulares, se añaden filas o columnas ficticias con costo 0. Agentes o tareas no asignados se reportan por separado.

Formula: Minimizar Σ C[i][σ(i)] para todo i sujeto a que σ sea una permutación (correspondencia uno a uno) Pasos del método húngaro: 1. Restar los mínimos de fila 2. Restar los mínimos de columna 3. Cubrir los ceros con el mínimo de líneas 4. Ajustar la matriz y repetir hasta el óptimo

Ejemplo de cálculo

Matriz de costos: [[9,2,7],[6,4,3],[5,8,1]]. Reducción por filas → [[7,0,5],[3,1,0],[4,7,0]]. Reducción por columnas → [[4,0,5],[0,1,0],[1,7,0]]. Los ceros permiten una tarea por agente: Agente 1→Tarea 2 (costo 2), Agente 2→Tarea 1 (costo 6), Agente 3→Tarea 3 (costo 1). Costo total = 9, menor que el emparejamiento tentador Agente 2→Tarea 3, Agente 3→Tarea 1 (10).

Cuándo usar esta calculadora

• Un supervisor de producción que asigna trabajadores a máquinas para minimizar el tiempo total de procesamiento o el costo
• Un gerente de proyecto que asigna miembros del equipo a tareas según la coincidencia de habilidades y las estimaciones de esfuerzo
• Un coordinador de logística que asigna vehículos de reparto a rutas para minimizar la distancia total recorrida
• Un administrador universitario que programa salas de examen para cursos a fin de minimizar conflictos o distancias de desplazamiento

Errores comunes a evitar

• Introducir costos de forma inconsistente — todos los valores de la matriz de costos deben usar la misma unidad (dólares, horas, distancia); mezclar unidades produce asignaciones sin sentido
• Olvidar cambiar entre los modos minimizar y maximizar — si asigna por beneficio o preferencia (mayor es mejor), seleccione maximizar; para costo o tiempo (menor es mejor), seleccione minimizar
• Usar la asignación en problemas con múltiples asignaciones por agente — el algoritmo húngaro asigna cada agente exactamente a una tarea; si los agentes pueden manejar varias tareas, use un modelo diferente
• No manejar los emparejamientos inviables — si ciertas combinaciones agente-tarea son imposibles, fije su costo en un número muy grande en lugar de dejarlas en cero

Cómo interpretar los resultados

• El costo total representa el óptimo global — ninguna otra asignación uno a uno puede lograr un total menor (o mayor, en el caso de maximización)
• Si algunas filas o columnas aparecen como no asignadas, hay más agentes que tareas (o viceversa) — esos agentes/tareas quedan libres
• Compare el total óptimo con la asignación ingenua (p. ej., fila 1 a columna 1) para ver cuánta mejora aporta el algoritmo

Normas y referencias relacionadas

• Kuhn, H. W. (1955), 'The Hungarian Method for the Assignment Problem', Naval Research Logistics Quarterly — publicación original del algoritmo
• Munkres, J. (1957), 'Algorithms for the Assignment and Transportation Problems', Journal of the SIAM — el refinamiento que estableció la ejecución en tiempo polinómico
• Burkard, Dell'Amico & Martello (2009), Assignment Problems (SIAM) — referencia moderna integral sobre modelos y algoritmos de asignación

Preguntas frecuentes

¿Se puede maximizar?

Sí. Negar todos los costos o restar del máximo, luego resolver la minimización. La asignación óptima es la misma.

¿Si el número de trabajadores y tareas no es igual?

Se añaden filas o columnas ficticias con costo 0. Las asignaciones a entradas ficticias indican trabajadores o tareas no asignados.

¿Puede el problema de asignación manejar restricciones del mundo real como habilidades o disponibilidad de los trabajadores?

No directamente en la formulación básica. Sin embargo, puede codificar asignaciones inviables fijando su costo en un número muy grande (p. ej., 999999), lo que en la práctica impide que el algoritmo las seleccione. Para restricciones complejas, considere usar solucionadores de programación lineal entera.