PROBLEMA DE TRANSBORDO


El Problema de Transbordo, Intertransporte o Reembarque es una variación del modelo original de transporte que se ajusta a la posibilidad común de transportar unidades mediante nodos fuentes, destinos y transitorios, mientras el modelo tradicional solo permite envíos directos desde nodos fuentes hacia nodos destinos. 

Existe la posibilidad de resolver un modelo de transbordo mediante las técnicas tradicionales de resolución de modelos de transporte y este procedimiento se basa en la preparación del tabulado inicial haciendo uso de artificios conocidos con el nombre de amortiguadores, los cuales deben ser iguales a la sumatoria de las ofertas de los nodos de oferta pura y de coeficiente cero (0) en materia de costos.


Sin embargo la resolución de un problema de transbordo haciendo uso de los algoritmos de resolución de modelos de transporte es una idea anacrónica, teniendo en cuenta la posibilidad de acceso a herramientas de cómputo capaces de resolver problemas complejos una vez modelados mediante las técnicas de programación lineal.

 

La importancia de los modelos de transbordo aumenta con las nuevas tendencias globales de gestión de cadenas de abastecimiento, en las cuales se deben de optimizar los flujos logísticos de productos teniendo en cuenta la importancia de minimizar los costos, asegurar disponibilidad de unidades y reconociendo la importancia de los centros de distribución en la búsqueda del equilibrio entre las proyecciones y la realidad de la demanda.

Problema de Transbordo
www.ingenieriaindustrialonline.com

RESOLUCIÓN DE UN PROBLEMA DE TRANSBORDO MEDIANTE PROGRAMACIÓN LINEAL


Para poder resolver un problema de transbordo mediante programación lineal basta con conocer una nueva familia de restricciones, las llamadas restricciones de balanceo. En un problema de transbordo existen 3 clases de nodos, los nodos de oferta pura, los de demanda pura y los nodos transitorios que posibilitan el transbordo y que deben de balancearse para hacer que el sistema sea viable, es decir, que todas las unidades que ingresen a un nodo sean iguales a las que salgan del mismo (unidades que salen + unidades que conserve el nodo).

EL PROBLEMA

Modelar mediante programación lineal el problema de transbordo esbozado en la siguiente figura (dar click para ampliar).

Problema de Transbordo
TAHA - Investigación de Operaciones

La figura muestra una serie de nodos y sus respectivas rutas mediante las cuales se supone distribuir las unidades de un producto, el número que lleva cada arco (flecha) representa el costo unitario asociado a esa ruta (arco), y las cantidades que se ubican en los nodos iniciales representan la oferta de cada planta, así como las cantidades de los nodos finales representa la demanda de cada distribuidor.

LAS VARIABLES DE DECISIÓN

En este caso como en la mayoría las variables de decisión deben representar la cantidad de unidades enviadas por medio de cada ruta. Es muy aconsejable denotar cada nodo con un número para simplificar la definición nominal de las variables.

Problema de Transbordo

Una vez renombrado cada nodo definiremos las variables:

 

XA,C = Cantidad de unidades enviadas desde P1 hacia T1

XA,D = Cantidad de unidades enviadas desde P1 hacia T2

XB,C = Cantidad de unidades enviadas desde P2 hacia T1

XB,D = Cantidad de unidades enviadas desde P2 hacia T2

XC,D = Cantidad de unidades enviadas desde T1 hacia T2

XC,E = Cantidad de unidades enviadas desde T1 hacia D1

XC,F = Cantidad de unidades enviadas desde T1 hacia D2

XD,F = Cantidad de unidades enviadas desde T2 hacia D2

XD,G = Cantidad de unidades enviadas desde T2 hacia D3

XE,F = Cantidad de unidades enviadas desde D1 hacia D2

XF,G  = Cantidad de unidades enviadas desde D2 hacia D3

RESTRICCIONES

Existen en este modelo 3 tipos de restricciones y están estrechamente relacionadas con los tipos de nodos existentes, para un nodo oferta pura existe la restricción de oferta; para un nodo demanda pura existe la restricción de demanda, y para un nodo transitorio y/o transitorio de demanda existe la restricción de balance. Recordemos que los nodos transitorios son aquellos que tienen rutas (arcos o flechas) de entrad y salida, y si además este presenta un requerimiento de unidades se denomina transitorio de demanda.

 

Restricciones de Oferta:

 

XA,C + XA,D = 1000

XB,C + XB,D = 1200

 

Restricciones de demanda:

 

XD,G + XF,G = 500

 

Restricciones de balanceo para nodos únicamente transitorios:

Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a las unidades que salgan.

 

XA,C + XB,C - XC,D - XC,E - XC,F = 0

XA,D + XB,D + XC,D - XD,F - XD,G = 0

 

Restricciones de balanceo para nodos transitorios con requerimientos:

Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a la sumatoria de las unidades que salen más los requerimientos del nodo (demanda).

 

XC,E - XE,F = 800

XC,F + XD,F + XE,F - XF,G = 900

FUNCIÓN OBJETIVO

En este caso la definición de la función objetivo se limita a la consignación de cada ruta con su respectivo costo bajo el criterio "minimizar".

 

ZMIN = 3XA,C + 4XA,D  + 2XB,C + 5XB,D + 7XC,D + 8XC,E + 6XC,F  + 4XD,F + 9XD,G + 5XE,F + 3XF,G

INGRESANDO EL MODELO A WINQSB

Problema del Transbordo
www.ingenieriaindustrialonline.com

SOLUCIÓN OBTENIDA MEDIANTE WINQSB

Problema del Transbordo
www.ingenieriaindustrialonline.com

Esta es la representación grafica de la solución cuyo costo óptimo es de 20.700 unidades monetarias

Problema del Transbordo
www.ingenieriaindustrialonline.com


RESOLUCIÓN DE UN PROBLEMA DE REDES DE SUMINISTRO


EL PROBLEMA

Este es un problema propuesto en el texto "Investigación de Operaciones de TAHA" que hace referencia a una red de gasoductos en la que los distintos nodos representan estaciones de bombeo y recepción, los costos se encuentran en las rutas de la siguiente figura.

Problema del Transbordo
Investigación de Operaciones - TAHA

VARIABLES DE DECISIÓN

X12 = Cantidad de galones enviados desde la estación 1, hacia la estación 2

X17 = Cantidad de galones enviados desde la estación 1, hacia la estación 7

X37 = Cantidad de galones enviados desde la estación 3, hacia la estación 7

X34 = Cantidad de galones enviados desde la estación 3, hacia la estación 4

X72 = Cantidad de galones enviados desde la estación 7, hacia la estación 2

X75 = Cantidad de galones enviados desde la estación 7, hacia la estación 5

X57 = Cantidad de galones enviados desde la estación 5, hacia la estación 7

X62 = Cantidad de galones enviados desde la estación 6, hacia la estación 2

X65 = Cantidad de galones enviados desde la estación 6, hacia la estación 5

X56 = Cantidad de galones enviados desde la estación 5, hacia la estación 6

X54 = Cantidad de galones enviados desde la estación 5, hacia la estación 4

 

RESTRICCIONES

      Restricciones de oferta y demanda:

 

X12 + X17 = 50000

X37 + X34 = 60000

X12 + X72 + X62 = 90000

X34 + X54 =20000

 

Restricciones de balance

 

X17 + X37 + X57 - X72 - X75 = 0

X56 - X65 - X62 = 0

X75 + X65 - X56 - X54 = 0

FUNCIÓN OBJETIVO

      ZMIN = 20X12 + 3X17 + 9X37 + 30X34 + 40X72 + 10X75 + 10X57 + 8X62 + 4X65 + 4X56 + 2X54

 

INGRESANDO EL MODELO A WINQSB

Problema del Transbordo
www.ingenieriaindustrialonline.com

SOLUCIÓN OBTENIDA MEDIANTE WINQSB

Problema del Transbordo
www.ingenieriaindustrialonline.com

Esta es la representación grafica de la solución cuyo costo óptimo es de 2'660.000 unidades monetarias

Problema del Transbordo
www.ingenieriaindustrialonline.com

PROBLEMA DE LA RUTA MÁS CORTA


Ya el nombre de este tipo de problemas es bastante sugestivo, se trata si es necesario decirlo de una modalidad de problemas de redes en el cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total que una un nodo fuente con un nodo destino, sin importar el número de nodos que existan entre estos.

 

Esta modalidad de problemas puede solucionarse como un modelo de transbordo normal, sin embargo la principal sugerencia es la de establecer una oferta en el nodo fuente igual a una unidad (1) y establecer una demanda en el arco destino igual a una unidad (1).

EL PROBLEMA

Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para llegar a dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace indispensable hallar la ruta de acceso al nodo 9 más corta. Las distancias entre nodos de la mina se encuentran en la siguiente gráfica dadas en cientos de metros. Formule un modelo de transbordo y resuelva mediante cualquier paquete de herramientas de investigación operativa que permita establecer la ruta más corta para poder así auxiliar al minero.

La ruta más Corta
www.ingenieriaindustrialonline.com

VARIABLES DE DECISIÓN

El nombre de las variables en este caso poco importa, dado que de ser escogida para la solución básica eso significa simplemente que será empleada como ruta para ir a rescatar al minero, sin embargo nada tiene de malo el que se le pueda asociar con el envío de unidades desde la entrada de la mina hacia el minero, por ende puede sugerirse este como nombre de las variables. "Cantidad de unidades enviadas desde el nodo i hacia el nodo j".

 

X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2

X13 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3

X23 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3

X24 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4

X32 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2

X34 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4

X35 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5

X46 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6

X47 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7

X54 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4

X56 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 6

X57 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 7

X58 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 8

X67 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 7

X69 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 9

X76 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 6

X78 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 8

X79 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 9

X87 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 7

X89 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 9

 

RESTRICCIONES

Restricciones de Oferta y Demanda

 

Hay que recordar que el objetivo de este modelo es la consecución de un plan de ruta que nos permita encontrar al minero lo más pronto posible al recorrer la distancia mínima posible, por ende la clave para plantear el modelo como si fuese de transbordo es establecer una demanda y oferta igual a la unidad (1).

 

X12 + X13 = 1

X69 + X79 + X89 = 1

 

Restricciones de Balance

 

X12 + X32 - X23 - X24 = 0

X13 + X23 - X32 - X34 - X35 = 0

X24 + X34 + X54 - X46 - X47 = 0

X35 - X54 - X56 – X57 – X58 = 0

X46 + X56 + X57 - X67 – X69 = 0

X67 + X47 + X57 + X87 – X76 – X78 – X79 = 0

X78 + X58 – X89 = 0

 

En palabras sencillas: "Todo lo que entra a cada nodo es igual a lo que sale de él"

FUNCIÓN OBJETIVO

ZMIN = 4X12 + 2X13 + 2X23 + 7X24 + 4X32 + 9X34 + 6X35 + 1X46 + 5X47 + 2X54 + 4X56 + 3X57 + 2X58 + 1X67 + 5X69 + 4X76 + 3X78 + 5X79 + 2X87 + 7X89

INGRESANDO LOS DATOS A WINQSB

La ruta más corta
www.ingenieriaindustrialonline.com

SOLUCIÓN OBTENIDA MEDIANTE WINQSB

La ruta más corta
www.ingenieriaindustrialonline.com

La ruta más corta para rescatar al minero  tiene como distancia total 1600 metros (dado que las distancias estaban dadas en cientos de metros) y es tal como se muestra en la siguiente gráfica.

La ruta más corta
www.ingenieriaindustrialonline.com

Sin embargo WinQSB cuenta con una metodología mucho más sencilla de resolución de algoritmos de ruta más corta, metodología que explicaremos más adelante, de todas formas hemos encontrado como aplicando debidamente la razón y un algoritmo conocido como el de transbordo podemos solucionar problemas distintos en teoría.