Please enable JavaScript.

Coggle requires JavaScript to display documents.

Metodo Hungaro, Investigacion Operativa I Integrante: Lara Boyerman …

- - - - Jenő Egerváry
        
        generalizó el teorema de König y permitió a Kuhn desarrollar el método
      - Dénes König
        
        Desarrolló la teoría de grafos en la cual se basa este algoritmo
- - - - Calculamos los mínimos de cada fila y los restamos a los elementos de esa fila y hacemos lo mismo con las columnas (pasos 1 y 2). En la matriz resultante (C`) dibujamos líneas de tal manera que tapen todos los ceros y a su vez se crucen entre ellas (paso 3). Vemos que hay dos líneas, pero el mayor valor del número de filas o columnas es tres. Hay que seguir.
        
        Comenzamos por la fila o columna con menos ceros (E1,T1). Si una tarea está ya asignada no se puede volver a asignar, por ejemplo, con el E2 no se puede utilizar el primer cero de la T1, ya que esta tarea estaba asignada al E1. El coste total, en el método húngaro, será la suma de los costes de la matriz original (Paso 1) situados en la misma posición que los ceros elegidos (paso 5).
        
        Ahora elegimos el menor de los números no tapados, en este ejemplo es el dos (azul oscuro). Lo restamos a los anteriores y lo sumamos a los que se sitúan donde se cruzan las líneas. En nuestro caso es otro dos (E3,T1). Nos queda una nueva matriz (paso 4). Volvemos a dibujar las líneas y contamos. Hay tres líneas, igual que el número de filas o columnas. Se acaba el algoritmo.