¿Cuál es el problema de asignación?

El problema de asignación es un problema clásico de optimización combinatoria: dado un conjunto de trabajadores y tareas, cada uno con un costo asociado, encontrar el emparejamiento uno a uno que minimice el costo total. Aparece naturalmente en programación, logística, asignación de recursos e investigación operativa — cualquier situación en la que necesites emparejar dos grupos de la manera más eficiente posible.

El problema se resuelve con el algoritmo húngaro (también llamado algoritmo de Munkres), un método eficiente desarrollado en los años 50. A diferencia de los enfoques de fuerza bruta que deben evaluar cada permutación, el algoritmo húngaro encuentra la solución óptima en tiempo polinómico, lo que lo hace práctico incluso para matrices moderadamente grandes.

Descripción de la herramienta

Ingresa una matriz de costos que represente cuánto cuesta asignar cada trabajador a cada tarea, luego haz clic en Resolver para encontrar instantáneamente la asignación óptima. La herramienta destaca qué pares trabajador-tarea minimizan el costo total y muestra el resultado en una tabla clara junto con el costo total óptimo.

Ejemplos

Matriz de entrada (3 trabajadores × 3 tareas):

Tarea 1 Tarea 2 Tarea 3
Trabajador 1 400 150 400
Trabajador 2 400 450 600
Trabajador 3 300 225 300

Asignaciones óptimas:

Trabajador Tarea Costo
Trabajador 1 Tarea 2 150
Trabajador 2 Tarea 1 400
Trabajador 3 Tarea 3 300

Costo total: 850

Características

  • Matriz editable — haz clic en cualquier celda o encabezado de columna para renombrar trabajadores, tareas y costos directamente en la tabla
  • Tamaño configurable — admite matrices de 2×2 hasta 8×8
  • Resultados instantáneos — el algoritmo húngaro se ejecuta en el navegador sin viajes al servidor

Cómo funciona

La herramienta utiliza el algoritmo de Munkres (húngaro) para resolver el problema de asignación de manera óptima. Construye una matriz de costos a partir de tus entradas, aplica una serie de pasos de reducción de filas y columnas, e iterativamente encuentra un emparejamiento máximo de ceros hasta que se identifica una asignación óptima completa. La complejidad temporal es $O(n^3)$, donde $n$ es la dimensión de la matriz.

Para matrices no cuadradas (más trabajadores que tareas o viceversa), el algoritmo rellena la matriz con ceros para que cada trabajador y cada tarea sean emparejados.

Opciones explicadas

  • Número de trabajadores / filas — controla cuántas filas aparecen en la matriz de costos (2–8)
  • Número de tareas / columnas — controla cuántas columnas aparecen en la matriz de costos (2–8)
  • Celdas de la matriz de costos — ingresa el costo de asignar un trabajador específico a una tarea específica; se acepta cualquier valor numérico

Limitaciones

  • El tamaño de la matriz está limitado a 8×8 (64 celdas)
  • El algoritmo minimiza el costo total; para maximizar (por ejemplo, para matrices de ganancias), niega los valores antes de ingresarlos
  • Los valores de celdas no numéricos se tratan como cero