Transporte y transbordo

En éste capítulo estudiaremos un modelo particular de problema de programación lineal, uno en el cual su resolución a través del método simplex es dispendioso, pero que debido a sus características especiales ha permitido desarrollar un método más práctico de solución.

El modelo de transporte se define como una técnica que determina un programa de transporte de productos o mercancías desde unas fuentes hasta los diferentes destinos al menor costo posible.

También estudiaremos el problema del transbordo en el que entre fuentes y destinos, existen estaciones intermedias.

Modelo General del Problema del Transporte

Es un caso especial de problema de programación Lineal, en el que todos los coeficientes de las variables en las restricciones tienen coeficiente uno (1), esto es:

a_i,j = 1 ; para todo i , para todo j

Gráficamente:

 

Matemáticamente:

Observación:

Metodología general:

Ejemplo:

Tres (3) fábricas envían su producto a cinco (5) distribuidores. Las disponibilidades, los requerimientos y costos unitarios de transporte, se dan en la siguiente tabla.

¿Qué cantidad del producto se debe enviar desde cada fábrica a cada distribuidor para minimizar los costos del transporte?

NOTA: La “X” significa que desde la fábrica 3 es imposible enviar unidades al distribuidor 5

Solución

Observe que el modelo no es perfecto: La oferta es diferente a la demanda. Se adiciona una fábrica de relleno con costos de transporte igual a cero (0) y que ofrezca justo lo que le hace falta a la oferta para ser igual a la demanda

Formulación 

X_ij = Unidades a enviar desde la fábrica i-ésima (i=1,2,3,4) al distribuidor j-ésimo (j=1,2,3,4,5)

Solución Básica Factible

Como cada variable figura dos (2) veces en el sistema de ecuaciones, entonces tiene m+n-1 grados de libertad y el número de variables básicas debe ser igual al número de grados de libertad del sistema. Lo anterior nos asegura una solución básica factible no degenerada.

NÚMERO DE VARIABLES BÁSICAS = m + n – 1

MÉTODOS DE APROXIMACIÓN

MÉTODO DE LA ESQUINA NOROESTE

 

Características

. Sencillo y fácil de hacer

. No tiene en cuenta los costos para hacer las asignaciones

. Generalmente nos deja lejos del óptimo.

 

Algoritmo

1. Construya una tabla de ofertas (disponibilidades) y demandas (requerimientos).

2. Empiece por la esquina noroeste.

3. Asigne lo máximo posible (Lo menor entre la oferta y la demanda, respectivamente)

4. Actualice la oferta y la demanda y rellene con ceros el resto de casillas (Filas ó Columnas) en donde la oferta ó la demanda halla quedado satisfecha.

5. Muévase a la derecha o hacia abajo, según halla quedado disponibilidad para asignar.

6. Repita los pasos del 3 al 5 sucesivamente hasta llegar a la esquina inferior derecha en la que se elimina fila y columna al mismo tiempo.

Nota: No elimine fila y columna al mismo tiempo, a no ser que sea la última casilla. El romper ésta regla ocasionará una solución en donde el número de variables básicas es menor a m+n-1, produciendo una solución básica factible degenerada.

En nuestro problema de ejemplo:

Aquí, asignamos en la fila 1, columna 1 lo máximo posible entre 40 y 30 o sea 30 unidades; X₁₁=30 variable básica. Actualizamos la oferta y la demanda, quedando éstas en: 10 y 0 y rellenamos con cero el resto de la columna 1, ya que la demanda de 30 unidades quedó satisfecha. Terminando el método, el tablero aparecerá así:

Como evitar eliminar fila y columna al mismo tiempo, sin estar en la última casilla, uso de ε

Supongamos que nuestro problema es:

Para éste caso, procedemos así: Escoger satisfacer la fila o la columna (oferta o demanda), para nuestro ejemplo escogemos satisfacer la oferta, entonces decidimos que a la demanda le queda una cantidad muy pequeña por satisfacer, llamada ε (epsilon) cuyo valor es aproximadamente igual a cero (0), ≅ 0 y para efectos de cálculos futuros ε = 0.

MÉTODO DEL COSTO MÍNIMO

 

Características

. Es más elaborado que el método de la esquina noroeste

. Tiene en cuenta los costos para hacer las asignaciones

. Generalmente nos deja alejados del óptimo

 

Algoritmo

1. Construya una tabla de disponibilidades, requerimientos y costos

2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate, escoja arbitrariamente (Cualquiera de los empatados).

3. Asigne lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos).

4. Rellene con ceros (0) la fila o columna satisfecha y actualice la disponibilidad y el requerimiento, restándoles lo asignado.

Nota: Recuerde que no debe eliminar ó satisfacer fila y columna al mismo tiempo, caso en que la oferta sea igual a la demanda, en tal caso recuerde usar la ε (Epsilon).

5. Muévase a la casilla con el costo mínimo de la tabla resultante (Sin tener en cuenta la fila o columna satisfecha).

6. Regrese a los puntos 3,4,5 sucesivamente, hasta que todas las casillas queden asignadas.

En nuestro ejemplo, la tabla queda así:

Ahora escogemos el menor costo en la tabla que queda, volviéndose a presentar un múltiple empate, el cual dirimimos escogiendo la casilla de la fila 4, columna 2, y asignamos lo máximo posible entre 40 y 20. Diligenciando todo el tablero obtenemos:

MÉTODO DE VOGEL

 

Características

. Es más elaborado que los anteriores, más técnico y dispendioso.

. Tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones.

. Generalmente nos deja cerca al óptimo.

 

Algoritmo

1. Construir una tabla de disponibilidades (ofertas), requerimientos (demanda) y costos.

2. Calcular la diferencia entre el costo mas pequeño y el segundo costo más pequeño, para cada fila y para cada columna.

3. Escoger entre las filas y columnas, la que tenga la mayor diferencia (en caso de empate, decida arbitrariamente).

4. Asigne lo máximo posible en la casilla con menor costo en la fila o columna escogida en el punto 3.

5. asigne cero (0) a las otras casillas de la fila o columna donde la disponibilidad ó el requerimiento quede satisfecho.

6. Repita los pasos del 2 al 5, sin tener en cuenta la(s) fila(s) y/o columna(s) satisfechas, hasta que todas las casillas queden asignadas.

Nota: Recuerde que no debe satisfacer filas y columnas al mismo tiempo; caso en que la disponibilidad sea igual al requerimiento; en tal caso use el ε (epsilon).

Ahora recalculamos las diferencias, sin tener en cuenta la columna 4, que está satisfecha.

Una vez ejecutado todo el algoritmo hasta asignar todas las casillas, obtenemos la siguiente asignación básica y factible inicial.

Fíjese que el número de variables básicas es: m+n-1=8

Solución básica factible no degenerada:

Conclusión: Hemos conseguido tres (3) soluciones básicas factibles no degeneradas (# de variables básicas = m+n-1=8) por medio de tres (3) métodos: El de la esquina noroeste, el del costo mínimo y el de Vogel.  Pero ninguna de ellas nos garantiza que la solución encontrada es la óptima. Para saberlo, debemos estar seguros que ninguna de las variables no básicas pueda entrar a la base haciendo que la función objetivo disminuya. Para discernir un método que nos evalúe el efecto de introducir una unidad de cada variable no básicas, recurrimos al método algebraico que posteriormente se convertirá en el método MODI.

 

Importante: A partir de cualquiera de éstas tres (3) soluciones básicas factibles no degeneradas, debemos comenzar a iterar, para encontrar el óptimo.

Método algebraico

El sistema de ecuaciones iniciales es:

Observe que la nueva función objetiva es:

Fíjese que se han eliminado todas las variables básicas de la función objetivo, siendo solamente Z la variable básica con un valor de 2.650

Si nos preguntamos: Cual es la variable que al aumentar hace que Z disminuya más, la respuesta es X31 (Tiene el coeficiente más negativo), luego es la mejor candidata para ser la variable que entra ya que por cada unidad que aumente, los costos totales del transporte se disminuyen en 2 unidades monetarias.

Nota: Éste proceso es muy dispendioso!! y por lo tanto vamos a considerar otro.

Método de tanteo:

Partiendo de la solución básica factible obtenida mediante el método de Vogel.

Conclusión: Mediante éste método podemos analizar todos los efectos, de considerar enviar una unidad desde las fábricas a los distribuidores, en las casillas de las variables no-básicas (Xij = 0) , para observar si existen variables no-básicas que al entrar a la base, hagan que Z disminuya; Por supuesto, los resultados coincidirán con los coeficientes de la función objetiva lograda mediante el método algebraico.

Conclusión: El presente método es muy dispendioso, aunque un poco menos que el método algebraico; Si se efectúa en su totalidad, el resultado es:

Ahora se describe un método más practico para encontrar éste último tablero en donde podemos escoger la variable que entra de forma rápida. Primero se muestra la deducción matemática del método y después su aplicación práctica. El procedimiento recibe el nombre del Método Modificado de distribución (Modi), ya que lleva a escoger la variable que entra, la variable que sale y la nueva solución mejorada en donde Z disminuye su valor.

Método Modificado de distribución (Modi)

Variable que entra

El problema original es:

Partiendo de la solución básica factible encontrada por el método de vogel, aplicamos el método de modi, para averiguar cual es la variable no básica que debe entrar y cual la variable básica que debe salir. para ello efectuamos los siguientes pasos:

1. Construimos una tabla de costos para las variables básicas y en ella calculamos los u_i y los v_j que cumplan C_ij – u_i – v_j = 0

2. Construimos una tabla de costos ó coeficientes en la función objetiva para las variables no básicas cuyo valor es C_ij – u_i – v_j

Fíjese que en ésta última tabla, están todos los coeficientes de las variables no básicas en la función objetiva, después de haber sumado múltiplos de las restricciones a la función objetivo para eliminar las variables básicas. La nueva función objetivo es:

La variable que al crecer hace que Z disminuya más es X₃₁ , luego escogemos ésta variable para entrar a la base.

Observe que en la tabla de costos para las variables no básicas se encuentran los valores en que aumenta ó disminuye Z por cada unidad de crecimiento de las variables no básicas.

Identificada la variable para entrar (X₃₁), debemos determinar la variable para salir, que debe ser aquella que primero se vuelva cero (0) a medida que la variable que entra crezca. para ello, construimos un circuito cerrado de (+) y (-), empezando, sumando en la casilla de la variable que entra X₃₁. Observe que el circuito de (+) y (-) tiene como objetivo preservar la suma de las filas y de las columnas, esto es, seguir satisfaciendo la oferta y la demanda, conservando la factibilidad del problema.

La pregunta aquí es: Ésta es la solución óptima?, la respuesta la conoceremos cuando calculemos la nueva tabla de costos para las variables no básicas.

Solución óptima

Total de unidades enviadas 170, a un costo total de $2.590

Observe que el distribuidor 4 se quedará sin sus 40 unidades y que el distribuidor 5 sin sus 10 unidades, en total quedará una demanda insatisfecha de 50 unidades (Información que conocimos desde el principio), lo relevante aquí, es que ahora sabemos a quién no enviarle las 50 unidades que no tienen los distribuidores y que podemos tomar decisiones administrativas referentes a la demanda no cubierta, tales como:

1. Conseguir las 50 unidades a través de la competencia agremiada, como consecuencia de acuerdos previamente establecidos.

2. Acordar con el distribuidor 4 y 5 cubrir dicha demanda en el periodo de producción siguiente.

3. Otras decisiones podrán ser tomadas en concordancia con la situación real.

 

Problema de transporte con costos de producción

Una compañía tiene 4 fábricas (F₁ , F₂ , F₃ , F₄), que envían su producción a 4 almacenes (A₁ , A₂ , A₃ , A₄). Los costos y capacidades de producción, en cada una de las 4 fábricas son:

Simplificando la función objetivo, queda así:

Número de variables básicas: m + n – 1 = 4 + 5 – 1 = 8

Partiendo de ésta solución básica factible no degenerada encontrada por el método de aproximación de vogel, aplicamos el método de modi, para efectuar las iteraciones y encontrar la solución óptima.

EL PROBLEMA DEL TRANSBORDO 

Igualamos la oferta y la demanda mediante la creación de una planta de producción ficticia.

De acuerdo a la matriz de costos y al gráfico presentado en el problema 6 del capítulo de formulación, las unidades deberán ser despachadas así:

Desde la planta de producción P₁ , enviar 20 monitores de alta resolución al centro de ventas V₂ , a través del centro de control de calidad C₁.

Desde la planta de producción P₁, enviar 60 unidades al centro de ventas V₃, a través del centro de control de calidad C₂.

Desde la planta de producción P₂, enviar 60 unidades al centro de ventas V₃, a través del centro de control de calidad C₂ .

Sistema Operativo de Producción

Este problema corresponde al enunciado del problema número 14 del capítulo de formulación. Allí se resolvió mediante el método simplex; Aquí construimos una tabla de costos, disponibilidades y requerimientos.

Xij = Unidades a fabricar mediante la fuerza de trabajo regular en el trimestre i-ésimo (i=1,2,3,4), para atender la demanda del trimestre j-ésimo (j=1,2,3,4).

Hij = Unidades a fabricar mediante la fuerza de trabajo en horas extras en el trimestre i-ésimo (i=1,2,3,4), para atender la demanda del trimestre j-ésimo (j=1,2,3,4)

Mij = Unidades a fabricar mediante la fuerza de trabajo subcontratada en el trimestre i-ésimo (i=1,2,3,4), para atender la demanda del trimestre j-ésimo (j=1,2,3,4)

Siendo j = i, … ,n ; Ya no es lógico producir unidades para atender demandas pasadas.

En la parte superior derecha de cada casilla aparece el costo unitario por unidad producida, es así como una unidad producida mediante la fuerza de trabajo regular, para suplir la demanda del segundo trimestre, tiene un costo de $53, distribuidos así: $50 de producción más $3 de inventario.

Empezamos por la esquina noroeste y asignamos lo máximo posible para atender la demanda de 50.000 unidades, produciendo lo máximo posible en tiempo normal, cubrimos la demanda.

Nos movemos a la fila del segundo trimestre con producción en tiempo normal y asignamos lo máximo posible (50.000), haciéndose necesario producir lo máximo posible en horas extras, (50.000) y en trabajo suplementario (40.000), para un total de 140.000 unidades a producir, quedando sin cubrir la demanda de 10.000 unidades, ya que la totalidad de la demanda para el segundo trimestre es de 150.000 unidades. Lo anterior obliga a recurrir a unidades (lo más baratas posibles) producidas en el trimestre inmediatamente anterior, luego asignamos 10.000 unidades a producir en el primer trimestre en tiempo extra para cubrir la demanda del segundo trimestre; Este movimiento se muestra en la tabla parcial siguiente:

Completando la tabla, los datos aparecen así:

En la última columna queda diseñado el plan de producción por tipo de fuerza de trabajo y por trimestre; En la última fila se muestran los costos de las unidades producidas por trimestre. Los inventarios trimestrales se observan sobre cada columna, anteriores al trimestre observado y ellos son: 70.000 y 60.000 unidades para los semestres 2 y 3 respectivamente, todas unidades producidas durante el primer semestre.

Fuente: FRANCISCO ALFONSO CHEDIAK PINZON, “Investigación de Operaciones I Volumen I”. Colombia. 2002. Edidorial León Editores.