Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 91 vistas

    Método Húngaro-Maximizacion

    Cargado por

    selena
    El método húngaro es un algoritmo para resolver problemas de asignación que consta de tres pasos: 1) reducir la matriz de costos restando el menor valor de cada fila y columna, 2) trazar líneas para cubrir los ceros y reducir otros valores, y 3) construir la solución óptima a partir de los ceros restantes. Cuando el objetivo es la maximización, se restan los mayores valores en lugar de los menores. El documento también presenta un ejemplo de aplicar el método húngaro para maximizar la cosecha de café asignando

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Método Húngaro-Maximizacion

    Cargado por

    selena
    91 vistas5 páginas
    El método húngaro es un algoritmo para resolver problemas de asignación que consta de tres pasos: 1) reducir la matriz de costos restando el menor valor de cada fila y columna, 2) trazar líneas para cubrir los ceros y reducir otros valores, y 3) construir la solución óptima a partir de los ceros restantes. Cuando el objetivo es la maximización, se restan los mayores valores en lugar de los menores. El documento también presenta un ejemplo de aplicar el método húngaro para maximizar la cosecha de café asignando

    Título original

    Método Húngaro-maximizacion

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El método húngaro es un algoritmo para resolver problemas de asignación que consta de tres pasos: 1) reducir la matriz de costos restando el menor valor de cada fila y columna, 2) trazar líneas para cubrir los ceros y reducir otros valores, y 3) construir la solución óptima a partir de los ceros restantes. Cuando el objetivo es la maximización, se restan los mayores valores en lugar de los menores. El documento también presenta un ejemplo de aplicar el método húngaro para maximizar la cosecha de café asignando

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    91 vistas5 páginas

    Método Húngaro-Maximizacion

    Cargado por

    selena
    El método húngaro es un algoritmo para resolver problemas de asignación que consta de tres pasos: 1) reducir la matriz de costos restando el menor valor de cada fila y columna, 2) trazar líneas para cubrir los ceros y reducir otros valores, y 3) construir la solución óptima a partir de los ceros restantes. Cuando el objetivo es la maximización, se restan los mayores valores en lugar de los menores. El documento también presenta un ejemplo de aplicar el método húngaro para maximizar la cosecha de café asignando

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 5

    Método Húngaro

    Pasos para el método húngaro:

    - Paso 1: De la matriz de costos m*m, encontrar primero el mínimo elemento de cada
    fila, y restarlo a cada costo de la fila. Repetimos la operación por columnas, buscando
    el costo mínimo en cada columna, y construyendo una nueva matriz (denominada
    matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna.
    - Paso 2: Repetiremos este paso hasta encontrar una solución:
    1) Trace el número mínimo de líneas (horizontales, verticales o ambas) en la última
    matriz de costos reducidos que cubra todos los ceros.
    2) Si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima
    entre los ceros cubiertos de la matriz. Si no continuamos.
    3) Selecciones el elemento no cubierto más pequeño y réstelo de todos los elementos
    no cubiertos; después, súmelo a todos los elementos en la intersección de dos líneas.
    - Paso 3: Usando los ceros que hemos obtenido construimos la solución sabiendo que
    solo es posible asignar i a j, si el elemento xij de la matriz de costos reducidos
    modificada es 0. Se llega por descarte a una (o varias) soluciones óptimas.

    Caso especial al aplicar el Método Húngaro cuando se trata de Maximizar

    Cuando hay que pasar de maximizar a minimizar en lugar de operar con el menor de toda la
    matriz podemos ir tomando el mayor de cada fila o columna e ir restándole todos los
    elementos de esa fila o columna con lo cual conseguiremos obtener por lo menos un cero
    como mínimo en cada fila o columna. Si en alguna columna no hubiera ceros le quitamos el
    mayor a la columna.

    Problema de maximización mediante el Método Húngaro

    - Una organización de recolección de café cuenta con tres equipos de siembra y cosecha
    del mismo (equipos 1, 2, 3). Estos equipos de trabajo se encuentran entrenados para
    trabajar en condiciones particulares del proceso, condiciones como lo son el tipo de
    suelo, las condiciones del clima y el tipo de grano. La organización cuenta con cuatro
    terrenos disponibles para efectuar el proceso de siembra y cosecha (terrenos A, B, C,
    D), estos terrenos tienen condiciones particulares de suelo, clima y tipo de grano. Cada
    equipo cuenta con la capacidad de efectuar el proceso en solo uno de los terrenos
    disponibles, salvo el equipo 2, que cuenta con una serie de herramientas tecnológicas
    que le permiten realizar la siembra y cosecha del grano en dos de los terrenos
    disponibles.
    El siguiente tabulado muestra la capacidad (en cientos de sacos) de cosecha de café de
    cada uno de los equipos dependiendo de cada uno de los terrenos.
    Solución

    Partimos de un concepto fundamental para la aplicación del método húngaro (el número de
    filas debe ser exactamente igual al número de columnas). Por ende, la acción a realizar debería
    ser crear un equipo ficticio, el cual nos deje el tabulado balanceado y a este asignarle un
    número de sacos cosechados equivalente a cero en cada uno de los terrenos. Sin embargo el
    problema nos indica que uno de los equipos se encuentra en capacidad de que se le asignen
    dos terrenos, en este caso crearemos un equipo 2 alternativo (Equipo 2B) el cual nos
    balanceará el tabulado y nos hará prescindir del equipo ficticio pensado inicialmente. A este
    equipo 2B que crearemos le corresponderá la misma capacidad de cosecha del equipo 2A del
    terreno:

    Una vez balanceado el tabulado debemos de cuestionarnos acerca del criterio de optimización.
    En este caso nuestro objetivo es maximizar, por lo que tendremos que aplicar un paso
    adicional.

    Lo primero que debemos hacer es ubicar el mayor valor del tabulado inicial.

    En este caso este valor es 15, por lo cual procederemos a realizar la siguiente operación con
    cada uno de los valores:

    Restaremos a 15, el valor de cada una de las celdas y este valor quedará en cada una de las
    celdas correspondientes.
    Ahora nuestro tabulado inicial quedará de la siguiente manera:

    A partir de este tabulado ya podemos aplicar el algoritmo del método húngaro como se
    aplicaría en un caso e minimización (normalmente).

    Ahora encontramos el menor elemento de cada fila.

    Y se lo restamos a todas las celdas de la fila.


    Ahora efectuamos este mismo paso, pero esta vez con las columnas. Elegimos el menor de los
    valores de cada columna y se lo restamos a cada una de las celdas de la columna
    correspondiente.

    Ahora procedemos a cubrir la mayor cantidad de ceros, con la menor cantidad de líneas, si el
    número de líneas que empleemos es igual al grado de la matriz (en este caso matriz grado 4,
    4×4) habremos llegado al final del ejercicio.
    Dado que el número de líneas es igual al grado de la matriz, hemos concluido el algoritmo. Lo
    único que quedará será asignar a cada equipo el terreno en el que el intercepto es igual a 0
    (cero).

    Las asignaciones, como es lógico deberán iniciarse por el equipo al cual solo corresponda un
    terreno, en este caso al Equipo 3 le corresponde el Terreno A. De esta manera al Equipo 1 le
    corresponde el Terreno D. Mientras tanto el Equipo 2 se encargará de la cosecha en los
    terrenos B y C. Según el tabulado del problema (recordemos que es de maximización), la
    cantidad de sacos (expresada en cientos de sacos) será así:

    También podría gustarte