Metodo asignación

República Bolivariana de Venezuela
Ministerio del poder popular
Para la Educación
Universidad Centroccidental Lisandro Alvarado
Barquisimeto Edo -Lara



Alumno: Vásquez Walter
Cedula: 19.967.310
Materia: Investigación de OperacionesProfesor: Edwing Salazar

Bibliografía:

1) Aplicaciones de la Programación Lineal Proyecto e-Math 1 Financiado por la Secretaría de Estado de Educación y Universidades (MECD) Autor: Juan Javier Faulin

2) Investigación de Operaciones G. D. Eppen, F. J. Gould, C. P. Schmidt, J. H. Moore y L. R. Weatherford editorial Pearson Educación, 5ta edición

El modelo deasignación se presenta en muchos contextos administrativos. En términos generales, el problema consiste en determinar la asignación óptima de n agente u objetos “invisibles” a una n tareas. Ejemplo la administración tal vez tenga que asignar agentes de ventas a territorios de ventas. Los gentes u objetos asignar son individuales, en el sentido de que ningún agente puede dividirse entre variastareas. Para cada agente la restricción importante es que solo puede ser asignado a una tarea

El objetivo aquí será asignar de la forma más eficiente posible un trabajo a cada empleado o máquina. Ejemplos de este tipo de asignación serían la distribución de coches patrulla por las calles de una ciudad o la destino de cada jefe de ventas a una determinada zona geográfica. El objetivo puede ser bienminimizar los tiempos o costes de desplazamiento, o bien maximizar la efectividad de las asignaciones.

Aparte de poder utilizar los algoritmos tradicionales (Simplex y Karmarkar), este tipo de problemas también puede resolverse usando técnicas especialmente diseñadas para sus características como el método húngaro, el cual necesita de menos iteraciones para dar con la solución.
Unapropiedad particular de los problemas de asignación es que tanto los coeficientes tecnológicos cómo los términos independientes (right-hand-side) siempre toman el valor 1. Además, todas las variables serán binarias, tomando el valor 1 si la asignación propuesta se eva a cabo y 0 en caso contrario.
Método húngaro para la asignación.
La más conocida técnica de solución para el problema de asignación puraes el método húngaro, desarrollado a partir del teorema que demostró el matemático húngaro König en 1916. Este método utiliza la propiedad de reducción de matrices para reducir la matriz original de costo, hasta que los costos C i j asociados con la asignación óptima, sean cero y todos los otros costos sean no negativos.
En el método húngaro, se reduce la matriz de tal manera que haya al menosun cero en cada renglón y columna, comprobando con el teorema de König si se ha alcanzado la solución óptima. Si el número mínimo de renglones y/o columnas necesarios para cubrir todos los ceros es n, entonces existe una asignación óptima (no necesariamente única).
Ejemplo. Método Húngaro en la asignación
La siguiente matriz muestra costos C i j de n = 5 candidatos i ( i = 1,2,...,5 ) asícalificados, en el desempeño de n = 5 actividades j ( j = 1,2,..,5 ). Con el método húngaro calcule la asignación óptima.
i/j | 1 | 2 | 3 | 4 | 5 |
1 | 3 | 8 | 12 | 10 | 3 |
2 | 8 | 7 | 2 | 9 | 7 |
3 | 6 | 4 | 2 | 7 | 5 |
4 | 8 | 4 | 2 | 3 | 5 |
5 | 9 | 10 | 6 | 9 | 10 |

Paso 1. Reste el menor ( U i ) de los costos C i j en cada renglón:
i/j | 1 | 2 | 3 | 4 | 5 | Ui |
1 | 3 | 8 | 12| 10 | 3 | U1=3 |
2 | 8 | 7 | 2 | 9 | 7 | U2=2 |
3 | 6 | 4 | 2 | 7 | 5 | U3=2 |
4 | 8 | 4 | 2 | 3 | 5 | U4=2 |
5 | 9 | 10 | 6 | 9 | 10 | U5=6 |

Paso 2.- Reste el menor ( V j ) de los costos C i j en cada columna:
i/j | 1 | 2 | 3 | 4 | 5 |
1 | 0 | 5 | 9 | 7 | 0 |
2 | 6 | 5 | 0 | 7 | 5 |
3 | 4 | 2 | 0 | 5 | 3 |
4 | 6 | 2 | 0 | 1 | 3 |
5 | 3 | 4 | 0 | 3 | 4 |
Vj | V1= 0 |...