• Author / Uploaded
• kenn berrios

Citation preview

UNIVERSIDAD DE ORIENTE FACULTAD DE INGENIERIA Y ARQUITECTURA OPERACIONES DE DECISION Tema de investigación: El Problema de Transbordo Catedrática: Ing. Yesenia Marisol Valle Benítez Estudiantes: Berrios Manzanares Kevyn Francisco Bonilla Catacho Kevin Wilfredo Hernández Lovo José Fabricio Portillo Orellana Bernardo Ismael Romero Álvarez Walter Mauricio

CICLO II/2019

UNIVO, 27 DE NOVIEMBRE DE 2019

Índice Introducción ............................................................................................................... 1 1. Objetivos................................................................................................................ 2 1.1 Objetivo General .............................................................................................. 2 1.2 Objetivos Específicos....................................................................................... 2 2. Marco Teórico ....................................................................................................... 3 2.1 Método de VOGEL........................................................................................... 3 Algoritmo de VOGEL .......................................................................................... 3 2.2 Por medio de la esquina NOROESTE ............................................................. 5 2.3 Por medio de costos mínimos ......................................................................... 7 2.4. El problema del transbordo ............................................................................. 8 2.4.1 Ejemplo para el problema de transbordo ................................................ 10 2.5 El problema de asignación ............................................................................ 16 3. Conclusión ........................................................................................................... 19 Bibliografía............................................................................................................... 20

Introducción El problema de transporte consiste en determinar un sistema de rutas, las cuáles partirán de uno o más depósitos, los cuales deberán de satisfacer la demanda de varios clientes. La finalidad, es el de entregar la demanda de dichos clientes, minimizando el costo total involucrado en las rutas. Este tipo de problemas aparece de forma natural en las áreas de transporte, el cual es de esperarse que implique un costo sobre el producto que se está distribuyendo, de ahí que una buena planeación de distribución puede resultar en la disminución de dichos costos de transporte. En el presente trabajo se estarán desarrollando métodos enfocados en la resolución de problemas de esta naturaleza (de transporte), profundizando en el modelo de transbordo, el cual es una variación del modelo tradicional de transporte, dicho método posee la particularidad de estratificar o clasificar los nodos en: nodos fuentes, nodos intermediarios y nodos destinos, lo que hace más flexible dicho modelo.

1

1. Objetivos 1.1 Objetivo General •

Demostrar la solución de un problema de transbordo mediante el diseño de un modelo de programación lineal para optimizar el proceso de distribución de mercadería, seleccionando la ruta óptima que disminuyan los costos de transporte.

1.2 Objetivos Específicos •

Definir el algoritmo de solución del modelo de transbordo.

•

Interpretar y dar a conocer los diferentes casos de aplicación del modelo de transporte.

•

Determinar la asignación de suministros en cada una de las rutas de distribución.

•

Lograr minimizar los costos que genera la red de distribución establecida.

2

2. Marco Teórico 2.1 Método de VOGEL Es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo, produce mejores resultados iniciales que los mismos.

Algoritmo de VOGEL El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método. •

Paso 1. Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.

•

Paso 2. Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

•

Paso 3. De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).

3

•

Paso 4: de ciclo y excepciones. Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse. Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse. Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse. Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.

4

2.2 Por medio de la esquina NOROESTE Origen: 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. Aplicación: una vez elaborados los productos es necesario definir los lugares y las cantidades de estos a enviar a las diferentes plazas, en términos de los menores costos. De esta manera proponer soluciones óptimas y factibles en las empresas, que las hacen ser más competitivas para la permanencia en el mercado. 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. 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).

Tabla 1. Resolución de la esquina noroeste.

5

•

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".

6

2.3 Por medio de costos mínimos El método del costo mínimo o método de los mínimos costos es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos. El diagrama de flujo de este algoritmo es mucho más sencillo que los anteriores, dado que se trata simplemente de la asignación de la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz hasta finalizar el método.

Algoritmo del costo mínimo. •

Paso 1. De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades posible, 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".

7

2.4. El problema del 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 Ilustración 1. Problema de transbordo.

la

búsqueda

del

equilibrio

entre

las

proyecciones y la realidad de la demanda. En el modelo de transbordo se reconoce que puede ser más económico el transporte pasando por nodos intermedios o transitorios antes de llegar al destino final. Este concepto es más general que el del modelo normal de transporte, en el que sólo se permiten envíos directos entre una fuente y un destino. En esta sección se explica cómo se puede convertir y resolver un modelo de transbordo en un modelo de transporte normal, usando la idea de un amortiguador. 8

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).

9

2.4.1 Ejemplo para el problema de transbordo Dos fábricas de automóviles, P1 y P2, se enlazan con tres agencias, D1, D2 y D3, a través de dos centros de distribución, T1 y T2, de acuerdo con la red de la figura a continuación. Las cantidades de oferta en las plantas P1 y P2 son 1000 y 1200 autos, y las cantidades de demanda en las agencias D1, D2 y D3 son 800, 900 y 500 autos. El costo de transporte por vehículo, en cientos de $ entre pares de nudos se ve en los enlaces (o arcos) de la red. En la red de la figura que se presentara a continuación hay transbordos porque toda la oferta de 2200 (= 1000 + 1200) autos de los nodos P1 y P2 podría pasar en principio por cualquier nodo de la red, antes de llegar a su destino en los nodos D1, D2 y D3.

Ilustración 2. Red de transporte.

A este respecto, los nodos de la red que tienen arcos de entrada y salida al mismo tiempo (T1, T2, D1 y D2) funcionan como fuentes y destinos al mismo tiempo, y se llaman nodos de transbordo. Los nodos restantes pueden ser nodos de oferta pura (P1 y P2) o nodos de demanda pura (D3). El modelo de transbordo se puede transformar en un modelo normal de transporte con 6 fuentes (P1, P2, T1, T2, D1 y D2) y cinco destinos (T1, T2, D1, D2 y D3). Las cantidades de oferta y demanda en los distintos nodos se calculan como sigue: Oferta en un nodo de oferta pura = Suministro original Demanda en un nodo de demanda pura = Demanda original 10

Oferta en un nodo de transbordo = Oferta original + Amortiguador Demanda en un nodo de demanda pura = Demanda original + Amortiguador La cantidad amortiguadora debe ser lo suficientemente grande como para permitir que toda la oferta (o demanda) original pase por cualquiera de los nodos de transbordo. Sea B la cantidad deseada de amortiguador. Entonces B = Oferta (o demanda) total = 1000 + 1200 (u 800 + 900 + 500) = 2200 autos La ilustración 2 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.

Ilustración 3. Red de transporte.

11

Una vez renombrado cada nodo definiremos las variables. XAC = Cantidad de unidades enviadas desde Pl hacia Tl XA, D = Cantidad de unidades enviadas desde Pl hacia T2 XB, C = Cantidad de unidades enviadas desde P2 hacia Tl XB, D = Cantidad de unidades enviadas desde P2 hacia T2 XC, D = Cantidad de unidades enviadas desde Tl hacia T2 XC, E = Cantidad de unidades enviadas desde Tl hacia Dl XC, F = Cantidad de unidades enviadas desde Tl 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 Dl hacia D2 XF, G = Cantidad de unidades enviadas desde D2 hacia D3

12

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 entrada 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

13

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 criterio "minimizar". Min Z = 3XA, C+ 4XA, D + 2XB, C + 5XB, D + 7XC, D + 8XC, E + 6XC, F + 4XD, F +9XD, G + 5XE, F + 3XF, G Este planteamiento matemático fue resuelto mediante una herramienta online “PHPSimplex” obteniendo como resultado un costo óptimo de $20,700 dado que los costos de transporte están dados en cientos de dólares el costo real es: $2,070,000.

Ilustración 4. Red de transporte.

El algoritmo de transporte se basa en la hipótesis que el modelo está balanceado, y eso quiere decir que la demanda total es igual a la oferta total. Si el modelo está desbalanceado siempre se podrá aumentar con una fuente o un destino ficticios para restaurar el equilibrio o balance.

14

Cuando la demanda es mayor que la oferta se agrega una fuente (planta) ficticia con la capacidad para completar la demanda exigida de esta firma balancear el modelo de transporte. En este caso, el costo de transporte por unidad, desde la planta ficticia a los dos destinos es cero, porque no existe esa fábrica. El costo de transporte por unidad desde la fuente ficticia a los destinos puede asumir también valores positivos. Por ejemplo, para asegurar que el nodo receptor (demanda pura) recibe toda su demanda, se asignará un costo (penalización) alto de transporte por unidad al elemento cero, desde la fuente ficticia creada. También podemos demostrar el caso en el que la oferta es mayor que la demanda, suponiendo que la sumatoria de los nodos de demanda pura es inferior a la sumatoria de los nodos de oferta pura. En este caso se debe agregar un centro de distribución ficticio que “reciba” el exceso de oferta. También, los costos unitarios de transporte al centro ficticio de distribución son cero, a menos que se deseen imponer otras condiciones. Por ejemplo, se puede pedir que una fábrica “mande todo” asignando un costo unitario de transporte (muy) alto, desde la fábrica indicada hasta el destino ficticio.

15

2.5 El problema de asignación Muchas de las situaciones exigen una respuesta, sea si o no. Así es como podemos representar estas dos posibilidades con los valores de 0(no) y 1(si). Y aprovechar las matemáticas para que nos ayuden ante estas decisiones difíciles, a lo que llamamos Programación Lineal.

El Problema de asignación consisten en asignar recursos a determinadas tareas en función de un objetivo ligado a la eficiencia de un sistema. Un ejemplo típico es la asignación de operarios a manejar una serie de máquinas.

Para que se ajuste a la definición de un problema de asignación, es necesario que este tipo de aplicaciones se formule de manera tal que se cumplan los siguientes supuestos.

1. El número de asignados es igual al número de tareas. (Este número se denota por n. 2. A cada asignado se le asigna sólo una tarea. 3. Cada tarea debe realizarla sólo un asignado. 4. Existe un costo ci j asociado con el asignado i (i = 1, 2, n) que realiza la tarea j (j = 1, 2, n). 5. El objetivo es determinar cómo deben hacerse las n asignaciones para minimizar los costos totales. Cualquier problema que satisface todos estos supuestos se puede resolver en forma muy eficiente mediante los algoritmos diseñados de manera especial para los problemas de asignación. Los primeros tres supuestos son bastantes restrictivos. Muchas aplicaciones potenciales no las satisfacen por completo. Con frecuencia es posible reformular el problema para hacerlo que se ajuste.

16

Modelo del problema de asignación. El modelo matemático para manejar el problema de asignación utiliza las siguientes variables de decisión:

𝑥𝑖𝑗 = {

1, 0,

𝑠𝑖 𝑠𝑒 𝑎𝑠𝑖𝑔𝑛𝑎 𝑖 𝑝𝑎𝑟𝑎 𝑟𝑒𝑎𝑙𝑖𝑧𝑎𝑟 𝑙𝑎 𝑡𝑎𝑟𝑒𝑎 𝑗, 𝑠𝑖 𝑛𝑜 𝑒𝑠 𝑎𝑠𝑖,

para 𝑖 = 1,2, …, 𝑛 y 𝑗 = 1, 2, …, 𝑛. Entonces, cada 𝑥𝑖𝑗 es una variable binaria (toma valores 0 o 1). Las variables binarias son importantes en investigación de operaciones para representar las decisiones de si o no. Si Z es el costo total, el modelo del problema de asignación es: Minimizar 𝑛

𝑍=∑ 𝑖=1

𝑛

∑ 𝑐𝑖𝑗 𝑥𝑖𝑗 , 𝑗=1

Sujeta a: 𝑛

∑ 𝑥𝑖𝑗 = 1

𝑝𝑎𝑟𝑎 𝑖 = 1,2, … , 𝑛,

𝑗=1 𝑛

∑ 𝑥𝑖𝑗 = 1

𝑝𝑎𝑟𝑎 𝑗 = 1,2, … , 𝑛,

𝑖=1

y 𝑥𝑖𝑗 ≥ 0, (𝑥𝑖𝑗 𝑏𝑖𝑛𝑎𝑟𝑖𝑎,

𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑎 𝑖 𝑦 𝑗 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑎 𝑖 𝑦 𝑗).

El primer conjunto de restricciones funcionales especifica que cada asignado realice sólo una asignación, mientras que el segundo conjunto requiere que cada asignación sea realizada sólo por un asignado. Si se elimina la restricción entre paréntesis de 𝑥𝑖𝑗 sean binarias, resulta claro que el modelo es un tipo especial de problema de programación lineal, por lo que se puede resolver de inmediato. 17

Otro modelo por el cual se puede resolver un problema de asignación es el método Húngaro. El método húngaro es un método de optimización de problemas de asignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes Konig y Jeno Egerváry dos matemáticos húngaros. Algoritmo Húngaro. Paso 1. Antes que nada, cabe recordar que el método húngaro trabaja en una matriz de costos n*m (el número de filas es igual al número de columnas n=m). Paso 2. Una vez se cumple el procedimiento anterior se debe construir una nueva matriz n*m, en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor mínimo de la fila a la cual cada costo corresponde (valor mínimo hallado en el primer paso). Paso 3. Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos ahora a las columnas, es decir, se halla el valor mínimo de cada columna, con la diferencia que este se halla de la matriz resultante en el segundo paso. Paso 4. A continuación se deben de trazar líneas horizontales o verticales o ambas (únicamente de esos tipos con el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el menor número de líneas posibles. Paso 5. Este paso consiste en encontrar el menor elemento de aquellos valores que no se encuentran cubiertos por las líneas del paso 4, ahora se restara del restante de elementos que no se encuentran cubiertos por las líneas.

18

3. Conclusión Actualmente el objetivo de todas las empresas es la alta movilidad entre países, es decir, la globalización de los mercados y el desarrollo de nuevas tecnologías sumados a las respuestas efectivas de aquellas empresas que buscan el crecimiento en el exterior asegurando el desarrollo del comercio internacional, esto conlleva a la dificultad de los procesos de distribución del producto de forma eficiente y a tiempo. Dado este problema se ha establecido el modelo de transporte y sus variantes que han satisfecho la necesidad de otorgar una solución óptima a las diferentes redes de distribución de las empresas, mediante los diferentes casos de aplicación del modelo de transbordo, son clase especial de programación lineal que tiene que ver con transportar un artículo desde sus fuentes (es decir, fábricas) en algunos casos pasando por nodos u almacenes transitorios hasta llegar a su destino final. Mediante estos algoritmos algebraicos podemos determinar la ruta de distribución que conlleven a un costo mínimo del total del transporte y que al mismo tiempo satisfaga los límites de la oferta y la demanda. En el modelo se supone que el costo de transporte es proporcional a la cantidad de unidades transportadas en determinada ruta. En general, se puede ampliar el modelo de transporte a otras áreas de operación, entre otras el control de inventarios, programación de empleos y asignación de personal.

19

Bibliografía

• Hillier, F. S., & Libierman, G. J. (s.f.). INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES. México, D.F.: McGRAW-HILL. •

ingenieriaindustrialonline. (s.f.). ingenieriaindustrialonline. Obtenido de ingenieriaindustrialonline: https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingenieroindustrial/investigación-de-operaciones/problema-de-transbordo/

•

Iris Abril Martínez Salazar, G. V. (2014). INVESTIGACIÓN OPERACIONES. México D.F.: Grupo Editorial Patria S.A. de C.V.

•

Taha, H. A. (2004). INVESTIGACIÓN DE OPERACIONES. México, D.F.: Pearson educación.

DE

20