a
b
c
d
x
y
z
AC
i
Randomize
Acerca de la calculadora del método húngaro
Resuelva problemas de asignación y transporte usando el método húngaro en línea con solución detallada paso a paso. con descripción completa y detallada paso a paso de las soluciones, que resuelve problemas de programación lineal de hasta 20×20 con coeficientes de tipo: números decimales y fracciones.
Para iniciar el cálculo, primero hay que introducir las dimensiones del problema en los campos de entrada en la parte superior de la pantalla y elegir la operación deseada en el menú lateral.
Un poco más abajo encontrará una ventana de entrada donde se deben ingresar los coeficientes, las restricciones y los valores del lado derecho usando el teclado. Aquí también se encuentra el panel de control de entrada, que simplifica el trabajo con los problemas de PL y contiene los siguientes elementos de control:
- El primer elemento permite expandir la ventana de entrada. Esto puede ser especialmente útil cuando la tabla no cabe completamente en la pantalla. Si la tabla aún no es totalmente visible después de expandir la ventana, puede cambiar la escala con los botones + / -;
- El segundo elemento copia los datos de entrada del problema actual al búfer de memoria. Esto puede ser útil cuando se resuelve con frecuencia el mismo problema de PL o se necesita transferir datos entre operaciones;
- Y el último elemento pega los datos de entrada copiados anteriormente, lo que permite restaurar los datos del problema en pocos clics en lugar de volver a ingresarlos manualmente;
Y más abajo encontrará una barra de herramientas que permite personalizar la calculadora y facilitar su uso. Está dividida visualmente en tres partes, cada una de las cuales se encarga de la siguiente funcionalidad:
- La primera parte permite seleccionar el formato numérico utilizado al mostrar el resultado de la solución. También puede desactivar los comentarios paso a paso si ya conoce el método y solo necesita verificar sus propios cálculos, u ocultar la solución paso a paso por completo si solo necesita la respuesta final;
- La segunda parte contiene botones que permiten modificar las dimensiones de la tabla de entrada, borrar coeficientes individuales o toda la entrada, y el botón principal con el signo igual que lleva a la pantalla de solución. Todos estos botones tienen atajos de teclado. Pase el cursor sobre un botón para ver la tecla correspondiente en un tooltip. También puede usar las teclas de flecha para mover el cursor entre los campos de entrada;
- Y la última parte permite elegir el número de dígitos después del punto decimal para redondear resultados no enteros. Una vista previa en tiempo real muestra cómo aparecerán los valores redondeados;
¿Qué es el método húngaro?
El método húngaro (algoritmo de Kuhn-Munkres) resuelve el problema de asignación: dada una matriz de costos n×n, encontrar un emparejamiento perfecto entre n trabajadores y n tareas que minimice el costo total. El problema de asignación es un caso especial del problema de transporte donde cada oferta y cada demanda es igual a 1. El algoritmo se ejecuta en tiempo polinómico y garantiza encontrar la asignación globalmente óptima.
¿Cómo resolver un problema de asignación con el método húngaro?
Comience restando el mínimo de columna de cada elemento de cada columna (reducción de columnas) y luego reste el mínimo de fila de cada elemento de cada fila (reducción de filas). Encuentre el número mínimo de líneas horizontales y verticales necesarias para cubrir todos los ceros en la matriz reducida. Si se necesitan n líneas, los ceros cubiertos contienen una asignación óptima — extráigala. De lo contrario, encuentre el elemento no cubierto más pequeño, réstelo de todos los elementos no cubiertos y súmelo a todos los elementos cubiertos por dos líneas, luego repita el paso de cobertura de ceros. Continúe hasta que se puedan seleccionar n ceros independientes, obteniendo la asignación óptima.
Ejemplo de resolución de un problema de asignación con el método húngaro
La solución del problema comienza con una etapa preliminar. El resultado de la misma será la matriz C0 que se denomina matriz de costos de mercancías adaptada, y la matrizX0, matriz de volúmenes de tráfico de mercancías.
La etapa preliminar comienza con la obtención de la matriz C', para la cual encontramos los valores mínimos en las columnas de la matriz C y los restamos elemento a elemento de las columnas correspondientes.
Obtenemos la matriz C0 repitiendo una operación similar ahora para las filas de la matriz C'.
En las matrices X0 en lugar de los elementos no nulos de la matriz C0 necesariamente se ubica 0. En las posiciones de los elementos vacíos de la matriz, escribimos el menor de dos valores: el saldo de existencias, en la fila donde se encuentra la celda vacía, y el saldo de necesidades, en la columna donde se encuentra.
El valor de la suma de los saldos de necesidades y existencias es una medida absoluta de la distribución óptima de recursos presentada en la matriz X actual. Para una distribución óptima, esta suma es 0.
Tras la etapa preliminar, comenzamos a realizar el proceso iterativo de búsqueda de la matriz X óptima. Cada iteración termina con la obtención de una nueva matriz X como resultado de la implementación exitosa de la segunda etapa. La iteración comienza con la primera etapa. Si no es posible implementar con éxito la segunda etapa, se realiza la tercera etapa y luego se vuelve a la primera.
Primera etapa
Complementamos las filas y columnas de la matriz C actual con los residuos de la matriz X actual. Marcamos con una línea horizontal encima los ceros de la matriz C actual ubicados en el lugar de los elementos no nulos de la matriz X actual. Marcamos con signos más los elementos de la matriz C actual cuyo residuo es 0;
Segunda etapa
La segunda etapa consiste en la construcción de una cadena; si se logra, obtenemos una nueva matriz X y completamos la iteración actual. Si no, se pasa a la tercera etapa.
Construcción de una cadena:
Buscamos un cero en una columna no marcada con + arriba y lo denotamos con un guión horizontal; a la derecha de la fila donde se encuentra, añadimos +. Si el residuo de la fila donde se ubica ese cero no es cero, la construcción de la cadena puede considerarse completa; de lo contrario, continuamos construyendo la cadena. El siguiente elemento que permite extender la cadena debe ser 0 y cumplir los siguientes requisitos:
- ubicado en la fila donde 0' - en la columna marcada con + arriba;
- marcado arriba con una línea horizontal;
Si se encuentra un cero que cumple estos requisitos, lo denotamos con * y retiramos el + de la columna donde se encuentra, encerrándolo entre paréntesis. Después de encontrar 0* es necesario encontrar 0 en la columna donde se ubica. Si existe, lo denotamos con una barra horizontal. Si el cero encontrado 0' está en una fila con residuo cero, continuamos construyendo la cadena intentando encontrar 0* en esa fila. Si el residuo de la fila donde se ubica 0' no es cero, el proceso de construcción de la cadena está completo. Si se agotaron todas las opciones para construir la cadena y no fue posible construirla, se pasa a la tercera etapa. Una cadena es un conjunto de un número impar de ceros, en el que en las posiciones pares siempre hay 0* , y en las impares 0'. La longitud mínima de la cadena es un 0.
Tras obtener la cadena, definimos Θ. Θ es el mínimo de los siguientes números:
- discrepancia de la columna donde se ubica 0' con la que comienza la cadena;
- discrepancia de la fila donde se ubica 0' en la que termina la cadena;
- valores de la matriz X actual ubicados en las posiciones 0* de la cadena;
Tras determinar Θ, procedemos al cálculo de la nueva matriz X, sumando Θ a los elementos de la matriz X actual ubicados en las posiciones 0' de la cadena, y restando Θ a los elementos de la matriz X actual en las posiciones 0* de la cadena;
Tercera etapa
Incluimos en los contornos rectangulares las filas y columnas marcadas con +. Entre los elementos que no están en los contornos, elegimos el valor más pequeño. Obtenemos la matriz intermedia C~, restando el valor más pequeño a los elementos de las filas que no están en los contornos, dejando sin cambios las filas en los contornos. Obtenemos una nueva matriz C sumando el valor más pequeño a los elementos de las columnas de la matriz C~que están en los contornos, dejando sin cambios las columnas que no están en los contornos. Al obtener la nueva matriz C, se completa la tercera etapa. Después de eso, aplicamos las operaciones de la primera y segunda etapa a la matriz obtenida.
Aplicamos la primera y segunda etapa.
Como no es posible construir una cadena, pasamos a la tercera etapa.
Obtenemos una matriz intermedia.
Obtenemos una nueva matriz C.
Aplicamos la primera y segunda etapa.
Encontramos Θ.
Calculamos la nueva matriz X.
Aplicamos la primera y segunda etapa.
Como no es posible construir una cadena, pasamos a la tercera etapa.
Obtenemos una matriz intermedia.
Obtenemos una nueva matriz C.
Aplicamos la primera y segunda etapa.
Encontramos Θ.
Calculamos la nueva matriz X.
Como el valor de la suma de los saldos de necesidades y existencias es cero, la matriz X es óptima y se puede obtener el resultado encontrando la suma de los productos de los elementos no nulos de la matriz X actual y los elementos correspondientes de la matriz C original.
(3 * 0) + (1 * 1) + (1 * 2) + (5 * 0) + (5 * 0) = 3
Preguntas frecuentes
¿Qué resuelve el método húngaro?
Resuelve el problema de asignación: emparejar n trabajadores con n tareas de modo que el coste total sea mínimo y cada trabajador quede asignado exactamente a una tarea.
¿Por qué la matriz de costes tiene que ser cuadrada?
Cada trabajador debe emparejarse con exactamente una tarea, por lo que el número de trabajadores y de tareas debe ser igual. Cuando no lo son, se añaden filas o columnas ficticias con coste cero para cuadrar la matriz.
¿Cómo funciona la reducción de filas y columnas?
Restar la entrada más pequeña de cada fila y luego de cada columna crea ceros sin cambiar qué asignación es óptima. A continuación, el método encuentra un conjunto completo de ceros independientes, ajustando la matriz hasta que exista uno.
¿Cómo interpreto el resultado?
El resultado marca la asignación óptima de trabajadores a tareas y reporta el coste total mínimo: la suma de los costes originales de los pares elegidos.