Asign
-
Upload
carlos-bacalla -
Category
Documents
-
view
213 -
download
0
description
Transcript of Asign
![Page 1: Asign](https://reader036.fdocumento.com/reader036/viewer/2022072008/55cf8fa6550346703b9e6f50/html5/thumbnails/1.jpg)
PROBLEMA DE ASIGNACION
Dado un problema de asignacion, describiremos un metodo para encontrar una asignacion optima.
ALGORITMO
INPUT: la matriz de costos de un problema de asignacion.OUTPUT: Una solucion optima del problema de asignacion asociado a la matriz.
METODO HUNGARO
MATRIZ REDUCIDA.
Paso 1: Para cada fila de la matriz se resta a cada celda el mınimo coste de dicha fila.Paso 2: Para cada columna de la matriz se resta a cada celda el mınimo valor de dicha columna.
SOLUCION OPTIMAPaso 3: Sea k el numero maximo de celdas cero independientes.Paso 4: — Si k coinciden con el orden de la matriz, la ASIGNACION OPTIMA viene dada por las celdas
independientes.— En caso contrario trazar k lıneas que cubran todos los ceros.
Paso 5: Sea c0 el mınimo valor no cubierto.— Restar c0 a cada celda no cubierta.— Sumar c0 a cada celda cubierta por 2 lıneas.
Paso 6: Volver al Paso 3.