Dada una matriz de costes n×n, el problema de emparejar uno-a-uno n trabajadores/recursos con n tareas para minimizar el coste o tiempo total; uno de los problemas combinatorios fundacionales de la OR (en la literatura: Assignment Problem; resuelto por el algoritmo húngaro de Kuhn-Munkres en tiempo polinómico O(n³)).
En pocas palabras
¿Te suena?
- Somos una oficina de ingeniería con 5-30 ingenieros + 10-50 encargos de proyecto; la decisión semanal de quién va a cada encargo se toma por intuición y se confirma con el planificador + hoja de cálculo.
- Somos un bufete que reparte 20-80 expedientes nuevos por semana; el coste de cada abogado por tipo de expediente (especialización + tarifa horaria + relación previa con el cliente) es distinto, y el reparto se hace por antigüedad o por 'quién está disponible'.
- Somos una empresa de facility-management con 10-50 vehículos + técnicos urbanos; asignamos 10-50 avisos diarios a los técnicos, con distancias + competencias + duraciones distintas.
- Somos planificadores en un hospital con 5-30 cirujanos + 10-50 casos; la duración y la puntuación de calidad de cada cirujano por tipo de caso son distintas, y la asignación se hace con la intuición 'el cirujano más experto al caso más complejo'.
- Somos un centro educativo; 20-80 profesores + 20-80 clases/asignaturas a casar, con preferencias + especialidad + adecuación al nivel distintas, y la asignación es semi-manual.
- Nuestra matriz de asignación es 'rectangular' (7 técnicos + 12 tareas, o 15 técnicos + 9 tareas) — al no ser cuadrada no está claro cómo resolver con el algoritmo húngaro ni si debemos aplicar extensión con dummy.
- Sabemos que la asignación actual no es óptima, pero no podemos medir cuánto se aleja del óptimo — no tenemos número de referencia 'coste óptimo'.
- Estamos atados a un software WFM de proveedor único; dice tener 'módulo de optimización de asignación', pero qué algoritmo (húngaro, LAP, heurística) usa no es transparente.
Por qué importa
Cómo se resuelve
Profundidad técnica
Cómo se resuelve
Profundidad técnicaEn una frase: Dada una matriz de costes C[i,j] para pares persona-tarea (tarifa horaria × duración esperada + penalización por desajuste de competencia + desplazamiento), el algoritmo húngaro encuentra el emparejamiento óptimo uno-a-uno en tiempo O(n³) — cada persona a una sola tarea, cada tarea a una sola persona, con coste total mínimo.
En la literatura de Investigación de Operaciones (disciplina que usa matemáticas e informática para resolver decisiones de negocio) y optimización combinatoria, este problema se estudia como Assignment Problem (problema de asignación). Su solución clásica es el algoritmo húngaro (1955); en 1957 se reformuló como un procedimiento polinómico O(n³) totalmente formal, por lo que en la literatura moderna también se conoce como algoritmo de Kuhn-Munkres. El nombre viene de los teoremas de emparejamiento bipartito cuyos cimientos sentaron matemáticos húngaros. Tres fases:
1. Modelado — matriz de costes n×n + asignación uno-a-uno. Entradas: (a) n recursos (p. ej. personal, vehículos, máquinas) — cada uno con perfil de competencias, coste por hora, ubicación/disponibilidad, (b) n tareas — cada una con tipo, duración esperada, ubicación, plazo, requisito de calidad, (c) matriz de costes n×n C[i,j] — el coste (o tiempo, o beneficio negativo) de asignar el recurso i-ésimo a la tarea j-ésima; componentes: penalización por desajuste de competencia + tarifa horaria × duración esperada + coste de desplazamiento + penalización de preferencia/encaje. Variables de decisión: x[i,j] ∈ {0,1} — si el recurso i se asigna a la tarea j. Restricciones: cada recurso a exactamente una tarea (∑_j x[i,j] = 1, ∀i), cada tarea a exactamente un recurso (∑i x[i,j] = 1, ∀j). Objetivo: minimizar ∑{i,j} C[i,j] × x[i,j]. El modelo debe ser cuadrado y equilibrado; en el caso rectangular (m≠n) se usa extensión con dummy: con m=7 personas + n=12 tareas, añade 5 personas dummy; el coste de cada dummy en cada tarea es 0 (si es admisible dejar la tarea sin asignar) o un M muy grande (si toda tarea debe asignarse). Para m>n, añade tareas dummy. Para la variante de maximización (maximizar beneficio total), sustituye coste por -beneficio; el mismo algoritmo se ejecuta.
2. Solución — algoritmo húngaro y alternativas modernas. El núcleo del algoritmo húngaro es reducción de filas/columnas + cobertura sobre el grafo de ceros + aumentación en celdas no cubiertas: (a) resta el mínimo de cada fila (cada fila tiene al menos un cero), (b) resta el mínimo de cada columna (cada columna tiene al menos un cero), (c) encuentra un emparejamiento máximo en los ceros, (d) si el emparejamiento no es perfecto (n pares), cubre las filas/columnas no asignadas con el número mínimo de líneas mediante un procedimiento secuencial de cobertura, resta el mínimo de las celdas no cubiertas de las filas no cubiertas y súmalo en las intersecciones de cobertura, actualiza el conjunto de ceros, (e) repite hasta encontrar emparejamiento perfecto. Complejidad O(n³), tiempo polinómico, óptimo garantizado. Alternativas modernas: LAP — Linear Assignment Problem resuelto por algoritmos del camino aumentante más corto, 5-20 veces más rápido en la práctica; el algoritmo auction — apto para paralelización, práctico a gran escala. LP-base alternativa: la relajación LP del problema es totalmente unimodular y devuelve el óptimo entero directamente. Bottleneck Assignment: objetivo no es la suma sino el máximo coste asignado (equidad max-min). Quadratic Assignment (QAP): el coste depende de interacciones — NP-difícil, problema distinto.
3. Integración en campo. Salida en tres capas: (a) lista de asignación — cada par recurso-tarea, inicio-fin esperado, contribución al coste; el planificador la publica, (b) comparación de alternativas — junto al óptimo se ofrecen 2-3 alternativas casi-óptimas (prioridad de distancia, de competencia, de continuidad con cliente), (c) realimentación a la matriz de costes — tras la ejecución, se mide la duración/calidad real y se actualizan las estimaciones. Integración: HR (perfil de competencias, salarios, calendario de disponibilidad), CRM/proyecto (cartera de tareas, continuidad), GIS (localización + distancia). Comité mensual de asignación: análisis real-vs-óptimo, calibración de la matriz, equilibrio de carga, continuidad persona-cliente, satisfacción tras la asignación.
Alternativas
Manual + hoja de cálculo
GratisCero licencia
Para quién: Pool pequeño (recursos <10, tareas <10), asignación de una sola etapa
- + Coste de software cero
- + El conocimiento del planificador queda en primer plano
- + Para matrices 5×5 o 7×7 puede encontrarse un casi-óptimo manualmente
- − Por encima de 10×10, óptimo manual inviable — intuición desvía 15-30%
- − Deriva de estimación de la matriz no se mide
- − Caso rectangular (m≠n) se gestiona por intuición; no se aplica extensión con dummy
- − Justificación de la asignación no queda registrada — quejas de transparencia sin respuesta
Módulo húngaro/LAP open-source + integración a medida
Código abiertoLicencia gratis; desarrollo 8-16 semanas o 300K-1M TRY consultoría
Para quién: Empresa de servicios mediana con equipo técnico, integrada con HR/CRM
- + Algoritmo húngaro + LAP maduros en bibliotecas open-source
- + Tiempo polinómico O(n³) — 100×100 en segundos
- + Óptimo garantizado; sin deriva heurística
- + Variantes rectangular + maximización + bottleneck disponibles
- + Código abierto — transparencia auditable
- − Requiere conocimiento OR + equipo de software propio
- − Estimación de la matriz de costes requiere modelo de datos aparte — el algoritmo resuelve, la entrada la das tú
- − Asignación dinámica multi-período requiere modelado extra
- − Mantenimiento queda en la empresa
Software de gestión de personal (WFM) con módulo de asignación
Empresarial200K-1.2M TRY licencia + 80K-400K TRY/año mantenimiento (banda del mercado TR)
Para quién: Empresa mediano-grande (recursos 30-200), necesidad integrada CRM/HR/operaciones
- + Módulo de asignación integrado (biblioteca húngara o LAP dentro)
- + HR + CRM + planificación integrados
- + Asignación dinámica multi-período soportada
- + Soporte operativo + formación
- − Variante de algoritmo puede no ser transparente
- − Licencia alta + despliegue largo (9-15 meses)
- − Modelo de estimación de la matriz 'caja negra' — debe negociarse
- − Riesgo de lock-in con proveedor único
Plataforma enterprise OR + modelo de asignación a medida
EmpresarialAnual 600K-3M TRY (plataformas OR grandes)
Para quién: Empresa grande, multi-región + multi-período + requisitos estocásticos
- + Húngaro + LAP + auction + variantes estocásticas integrados
- + Generalized Assignment Problem (GAP — varias tareas por recurso) como módulo
- + Optimización multi-objetivo (coste + equidad + continuidad)
- + Metodología transparente — los resultados son auditables por un especialista independiente
- − Licencia alta + despliegue largo (12-24 meses)
- − Alcance amplio — exceso para escala pequeña/mediana
- − Equipo especialista OR + integración en campo necesario
- − Personalización a la regulación local alarga el proyecto
Recomendación
Pregunta en la reunión
- ¿Qué corre realmente el módulo de asignación por debajo — un algoritmo de emparejamiento sistemático (húngaro / camino de aumento más corto / tipo auction), un solver de programación lineal, o una regla heurística? ¿Queda documentado en la especificación qué variante se usa y si garantiza óptimo?
- ¿Cómo gestiona el caso rectangular (m≠n) — añade fila/columna dummy automáticamente o lo hace el usuario? ¿Cómo elige el coste dummy (0 o M grande)?
- ¿Soporta la variante de maximización (maximizar beneficio total) — la conversión coste/beneficio es automática?
- ¿Soporta bottleneck assignment (equidad max-min)? ¿En qué escenarios se recomienda?
- ¿Cómo se estima la matriz C[i,j] — entrada manual del usuario, derivada del histórico, o híbrido? ¿Hay informe de deriva?
- ¿Soporta asignación multi-objetivo (coste + equidad + continuidad) o sólo objetivo único? ¿Ofrece suma ponderada + frontera de Pareto?
- Tras un piloto con datos operativos reales (6-10 semanas), ¿qué informe de ahorro frente a la asignación manual previa puede entregarse — coste total, tiempo de asignación, equilibrio de carga?
- Si finaliza el contrato, ¿en qué formato estándar podemos exportar el histórico de la matriz, el archivo de asignaciones, el registro de continuidad y los parámetros del algoritmo?
Detalles técnicos
Nota editorial
En el habla común este problema se llama “reparto de trabajo”, “asignación de personal” o “asignación de recursos”. En la literatura académica es el Assignment Problem; la solución clásica es el algoritmo húngaro, también conocido como algoritmo de Kuhn-Munkres, un algoritmo combinatorio polinómico O(n³). El nombre viene de los teoremas de emparejamiento bipartito desarrollados a principios del siglo XX por los matemáticos húngaros Dénes König y Jenő Egerváry; Harold Kuhn construyó el algoritmo sobre esa base en su artículo de 1955, y James Munkres lo convirtió en un procedimiento polinómico formal en 1957. No confundir con #072 (Stable Matching): el stable matching trabaja con listas de preferencias de dos lados — el candidato A prefiere la institución X y la institución X prefiere al candidato A, y el matching se construye para que no haya pareja bloqueante. En la asignación hay sólo una matriz de costes unilateral — la persona tiene un coste sobre la tarea, la tarea no tiene orden de preferencia; no hay pago pero sí coste, y el objetivo es la suma de costes (óptimo social). No confundir con #094 (Transportation Problem): en transporte, m fuentes y n destinos pueden ser distintos (m≠n), y cada fuente puede enviar una cantidad divisible a varios destinos. En la asignación cada recurso va a exactamente un destino y cada destino recibe de exactamente una fuente — asignación cuadrada 0/1.
Punto más olvidado en campo: extensión con dummy para el caso rectangular (m≠n). El algoritmo húngaro original exige matriz cuadrada n×n; en la práctica llega 7 personas + 12 tareas, o 15 personas + 9 tareas. La solución es sencilla pero el profesional no la conoce: extiende a cuadrada con filas/columnas dummy. (a) m<n (menos personas que tareas): añade (n-m) personas dummy, con coste M (muy grande) en cada tarea — si se exige ’toda tarea debe asignarse’; si ’tareas extra pueden quedar sin asignar’ es aceptable, coste 0 y las tareas no asignadas ‘van’ a los dummy (en realidad, quedan sin asignar). (b) m>n (más personas que tareas): añade tareas dummy; el personal asignado a dummy ’no toma encargo esta semana’. Los profesionales desconocen este procedimiento — pérdida de óptimo 10-25%. Segundo punto olvidado: conversión maximización ↔ minimización. Algunos problemas son ‘maximizar beneficio total’ (p. ej. competencia + encaje cliente); el algoritmo húngaro es de minimización, pero sustituyendo coste por -beneficio, o aplicando (max_beneficio - beneficio), se convierte en minimización; el mismo algoritmo. Tercer punto olvidado: deriva en la estimación de la matriz. Para que el algoritmo entregue el óptimo, C[i,j] debe estar bien estimada; estimaciones malas dan asignaciones malas. Cómo se estima la matriz (histórico, fórmula de competencia, tarifa de desplazamiento) es un problema de modelado previo al algoritmo — los profesionales lo hacen por intuición, y la calidad de salida queda acotada por la calidad de estimación. Cuarto punto olvidado: confusión con el problema cuadrático (QAP). En la asignación lineal clásica cada celda es independiente; en QAP dos asignaciones interactúan (si las personas i e i’ van ambas a la misma región, hay coste de transferencia) — NP-difícil, clase distinta (Koopmans-Beckmann 1957). Mezclar produce la sorpresa ‘por qué tarda tanto’.
Ruta paso a paso — para una pyme
Etapa 1 — Mide la matriz de costes y déjala explícita. Al menos 6-12 meses de histórico: por cada par persona-tarea la duración real, la puntuación de calidad, la distancia de desplazamiento, el encaje cliente/proyecto. Fórmula por escrito: C[i,j] = α × duración_estimada[i,j] × tarifa_horaria[i] + β × distancia[i,j] + γ × desajuste_competencia[i,j] + δ × penalización_continuidad[i,j]. Los pesos (α, β, γ, δ) son decisión gerencial; al inicio α=1, β=0.5, γ=2 (alto), δ=0.3. Tras cada asignación se registra la desviación real-vs-estimada.
Etapa 2 — Construye el capital de conocimiento. Mapa de competencias del personal (competencia × nivel), taxonomía de tareas (clases + competencias requeridas + duración media), tarifa de desplazamiento (región×región), reglas de continuidad con cliente (qué clientes exigen el mismo profesional, cuáles lo prefieren). Este dataset alimenta el modelo de estimación de la matriz.
Etapa 3 — Piloto. 6-10 semanas. En un sub-conjunto (p. ej. una región o un tipo de trabajo) calcula el óptimo con el algoritmo húngaro y muéstralo en paralelo a la asignación manual. El planificador decide; el algoritmo recomienda. Pon a prueba el procedimiento dummy para el caso rectangular. Criterios de éxito definidos por adelantado: coste total -10% mín., tiempo del planificador -50% mín., desbalance de carga -20% mín.
Etapa 4 — Despliegue. Extiende a todo el alcance + optimización multi-objetivo en 9-15 meses. Comité mensual: análisis real-vs-óptimo, calibración trimestral, balance de carga, continuidad cliente.
Riesgos — qué puede salir mal
Deriva de estimación de la matriz. Si C[i,j] está mal estimada, el algoritmo encuentra un óptimo equivocado. Solución: calibración trimestral, celdas con desviación >25% disparan análisis.
Competencia multi-dimensional — un único escalar no basta. Solución: formulación multi-objetivo o reportar componentes por separado.
Preferencias en conflicto (dimensión social). Solución: penalización de preferencia en la matriz o alternativas en la frontera de Pareto.
Lock-in con WFM de proveedor único. Sin cláusula de exportación anual en formato estándar, perder el proveedor implica perder la memoria operativa.
Visión técnica de la solución
| Enfoque | Escala típica | Tiempo | ¿Óptimo garantizado? |
|---|---|---|---|
| Asignación intuitiva | Pequeño (n<10) | inmediato | No, 70-85% |
| Manual + hoja (semi-sistemático) | Pequeño (n<10) | minutos | No, casi-óptimo |
| Algoritmo húngaro (Kuhn 1955 / Munkres 1957) | Medio (n<200) | segundos | Sí, O(n³) |
| LAP shortest augmenting path (Jonker-Volgenant 1987) | Medio-grande (n<2000) | segundos | Sí, 5-20× más rápido |
| Auction (Bertsekas 1988) | Grande + paralelo | segundos-minutos | Sí (ε-convergencia) |
| LP genérico (totalmente unimodular) | Toda escala | minutos | Sí (entero por relajación) |
| Bottleneck (max-min) | Equidad | segundos | Sí (búsqueda binaria) |
| QAP (cuadrático) | Interacciones | horas | No, NP-difícil |
| GAP (generalizado) | Varias tareas por recurso | horas | NP-difícil |
Función objetivo:
- Objetivo 1 — Mínimo coste total: asignación lineal clásica.
- Objetivo 2 — Mínimo tiempo total: tiempo-céntrica.
- Objetivo 3 — Bottleneck (max-min): equidad.
- Objetivo 4 — Multi-objetivo: Pareto o suma ponderada.
Variantes — elegir según el campo:
- Asignación lineal clásica (cuadrada + equilibrada).
- Rectangular (m≠n) con dummy.
- Maximización (coste := -beneficio).
- Bottleneck (max-min).
- GAP (capacidades).
- QAP (interacciones).
- Dinámica multi-período.
- Estocástica.
Fuentes académicas
Listadas en el frontmatter bajo sources.
Fuentes
- Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83-97. Fuente fundacional de la solución polinómica; nombre en honor de los matemáticos húngaros König y Egerváry.
- Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32-38. El método de Kuhn convertido en procedimiento polinómico O(n³) formal.
- Burkard, R., Dell’Amico, M. y Martello, S. (2009). Assignment Problems. SIAM. Referencia canónica para los problemas de asignación (linear, bottleneck, cuadrático, generalizado).
- Jonker, R. y Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4), 325-340. Algoritmo LAP — 5-20× más rápido que el húngaro clásico en la práctica.
- Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176(2), 774-793. Revisión de 50 años.
- Bertsekas, D. P. (1988). The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14(1), 105-123. Algoritmo auction apto para paralelización.
- YÖK Thesis Centre — palabra clave: ‘atama problemi’, ‘Macar algoritması’ o ‘Hungarian’ — 25+ tesis de academia TR. tez.yok.gov.tr
Glosario
- Problema de Asignación
- Emparejamiento uno-a-uno de un conjunto de recursos (personas, vehículos, máquinas) a un conjunto de tareas al menor coste o máximo beneficio.
- Algoritmo Húngaro
- Algoritmo combinatorio que resuelve el problema de asignación (matriz de costes n×n, emparejamiento uno-a-uno de coste mínimo) en tiempo polinómico O(n³); Kuhn (1955) y Munkres (1957).
- Emparejamiento Bipartito Ponderado
- Problema de OR de encontrar, en un grafo bipartito con aristas con pesos, un emparejamiento de peso total máximo (o mínimo) entre dos conjuntos disjuntos de vértices.
Problemas relacionados
¿Cómo Construyo Patrones Semanales — Demanda Cubierta, Descanso, Horas y Equidad Sosteniéndose Juntos?
El responsable de RR.HH. o de operaciones de un servicio 7 días 24 horas (centro de llamadas de una cadena minorista, recepción hotelera, seguridad, limpieza hospitalaria) no asigna turnos sueltos sino **patrones semanales** para 100-500 empleados: quién trabaja qué días, en qué turno (mañana/tarde/noche), con qué distribución de descansos — demanda cubierta en horas pico y carga de fin de semana y noche repartida con justicia. El plan intuitivo sangra por uno de dos extremos: falta de personal en pico (cola en caja, ventas perdidas, llamadas abandonadas) o exceso en horas valle (80-200 TRY/hora de mano de obra, unos 30-60K TRY al mes desperdiciados en una operación de 100 personas). Además, los incumplimientos contractuales (tope semanal de 45 horas, 5 días seguidos, 7-10 noches al mes) generan sanciones de nómina y riesgo laboral; sin un criterio de equidad escrito, la rotación sube al 40-80 % y cada nueva contratación cuesta 8-30K TRY de formación. En una operación de 200 personas, la nómina anual ronda los 30-80M TRY; una mejora del 10 % equivale a 3-8M TRY al año.
¿Qué Técnico a Qué Cliente, a Qué Hora?
Un servicio de climatización, una empresa de mantenimiento de ascensores, un servicio técnico de electrodomésticos, un proveedor de técnicos ISP o un servicio de maquinaria agrícola con 5–50 técnicos de campo recibe cada mañana una lista de demandas: 30–150 clientes con mantenimiento periódico planificado, reparación de avería o instalación. La decisión: qué técnico, qué cliente, en qué orden, a qué hora. Restricciones a respetar a la vez: ventana horaria del cliente (mañana / tarde / franja específica), competencia técnica (climatización marca A vs B, tipo de ascensor, infraestructura de internet), tiempo de viaje (20–90 min intraurbano), repuestos en el vehículo del técnico, prioridad de avería urgente. La asignación manual sirve hasta 10–15 técnicos; por encima, el equipo de dispatch pasa 2–4 horas al día al teléfono — citas que se mueven, clientes descontentos y técnicos parados son rutina.