Métodos de transporte y asignación: Esquina Noroeste, Costo Mínimo, Vogel y Húngaro

Resumen

El documento explica cuatro métodos para resolver problemas de transporte y asignación: el de la Esquina Noroeste, el de Costo Mínimo, la Aproximación de Vogel (MAV) y el Método Húngaro. Para cada uno describe el procedimiento, su resultado y sus ventajas. Sirve para aprender a obtener soluciones iniciales y óptimas en problemas de optimización de recursos.

Puntos clave

El método de la Esquina Noroeste empieza en la celda superior izquierda y produce una solución válida, pero generalmente no la de costo mínimo.
El método de Costo Mínimo asigna primero en la celda de menor costo de toda la tabla y suele superar a la Esquina Noroeste.
El método de Vogel calcula penalizaciones como la diferencia entre los dos costos menores de cada fila o columna y es la mejor solución inicial.
Una solución de transporte válida tiene m+n-1 asignaciones.
El método Húngaro asigna recursos a tareas de forma 1 a 1, restando mínimos por filas y columnas y trazando líneas que cubran los ceros.
Si un problema de asignación está desbalanceado, se añaden filas o columnas ficticias con costo 0.

Ponte a prueba

1. Método de la Esquina Noroeste

Imagina que llenas una tabla empezando siempre desde la esquina superior izquierda (noroeste). Es el método más sencillo, pero suele arrojar el resultado de mayor costo.

Clave: Empieza en la celda (Fila 1, Columna 1). Asigna la mayor cantidad posible. Tacha la fila o columna que se agotó. Continúa hacia la derecha o hacia abajo.
Resultado: Proporciona una solución válida (m+n-1 asignaciones), pero generalmente no es el costo mínimo. Sirve principalmente como punto de partida para otros métodos.
Ejemplo 1: Con la tabla del Ejemplo 1: se asignaron 30-A1, 5-A2, 20-B2, 15-B3, 10-C3, 20-C4 → CT = 6*30 + 4*5 + 4*20 + 6*15 + 8*10 + 6*20 = (calculado en clase).

2. Método de Costo Mínimo

En lugar de comenzar por la esquina, se busca el costo más bajo de toda la tabla para realizar la primera asignación. Es equivalente a priorizar siempre el producto más económico.

Clave: Buscar el número más pequeño en toda la matriz, asignar el máximo posible, tachar la fila o columna agotada y repetir el proceso con la tabla restante.
Ventaja: Generalmente ofrece un resultado superior a la Esquina Noroeste, ya que considera los costos desde el inicio.
Nota: Ante un empate (dos celdas con el mismo costo mínimo), elige aquella que permita asignar una mayor cantidad de unidades.

3. Método de Aproximación de Vogel (MAV)

Es el más eficiente de los tres métodos iniciales. Calcula una 'penalización' por no elegir la mejor opción en cada fila y columna, representando el costo de oportunidad de una mala decisión.

Penalización de fila: (2.º costo menor) − (1.er costo menor) de esa fila.
Penalización de columna: (2.º costo menor) − (1.er costo menor) de esa columna.
Regla de asignación: Elige la fila o columna con la penalización más alta. En esa fila/columna, asigna en la celda de costo mínimo.
Empate en penalización: Si dos filas o columnas tienen la misma penalización, asigna donde puedas colocar más unidades (mayor valor entre oferta y demanda disponibles).
Resultado: Es la mejor solución inicial, frecuentemente cercana o igual al óptimo.

4. Método de Asignación (Método Húngaro)

Este método difiere del de transporte, ya que asigna un recurso a una tarea específica (1 persona = 1 trabajo). No se manejan ofertas ni demandas en cantidades, sino una relación de 1 a 1.

Paso 1: Restar el mínimo de cada fila a todos los valores de dicha fila.
Paso 2: Restar el mínimo de cada columna a todos los valores de esa columna (sobre la matriz ya modificada).
Paso 3: Trazar el número mínimo de líneas (horizontales o verticales) que cubran todos los ceros. Si el número de líneas es igual a n, realiza la asignación en los ceros.
Si el número de líneas es menor a n: Toma el valor mínimo no cubierto por ninguna línea. Resta este valor a todos los elementos no cubiertos y súmalo a los que están cubiertos dos veces. Los cubiertos una sola vez permanecen igual. Repite el Paso 3.
Asignación final: Elige la fila o columna con un solo cero, asigna ahí, elimina esos ceros de fila y columna, y continúa.
Desbalanceado: Si hay más recursos que tareas (o viceversa), añade filas o columnas ficticias con costo 0.

Preguntas frecuentes

¿Qué diferencia hay entre el método de la Esquina Noroeste y el de Costo Mínimo?

La Esquina Noroeste comienza siempre en la celda superior izquierda, mientras que el de Costo Mínimo empieza en la celda con el costo más bajo de toda la tabla. Por eso el de Costo Mínimo generalmente ofrece un resultado mejor.

¿Cuándo se usa el Método Húngaro?

Se usa en problemas de asignación, donde cada recurso se asigna a una tarea específica en una relación de 1 a 1. No maneja ofertas ni demandas en cantidades.

¿Qué hacer si hay empate en las penalizaciones del método de Vogel?

Si dos filas o columnas tienen la misma penalización, se asigna en la posición donde se puedan colocar más unidades, es decir, el mayor valor entre oferta y demanda disponibles.