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 puntos de oferta o factorías con una producción determinada (representada mediante un vector, F) y puntos de demanda o mercados de demanda determinada (vector M):

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

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

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

El precio total a pagar por el transporte, , 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:

Problemas equilibrados[2] [editar]

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

(o, abreviadamente, , es decir, la oferta total es igual a la demanda total).

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

.

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

.

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 .

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 ()
Factoría 2 costo(2,1) costo(2,2) ... costo (2, j) ... costo(2, m) Oferta 2 ()
... ... ... ... ... ... ... ...
Factoría i costo (i,1) costo (i,2) ... costo(i,j) ... costo(i,m) Oferta i ()
... ... ... ... ... ... ... ...
Factoría n costo(n, 1) costo(n,2) ... ... ... costo(n, m) Oferta n ()
Demanda 1 () Demanda 2 () ... Demanda j () Demanda 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 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 y (cada renglón tendrá un y cada columna tendrá un ). Estos multiplicadores se obtienen de las ecuaciones: para cada variable básica

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 de las variables no básicas se utiliza la relación:

Suponga que es la variable no básica, entonces se calcula con .

Si al calcular estos valores alguno es positivo, se elige al valor más positivo del como la variable de entrada. En el caso de que todos sean , 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 , 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 B
Factoría 2 B B B
Factoría 3 B

Para determinar el valor de la variable de entrada y establecer la variable de salida:

En este caso el valor de la variable de entrada 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 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.