Problema de transporte

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Un problema de transporte[1] es, en matemáticas y economía, un caso particular de problema de programación lineal en el cual se debe minimizar el coste del abastecimiento a una serie de puntos de demanda a partir de un grupo puntos de oferta —posiblemente de distinto número—, teniendo en cuenta los distintos precios de envío de cada punto de oferta a cada punto de demanda.

Planteamiento[editar]

Se disponen n \in \mathbb{N} puntos de oferta o factorías con una producción determinada (representada mediante un vector, F) y m \in \mathbb{N} puntos de demanda o mercados de demanda determinada (vector M):

F \in \mathbb{R}^n;\; F = (F_1, F_2, F_3, \cdots, F_n)
M \in \mathbb{R}^m;\; M = (M_1, M_2, M_3, \cdots, M_m)

Además se dispone como dato de una matriz de precios, C, de forma que C_{i j} es el precio de envío por unidad desde la factoría F_i al mercado M_j:

C \in \mathcal{M}_{n \times m}(\mathbb{R})

El objetivo es calcular una nueva matriz, X, de forma que X_{i j} sea el número de unidades que se envían de la factoría F_i al mercado M_j.

X \in \mathcal{M}_{n \times m}(\mathbb{R})

Con estos datos podemos formular las condiciones que se han de cumplir:

\sum_{i = 1}^{n} X_{i j} \geq M_j \;\; \forall j \in \mathbb{N} / 1 \leq j \leq m
\sum_{j = 1}^{m} X_{i j} \leq F_i \;\; \forall i \in \mathbb{N} / 1 \leq i \leq n
X_{i j} \geq 0 \;\; (i, j \in \mathbb{N}; 1 \leq i \leq n; 1 \leq j \leq m)

El precio total a pagar por el transporte, C_T, que se ha de minimizar, se determinará por la suma de los productos del precio de cada unidad por el coste de envío por unidad de cada fábrica a cada mercado:

C_T = \sum_{i = 1}^{n} \sum_{j = 1}^{m} X_{i j} \cdot C_{i j}
\min \; C_T

Problemas equilibrados[2] [editar]

Se dice que el problema está equilibrado cuando se cumple que:

\sum_{i = 1}^{n} F_i = \sum_{j = 1}^{m} M_j

(o, abreviadamente, \sum F = \sum M, es decir, la oferta total es igual a la demanda total).

En caso de que \sum F > \sum M (Oferta total sea mayor a la demanda total) se incorporaría un centro de consumo adicional al problema, el centro de consumo artificial, M_a, de forma que su demanda sea el excedente ( M_a = \sum F - \sum M) y el coste de envío a este mercado sea nulo:

C_{i a} = 0 \;\; \forall i \in \mathbb{N} / 1 \leq i \leq n.

En caso de que \sum F < \sum M (Demanda total mayor a la oferta total) se incorporaría una factoría adicional al problema, la factoría artificial, M_b, de forma que su oferta sea el excedente (M_b = \sum M - \sum F ) y el coste de envío de esta factoría sea nulo:

C_{b j} = 0 \;\; \forall j \in \mathbb{N} / 1 \leq j\leq m.

Representación Gráfica del Problema de Transporte[editar]

Se muestra la presentación gráfica del problema de transporte donde:

Problema de Transporte
Representación Gráfica del Problema de Transporte
  • Nodos: Factorías y Mercados. A cada nodo se le asocia una restricción con su oferta Fi y demanda Mj.
  • Arcos: Ruta a seguir para transportar las mercancías. A cada arco se le asocia una variable de decisión X_{i,j}.

Tabla de Transporte[editar]

La estructura del problema de transporte permite una representación compacta del problema utilizando el formato de tabla de transporte como se muestra a continuación.[3]

Mercado 1 Mercado 2 Mercado j Mercado m
Factoría 1 costo(1, 1) costo(1, 2) ... costo (1, j) ... costo(1, m) Oferta 1 (F_1)
Factoría 2 costo(2,1) costo(2,2) ... costo (2, j) ... costo(2, m) Oferta 2 (F_2)
... ... ... ... ... ... ... ...
Factoría i costo (i,1) costo (i,2) ... costo(i,j) ... costo(i,m) Oferta i (F_i)
... ... ... ... ... ... ... ...
Factoría n costo(n, 1) costo(n,2) ... ... ... costo(n, m) Oferta n (F_n)
Demanda 1 (M_1) Demanda 2 (M_2) ... Demanda j (M_j) Demanda m (M_m)

Cabe mencionar que los costes deben ser colocados en la esquina superior derecha.

Comparación entre los planteamientos[editar]

Entre cada representación existe una equivalencia que se menciona a continuación:

Modelo de Programación Lineal Gráfica Tabla de Transporte Número
Restricción Nodo Renglón (oferta) o columna (demanda) n+m
Variable X_{i,j} Arco Casilla nm

Solución del Problema de Transporte[editar]

El problema de transporte puede ser resuelto de las siguientes formas:

  • Método Simplex: El problema de transporte puede ser resuelto planteando el modelo de programación lineal y utilizar ya sea el método de la M Grande o el método de las dos fases (métodos variantes del método simplex).
  • Técnica de Transporte: Consta de los mismos pasos del método simplex sin embargo es una técnica especifica de solución.

Para que un problema de transporte pueda ser resuelto a través de la técnica de transporte debe cumplir con las características:

  • Ser un problema equilibrado (la oferta total y la demanda total deben ser igual).
  • Contar con (n+m-1) variables básicas, siendo n los puntos de demanda y m los puntos de oferta.

Técnica de Transporte[editar]

Para aplicar la técnica de transporte se utiliza la tabla de transporte equilibrada. Los pasos son los mismo del método simplex, los cuales contemplan:

  • Establecer solución básica factible inicial:

Existen varios métodos para hacer esto: Noreste y sus variaciones(Suroeste, Suroeste, etc), y Costo mínimo o el método de Vogel[3] : Con cualquiera de estos métodos se debe obtener una solución que contemple n+m-1 variables básicas.

  • Definir la variable de entrada:

Para encontrar la variable de entrada se utilizará los criterios ya establecidos del método simplex para un caso minimizado. Y se encontrara la variable utilizando el método de multiplicadores o método de u-v. Dicho método utiliza el modelo dual del modelo de programación lineal. El método calcula los valores de las variables duales u_i y v_j (cada renglón tendrá un u_i y cada columna tendrá un v_j). Estos multiplicadores se obtienen de las ecuaciones: u_i+v_j=c_{i,j} para cada variable básica x_{i,j}

En total se tendrán n+m-1 ecuaciones y m+n multiplicadores. Es necesario utilizar un valor arbitrario para uno de ellos y de ahí encontrar los demás valores de los multiplicadores.

Para el encontrar el z_j-c_j de las variables no básicas se utiliza la relación:

Suponga que x_{s,r} es la variable no básica, entonces se calcula con u_s+v_r-c_{s,r}.

Si al calcular estos valores alguno es positivo, se elige al valor más positivo del z_j-c_j como la variable de entrada. En el caso de que todos sean z_j-c_j<0, entonce la solución actual es la óptima.

  • Establecer la variable de salida

Para identificar la variable de salida será necesario construir un circuito. Los circuitos se construyen a partir de la solución básica factible. Un circuito debe contener únicamente variables básicas con excepción de la variable de entrada. Suponga un ejemplo con la siguiente tabla con 3 factorías y 4 mercados, en este caso se tendrán 6 variables básicas (3+4-1) y una posible solución inicial podría ser (se pone B para indicar que es variable básica):

Mercado 1 Mercado 2 Mercado 3 Mercado 4
Factoría 1 B B
Factoría 2 B B B
Factoría 3 B

Suponga que la variable entrada es la casilla (3,1), esta variable deberá tomar un valor de +\nu, esto ocasiona un reajuste de las demás casillas básicas, el análisis se realiza por columna y por renglón, por tanto el reajuste será:

Mercado 1 Mercado 2 Mercado 3 Mercado 4
Factoría 1 B-\nu B+\nu
Factoría 2 B-\nu B B+\nu
Factoría 3 +\nu B-\nu

Para determinar el valor de la variable de entrada x_{i,j} y establecer la variable de salida:

x_{i,j}=min\left \{ X_{p,q}/X_{p,q}-\nu\ X_{p,q} b\acute{a}sica\right \}

En este caso el valor de la variable de entrada \nu se encuentra en los valores de de las casillas (1,1), (2,2) y (3,4) de estos se elige el valor más pequeño (esta casilla será la variable de salida). Una vez que se tenga el valor \nu se hace las sumas y las restas de las demás casillas del circuito. Se regresa al paso de la variable de entrada.

Referencias[editar]

  1. Conferencia: International Conference on Numerical Analysis and Applied Mathematics (ICNAAM) Ubicación: Rhodes, GREECE Fecha: SEP 22-28, 2014 PROCEEDINGS OF THE INTERNATIONAL CONFERENCE OF NUMERICAL ANALYSIS AND APPLIED MATHEMATICS 2014 (ICNAAM-2014) Colección: AIP Conference Proceedings Volumen: 1648 Número de artículo: UNSP 720008 Fecha de publicación: 2015
  2. Winston, Wayne L. (2005). «Problema de Transporte, asignación y transbordo». En Cuarta edición. Investigación de Operaciones Aplicaciones y Algoritmos. México: Thomson. p. 363. ISBN 970-686-362-1. Consultado el 3 de marzo de 2016. 
  3. a b Taha, Hamdy A. (2012). «Modelo de Transporte y sus variantes». En Novena edición. Investigación de Operaciones. México: Pearson. p. 190. ISBN 978-607-32-0797-3. Consultado el 3 de marzo de 2016. 

Bibliografía[editar]

  • Hillier, F. S., Lieberman, G. J., & Elmer, M. M. (2006). Introducción a la investigación de operaciones. México, D.F.: McGraw-Hill.
  • Taha, H. A. (2011). Operations research: An introduction. Upper Saddle River, NJ: Prentice Hall.
  • Winston, W. L., & Goldberg, J. B. (2004). Investigación de operaciones: Aplicaciones y algoritmos. Australia: Thomson.