Algoritmo húngaro / problema de asignación con función de coste que depende del emparejamiento resultante

Question

El algoritmo húngaro estándar resuelve el problema de asignar n trabajadores a n puestos de trabajo con una función de costes dada.

En mi variante, la función de coste depende de la coincidencia final producida por el algoritmo. Lo explico con un ejemplo:

si coste[w1][j1] = 10 $, in the new variant, if the final matching has w2 and j2 matching, then cost[w1][j1] = 5$ .

Es como decir que si soy un trabajador y cobro 10 $for some job j1 and if this other worker is assigned a j2 job, then I'm going to reduce my price to 5$ para el trabajo j1.

Editar: Creo que es seguro asumir que cualquier emparejamiento (wp, jp) puede o no tener relación con (wq, jq). Si la relación existe, el coste de (wp, jp) se reduce si (wq, jq) forma parte del emparejamiento final. La relación entre los emparejamientos está predefinida. Matemáticamente, podemos suponer que sabemos que existe una función f, donde f(wp, jp, wq, jq) devolverá una tupla (booleana, descuento). Si el booleano es verdadero y wp coincide con jp, entonces aplicamos el descuento al coste de wq y jq.

Answer 1

Se puede capturar cada una de estas interacciones mediante un producto ponderado de dos variables de decisión binarias. El objetivo lineal se convierte en cuadrático, y el problema resultante se denomina problema de asignación cuadrática .