Método Húngaro - Nota: 17 PDF

Preview

Summary

El Método Húngaro un método para el problema de asignación....

Description

INDICE INTRODUCCIÓN..........................................................................................................5 1.

Problemas de Asignación.......................................................................................6

1.1.

Suposiciones de un Problema de Asignación.........................................................7

2.

Método Húngaro....................................................................................................7

2.1.

Antecedentes..........................................................................................................7

2.2.

Características........................................................................................................8

2.3.

Objetivos................................................................................................................8

2.4.

Desventajas............................................................................................................8

2.5.

Pasos para Resolver el Método Húngaro...............................................................8

Paso 1: Restar los Mínimos de cada Fila......................................................................9 Paso 2: Restar los mínimos de cada columna.............................................................10 Paso 3: Cubrir todos los ceros con un mínimo número de líneas...............................10 Paso 4: Crear ceros adicionales..................................................................................11 Paso 5: Repetición del Paso 3.....................................................................................11 Asignación óptima......................................................................................................12 3.

Problemas resueltos con software........................................................................13

3.1.

Solver...................................................................................................................13

Paso 1..........................................................................................................................14 Paso 2..........................................................................................................................14

2

Paso 3..........................................................................................................................15 Paso 4..........................................................................................................................15 Paso 5..........................................................................................................................16 4.

Justificación.........................................................................................................20

5.

Conclusiones........................................................................................................20

6.

Bibliografía..........................................................................................................21

3

INDICE DE TABLAS Tabla 1: Ejemplo del Método Húngaro...........................................................................................8 Tabla 2:Ejemplo del Método Húngaro – Paso 1.............................................................................8 Tabla 3: Ejemplo del Método Húngaro – Paso 2............................................................................9 Tabla 4: Ejemplo del Método Húngaro – Paso 3............................................................................9 Tabla 5: Ejemplo del Método Húngaro – Paso 5..........................................................................10 Tabla 6: Ejemplo del Método Húngaro – Paso 5..........................................................................10 Tabla 7: Ejemplo del Método Húngaro – Asignación Optima......................................................11 Tabla 8: Ejemplo del Método Húngaro – Resultado.....................................................................12

INDICE DE FIGURAS Figura 1: Ejemplo con Solver.......................................................................................................12 Figura 2: Ejemplo con Solver – Paso 1........................................................................................13 Figura 3: Ejemplo con Solver – Paso 2........................................................................................14 Figura 4: Ejemplo con Solver – Paso 3........................................................................................14 Figura 5:Ejemplo con Solver – Paso 4.........................................................................................14 Figura 6: Ejemplo con Solver – Paso 5........................................................................................15 Figura 7: Ejemplo con Solver – Paso 5a......................................................................................16 Figura 8: Ejemplo con Solver – Paso 5b......................................................................................16 Figura 9: Ejemplo con Solver – Paso 5c......................................................................................17 Figura 10: Ejemplo con Solver – Paso 5d....................................................................................17 Figura 11: Ejemplo con Solver – Paso 5e.....................................................................................18 Figura 12: Ejemplo con Solver – Resultado.................................................................................18

4

5

INTRODUCCIÓN Lo primero que debemos hacer para poder aplicar el método húngaro es identificar el tipo de problema que tenemos que resolver, el método húngaro se usa para los problemas de asignación el cual es un caso especial del modelo de transporte. Lo segundo es que para esto debemos que tener en cuenta las suposiciones de este tipo de problemas. En el punto 3 tenemos los antecedentes del método húngaro, donde encontramos al inventor de este método y los aportes que ha dado con el pasar de los años. Luego tenemos las características del método húngaro, sus objetivos, importancia, ventajas, desventajas y finalmente los pasos que se ejecutan para desarrollar este método. En el punto 4 tenemos la justificación que son las razones y argumentos que se validan para la realización del estudio de este método. Y finalmente tenemos nuestras conclusiones la cual inferimos por los resultados que obtenemos al aplicar este método.

6

1. Problemas de Asignación El modelo de asignación es un caso especial del modelo de transporte, donde los trabajadores representan los orígenes y los trabajos representan los destinos. La oferta (demanda) en cada origen (destino) es igual a 1. El costo de “transportar” al trabajador i al trabajo j es cij. De hecho, el modelo de asignación puede resolverse de forma directa como un modelo de transporte (o como una PL regular). Sin embargo, el hecho de que la oferta y la demanda sean iguales a 1 conduce al desarrollo de un algoritmo de solución simple llamado método húngaro. Aunque el nuevo método de solución parece totalmente ajeno al modelo de transporte, en realidad el algoritmo tiene su origen en el método simplex, al igual que el modelo de transporte

1.1. Suposiciones de un Problema de Asignación -

El número de asignados es igual al número de tareas (se denota por n). (esto puede variar).

-

Cada asignado se asigna exactamente a una tarea.

-

Cada tarea debe realizarla exactamente un asignado.

-

Existe un costo cij asociado con el asignado i (i=1, 2, n).

-

El objetivo es determinar cómo deben hacerse las asignaciones para minimizar los costos totales.

7

2. Método Húngaro 2.1. Antecedentes La primera versión conocida del método húngaro fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.

2.2. Características -

Es un modelo de programación lineal que se ocupa de la asignación de tareas trabajos a los recursos.

-

Sirve para minimizar los costes totales o del tiempo necesario para la realización de las diferentes tareas en los diferentes CT.

2.3. Objetivos Sirve para optimizar problemas de asignación ya que es más eficaz que el empleado para resolver problemas de transporte por el grado de degeneración que pueden presentar los problemas de asignación es ayudar a la toma de decisiones. Está diseñado para la resolución de problemas de minimización únicamente, será entonces cuestión de agregar un paso adicional para abordar ejercicios de maximización. 2.4. Desventajas -

Los diferentes trabajos no se pueden dividir.

-

Los trabajos se asignan según la capacidad disponible de los puestos de trabajo.

8

2.5. Pasos para Resolver el Método Húngaro Ejemplo: Consideremos una empresa donde existen cuatro actividades (A1, A2, A3, A4) que deben ser ejecutadas por cuatro trabajadores (T1, T2, T3, T4). Se debe asignar una actividad por trabajador. La siguiente matriz muestra el costo de asignar un determinado trabajador a una determinada actividad. El objetivo que se desea obtener es minimizar el costo total de la tarea compuesta por estas cuatro actividades.

Tabla 1: Ejemplo del Método Húngaro.

Fuente: Elaboración propia.

Paso 1: Restar los Mínimos de cada Fila. Se comienza por restar el elemento con el valor mínimo de cada fila de los demás elementos de esa fila. Por ejemplo, el elemento más pequeño en la primera fila es 69. Entonces, se tiene que restar 69 de cada elemento en la primera fila. La matriz resultante es la siguiente: Tabla 2:Ejemplo del Método Húngaro – Paso 1

9

Fuente: Elaboración propia.

Paso 2: Restar los mínimos de cada columna. De la misma forma, se resta el elemento con el valor mínimo de cada columna de los demás elementos de esa columna, obteniendo la siguiente matriz: Tabla 3: Ejemplo del Método Húngaro – Paso 2

Fuente: Elaboración propia.

Paso 3: Cubrir todos los ceros con un mínimo número de líneas. A continuación, se determinará el mínimo número de líneas (horizontales o verticales) que se requieren para cubrir todos los ceros en la matriz. En este caso todos los ceros se pueden cubrir usando 3 líneas: Tabla 4: Ejemplo del Método Húngaro – Paso 3

10

Fuente: Elaboración propia.

Debido a que el número de líneas requeridas es tres y es menor que el tamaño de la matriz (n=4), se continúa con el paso 4. Paso 4: Crear ceros adicionales. Se selecciona el menor elemento no cubierto por las líneas, cuyo valor es 6. Se resta este valor de todos los elementos no cubiertos y este mismo valor se suma a todos los elementos cubiertos por la intersección de dos líneas. Esto da como resultado la siguiente matriz: Tabla 5: Ejemplo del Método Húngaro – Paso 5

Fuente: Elaboración propia.

Tal como está indicado en el método húngaro, se debe realizar de nuevo el paso número tres.

11

Paso 5: Repetición del Paso 3. Nuevamente se determina el mínimo número de líneas requeridas para cubrir todos los ceros en la matriz. En esta ocasión se requieren cuatro líneas: Tabla 6: Ejemplo del Método Húngaro – Paso 5

Fuente: Elaboración propia.

Entonces debido a que el número de líneas requeridas es 4, igual al tamaño de la matriz (n=4), se tiene una asignación óptima entre los ceros en la matriz. Por tanto, el algoritmo se detiene. Asignación óptima. Tal como indica el método, la selección realizada de los siguientes ceros corresponde a una asignación óptima: Tabla 7: Ejemplo del Método Húngaro – Asignación Optima

Fuente: Elaboración propia.

12

Esta selección de ceros corresponde a la siguiente asignación óptima en la matriz de costos original:

Tabla 8: Ejemplo del Método Húngaro – Resultado

Fuente: Elaboración propia.

Por tanto, el trabajador 1 debe realizar la actividad 3, el trabajador 2, la actividad 2, el trabajador 3, la actividad 1 y el trabajador 4 debe realizar la actividad 4. Entonces como resultados tenemos que, el costo total de esta asignación óptima es de 69+37+11+23=140.

3. Problemas resueltos con software 3.1. Solver En siguiente ejemplo nos pide minimizar los valores asignados entre el equipo de mantenimiento y las maquinas, siendo un problema de asignación se usará el método húngaro y será resuelto por Solver, herramienta de Excel. En la tabla n°1, se encuentran los siguientes valores: Figura 1: Ejemplo con Solver

13

Fuente: Elaboración propia.

Paso 1. Los valores asignados en la tabla n°1 se deberán convertir en 0 y se creará 3 columnas al lado derecho del cuadro y 3 al lado inferior con los nombres de “Total”, “Signo” (el cual es “=” ) , “Oferta” ( columna) y “Demanda” ( fila). Figura 2: Ejemplo con Solver – Paso 1

Fuente: Elaboración propia.

14

Paso 2. En la fila y columna del total se sumarán los valores, los cuales son 0 y en la demanda y oferta se igualarán al número 1 Figura 3: Ejemplo con Solver – Paso 2

Fuente: Elaboración propia. Paso 3. En la casilla donde va el resultado se usa la siguiente formula =Sumaproducto( Matriz anterior, Matriz actual) . Figura 4: Ejemplo con Solver – Paso 3

Fuente: Elaboración propia.

15

Paso 4. Luego de realizar la debida estructura para el método pasaremos a abrir el Solver el cual se encuentra en el lado derecho de la ventana de datos. Figura 5:Ejemplo con Solver – Paso 4

Fuente: Elaboración propia.

Paso 5. Rellenaremos los cuadros según corresponda. En establecer objetivo seleccionaremos la casilla que obtendrá el resultado, seleccionares Min ya que el ejercicio nos pide minimizas y en Cambiando celdas de variables se seleccionará la matriz de los 0. Figura 6: Ejemplo con Solver – Paso 5

16 Fuente: Elaboración propia.

Para las restricciones serán las siguientes con el signo igual: Figura 7: Ejemplo con Solver – Paso 5a

Fuente: Elaboración propia. Figura 8: Ejemplo con Solver – Paso 5b

Fuente: Elaboración propia.

En el siguiente la matriz de 0´s será mayor igual a 0

17 Figura 9: Ejemplo con Solver – Paso 5c

Fuente: Elaboración propia.

Luego de colocar los respectivos datos el método de resolución será por SIMPLEX LP y se le da a resolver. Figura 10: Ejemplo con Solver – Paso 5d

18 Fuente: Elaboración propia.

Luego aceptar Figura 11: Ejemplo con Solver – Paso 5e

Fuente: Elaboración propia.

Y el resultado saldrá en la casilla respectiva. En el caso del ejercicio, el resultado es 26. Figura 12: Ejemplo con Solver – Resultado

Fuente: Elaboración propia.

19

4. Justificación Es necesario discutir el siguiente resultado: Si se suma una constante a cada costo de una fila o de una columna de un problema de transporte balanceado, la solución al problema es invariante. Para mostrar que el resultado es correcto, supongamos que se agrega una constante k a cada costo en la primera fila de un ejemplo, entonces: Nuevo valor de la función objetivo = valor anterior +

k ( x 11 +x 12+ x 13 + x14)

Como cualquier solución factible del problema debe cumplir que: x 11 +x12 +x 13+x 14 =1 Nuevo valor de la función objetivo = valor anterior + k Debido a que minimizar el valor de una función más una constante es equivalente a minimizar la función, la solución óptima no cambia si se agrega una constante k a cada costo de la primera fila. Se puede aplicar el mismo argumento a cualquier otra fila o columna. 5. Conclusiones El método húngaro está basado en el método simplex. La asignación de recursos no solo significa transporte, producción o herramientas, sino también tareas a cualquiera que las pueda realizar ya sean personas o máquinas. Para este tipo de asignaciones se aplican los modelos de asignación, donde no necesariamente el número de fuentes será igual al número de destinos. El método húngaro es el medio más conocido para la solución de problemas de asignación puro, su finalidad es ir reduciendo la matriz hasta que sus costos sean cero y así determinar la solución que minimice los costos de asignación.

20

6. Bibliografía -

Hamdy A. Taha. (2012). Investigación de operaciones. México: Pearson Educacion.

-

Lopez Reyes, Danae. (2015). El metodo Hungaro de Asignacion: Aplicaciones. Universidad de Sevilla , 1, 55.

-

Anónimo. (2004). Fundamentos de Investigación de Operaciones Asignación y Vendedor Viajero. Primer Semestre, 1, 19.

-

Geo tutoriales. (2015). El Método Húngaro como Algoritmo de Solución del Modelo de Asignación. 2020, de Programación de Trabajos, Programación Entera Sitio web: https://www.gestiondeoperaciones.net/programacionentera/el-metodo-hungaro-como-algoritmo-de-solucion-del-modelo-deasignacion/...