METODO DEL TRANSPORTE

Índice

5.1 Definición del problema de transporte 3

5.2 Método de la esquina noroeste 6

5.3 El método de aproximación de Vogel 12

5.4 Procedimientos de optimización 22

5.5 Definición del problema de asignación 26

5.6 El método húngaro 27

5.7 Uso de software 30

5.1 Definición del Problema del transporte.

La manera más fácil de reconocer un problema de transporte es por su naturaleza o estructura "de - hacia": de un origen hacia un destino, de una fuente hacia un usuario, del presente hacia el futuro, de aquí hacia allá. Al enfrentar este tipo de problema, la intuición dice que debe haber una manera de obtener una solución. Se conocen las fuentes y los destinos, las capacidades y demandas y los costos de cada trayectoria. Debe haber una combinación óptima que minimice el costo (o maximice la ganancia). La dificultad estriba en el gran número de combinaciones posibles.

En general, los problemas de transporte se ocupan (en forma literal o imaginaría) de la distribución desde cualquier grupo de centros de suministro, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos de modo que se minimice el costo total de distribución.

Cada origen tiene ciertos recursos (oferta) para distribuir a los destinos y cada destino tiene cierta demanda de estos recursos que recibe de los orígenes. El modelo de un problema de transporte hace la siguiente suposición acerca de estos recursos (ofertas) y demandas.

Suposición de requerimientos. Cada origen tiene una cantidad fija de unidades (oferta), las cuales tienen que distribuirse entre los destinos. De manera similar, cada destino tiene una demanda fija de unidades, que tiene que ser satisfecha desde los orígenes.

Esta suposición significa que debe haber un equilibrio entre la oferta total de todos los orígenes y la demanda total de todos los destinos.

Suposición de costo. El costo de distribuir unidades de cualquier origen dado a cualquier destino dado es directamente proporcional al número de unidades distribuidas. Por lo tanto, este costo es justo el costo unitario de distribución por el número de unidades distribuidas.

Los únicos datos necesarios para el modelo del problema de transporte son los recursos ( capacidades, existencias, oferta), las demandas y los costos unitarios. Éstos son los parámetros del modelo.

Formulación del Problema del transporte.

Supongamos que hay m centros de oferta (orígenes) y n centros de demanda (destinos) asimismo, supongamos que Ej es el número de unidades de mercancía disponibles en cada centro de oferta, y Dj el número requerido de unidades de mercancía en el centro de demanda. Si consideramos Cij como el costo unitario de transporte en la ruta de un centro de oferta a uno de demanda. El objetivo es determinar el número de unidades de mercancía que debe transportarse de las fuentes (i) a los destinos (j) de tal forma que se minimice el costo total del transporte. Si Xijes la cantidad transportada del centro de oferta (i) al centro de demanda (j) Entonces nuestro modelo será:

Una forma agradable de visualizar un problema de transporte en forma gráfica es usar su representación de red. Esta representación ignora la disposición geográfica de los orígenes y destinos. En su lugar, simplemente alinea todos los orígenes en una columna a la izquierda (donde E1 es el símbolo del origen 1, etc.)y todos los destinos en una columna a la derecha (donde Dj es el símbolo del destino 1, etc).

Para problemas muy grandes no es muy conveniente trazar la red completa y desplegar todos los datos. En consecuencia, la representación de red en realidad es un medio de visualización.

figura 6.1

La formulación del modelo de PL correspondiente a la figura 6.1 es:

La función objetivo del modelo de PL es, entonces, minimizar la suma de los costos de transporte para las 12 rutas. Es decir, la función objetivo es:

Las restricciones van de la capacidad limitada de cada planta a la demanda de cada almacén. Para la fabrica E1 la restricción es:

Esto significa que la cantidad total que se manda desde la fábrica E1 debe ser igual que su capacidad. Análogamente, se debe satisfacer la demanda de cada almacén. Para el almacén D1 se tiene:

Si se escribe todo el modelo, resulta:

• Las características matemáticas únicas que se deducen del modelo de transporte planteado son:

• Los coeficientes en cada restricción son todos 1 o cero (para las variables que no aparecen). Esto siempre es cierto para un problema de transporte.

• La suma de las existencias en los orígenes es igual a la suma de las demandas de los destinos. Lo que resulta es que, debido a estas características únicas, es posible que haya técnicas de solución del problema del transporte mas sencillas de solución.

• Otra característica de la formulación del modelo de PL es que se tiene un total de siete restricciones: una para cada origen y cada destino. Sin embargo, una de ellas es redundante. Realmente se necesitan sólo seis restricciones. La razón es que se sabe que la cantidad total que se manda desde todas las fábricas debe ser igual que la cantidad total que se recibe en todos los almacenes. Supóngase que se omite la restricción del cuarto almacén. Al resolver el problema se sabe cuánto se mandó de cada fábrica a los tres primeros almacenes y la cantidad total que se mandó desde las fábricas. Se sabrá entonces que la diferencia entre estas dos cantidades se tuvo que mandar al cuarto almacén. Esto lleva a la regla general de que el número de restricciones independientes siempre será una menos que la suma del número de orígenes y el número de destinos. Para cualquier problema de PL, el número de variables en la solución final no puede exceder el número de restricciones independientes. Entonces, para el ejemplo, cuando mucho se usarán 6 de las 12 rutas para la solución óptima. Esta regla es muy importante al resolver problemas con el método del transporte.

5.2 MÉTODO DE LA ESQUINA NOROESTE

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.

Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado. Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste.

ALGORITMO DE RESOLUCIÓN DE LA ESQUINA NOROESTE

Se parte por esbozar en forma matricial el problema, es decir, filas que representen fuentes y columnas que representen destinos, luego el algoritmo debe de iniciar en la celda, ruta o esquina Noroeste de la tabla (esquina superior izquierda).

PASO 1:

En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidades posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.

PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.

PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse".

La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".

EJEMPLO DEL MÉTODO DE LA ESQUINA NOROESTE

Por medio de este método resolveremos el problema de transporte propuesto y resuelto en módulos anteriores mediante programación lineal.

EL PROBLEMA

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.

Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.

SOLUCIÓN PASO A PASO

Ahora la cantidad asignada a la esquina

...