Problema de la asignación

Problema de la asignación

Problema de la asignación

El problema del asignamiento es encontrar un matching de peso máximo en un grafo bipartido ponderado. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática.

En su forma más general, el problema es como sigue:

Hay un número de agentes y un número de tareas. Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste que puede variar dependiendo del agente y la tarea asignados. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total del asignamiento sea minimizado.

Si el número de agentes y tareas son iguales y el coste total de la asignación para todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema de asignamiento linear. Normalmente, cuando hablamos de problema de asignación sin ninguna matización adicional, nos referimos al problema de asignamiento linear.

Algoritmos y generalizaciones

El algoritmo Húngaro es uno de los muchos algoritmos que han sido diseñados para resolver el problema del asignamiento lineal con un tiempo acotado por una expresión polinómica del número de agentes.

El problema del asignamiento es un caso especial del problema del transportador, que es un caso especial del problema del flujo de coste mínimo. Es posible resolver cualquiera de estos problemas mediante el algoritmo simplex, cada especialización tiene algoritmos más eficientes tomando ventaja de su estructura especial.

Definición matemática formal

La definición formal del problema del asignamiento (o problema linear del asignamiento) es

Dados dos conjuntos, A y T. de igual tamaño, juntos con una función peso C : A × TR. Encuentra una biyección f : AT como la función de coste:


\sum_{a\in A}C(a,f(a))
está minimizada.

Normalmente la función peso es vista como una matriz cuadrada de valores reales C, con lo que el coste de la función queda así:

\sum_{a\in A}C_{a,f(a)}

El problema es "linear" porque la función coste a optimizar así como todas las restricciones contienen solo términos lineales.

Tutoriales

Obtenido de "Problema de la asignaci%C3%B3n"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Problema de la asignación cuadrática — Saltar a navegación, búsqueda Contenido 1 Origen 2 Definición 3 Modelo Matemático 4 …   Wikipedia Español

  • Asignación de memoria — Saltar a navegación, búsqueda La asignación de memoria consiste en el proceso de asignar memoria para propósitos espécificos, ya sea en tiempo de compilación o de ejecución. Si es en tiempo de compilación es estática, si es en tiempo de ejecución …   Wikipedia Español

  • Problema de satisfacibilidad booleana — Saltar a navegación, búsqueda En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde… …   Wikipedia Español

  • Problema del polizón — En economía, negociación colectiva, psicología y ciencias políticas, se llama polizones a aquellos individuos o entes que consumen más que una parte equitativa de un recurso, o no afrontan una parte justa del costo de su producción. El problema… …   Wikipedia Español

  • Problema de satisfacibilidad booleana — En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde interesa saber si una expresión… …   Enciclopedia Universal

  • Ramificación y poda — Saltar a navegación, búsqueda El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y Acotación) es una variante del Backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica… …   Wikipedia Español

  • Luigi Pasinetti — «Pasinetti» redirige aquí. Para otras acepciones, véase Pasinetti (desambiguación). Luigi Pasinetti. Luigi L. Pasinetti (12 de Septiembre de 1930) es un economista italiano de la escuela de economía postkeynesiana. Pasinetti es considerado el… …   Wikipedia Español

  • DocCF — Saltar a navegación, búsqueda DocCF Software de Gestión Escolar Desarrollador Grupo CF Developer …   Wikipedia Español

  • Atis-Amor — Saltar a navegación, búsqueda Atis Amor en el museo del Bargello. Atis Amor es una escultura de bronce de Donatello, que data de alrededor de 1440 1443. La obra, presenta algunas trazas de la p …   Wikipedia Español

  • Real Conservatorio Superior de Música de Madrid — Coordenadas: 40°24′33.22″N 3°41′39.69″O / 40.4092278, 3.6943583 …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”