Companies that need to procure large amounts of a certain product usually get what is known as sales volume discounts from the providers. Volume discounts establish an amount above which a discount is applied for any additional units bought, or for the total purchase.
The total cost function, depending on whether this discount is applied to additional units or to the total purchase looks like this:
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, …) 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:
[math]f(x)=frac{(x_i-a_i)(b^i_{i+1}-b^i_i)}{a_{i+1}-a_i}+b^i_ i ; a_ileq x_i leq a_{i+1}[/math]
Así, suponiendo que x es una variable continua positiva, comenzaremos escribiendo la variable como sigue:
[math]x=sum_{i=1}^{n-1}x_i; x_iin mathbb{R}^{+};forall{i=1..n-1}[/math]
donde, 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:
[math]a_iy_i leq x_i leq a_{i+1}y_i; ; forall{i=1..n-1}[/math]
donde
[math]y_iin {0,1}; ; forall{i=1..n-1}; ; sum_{i=1}^{n-1}y_i=1[/math]
Con esto, ya estaríamos en condiciones de poder escribir nuestra PWL como una expresión lineal del siguiente modo:
[math]f(x)= sum_{i=1}^{n-1}(m_ix_i-c_iy_i)[/math]
donde
[math]m_i=frac{b^i_{i+1}-b^i_i}{a_{i+1}-a_i} ;; y ;; c_i=m_ia_i-b^i_i; forall{i=1..n-1}[/math]
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:
[math]m_ix_i-c_i=m_i(x_i-a_i)+b^i_i=frac{(x_i-a_i)(b^i_{i+1}-b^i_i)}{a_{i+1}-a_i}+b^i_i[/math]
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
[math]frac{b^i_{i+1}-b^i_i}{a_{i+1}-a_i}leq frac{b^{i+1}_{i+2}-b^{i+1}_{i+1}}{a_{i+2}-a_{i+1}}; forall{i=1..n-2}[/math]
y
[math]b^{i+1}_{i+1}leq b^i_{i+1}; forall{i=1..n-1}[/math]
entonces podemos prescindir de las restricciones
[math]a_iy_ileq x_i; forall{i=1..n-1}[/math]
Una PWL con estas características tendría la siguiente forma:
