Problema de asignación generalizada

En matemáticas aplicadas , el problema de asignación generalizada máxima es un problema de optimización combinatoria . Este problema es una generalización del problema de asignación en el que tanto las tareas como los agentes tienen un tamaño. Además, el tamaño de cada tarea puede variar de un agente a otro.

Este problema, en su forma más general, se plantea de la siguiente manera: Hay varios agentes y varias tareas. A cada agente se le puede asignar cualquier tarea, lo que implica un costo y una ganancia que pueden variar según la tarea asignada. Además, cada agente tiene un presupuesto y la suma de los costos de las tareas que se le asignan no puede excederlo. Se requiere encontrar una asignación en la que ningún agente exceda su presupuesto y se maximice la ganancia total de la asignación.

En el caso especial en que los presupuestos de todos los agentes y los costos de todas las tareas son iguales a 1, este problema se reduce al problema de asignación . Cuando los costos y las ganancias de todas las tareas no varían entre los diferentes agentes, este problema se reduce al problema de la mochila múltiple. Si hay un solo agente, entonces, este problema se reduce al problema de la mochila .

A continuación, tenemos n tipos de artículos,${\displaystyle a_{1}}$a través de${\displaystyle a_{n}}$y m tipos de contenedores${\displaystyle b_{1}}$a través de${\displaystyle b_{m}}$Cada contenedor${\displaystyle b_{i}}$está asociado con un presupuesto${\displaystyle t_{i}}$. Para un contenedor${\displaystyle b_{i}}$, cada artículo${\displaystyle a_{j}}$tiene ganancias${\displaystyle p_{ij}}$y un peso${\displaystyle w_{ij}}$Una solución es una asignación de elementos a contenedores. Una solución factible es una solución en la que para cada contenedor${\displaystyle b_{i}}$El peso total de los artículos asignados es como máximo${\displaystyle t_{i}}$La ganancia de la solución es la suma de las ganancias por cada asignación de artículo a contenedor. El objetivo es encontrar una solución factible que maximice la ganancia.

Matemáticamente, el problema de asignación generalizada puede formularse como un programa entero :

${\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}$

El problema de asignación generalizada es NP-difícil . ^{[ 1 ]} Sin embargo, existen relajaciones de programación lineal que dan lugar a una${\displaystyle (1-1/e)}$-aproximación. ^{[ 2 ]}

Para la variante del problema en la que no todos los elementos deben asignarse a un contenedor, existe una familia de algoritmos para resolver el GAP mediante una traducción combinatoria de cualquier algoritmo para el problema de la mochila en un algoritmo de aproximación para el GAP. ^{[ 3 ]}

Utilizando cualquier${\displaystyle \alpha }$-algoritmo de aproximación ALG para el problema de la mochila , es posible construir un (${\displaystyle \alpha +1}$)-aproximación para el problema de asignación generalizado de manera voraz utilizando un concepto de ganancia residual. El algoritmo construye una programación en iteraciones, donde durante la iteración${\displaystyle j}$una selección tentativa de artículos para desechar${\displaystyle b_{j}}$Se selecciona. La selección para el contenedor${\displaystyle b_{j}}$podría cambiar ya que los artículos podrían volver a seleccionarse en una iteración posterior para otros contenedores. La ganancia residual de un artículo${\displaystyle x_{i}}$para contenedor${\displaystyle b_{j}}$es${\displaystyle p_{ij}}$si${\displaystyle x_{i}}$no se selecciona para ningún otro contenedor o${\displaystyle p_{ij}}$–${\displaystyle p_{ik}}$si${\displaystyle x_{i}}$se selecciona para el contenedor${\displaystyle b_{k}}$.

Formalmente: Usamos un vector${\displaystyle T}$para indicar el cronograma tentativo durante el algoritmo. Específicamente,${\displaystyle T[i]=j}$significa el artículo${\displaystyle x_{i}}$está programado en el contenedor${\displaystyle b_{j}}$y${\displaystyle T[i]=-1}$significa que el artículo${\displaystyle x_{i}}$no está programado. La ganancia residual en la iteración${\displaystyle j}$se denota por${\displaystyle P_{j}}$, dónde${\displaystyle P_{j}[i]=p_{ij}}$si el artículo${\displaystyle x_{i}}$no está programado (es decir,${\displaystyle T[i]=-1}$) y${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$si el artículo${\displaystyle x_{i}}$está programado en el contenedor${\displaystyle b_{k}}$(es decir${\displaystyle T[i]=k}$).

Formalmente:

Colocar${\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}$

Para${\displaystyle j=1,\ldots ,m}$hacer:

Llama a ALG para encontrar una solución para el contenedor${\displaystyle b_{j}}$utilizando la función de beneficio residual${\displaystyle P_{j}}$. Denotemos los elementos seleccionados por${\displaystyle S_{j}}$.

Actualizar${\displaystyle T}$usando${\displaystyle S_{j}}$, es decir,${\displaystyle T[i]=j}$a pesar de${\displaystyle i\in S_{j}}$.

• Problema de asignación

• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (19 de marzo de 2013). Problemas con la mochila . Saltador. ISBN 978-3-540-24777-7.