Método de la Esquina Noroeste (Algoritmo de Transporte en Programación Lineal)

El Método de la Esquina Noroeste (o esquina superior izquierda) es una heurística que se aplica a una estructura especial de problemas de Programación Lineal llamada Modelo de Transporte, la cual permite asegurar que exista una solución básica factible inicial (no artificial). Otros métodos para la obtención de una solución básica de inicio son el Método de Costo Mínimo y Método de Aproximación de Vogel. En general, el Método de Vogel produce la mejor solución básica de inicio y el de la Esquina Noroeste la peor, sin embargo, el Método de la Esquina Noroeste implica el mínimo de cálculos.

El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la esquina noroeste, o superior izquierda, de la tabla (variable ). A continuación una descripción de los pasos:

Paso 1: Asignar todo lo posible a la celda seleccionada y ajustar las cantidades asociadas de oferta y demanda restando la cantidad asignada.

Paso 2: Salir de la fila o la columna cuando se alcance oferta o demanda cero, y tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o columna. Si una fila y una columna dan cero al mismo tiempo, tachar sólo uno (la fila o columna) y dejar una oferta (demanda) cero en la fila (columna) que no se tachó.

Paso 3: Si queda exactamente una fila o columna sin tachar, detenerse. En caso contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a la de abajo si se tachó un reglón. Seguir con el Paso 1.

Método de la Esquina Noroeste

Para ilustrar la aplicación del Método de la Esquina Noroeste consideremos el siguiente problema balanceado de transporte que considera 3 silos productos (oferta) que satisfacen las necesidades de 4 molinos (demanda). El algoritmo de transporte se basa en la hipótesis que el modelo está balanceado, es decir, que la demanda total es igual a la oferta total (si el modelo no está balanceado siempre se podrá aumentar con una fuente ficticia o un destino ficticio para restaurar el equilibrio o balance).

Los costos unitarios de transporte desde el silo i al molino j se representan en la esquina superior derecha de cada cuadro. Por ejemplo el costo unitario de enviar una unidad de producto desde el silo 1 al molino 1 es de $10. Adicionalmente los silos 1, 2 y 3 tienen capacidad u oferta de 15, 25 y 10 unidades, respectivamente. Por otra parte los molinos 1, 2, 3 y 4 tienen requerimientos o demanda de 5, 15, 15 y 15 unidades, respectivamente. El modelo esta balanceado (suma oferta = suma demanda = 50 unidades).

Al aplicar el Método de la Esquina Noroeste al ejemplo anterior se obtienen los siguientes resultados. Las flechas indican el orden en el que se generan las cantidades asignadas:

• La cantidad asignada a la celda  son 5 unidades, dado que si bien el silo 1 tiene capacidad de 15 unidades, el molino 1 sólo necesita (demanda) 5 unidades (no se realizan más asignaciones a la columna 1 correspondiente al molino 1).

• A continuación nos movemos a la derecha y asignamos lo máximo posible (10 unidades remanentes) a la celda  (con lo cual se completa la capacidad del silo 1 y en consecuencia no es posible seguir realizando asignaciones en la fila 1).

• Luego asignamos 5 unidades a la celda  lo cual es por cierto menor que la capacidad del silo 2 pero lo suficiente para satisfacer los requerimientos del molino 2 (ahora no es posible generar asignaciones adicionales a la columna 2).

• Nos movemos a la derecha y se asignan 15 unidades del silo 2 al molino 3 () lo que cubre inmediatamente los requerimientos del molino 3 (no es necesario asignar más en la columna 3).

• Nuevamente nos movemos a la derecha y asignamos lo máximo posible (5 unidades que es la capacidad remanente del silo 2, es decir, ) con lo cual el silo 2 opera a máxima capacidad (ahora ya no es posible nuevas asignaciones en la fila 2).

• Finalmente se asignan 10 unidades del silo 3 al molino 4 () cubriendo la demanda de dicho molino (y la capacidad del correspondiente silo).

En consecuencia la solución básica factible inicial es: que reporta un costo del programa (valor en la función objetivo) de: Z=5(10)+10(2)+5(7)+15*(9)+5(20)+10*(18)=$520. Notar que si se implementa computacionalmente el problema anterior haciendo uso de Solver de Excel y utilizando como motor de resolución Simplex_LP se alcanza la siguiente solución óptima (celdas amarillas) con costo mínimo (valor óptimo) de $435.