Método Húngaro

Contenido

CONCEPTO 2

RESOLUCIÓN DE PROBLEMAS – MÉTODO HÚNGARO 2

MINIMIZACIÓN 2

MAXIMIZACIÓN 5

ESTRUCTURAS DE DATOS UTILIZADAS 8

Matriz: 8

Lista enlazada: 8

Grafo Bipartito: 8

Arboles B 9

ALGORITMOS UTILIZADOS 10

Algoritmo Hungaro: 10





CONCEPTO

Estos problemas ocurren en muchos contextos de la administración. En general consisten en elproblema para determinar la asignación óptima de agentes objetos “indivisibles”, en el sentido de que ningún agente se puede dividir entre varias tareas. La restricción importante, para cada agente, es que será designado a una solo una tarea.

El problema de asignación puede resolverse como un problema de transporte en el cual la oferta de cada origen y la demanda de cada destino son iguales a 1,o con el método simplex, sin embargo el método Húngaro resuelve este tipo de asignaciones de una manera más sencilla.

El enfoque general de este algoritmo consiste en "reducir" la matriz de costos mediante una serie de operaciones aritméticas.


RESOLUCIÓN DE PROBLEMAS – MÉTODO HÚNGARO


MINIMIZACIÓN

PASO 1. Elaboración de la tabla de costos por asignación.

[pic]

PASO 2. Restarel valor más pequeño de cada uno de los demás valores de la columna:

• En la primera columna, el valor más pequeño es 11.

• En la segunda columna, el valor más pequeño es 10.

• En la tercera columna, el valor más pequeño es 10.

• En la cuarta columna, el valor más pequeño es 11.

Estos valores se les restan a los demás valores de las columnas.

[pic]

Quedando latabla de la siguiente manera.

[pic]



PASO 3. Resta el valor más pequeño de cada fila a los demás valores de esa fila.

• En la primera fila, el valor más pequeño es 0.

• En la segunda fila, el valor más pequeño es 0.

• En la tercera fila, el valor más pequeño es 4.

• En la cuarta fila, el valor más pequeño es 0.

Estos valores se les restan a los demás valoresde las filas.

[pic]

Quedando la tabla de la siguiente manera.

[pic]



PASO 4. Se traza el mínimo número de líneas que puedan pasar a través de todos los ceros de la tabla. Las líneas diagonales no se permiten. En algunos casos este paso causa dificultades, ya que ordinariamente hay muchas formas de trazar estas líneas. Las diferentes alternativas son posibles siempre y cuando elnúmero de líneas sea mínimo.

Por ejemplo se pueden trazar las líneas en la tabla de la siguiente manera:

[pic]

Se podrían trazar de dicha manera, pero no es el mínimo, ya que también se podrían trazar de la siguiente manera con menos líneas.

[pic]

Este trazado abarca todos los ceros de la tabla, pero se realizó con 3 líneas únicamente, por lo tanto este trazado es mejor.

El detalle deeste trazado al momento de programarlo, es que tienes que trabajarlo con el llamado Algoritmo Húngaro. Este algoritmo se va a explicar posteriormente para su mejor entendimiento



PASO 5. Después de trazar el número mínimo de líneas se hace la prueba de optimalidad. Si en número de líneas es igual a número de renglones o columnas, es la solución óptima. Si el número de líneas es menor, serequiere continuar con el proceso hasta calcular la solución óptima.

En la tabla, el número de líneas es de 3 y el de renglones/columnas 4, por lo tanto hay que continuar con el procedimiento, el cual consiste de los siguientes pasos:

De los valores que no se tacharon, se selecciona el mínimo, en este ejemplo el mínimo es 3. Este valor se debe restar a todos los valores que no están cruzadospor ninguna línea.

También se debe sumar esta cantidad a todos los valores situados en la intersección de líneas.

Todos los demás valores (los que están cruzados únicamente por una línea), permanecen inalterados.

[pic]

Quedando la tabla de la siguiente manera.

[pic]



PASO 6. Esta tabla es posible solución, por lo tanto hay que realizar el procedimiento a partir del paso 4....