Las empresas que necesitan abastecerse de gran cantidad de un determinado producto suelen disponer de lo que se conoce como descuentos por volumen de compra por parte del proveedor. Los descuentos por volumen establecen una cuantía a partir de la cual se aplica un descuento sobre las unidades extra adquiridas, o bien sobre el total de la compra.
La función del coste total según se aplique este descuento a las unidades extra o al total de la compra tiene la siguiente forma:
Una vez adquirido el producto, su almacenamiento también tiene un coste asociado que en muchos casos se verá incrementado por una penalización si se supera cierta capacidad disponible. De este modo, una función de coste de almacenamiento podría tener la siguiente forma:
Decidir las cantidades de las que abastecerse en cada periodo teniendo en cuenta los costes asociados a esa adquisición (compra, almacenamiento, transporte, etc.) suele suponer un gran reto para las empresas y de ahí que hagan uso de herramientas de optimización para ayudarse en la toma de decisiones.
PWL no continuas
En su última entrada, Javier nos hablaba de las funciones lineales a trozos (PWL). En particular, nos hablaba de cómo formular PWL continuas. En ocasiones, nos encontraremos con PWL no continuas como las que aparecen arriba. Al igual que ocurría con las continuas, muchos de los productos que resuelven problemas de Programación Lineal Entera tienen esta formulación para las no continuas. Sin embargo, es interesante conocer cómo se modelizan.
Una PWL no continua tiene la siguiente forma:
Y su expresión sería:
De modo que en cada intervalo, la función es lineal.
Cómo linealizar una PWL no continua
La idea consiste en escribir x como suma de n-1 variables (una por cada intervalo) del mismo tipo que x, de las cuales sólo una tomará un valor distinto de cero y, en tal caso, su valor estará en el intervalo correspondiente. Con esta definición de la variable x, podremos escribir la PWL no continua como una combinación lineal de las n-1 variables, de modo que, para cada una de estas variables, si su valor es cero, su aportación al valor de la función sea nula, y en caso contrario:
Así, suponiendo que x es una variable continua positiva, comenzaremos escribiendo la variable como sigue:
En la que, como decía, sólo una de las variables del sumatorio será distinta de cero y en tal caso, con un valor dentro de su correspondiente intervalo. Esta característica se puede modelizar fácilmente haciendo uso de lo que se conoce como Special Ordered Sets de tipo 1 (SOS1) y como comentaba Javier con los de tipo 2, todos los motores de Programación Lineal Entera tienen una representación interna de este tipo de conjuntos.
Una modelización de esta última propiedad sin hacer uso de los SOS1 sería la siguiente:
donde
Con esto, ya estaríamos en condiciones de poder escribir nuestra PWL como una expresión lineal del siguiente modo:
donde
Se comprueba fácilmente que si una de las n-1 variables que hemos utilizado para definir x toma valor 0, su aportación a la función sería nula. Si por el contrario es distinta de cero, su aportación a la función sería:
como queríamos.
Consideraciones Adicionales
Al igual que ocurre con las PWL continuas, incluir una no continua en un problema lo hace más complejo ya que como hemos visto, para una PWL no continua con n-1 «trozos» se necesitan n-1 variables del mismo tipo que x, n-1 variables binarias y 2*n restricciones. En particular, añade mayor complejidad al problema que las PWL continuas.
Con la formulación que presentaba Javier para las PWL continuas, se vio que si la función está en el objetivo de un problema de maximización y era cóncava, la complejidad del problema no se veía afectada al incluir la PWL ya que se podía prescindir de la modelización del SOS2. Aunque esto no es así para esta modelización, sí hay casos concretos en los que podremos prescindir de alguna de las restricciones. Por ejemplo, si nuestra PWL no continua está en la función objetivo de un problema de maximización, es creciente en cada «trozo» y se verifica que
y
entonces podemos prescindir de las restricciones.
Una PWL con estas características tendría la siguiente forma:
¿Quieres saber más sobre programación matemática? Contáctanos sin problema y te ayudaremos.
Si quieres saber más sobre decide4AI, y mantenerte al tanto de futuros webinar o acciones, síguenos en las redes sociales (Linkedin, Twitter, Youtube).
