Método del Costo Mínimo (Algoritmo de Transporte en Programación Lineal)

El Método del Costo Mínimo determina una mejor solución básica factible inicial que el Método de la Esquina Noroeste debido a que se concentra en las rutas menos costosas.

De esta forma el Método del Costo Mínimo se inicia asignando lo máximo posible a la celda que tenga el mínimo costo unitario (en caso de empates, éstos se rompen de forma arbitraria). A continuación, la fila o columna ya satisfechos de tacha, y las cantidades de oferta y demanda se ajustan en consecuencia. Si se satisfacen de forma simultanea una fila y una columna, sólo se tacha uno de los dos (de forma idéntica que el Método de la Esquina Noroeste). Luego se busca la celda no tachada con el costo unitario mínimo y se repite el proceso hasta que queda sin tachar exactamente una fila o una columna.

Consideremos nuevamente el Problema de Transporte donde se desea satisfacer la demanda de 4 molinos a través de los envíos de 3 silos, donde los valores en la esquina superior derecha de cada cuadro representan los costos unitarios de transporte desde el silo i al molino j.

Fe de Erratas: En la imagen dice Molino 1, 2, 3 y 5 (columnas). Debería decir: Molino 1, 2, 3 y 4.

La aplicación del Método de Costo Mínimo al problema de transporte anterior da origen a la siguiente solución factible de inicio:

Los pasos aplicados para llegar a dichos resultados se resumen a continuación:

• La celda tiene el menor costo unitario, por tanto se asigna lo máximo posible (15 unidades correspondiente a la oferta del silo 1). Con se satisface tanto la demanda del molino 2 como la oferta del silo 1. Se tacha de forma arbitraria la columna 2.

• Ahora la celda tiene el mínimo costo unitario sin tachar. Se asigna y se tacha la columna 1 porque quedó satisfecha (lo cual deja una capacidad remanente del silo 3 de 5 unidades).

• Al continuar de este modo, se asignan en forma sucesiva 15 unidades a la celda , 0 unidades a la celda (la capacidad del silo 1 ya fue asignada), 5 unidades a la celda y 10 unidades a la celda .

La solución básica factible de inicio resultante con 6 variables básicas es: la cual reporta un valor en la función objetivo (costo) de Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=$475 que efectivamente es una mejor solución inicial que la obtenida por el Método de la Esquina Noroeste (que provee un valor de $520 al ser evaluado en la función objetivo) pero por cierto no es la solución óptima según se aprecia en la siguiente imagen que resume la implementación computacional del problema en Solver.