PROGRAMACIÓN LINEAL Y NO LINEAL EN EL PROBLEMA DEL TRASNPORTE Jose J. Arenas Departamento de Física, IES Monterroso, C/. Santo Tomás de Aquino S/N, 29680, Estepona (Málaga, España). [email protected]

RESUMEN El problema del transporte es un nombre que se le da al estudio del transporte óptimo. Usualmente, se trata de un tipo de problema de programación lineal que se puede resolver mediante el método simplex. Sin embargo, en casos en que la carga no está asegurada, si clasificamos la frecuencia de carga en función del precio ofertado y utilizamos métodos de regresión no lineal y teoría de la decisión, se deberían encontrar resultados más precisos. En este trabajo se aplican dichos métodos y se comparan los resultados con los obtenidos por la Regla de Laplace, encontrando que la regresión no lineal es más precisa.

Palabras clave: Teoría de la Decisión, Problema del Transporte, Programación lineal

ABSTRACT The transportation problem is a name given to the study of optimal transportation. Usually, it is a type of linear programming problem that may be solved using the simplex technique. On the other hand, in this paper, using nonlinear regression methods and decision theory models, more accurate results are obtained.

Keywords: Decision theory, transportation problem, Linear Programming

 

 

INTRODUCCIÓN El conocido como “problema de transporte” es clásico en el ámbito financiación empresarial y su optimización de costes (Bonilla, 1964) pero sigue siendo de actualidad (Barreras et al., 2008), así como en la enseñanza de economía y matemáticas para las ciencias sociales de enseñanzas medias (Moreno, 2007). Dicho problema trata un caso particular de programación lineal en el que se trata minimizar el coste del abastecimiento a varios puntos de demanda a partir de una serie de puntos de oferta, teniendo en cuenta los distintos precios de envío de cada punto de oferta a cada punto de demanda o destino (Laporte, 1992; Barcos et al., 2002). Frecuentemente, debido al elevado número de variables, se emplea el método Simplex u otros de programación lineal (Dantzig, 1951; Larrañeta, 1987; Serra de la Figuera, 2002) incluso en problemas en que el envío se basa en una probabilidad. Por otra parte, la Teoría de la Decisión (TD) o Teoría Formal de la Racionalidad Práctica considera tres tipos de situaciones en función de si el agente que debe decidir conoce o no el resultado de cada una de las acciones posibles (Mosterín, 2013: 83) I.

Decisión bajo condiciones de certeza. Se maximiza o minimiza un parámetro condicionado por ciertas restricciones. Estas situaciones se suelen resolver con programación lineal.

II.

Decisión bajo condiciones de riesgo. El agente debe decidir entre distintas acciones cuyas consecuencias puede estimar, pero estas dependen a su vez de probabilidades que se deben asignar a cada acción y, por tanto, a sus efectos. Para solucionar este tipo de problemas se debe maximizar el valor o utilidad esperada, que es la suma ponderada del producto de la función de la utilidad (u) por su probabilidad asignada (p), esto es: !!!

     

𝑝! · 𝑢! !!!

[1]

III.

Decisión bajo condiciones de incertidumbre. El agente desconoce parcial o completamente las consecuencias derivadas de cada acción, y no se asignan probabilidades. En este tipo de situaciones no existen reglas universalmente aceptadas que resuelvan el problema. Las dos vías de solución más conocidas se basan minimizar el máximo riesgo o en actuar teniendo en cuenta sólo la mejor consecuencia posible.

En el caso del problema del transporte, se suele dar la situación (I) de las tres enunciadas en la TD, ya que se trata de distribuir productos desde almacenes a puntos de destino y las distancias y los costes asociados a las rutas son valores asumidos como constantes. Por tanto, se identifica al problema como una toma de decisiones bajo condiciones de certeza, habilitando así el uso de programación lineal. Usualmente se trata de minimizar la función del coste bajo ciertas restricciones de oferta y demanda, profundizando en ocasiones mediante la Teoría de Grafos (Puchades & Mula, 2008). Por otra parte, es práctica habitual en las empresas de distribución que los vehículos de reparto vuelvan vacíos de regreso a su punto de partida, en cuyo caso deben asumir el coste del trayecto. En esas situaciones, las empresas se suelen encontrar en otra toma de decisiones, como es la posibilidad de escoger un trayecto de regreso alternativo y más largo, a cambio de encontrar en un destino determinado una carga cuyo precio compense el

 

2  

  coste del itinerario o, incluso, ofrezca beneficios. La dificultad en estos casos se da si la obtención de clientes que soliciten el vehículo está sujeta a leyes probabilísticas. Si se aplican métodos básicos para la obtención de dicha probabilidad de carga (como la Regla de Laplace), se puede utilizar también programación lineal, ya que, aunque nos encontramos en el caso (II) de la TD, se suele considerar la probabilidad como un valor constante para un intervalo temporal determinado. Sin embargo, la Regla de Laplace se utiliza cuando no se tiene más información que disminuya el grado de incertidumbre o en sucesos equiprobables, algo que no se debe asumir ya que la probabilidad de encontrar carga en un destino determinado, depende a su vez del precio que le asignemos a esta (regla elemental de la oferta-demanda), que es justo el parámetro que pretendemos encontrar. En este supuesto, la probabilidad será una función del precio (suponiendo constantes otros parámetros, por simplicidad), con lo que los métodos de programación lineal no podrán utilizarse ya que [1] no será lineal. En nuestro análisis, expondremos una situación de toma de decisiones y la analizaremos bajo las dos perspectivas del cálculo de probabilidades (Laplace y función de probabilidad). Nuestra hipótesis es que la función de probabilidad arrojará resultados más precisos. La situación inicial responde a una consulta real de una empresa proveedora de soluciones de transporte con rutas por Europa (la llamaremos “SuperF” como pseudónimo para mantener la privacidad en la metodología de dicha empresa). Dicha empresa, como hemos comentado, asigna valores constantes de probabilidad en diversos intervalos temporales a lo largo del año. En nuestro análisis, despreciaremos la influencia de las decisiones ajenas respecto a la del empresario, algo que tendría efecto en dicha probabilidad y que se podría tratar mediante métodos también propios de Economía, Matemáticas Aplicadas, o Física Teórica (Teoría de Juegos (Sánchez, 1998)).

MÉTODOS (EJEMPLOS) MÉTODOS LINEALES

Un camión que salió de Almería (cargado con pepinos no infectados) hacia el norte de Europa, se detiene en Barcelona en el camino de vuelta, ya vacío de carga. El conductor tiene la opción de regresar por el camino más corto hacia Almería o, por el contrario, realizar la ruta Barcelona-Madrid-Sevilla-Almería ya que en ocasiones encuentra carga en estos destinos, lo que le puede reportar beneficios. La cuestión es: ¿Qué precio mínimo (p) debe asignarse a cada carga y en cada trayecto para que el cómputo global beneficie anualmente al dueño del camión? Es decir, para que el camionero siempre haga esa ruta alternativa. Debe tenerse en cuenta que el camionero, durante los días de estancia en Madrid, tiene una probabilidad del 20% de que le llame el empresario para que vuelva inmediatamente a Almería de vacío para realizar una carga con destino al norte de Europa, lo que es claramente más rentable. Por otra parte, una vez en Madrid, el camionero podría pensar que es más beneficioso volver a Almería directamente y de vacío que continuar por la ruta a Sevilla, lo que deberá evitarse en el cálculo de precios.

Debe tenerse en cuenta también que el empresario siempre paga los costes del camión (combustible, salario del conductor, peajes, etc), es decir, también en los trayectos en que el vehículo circula cargado.

 

3  

  Datos: Distancias en ruta: Barcelona-Madrid = 627 km Madrid-Sevilla = 531 Km Sevilla-Almería = 409 Km Barcelona-Almería = 845 Km Madrid-Almería = 543 Km

Probabilidades de carga: Barcelona-Madrid (x)= 0.1 Madrid-Sevilla (y) = 0.7 Sevilla-Almería (z) = 0.4 Barcelona-Almería = 0 Madrid-Almería = 0

Estacionalidad aleatoria de carga (en donde únicamente es válida la probabilidad anterior): Barcelona-Madrid = todos los meses del año Madrid-Sevilla = 8 de cada 12 meses Sevilla-Almería = 9 de cada 12 meses

Costes asociados al camión; C = 0.75 €/Km

Tras una serie discusiones beneficio/pérdida por itinerario y suponiendo que el conductor tiene poder de decision en todos los nodos para regresar directamente o no, matematizamos el problema vía Simplex mediante la herrramienta online http://www.zweigmedia.com/MundoReal/simplex.html: Minimizar p = x + y + z sujeta a 0.1x + 0.373y + 0.24z >= 400.5 0.47y + 0.3z >= 195.938 0.47y + 0.3z >= 603.188 x >= 820.5 Solución Optimal: p = 2103.88; x = 820.5, y = 1283.38, z = 0 Quizá el mayor error de este método usualmente empleado por empresas de transporte es suponer que la situación en que el conductor se encuentra en una toma de decisiones bajo condiciones de certeza (I)

 

4  

  MÉTODOS LINEALES VS NO LINEALES

Supongamos ahora un camión que, tras una entrega, vuelve de vacío a su punto de origen por el trayecto más corto. El empresario sabe que, si se desvía de la ruta, es posible que encuentre carga en otro destino que compense parcial o totalmente los costes asociados (salario del conductor, combustible, etc). Sin embargo, puede suceder que se desvíe de la ruta prevista y no encuentre dicha carga, con lo que el coste será aún mayor que el inicialmente previsto. Por ello, el agente debe asignar un precio a la carga que compense los costes y tenga en cuenta que en ocasiones regresará vacío el camión. Es decir, debe encontrar al precio a partir del cual se compensa el coste del itinerario alternativo o bien debe encontrar el idóneo que maximiza beneficios. Se tienen las siguientes estadísticas (tabla 1) que hemos clasificado en función del precio ofertado en unidades monetarias (“u.m.” en adelante y por simplificación, equivaldrá en adelante a 100 €)):

Precio ofertado “ui” (u.m.)

Frecuencia de carga encontrada (pi)

Nº de veces que se ha ofertado a dicho precio (ni)

0

1

1

10

0,717

10

20

0,513

6

80

0,069

2

200

1,27·10-3

1

Tabla 1. estadísticas que clasificadas en función del precio ofertado en unidades monetarias (u.m.)

Identificando la frecuencia con la probabilidad, el empresario tendrá que encontrar un precio que, unido a la probabilidad, compense un determinado coste incluyendo el del itinerario alternativo, por ejemplo 10 u.m.. Ello corresponde a [1] simplificada ya que sólo suponemos un nodo:  𝑝 · 𝑢 > 10 [2]

 

5  

  Método de SuperF Puesto que la empresa aplica el método Simplex a problemas como este (aunque con más variables y nodos), la probabilidad “p” debe ser una constante ya que si dependiera del precio “u”, el producto 𝑝 · 𝑢 > 10 no produciría una inecuación lineal, con lo que no podría emplearse dicho método. Así, la única forma en que se pueden recoger los datos de la tabla para obtener un valor determinado de probabilidad de carga es realizar una media ponderada: 𝑝=

!!! !!! 𝑝! 𝑛! !!! !!! 𝑛!

=

11,387 = 0,57 20 [3]

De tal forma, SuperF se plantearía la pregunta: “¿A partir de qué precio resulta rentable la nueva ruta?” Sustituyendo en [3] en [2] se obtiene 𝑢 > 17,56  𝑢. 𝑚. [4] Método alternativo La probabilidad encontrada con la regla de Laplace, se puede ajustar, ya que en el fondo, la probabilidad de encontrar clientes en cualquier sector dependerá del precio de los productos ofertados. Identificando este principio básico de oferta-demanda, podemos clasificar las frecuencias de encontrar carga en función de los precios de esta, como hemos supuesto en nuestra tabla. Aunque la función de la probabilidad y precio no es continua, podemos suponerlo así para poder aplicar criterios de derivabilidad (máximos y mínimos en curvas). Buscando una función teórica que se aproxime a los datos e introduciendo: exponential fit {0,1},{10,0.717},{20,0.513},{80,0.069},{200,0.00127} en Wolfram Alpha (Figura 1), obtenemos: 𝑝 = 1,00025𝑒 !!,!"""#$%! ~𝑒 !!/!"   𝑅 ! ≈ 1 [5]

Figura 1. Probabilidad de encontrar carga (𝑝 = 𝑒 !!/!" ) en función del precio u ofertado. Obsérvese que la función corresponde a las leyes básicas de oferta-demanda, ya que es estrictamente decreciente, alcanza el valor máximo 1 cuando el precio es nulo y tiende a cero para precios muy elevados.

 

6  

  Hemos obtenido así la correlación entre probabilidad de carga y precio ofertado de la misma. Sustituyendo [5] en [2]: 𝑒 !!/!" 𝑢 > 10 [6] Por tanto, debemos encontrar que precios u satisfacen esta desigualdad, en caso de existir estos. Encontramos el intervalo aproximado en u.m. (solve e^(-u/30)u>10 en Wolfram Alpha): 18.57 < 𝑢 < 45.36 [7] Observamos así que los posibles valores de u que compensan el nuevo itinerario ni siquiera incluyen el resultado mínimo de SuperF (17,56 u.m.). Según nuestro método, la pregunta que precedería ahora sería: “¿Existe un precio que maximice el beneficio esperado?” Como hemos asumido la función como continua, podemos derivarla e igualarla a cero para encontrar los extremos de la misma. Llegamos de esta forma al máximo de la función: !

max 𝑒 !!" 𝑢 =

30 ≅ 11,04  para  𝑢 = 30   𝑢. 𝑚. , 𝑒 [8]

en donde se introduce en el mismo programa: maximize e^(-u/30)u, el cual se encuentra dentro del intervalo [7] (Figura 2).

!

Figura 2. Valor esperado (𝑒 !!" 𝑢) en función del precio u ofertado. Sólo el intervalo 18.57 < 𝑢 < 45.36 !

supera la restricción de las 10 u.m., encontrándose que max 𝑒 !!" 𝑢 =

!" !

≅ 11,04  para  𝑢 = 30   𝑢. 𝑚.

Representación en que hemos introducido en el software plot e^(-u/30)u>10 para reproducirla

 

7  

 

RESULTADOS Si sustituimos el precio mínimo obtenido por SuperF (17,56 u.m.) en la función probabilística (5), obtenemos que la probabilidad de encontrar carga a dicho precio es de 0,557, y al sustituir en la función de utilidad 𝑝 · 𝑢, se obtiene un valor de 9,78 u.m., lo que ni siquiera compensa las 10 u.m. requeridas en el planteamiento inicial (generando pérdidas del 2,2%, por tanto). Por otra parte, mediante el método alternativo, se encuentra que para un precio de 30 u.m., el valor esperado es de 11,04 u.m., lo que ofrece beneficios del 10,4%. Obtenemos así una diferencia final de 12,6 puntos porcentuales en el balance de ingresos/costes al comparar entre sí ambos métodos.

DISCUSIÓN Como se puede concluir al observar en otros trabajos que tienen en cuenta probabilidades, teoría de decisión, y funciones de utilidad en problemas de transporte (Ríos, 1961; Liendro, 2012), los resultados de aplicar dichos métodos mejoran los resultados. En nuestro caso, aunque los valores numéricos podrían ser otros, dependiendo de la situación y la empresa escogida para el análisis, se ha demostrado mediante la TD que la Regla de Laplace es excesivamente simple y es más preciso encontrar la función de probabilidad de hallar carga en los nodos o destinos de un vehículo, ya que esta dependerá a su vez del precio. De esta forma, la variación considerada aquí del problema del transporte, no se debe resolver con el método Simplex ya que no se trata de funciones lineales, por lo que se recomienda a la empresa clasificar las frecuencias de carga en función del precio para incorporar métodos de obtención de funciones de probabilidad por métodos de regresión no lineal (posiblemente exponencial) e incorporar estas funciones a los cálculos de optimización, siendo necesario emplear métodos de programación no lineal. Creemos que este tipo de situaciones podrían introducirse como ejemplos de aplicación de software específico en problemas de Economía y Matemáticas Aplicadas en el currículum de enseñanzas de bachillerato y superiores, ya que muestran que la programación lineal no siempre es adecuada. Por otra parte, este ejemplo con bases empíricas puede servir para que empresas de distribución optimicen o mejoren sus finanzas.

 

8  

 

BIBLIOGRAFÍA 1. Barcos, L., Rodríguez, V., Álvarez, M. J., & Robusté, F. (2002). Algoritmo basado en la optimización mediante colonias de hormigas para la resolución del problema del transporte de carga desde varios orígenes a varios destinos. In V Congreso de Ingeniería del Transporte. Santander (pp. 709-717). 2. Barreras, J. A. L., Tiznado, J. E. O., & Wilson, C. C (2008). Modelo matemático de transporte aplicado a una compañía dedicada a la manufactura y distribución de juguetes, usando programación lineal entera. Revista Ingeniería Industrial 7 (2). 3. Bonilla, M. (1964). Aplicaciones del modelo de transporte a la financiación de la empresa. Economía de la Empresa, p. 63. 4. Dantzig, G. B. (1951). Application of the simplex method to a transportation problem. Activity analysis of production and allocation, 13, 359-373. 5. Larrañeta, J. (1987). Programación lineal y grafos (No. 1). Universidad de Sevilla. 6. Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358 7. Liendro, N. F. (2012). Determinantes de la demanda de transporte en la ciudad de Salta (Doctoral dissertation, Tesis de grado, UNSa). 8. Moreno, B. (2007). Una aplicación de la programación lineal: el problema del transporte. Cuadernos de Docencia-Revista Digital de Educación. Volumen I, 3. 9. Mosterín, J. (2013). Ciencia, Filosofía y Racionalidad. Gedisa Editorial 10. Puchades, V., Mula, J. (2008). Aplicación de la Teoría de Grafos para mejorar la planificación de rutas de trabajo de una empresa del sector de la distribución automática. Revista de Métodos Cuantitativos para la Economía de la Empresa. (6), 7-22. 11. Ríos, S. (1961). Procesos de decisión. Trabajos de Estadística y de Investigación Operativa, 12(1), 47-69. 12. Sánchez, J. (1998). El problema del transporte, una aproximación desde la Teoría de Juegos. Universidad de Murcia. Tesis Doctoral. 13. Serra de la Figuera, D. (2002). Métodos Cuantitativos para la Toma de Decisiones, Barcelona (España), Gestión 2000, ISBN 978-84-8088-940-7.

 

 

9