Problema de asignación generalizada

Problema de optimización combinatoria

En matemáticas aplicadas , el problema de asignación máxima generalizada 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 es el siguiente: hay varios agentes y varias tareas. Se puede asignar a cualquier agente para realizar cualquier tarea, incurriendo en algunos costos y ganancias que pueden variar según la asignación de tarea del agente. Además, cada agente tiene un presupuesto y la suma de los costes de las tareas que se le asignan no puede superar este presupuesto. Se requiere encontrar una tarea en la que todos los agentes no excedan su presupuesto y se maximice el beneficio total de la tarea.

En casos especiales

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

Explicación de la definición

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

Matemáticamente, el problema de asignación generalizada se puede formular 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}}}$

Complejidad

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

Algoritmo de aproximación codicioso

Para la variante del problema en la que no todos los artículos deben asignarse a un contenedor, existe una familia de algoritmos para resolver el GAP mediante el uso de 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 algoritmo de aproximación ALG para el problema de la mochila , es posible construir una aproximación () para el problema de asignación generalizada de manera codiciosa utilizando un concepto de beneficio residual. El algoritmo construye un cronograma en iteraciones, donde durante la iteración se selecciona una selección tentativa de elementos para agrupar . La selección de bin puede cambiar ya que los elementos pueden volver a seleccionarse en una iteración posterior para otros bins. La ganancia residual de un artículo para bin es si no se selecciona para ningún otro bin o – si se selecciona para bin . ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ ${\displaystyle j}$ ${\displaystyle b_{j}}$ ${\displaystyle b_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{j}}$ ${\displaystyle p_{ij}}$ ${\displaystyle x_{i}}$ ${\displaystyle p_{ij}}$ ${\displaystyle p_{ik}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{k}}$

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

Formalmente:

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

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

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

Actualice usando , es decir, para todos . ${\displaystyle T}$ ${\displaystyle S_{j}}$ ${\displaystyle T[i]=j}$ ${\displaystyle i\in S_{j}}$

Ver también

• problema de asignacion

Referencias

1. Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Algoritmo de abejas para problemas de asignación generalizada , Matemáticas y Computación Aplicadas, vol. 215, Elsevier, págs. 3782–3795, doi :10.1016/j.amc.2009.11.018.
2. Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). "Algoritmos de aproximación estricta para problemas de asignación general máxima". {{cite journal}}: Citar diario requiere |journal=( ayuda )
3. Cohen, Reuven; Katzir, Lirán; Raz, Danny (2006). "Una aproximación eficiente al problema de asignación generalizada". Cartas de procesamiento de información . 100 (4): 162–166. CiteSeerX 10.1.1.159.1947 . doi :10.1016/j.ipl.2006.06.003. 

Otras lecturas

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