1-Definición del modelo de transporte. Planteo mediante PL PDF

Preview

Summary

Download 1-Definición del modelo de transporte. Planteo mediante PL PDF

Description

1) DEFINICIÓN DEL MODELO DE TRANSPORTE. PLANTEO MEDIANTE PL Definición del modelo de transporte Los problemas de transporte son una clase especial de problemas de programación lineal (PL). Un problema de transporte surge en la planeación de distribución de productos desde varios sitios de oferta (llamados “fuentes” u “orígenes”) hacia varios sitios de demanda (llamados “destinos”). Conociendo las cantidades ofrecidas por cada fuente y la cantidad demandada por cada destino, el objetivo de un problema de transporte es determinar un plan de transporte que minimice el costo de envío de la mercadería desde cada origen hasta cada destino. Notación y características del modelo 1) 2) 3) 4)

El problema se representa en forma de red. Hay m orígenes y n destinos. Cada origen y cada destino se representan con un nodo. Las rutas que unen los orígenes con los destinos se representan con arcos. El flujo de la red va desde los

orígenes hasta los destinos, y su dirección se indica mediante flechas. 5) El arco (i, j) que une el origen i con el destino j proporciona dos informaciones:  

el costo de transporte por unidad: cij la cantidad transportada: xij

6) La cantidad de la oferta en el origen i es a, y la cantidad de la demanda en el destino j es bj 7) Un destino puede cubrir su demanda desde una o más fuentes. 8) Una fuente puede enviar la mercadería que ofrece a uno o más destinos. 9) El objetivo del modelo es determinar un plan de transporte de la mercadería desde las fuentes hasta los destinos, de modo tal que minimice el costo total, al mismo tiempo que se satisfacen las restricciones de la oferta y la demanda. 10) Un supuesto importante en este modelo es que el costo es directamente proporcional a la cantidad de unidades transportadas. 11) Los datos del modelo son: cij ; ai ; bj 12) Las incógnitas del modelo son: xij 13) El modelo de transporte se utiliza en otras áreas como por ejemplo el control de inventarios y la asignación de personal, entre otras.

Representación del modelo de transporte Como dijimos, el modelo se representa en forma de red, con nodos y arcos, de la siguiente manera:

Apliquemos esta representación a un problema concreto. PROBLEMA: La Central es una empresa que fabrica y comercializa productos de limpieza. Tiene tres fábricas en la provincia de Córdoba: una en la zona norte, otra en la zona sur y la tercera en la zona este. La Central abastece, en estos momentos, a dos supermercados: A y B. La capacidad de producción de una determinada línea y tipo de producto, para el próximo trimestre, son: 3000, 4000 y 3500 unidades, respectivamente, según zonas N, S y E. Las demandas para el próximo trimestre de los supermercados A y B son, respectivamente, 4000 y 6500 productos.

La Tabla 1 muestra los costos de envío por cada producto, desde cada fábrica hasta cada supermercado. Tabla 1: Costos de envío por artculo, problema La Central

A

B

Norte

15

25

Sur

30

20

Este

18

40

La empresa desea confeccionar un plan de envíos de modo tal que el costo total sea el mínimo. Representación del problema En esta lectura solo queremos abordar la representación gráfica del problema mediante una red y su planteo como modelo de programación lineal. La resolución de este se abordará en lecturas posteriores. El planteo en forma de red es el siguiente:

Observa que los costos unitarios por ruta están sobre cada flecha. A la izquierda de cada nodo origen, se muestran las cantidades ofrecidas por ese centro; y a la derecha de cada nodo destino, las cantidades demandadas por cada supermercado. Planteo del problema mediante PL Variables de decisión La empresa tiene que realizar un plan de envíos desde los orígenes hasta los destinos al mínimo costo. Las variables que influyen directamente en los costos y que proporcionan dicho plan son las xij, que unen cada origen i con cada destino j, siendo la variable x la cantidad de unidades de mercadería que se deben enviar en esa ruta. Las unidades de mercadería pueden darse en cajas, en bolsas, o bien, como en este caso, en unidades del producto. Y son las siguientes: x₁₁;x₁₂;x₂₁;x₂₂;x₃₁;x₃₂. Por lo que se trata, entonces, de calcular cuántas unidades del producto deben enviarse de la sucursal Norte al supermercado A (ruta 1-1), cuántas de la sucursal Norte al supermercado B (ruta 1-2), cuántas de la sucursal Sur al supermercado A (ruta 2-1)…, y así hasta completar todos las posibles rutas: cada origen a todos los destinos; en este caso, por cada origen hay dos destinos. Como observarás, en este problema hay tres orígenes que deben satisfacer la demanda de dos destinos, por lo que la cantidad de variables básicas es: 3 x 2 = 6. En general, si tenemos m orígenes y n destinos, tenemos m x n rutas posibles y, por lo tanto, m x n variables de decisión. Función objetivo El objetivo del problema es hacer mínimo el costo total de transporte. El costo de transporte en una ruta es el valor que surge de multiplicar el costo unitario de transporte (“cij”) por la cantidad transportada en esa ruta (“xij”). Por lo tanto: en la ruta 1-1: costo = c₁₁. x₁₁ = 15. x₁₁, ya que el costo unitario en esta ruta es dato. Y así con las demás rutas, teniendo en cuenta los valores de los costos por producto de la Tabla 1 y sumando luego todos los costos de cada ruta, llegamos a nuestra función objetivo a minimizar:

Para nuestro problema, la función objetivo es: Minimizar: z = c₁₁ x x₁₁ + c₁₂ x x₁₂ + c₂₁ x x₂₁ + c₂₂ x x₂₂ + c₃₁ x x₃₁ + c₃₂ x x₃₂ Es decir: z = 15x₁₁ + 25x₁₂ + 30x₂₁ + 20x₂₂ + 18x₃₁ + 40x₃₂ Restricciones Sabemos que la minimización del costo total está sujeta a las cantidades ofrecidas en cada fuente y a las cantidades demandas por cada destino. Por lo tanto, tenemos tres conjuntos de restricciones: 

Un conjunto de restricciones tiene que ver con la oferta: cada origen no debe enviar más de lo que dispone. Por lo tanto: Es lógico que La suma de los envíos desde un origen o fuente no deba exceder su oferta.

Por lo tanto, en este conjunto hay m restricciones. Para nuestro problema, son tres restricciones: x₁₁ + x₁₂ < = 3000 x₂₁ + x₂₂< = 4000 x₃₁ + x₃₂< = 3500 El segundo conjunto de restricciones tiene que ver con los puntos de demanda: cada punto de demanda debe ser satisfecho. Por lo tanto: La suma de los envíos de las distintas fuentes a un destino debe satisfacer la demanda de ese destino.

Las n restricciones de este conjunto, referidas al problema de La Central, se transforman en dos restricciones, que son: x₁₁ + x₂₁ + x₃₁ > = 4000 x₁₂ + x₂₂ + x₃₂ > = 6500



El tercer conjunto de restricciones son las restricciones de no negatividad, ya que no puede existir una cantidad de productos negativos. Esto lo expresamos de la siguiente manera: xij > = 0 para i = 1, …, m y j = 1, …, n En nuestro problema, significa que las seis variables de decisión no pueden ser negativas: x₁₁, x₂₁, x₃₁, x₁₂, x₂₂, x₃₂ > = 0 Observa que en total, sin tener en cuenta las restricciones de no negatividad, un problema de transporte tiene m + n restricciones. Pero ¡CUIDADO! El número de restricciones suficientes para poder resolver un problema mediante el algoritmo de transporte es de m + n - 1 Como podrás ver, el problema de transporte es un tipo especial de problema de PL. En la próxima lectura ampliaremos este tema y veremos la forma de simplificar los cálculos para su resolución....