Minimización de costos
Sin preferencias
Sin demanda
Esta es la versión más sencilla, donde la demanda de un cliente es cubierta por una sola planta. Un ejemplo puede ser la asignación de un servicio de correo a un núcleo de población (una vivienda ve su necesidad cubierta si tiene adjudicado un cartero que le lleva el correo).
Se definen las variables como:
- \( x_{ij} \) = Variable de decisión binaria que toma valor 1 si la demanda del cliente \( j \) está cubierta por la planta \( i \) y 0 en caso contrario.
- \( y_i \) = Variable de decisión binaria que toma valor 1 si se abre la planta y 0 en caso contrario.
Para resolver el problema se dispone de los siguientes datos:
- \( c_{ij} \) = Costo de que la demanda del cliente \( j \) sea cubierta por la planta \( i \).
- \( f_i \) = Costo de apertura de la planta \( i \).
La función objetivo, al tratarse de minimizar costos totales, será:
\[ \min \sum_{i = 1}^n \sum_{j = 1}^m c_{ij} x_{ij} + \sum_{i=1}^n f_i y_i \]Y para las restricciones:
- Cada cliente ha de verse cubierto por una y sólo una planta. Luego, las \( m \) primeras restricciones son: \[ \sum_{i=1}^n x_{ij} = 1, \forall j \in J \]
- Sólo se abrirá una planta en el caso de que sea necesario para un cliente, luego \( y_i \) no puede valer 0 si algún \( x_{ij} \) vale 1. Es decir, las \( m \times n \) restricciones siguientes son: \( x_{ij} ≤ y_i \forall i \in I, j \in J \)
De forma que nuestro PPL quedará de la siguiente manera:
\[ \begin{eqnarray*} \min&&\sum_{i = 1}^n \sum_{j = 1}^m c_{ij} x_{ij} + \sum_{i=1}^n f_i y_i\\ s.a&&\sum_{i=1}^n x_{ij} = 1, \forall j \in J\\ &&x_{ij} ≤ y_i, \forall i \in I, j \in J \end{eqnarray*} \]Con demanda
En esta versión del problema, las plantas siguen sin tener restricción de capacidad, es decir, asumimos la posibilidad de que una planta pueda asumir la demanda de todos los clientes. En este caso, cada cliente requiere una cierta cantidad de demanda.
Por ejemplo, asumiendo como clientes un pequeño bar y un restaurante y como planta el servicio de distribución de bebidas, el bar que abastece a un pequeño barrio de la ciudad tiene una demanda menor que el gran restaurante que sirve a una mayor población.
Las variables tienen cierta modificación respecto a las anteriores y son:
- \( x_{ij} \) = Variable de decisión cuyo valor es la cantidad total de la demanda del cliente \( j \) suministrada desde la planta \( i \).
- \( y_i \) = Variable de decisión binaria que toma valor 1 se se abre la planta \( i \) y 0 en caso contrario.
Y nuevamente, tenemos los siguientes datos:
- \( c_{ij} \) = Costo unitario de que la planta \( i \) suministre al cliente \( j \).
- \( f_i \) = Costo de apertura de la planta \( i \).
- \( d_j \) = Demanda del cliente \( j \).
En esta versión del problema, nos queda la misma función objetivo:
\[ \min \sum_{i = 1}^n \sum_{j = 1}^m c_{ij} x_{ij} + \sum_{i=1}^n f_i y_i \]Respecto a las restricciones, tenemos que:
- La demanda de cada cliente ha de quedar satisfecha: \[ \sum_{i=1}^n x_{ij} = d_j, \forall j ∈ J \] Como podemos observar tenemos \( m \) restricciones.
- Sólo se puede suministrar a clientes desde plantas abiertas, es decir, si y \( i = 0 \), necesariamente tiene que ocurrir que \( x_{ij} = 0, \forall j ∈ J\). Además, la cantidad a suministrar debe ser como máximo la demanda requerida por el cliente. Por lo tanto, \( x_{ij} ≤ d_j \cdots y_i , \forall i ∈ I, j ∈ J \). Aquí obtenemos \( m \times n \) restricciones.
Por lo que finalmente, nuestro PPL quedará:
\[ \begin{eqnarray*}\min&&\sum_{i = 1}^n \sum_{j = 1}^m c_{ij} x_{ij} + \sum_{i=1}^n f_i y_i\\ s.a&&\sum_{i=1}^n x_{ij} = d_j, \forall j ∈ J\\ &&x_{ij} ≤ d_j y_i , \forall i \in I, j \in J \end{eqnarray*} \]Con preferencias
Esta versión agrega la suposición de que los clientes van a establecer una lista a priori con sus preferencias para ser servidos por alguna de las plantas. Este problema se modela como un problema de programación binivel (un problema de optimización que como restricción tiene otro problema de optimización). Se divide en dos partes, un nivel superior o ”líder” y un nivel inferior o ”seguidor”.
En el nivel superior se minimiza el costo total decidiendo donde instalar las plantas, considerando las preferencias de los clientes. Y en el nivel inferior se optimiza que se vean satisfechas las preferencias de los clientes.
Consideramos las siguientes suposiciones sin perder generalidad:
- Los clientes establecen de antemano sus preferencias con respecto a cada planta mediante una lista ordenada de números enteros del 1 al \( n \) donde 1 corresponde a la planta con mayor preferencia y \( n \) es la de menos.
- No se consideran restricciones de capacidad para las plantas, como en todos los problemas que estamos estudiando.
Las preguntas que queremos contestar son: ¿Dónde se instalarán las plantas? y ¿qué cliente va a ser servido por cada planta?.
Para modelizarlo matemáticamente, las variables que vamos a considerar, serán por tanto:
- \( x_{ij} \) = Variable de decisión binaria que toma valor 1 si la demanda del cliente \( j \) está cubierta por la planta \( i \) y 0 en caso contrario.
- \( y_i \) = Variable de decisión binaria que toma valor 1 se se abre la planta \( i \) y 0 en caso contrario.
Y los datos a considerar son:
- \( c_{ij} \) = Costo unitario de que la planta \( i \) suministre al cliente \( j \).
- \( f_i \) = Costo de apertura de la planta \( i \).
- \( p_{ij} \) = Preferencia del cliente \( j \) de ser servido por la planta \( i \). (\( p_{ij} \in \{1, \ldots, n \} \), donde un valor de \( p_{ij} = 1 \) corresponde al sitio con mayor preferencia).
De forma que nuestro problema quedará:
\[\begin{array}{llr}
\min&\sum_{i = 1}^n \sum_{j = 1}^m c_{ij} x_{ij} + \sum_{i=1}^n f_i y_i &(1)\\
s.a&
\left\{
\begin{array}{lr}
y_i \in \lbrace 0, 1 \rbrace, \forall i \in I&(2)\\
x \in \arg \min \sum_{i \in I} \sum_{j in J} p_{ij} x_{ij}&(3)\\
s.a\quad
\left\{
\begin{array}{lr} \sum_{i \in I} x_{ij} = 1, \forall j \in J&(4)\\ x_{ij} \le y_i, \forall i \in I, j \in J&(5)\\ x_{ij} \in \lbrace 0, 1 \rbrace, \forall i \in I, j \in J&(6)\end{array}
\right. &
\end{array}
\right.
\end{array}\]
Ahora, vamos a explicar cada línea:
- Aquí tenemos nuestra función objetivo, que minimiza la suma de costes de desplazamiento y costes de apertura.
- La variable \( y_i \) es binaria pues es abrir o no abrir la planta \( i \).
- \( x = (x_{ij} )_{i \in I, j \in J} \) ha de satisfacer lo mejor posible las preferencias.
- Cada cliente ha de ser abastecido por una única planta.
- Un cliente sólo puede ser abastecido por una planta abierta.
- Por definición, la variable \( x_{ij} \) tiene que ser binaria.
En la bibliografía se puede consultar una reformulación a un sólo nivel, en ”Un algoritmo Stackelberg-Evolutivo para resolver el problema binivel de localización de plantas con preferencias de los clientes”.