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 la tarea del agente. Además, cada agente tiene un presupuesto y la suma de los costos de las tareas que se le asignan no puede exceder este presupuesto. Se requiere encontrar una asignación en la que todos los agentes no excedan su presupuesto y se maximice el beneficio total de la asignación.
En casos especiales
En el caso especial en el que todos los presupuestos de los agentes y todos los costos de las tareas son 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 múltiples mochilas. 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 elementos, mediante y m tipos de contenedores mediante . Cada contenedor está asociado con un presupuesto . Para una papelera, cada elemento 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 elementos asignados es como máximo . El beneficio de la solución es la suma de los beneficios de cada asignación de contenedor de artículo. El objetivo es encontrar una solución viable con el máximo beneficio.
Matemáticamente, el problema de asignación generalizada se puede formular como un programa entero :
Complejidad
El problema de asignación generalizado es NP-difícil , [1] Sin embargo, hay relajaciones de programación lineal que dan una-aproximación. [2]
Algoritmo de aproximación codicioso
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 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]
Usando cualquier -algoritmo de aproximación ALG para el problema de la mochila , es posible construir un () -aproximación para el problema de asignación generalizada de una manera codiciosa utilizando un concepto de beneficio residual. El algoritmo construye un programa en iteraciones, donde durante la iteración una selección tentativa de artículos para tirar está seleccionado. La selección de binpodría cambiar ya que los elementos podrían volver a seleccionarse en una iteración posterior para otros contenedores. La ganancia residual de un artículo. para papelera es Si no está seleccionado para ningún otro contenedor o - Si está seleccionado para bin .
Formalmente: usamos un vector para indicar el horario tentativo durante el algoritmo. Específicamente, significa el artículo está programado en la papelera y significa ese artículo no está programado. La ganancia residual en iteración se denota por , dónde si el artículo no está programado (es decir ) y si el artículo está programado en la papelera (es decir ).
Formalmente:
- Colocar
- Para hacer:
- Llame a ALG para encontrar una solución a bin usando la función de beneficio residual . Denote los elementos seleccionados por .
- Actualizar utilizando , es decir, para todos .
Ver también
Referencias
- ^ Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Algoritmo de abejas para problemas de asignación generalizados , Matemáticas aplicadas y Computación, 215 , Elsevier, págs. 3782–3795, doi : 10.1016 / j.amc.2009.11.018.
- ^ Fleischer, Lisa; Goemans, Michel X .; Mirrokni, Vahab S .; Sviridenko, Maxim (2006). "Algoritmos de aproximación ajustados para problemas máximos de asignación general". Cite journal requiere
|journal=
( ayuda ) - ^ Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "Una aproximación eficiente para el problema de asignación generalizada". Cartas de procesamiento de información . 100 (4): 162-166. 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 . ISBN 978-3-540-24777-7.