1. No category

 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