Problema de asignación generalizada

En matemáticas aplicadas , un problema de asignación generalizada se entiende como un problema de optimización combinatoria , que es una generalización del problema de asignación , en el que el conjunto de ejecutantes tiene un tamaño que no es necesariamente igual al tamaño del conjunto de trabajos. En este caso, el ejecutante puede ser asignado para realizar cualquier trabajo (no necesariamente un trabajo, como en el problema de asignación). Al asignar un ejecutor para realizar el trabajo, se establecen dos valores: costos e ingresos. Cada artista tiene un presupuesto determinado, por lo que la suma de todos los costos no debe exceder este presupuesto. Se requiere encontrar tal asignación de artistas para realizar el trabajo con el fin de maximizar los ingresos.

Ocasiones especiales

En el caso de que los presupuestos de los artistas y todos los costos de trabajo sean iguales a 1, el problema se convierte en el problema de coincidencia máxima .

Si los precios y los ingresos de todas las asignaciones de trabajo son iguales, el problema se reduce a una mochila multiplicativa .

Si solo hay un agente, el problema se reduce al problema de la mochila .

Definición

Hay n trabajos y m ejecutantes . Cada artista tiene un presupuesto . Para cada par de ejecutante y trabajo se dan los ingresos y el peso . La solución es un subconjunto de trabajos U y una distribución de trabajos de U entre los ejecutantes. La decisión es aceptable si el monto de los costos por el trabajo asignado del artista intérprete o ejecutante no excede el presupuesto . La renta de la sentencia es la suma de todas las rentas de todas las distribuciones de obra-ejecutor. ${\displaystyle x_{1},\puntos,x_{n))$ ${\displaystyle b_{1},\puntos,b_{m))$ $bi}$ $Wisconsin}$ $bi}$ $x_{j}$ $p_{i,j}$ $w_{i,j}$ $bi}$ $Wisconsin}$

Matemáticamente, el problema de asignación generalizada se puede formular de la siguiente manera:

maximizar

\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.

sujeto a ;

\sum _{j=1}^{n}w_{ij}x_{ij}\leq w_{i}\qquad i=1,\ldots,m

\sum _{i=1}^{m}x_{ij}\leq 1\qquad j=1,\ldots,n

;

x_{ij}\in \{0,1\}\qquad i=1,\ldots,m,\quad j=1,\ldots,n

;

El problema de asignación generalizado es NP-hard e incluso APX-hard .

Fleischer, Gomans, Mirokni y Sviridenko propusieron un algoritmo de búsqueda local combinatoria con aproximación y un algoritmo basado en programación lineal con aproximación [1] . $(2+\varepsilon)$ $({\frac {e}{e-1))+\varepsilon)$

La aproximación es la aproximación más conocida del problema de asignación generalizada. $({\frac {e}{e-1))+\epsilon)$

Algoritmo de aproximación codicioso

Usando el algoritmo de aproximación del problema de asignación, se puede crear una aproximación ( ) para el problema de asignación generalizado a la manera de un algoritmo codicioso usando el concepto de ingreso residual. El algoritmo crea iterativamente una secuencia preliminar en la que se supone que debe asignar trabajo al ejecutante en la iteración . La elección del ejecutante se puede cambiar más adelante al asignar trabajo a otros ejecutantes. El ingreso restante del trabajo para el artista intérprete o ejecutante es , si el trabajo no se le da a otro artista intérprete o ejecutante, y - si el trabajo se le da al artista intérprete o ejecutante . $\alfa$ ${\ estilo de visualización \ alfa +1}$ $j$ $b_{j}$ $b_{j}$ $x_{yo}$ $b_{j}$ $p_{{ij}}$ $x_{yo}$ ${\ Displaystyle p_ {ij}}$ ${\ Displaystyle p_ {ik}}$ $b_{k}$

Formalmente:

Utilice el vector para la preselección y en este vector $T$

T[i]=j

significa que se supone que debe asignar un ejecutor a la obra ,

x_{yo}

b_{j}

T[i]=-1

significa que nadie ha sido asignado al trabajo.

x_{yo}

El ingreso restante por iteración se denota por , donde $j$ $P_{j}$

{\displaystyle P_{j}[i]=p_{ij))

si no se selecciona ningún trabajo (es decir, )

x_{yo}

T[i]=-1

{\displaystyle P_{j}[i]=p_{ij}-p_{ik))

, si se supone que la obra debe entregarse al ejecutante (es decir, ).

x_{yo}

b_{k}

T[i]=k

Así que el algoritmo se ve así:

Valores iniciales asignados para todos

T[i]=-1

i=1\ldots n

Para todos , haz:

{\ estilo de visualización j = 1... m}

Se utiliza un algoritmo de aproximación para obtener la distribución del trabajo del contratista utilizando la función de ingreso residual . Se indican las obras seleccionadas .

b_{j}

P_{j}

S_j

Corregido usando , es decir, para todos .

T

S_j

T[i]=j

{\ estilo de visualización i \ en S_ {j}}

fin de ciclo

Véase también

Problema de asignación

Notas

↑ L. Fleischer, MX Goemans, VS Mirrokni y M. Sviridenko. Algoritmos de aproximación ajustados para problemas generales de asignación máxima. En SODA'06: Proc

Enlaces

Reuven Cohen, Liran Katzir y Danny Raz, "Una aproximación eficiente para el problema de asignación generalizado" , Information Processing Letters, vol. 100, número 4, págs. 162–166, noviembre de 2006.
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni y Maxim Sviridenko, "Algoritmos de aproximación ajustada para problemas de asignación general máxima" , SODA 2006, págs. 611–620.
Hans Kellerer, Ulrich Pferschy, David Pisinger, Problemas de mochila , 2005. Springer Verlag ISBN 3-540-40286-1