Skip to main content

Solución de precios dinámicos con Dynamic programming

1 estrella2 estrellas3 estrellas4 estrellas5 estrellas (1 votos, promedio: 5,00 de 5)
Cargando…

Dynamic Programming (programación dinámica) es una de las herramientas más útiles en la resolución de todo tipo de problemas, con mucha aceptación por parte de los científicos de datos. Según su autor, Richard E. Bellman:

“consiste en descomponer un problema de optimización en subproblemas más sencillos, y almacenar la solución de cada subproblema de manera que cada subproblema se resuelva una sola vez”

Si lo buscáis por internet encontraréis ejemplos sencillos como el cálculo de los números de Fibonacci, el problema de la mochila (“knapsack”) o las torres de Hanoi. Estos algoritmos son muy didácticos pero poco útiles quizás para nuestra realidad. En esta entrada vamos a buscarle un uso más cotidiano y directo, el cálculo de precios dinámicos en un escenario de stock y tiempo limitado.

Vamos por el ejemplo:

Tenemos un campo de fútbol con una zona de 40 asientos y los vamos a poner en venta a 20 días del partido.

Nos preguntamos: ¿Cuál es el precio óptimo al que tenemos que poner las entradas cada día para optimizar el ingreso global llegado el día del partido?

Con la experiencia de partidos anteriores, ya conocemos la demanda de los potenciales clientes que decrece con el precio linealmente (lógico) y además crece exponencialmente conforme llegamos al último día -el día 20-, esto es también habitual puesto que muchos compradores no planifican y compran a última hora.

Declaramos como λ es la media de la estadística de poisson que depende del precio p y el tiempo t.

La función se puede graficar en tres dimensiones, donde podemos confirmar como la función decrece con el p (Price) y además asciende rápidamente cuando el t (horizon) se incrementa. El eje vertical representa la demanda λ.

 

Vamos a suponer sin perder generalidad que los compradores no tienen relación entre ellos, y por lo tanto compran de forma independiente. Si esto es así podemos modelar la demanda con una distribución de Poisson que a partir de la demanda media (λ) observada nos dice la probabilidad de que la demanda real sea de un número determinado de unidades (asientos).

Dynamic Programming nos ayuda en encontrar dicho precio óptimo diario. Dicho algoritmo se basa en una matriz de estados V (value) cuya dimensión = (capacidad * días).

La matriz es como un juego en que nos situamos en una casilla cada día, hasta el día del final del partido y la única acción de juego que tenemos es decidir cada día que precio (a) al que queremos poner las entradas.

El eje vertical x representa las unidades disponibles (capacidad) y el eje horizontal representan los días desde el inicio de la venta (1) al día del partido (20).

Este tablero matemáticamente se puede modelar como un proceso estocástico llamado Proceso de Decisión de Markov (MDP) determinado por la 4-tupla {S, A, Pa, Ra }:

  • S son un numero finito de estados (en nuestro caso la capacidad restante de asientos y el dia de la venta)
  • A un numero finito de acciones (en nuestro caso los posibles precios que podemos poner)
  • Pa (s, s’) es la probabilidad de saltar de un estado s a uno s’ dado que hemos tomado la acción a (lo obtenemos a partir de la distribución de Poisson)
  • Ra (s, s’) es la recompensa inmediata al saltar de un estado s a un estado s’ (este es el precio por el número de asientos vendidos).


                                          Fuente: https://en.wikipedia.org/wiki/Markov_decision_process

 

A partir de aquí nuestro objetivo es encontrar las acciones a óptimas en cada uno de los estados para maximizar la recompensa final.

Es aquí donde Dinamic Programming nos permite encontrar dicha solución, con un algoritmo iterativo llamado Value iteration que divide el problema general en problemas a nivel de cada estado (el subproblema).

La solución al subproblema del estado V(S) es la suma ponderada de la recompensa por saltar a un estado (le llamaremos R, en nuestro caso el ingreso por las entradas vendidas) y un factor de descuento (ϒ < 1) del valor del estado destino máximo que podemos obtener al día siguiente si saltase a este estado. Aquí a se refiere a los posibles estados (precios) que podemos tomar en dicho estado.

La interpretación del algoritmo es que el Valor de un estado de hoy es la recompensa de hoy más el valor futuro (todos los posibles futuros ponderados por las probabilidades de saltar a ellos).

El factor de ponderación (p) es la probabilidad de salto a este estado en función de la acción a que hayamos tomado (el precio que hemos decidido). Esta probabilidad se calcula gracias a que tenemos la distribución de Poisson que hemos comentado antes.

Bellman demostró (1957) que el algoritmo de Value iteration converge a la solución si se calcula de forma reiterada. El factor de descuento ϒ es el hiperparámetro que afectaría a la velocidad de dicha convergencia, pero no a la solución final.

El resultado para el ejemplo expuesto es la gráfica siguiente en la que podemos comprobar que el algoritmo lógicamente explota el precio máximo cuando encuentra mayor certeza en la venta de las localidades, es decir, cuando quedan menos localidades o cuando hay pocos días para el partido, momento en que los compradores pagan más por las entradas.

Este es un ejemplo de las posibilidades que Dynamic Programming puede ofrecernos en multitud de problemas. El uso de esta teoría se extiende a muchos campos como la inteligencia artificial, la seguridad, los sistemas distribuidos, la genética, la macroeconomía… que convierte problemas de tiempo exponencial en problemas de orden menor O(n^2) o O(n^3).

Podéis encontrar el notebook del caso comentado incluyendo la simulación de 1000 partidos usando la política de precios aleatoria vs la política que nos da value iteration para probar la bondad de la solución.

https://gist.github.com/m-alcu/453405602115a1c552504baeca0b959e

 

Martin Alcubierre Arenillas

Martin Alcubierre Arenillas

Ingeniero de Telecomunicaciones, con más de 15 años de Jefe de Proyecto en el sector de Banca-Seguros y Utilities, principalmente en integración de sistemas y proyectos de Business Intelligence. Desde hace 3 años participando en proyectos de desarrollo de soluciones móviles en el ámbito de la Salud (mHealth).

Martin Alcubierre Arenillas ha escrito 2 entradas


Martin Alcubierre Arenillas

Martin Alcubierre Arenillas

Ingeniero de Telecomunicaciones, con más de 15 años de Jefe de Proyecto en el sector de Banca-Seguros y Utilities, principalmente en integración de sistemas y proyectos de Business Intelligence. Desde hace 3 años participando en proyectos de desarrollo de soluciones móviles en el ámbito de la Salud (mHealth).

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.