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 c_{ij} representan los costos unitarios de transporte desde el silo i al molino j.

ejemplo-esquina-noroeste

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:

solucion-costo-minimo

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

  • La celda x_{12} tiene el menor costo unitario, por tanto se asigna lo máximo posible (15 unidades correspondiente a la oferta del silo 1). Con x_{12}=15 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 x_{31} tiene el mínimo costo unitario sin tachar. Se asigna x_{31}=5 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 x_{23}, 0 unidades a la celda x_{14} (la capacidad del silo 1 ya fue asignada), 5 unidades a la celda x_{34} y 10 unidades a la celda x_{24}.

La solución básica factible de inicio resultante con 6 variables básicas es: x_{12}=15, x_{14}=0, x_{23}=15, x_{24}=10, x_{31}=5, x_{34}=5 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.

solucion-solver-transporte-

Rating: 3.0/5. From 5 votes.
Please wait...

, , , , , , ,

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

  1. Fernando 07/04/2016 en 12:14 #

    Disculpa en la parte del x14 me podrías explicar ¿por qué se pone “0” cero?

    • GEO Tutoriales 07/04/2016 en 21:44 #

      @Fernando. La respuesta a tu pregunta es que la capacidad máxima del silo 1 fue asignada previamente en los pasos del algoritmo de costo mínimo.

  2. Julio 17/09/2016 en 17:53 #

    Buenas Tardes. No entiendo porque después de x14, continua por x24 en vez de seguir por x34 ya que este último posee el mínimo costo.

    • GEO Tutoriales 20/09/2016 en 22:32 #

      @Julio. Después de x14 se sigue a x34 asignando la capacidad remanente del Silo 3, para pasar finalmente a x24.

Deja un comentario