Asi Nomas

U IVERSIDAD CE TRAL DE CHILE
Optimización

Método de asignación
Este método esta relacionado con la asignación de un determinado número de orígenes
al mismo número de destinos, con el objetivode optimizar alguna función objetivo.
Suposiciones:
1.
2.
3.
4.

El número de asignados es igual al número de tareas.
Cada asignado se asigna exactamente a una tarea.
Cada tarea debe serrealizada exactamente por un asignado.
Existe un costo Cij asociado con el asignado i q realiza la tarea j.

Algoritmo Húngaro
Caso: Minimización
Paso 1:
Restar el valor más pequeño de cada uno delos demás valores de esa columna.
Paso 2:
Restar el valor más pequeño de cada reglón de los demás valores de ese reglón.
Paso 3:
Cúbranse todos los ceros en la matriz de costos, con el menor númerode líneas
horizontales y verticales que sea posible. Cada línea horizontal debe pasar por todo el
reglón y cada línea vertical debe pasar por toda la columna. El número de líneas debe
ser mínimo.No se permiten líneas diagonales.
Paso 4:
Verificar la optimalidad: Si el número de líneas es igual a N (número de reglones o
columnas), es la solución óptima. Si el número de líneas es menor que N,se requiere
continuar el proceso hacia la solución óptima.
Paso 5:
Obtención de la nueva solución básica factible: esto se puede lograr seleccionando el
valor más pequeño, el cual no debe estarcruzado por ninguna línea. Este valor se debe
restar de todos los valores que no están cruzados por ninguna línea. Sumar esta cantidad
a todos los valores situados en la intersección de las líneas.Los valores cruzados por
una línea horizontal o vertical permanecen inalterados. REPETIR PASO 3.

MBA, Ing. María Cristina Cordero Rebolledo

U IVERSIDAD CE TRAL DE CHILE
OptimizaciónEjercicio Método Húngaro
Caso minimización
En el terreno de una universidad, 4 contratistas diferentes 1, 2, 3, 4 se proponen
construir 4 edificios diferentes a, b, c, d. Debido a que los contratistas...