Loading...
ContenidoLoading...
Antecedentes ....................................................Nodos ................................................................
Definición del problema de asignación ........
Características ..................................................
Modelo de Transporte vs Asignación ............
Método Húngaro .............................................
Balanceado .......................................................
Caso especial (Maximización) .........................
Loading...
13
5
7
8
10
16
17
Antecedentes
El problema de asignación tuvo su origen en la revolución industrial, ya que el surgimiento de las máquinas hizo que fuera necesario asignar una tarea a un trabajador.
Thomas Jefferson en 1792 lo sugirió para asignar un representante a cada estado, pero formalmente aparece este problema en 1941.
Pero no es hasta 1955 cuando Harold W. Kuhn plantea el método húngaro, que fue posteriormente revisado por James Munkres en 1957. Dicho método está basado fundamentalmente en los primeros trabajos de otros dos matemáticos húngaros: Dénes Köning y Jenö Egervary.
Hoy en día en pleno apogeo de la globalización surge cada vez con mayor frecuencia el uso
Thomas Jefferson en 1792 lo sugirió para asignar un representante a cada estado, pero formalmente aparece este problema en 1941.
Pero no es hasta 1955 cuando Harold W. Kuhn plantea el método húngaro, que fue posteriormente revisado por James Munkres en 1957. Dicho método está basado fundamentalmente en los primeros trabajos de otros dos matemáticos húngaros: Dénes Köning y Jenö Egervary.
Hoy en día en pleno apogeo de la globalización surge cada vez con mayor frecuencia el uso
1
de este problema en la rama de la investigación de operaciones. Podemos decir que es la aplicación del método científico para asignar los recursos o actividades de forma eficaz, en la gestión y organización de sistemas complejos. Su objetivo es ayudar a la toma de decisiones.
El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada.
2
Nodos
Los problemas de flujo de red son uno de los problemas de optimización más importantes y frecuentes. Surgen en el análisis y diseño de grandes sistemas, como las redes de comunicación, transporte y fabricación.
Aunque también se pueden utilizar para modelar importantes problemas combinatorios, como la asignación, el camino más corto y los problemas de los vendedores ambulantes, conceptos básicos sobre grafos, redes con flujo o el problema de flujo en redes a coste mínimo.
Teoría de grafos Un grafo G es un par (N, A) donde N representa el conjunto de nodos del grafo y A representa el conjunto de arcos entre los nodos. Denotaremos por n = |N| el número total de nodos y m = |A| el número total de arcos del grafo.
Aunque también se pueden utilizar para modelar importantes problemas combinatorios, como la asignación, el camino más corto y los problemas de los vendedores ambulantes, conceptos básicos sobre grafos, redes con flujo o el problema de flujo en redes a coste mínimo.
Teoría de grafos Un grafo G es un par (N, A) donde N representa el conjunto de nodos del grafo y A representa el conjunto de arcos entre los nodos. Denotaremos por n = |N| el número total de nodos y m = |A| el número total de arcos del grafo.
3
Una red es un grafo con uno o más números asociados a cada arco y/o nodo, que pueden representar precios, distancias u otros parámetros de interés. Las propiedades que definimos para los grafos se aplican también a redes.
Llamaremos flujo al envío de elementos de un lugar a otro de una red, nos referiremos a estos elementos que fluyen por la red como unidades de flujo. Las unidades de flujo pueden ser bienes, personas, información o casi cualquier cosa.
El problema de flujo en redes a coste mínimo (PFCM) es el problema de flujo en redes esencial, ya que muchos de los problemas de redes con flujo que aparecen en la vida real son casos particulares o generalizaciones del mismo.
Llamaremos flujo al envío de elementos de un lugar a otro de una red, nos referiremos a estos elementos que fluyen por la red como unidades de flujo. Las unidades de flujo pueden ser bienes, personas, información o casi cualquier cosa.
El problema de flujo en redes a coste mínimo (PFCM) es el problema de flujo en redes esencial, ya que muchos de los problemas de redes con flujo que aparecen en la vida real son casos particulares o generalizaciones del mismo.
4
Definición del problema de asignación
Este tipo de problemas son lineales, con una estructura de transporte, solo que la oferta en cada origen es de valor uno y la demanda en cada destino es también de valor uno. Sería muy ineficiente resolver este tipo de problemas por medio del método simplex o por medio del algoritmo de transporte.
Debido a la estructura propia de los problemas de asignación, existen métodos de solución llamados "algoritmos de asignación" que son más eficientes que el simplex o que el método de transporte.
En el modelo de asignación, la idea fundamental de resolución es ¿Qué fuente satisface mejor el destino?
Múltiples son los casos en podemos hacer uso del problema de asignación para resolver diversas situaciones, entre los que
Debido a la estructura propia de los problemas de asignación, existen métodos de solución llamados "algoritmos de asignación" que son más eficientes que el simplex o que el método de transporte.
En el modelo de asignación, la idea fundamental de resolución es ¿Qué fuente satisface mejor el destino?
Múltiples son los casos en podemos hacer uso del problema de asignación para resolver diversas situaciones, entre los que
5