4. Modelización de restricciones lógicas con variables 0-1.¶
La programación Entera, mediante el uso de variable 0-1, permite expresar en forma de restricciones lineales una gama muy amplia de restricciones lógicas o cualitativas que aparecen muy frecuentemente en las aplicaciones de la Investigación Operativa. Esta capacidad de modelización hace que el uso de la programación entera se haya extendido a muchos entornos de producción, transporte, logística, localización, asignación de recursos, diseño de ingeniería, inversión, análisis económicos, etc. Entre otros muchos tipos de restricciones lógicas, podemos citar las más habituales.
1.- Máximo número de variables
2.- Variables incompatibles.
3.- Variables discretas.
4.- Variables semicontinuas.
5.- Costos fijos.
6.- Economías de escala o tarifas de precios.
7.- Dicotomías ( o restricciones ‘al menos una de dos’)
8.- Disyunciones o restricciones disyuntivas ( al menos k de varias )
9.- Regiones no convexas.
10.- Implicaciones o restricciones condicionales.
Para linealizar ( es decir, expresar en forma de restricciones lineales ) estas condiciones lógicas es necesario generalmente introducir unas variables 0-1 adicionales, que son los indicadores de variables y de restricciones. Entendiendo bien las relaciones entre variables y las restricciones y sus indicadores, el proceso de modelización de condiciones lógicas es sencillo.
4.1. Indicadores de variables continuas.¶
Sea x una variable continua, que puede tomar cualquier valor entre 0 y u (\(0 \leq x \leq u \)) y que puede corresponder, por poner ejemplo, a la cantidad de toneladas que se van a producir de cierto producto. En muchas situaciones interesa distinguir cuándo no se produce nada ( x=0 ), y cuándo se produce algo ( x>0 ). Para esto se introduce la variable binaria y que sólo toma valores 0 ó 1, que llamaremos la variables indicador de la variables continua x, de tal forma que y=0 indique que x=0, e y=1 indique que x>0. Es decir buscamos las equivalencias (\(x=0\Leftrightarrow y=0\)) y (\(x>0\Leftrightarrow y=1\)). Además, estas equivalencias deben ser expresadas en forma de restricciones lineales para poder ser incorporadas a un modelo de programación lineal entera. Para conseguir esto consideremos las siguientes restricciones.
1.- \(x \leq uy\). Esta restricción equivale a: \(y=0 \Rightarrow x=0\) o su equivalente: \(x>0 \Rightarrow y=1\). En muchos casos es suficiente añadir esta restricción para conectar o asociar la variable x con su indicador y.
2.- Para la otra implicación: y=1 \Rightarrow x>0, o su equivalente x=0 \Rightarrow y=0, hay que sustituir la condición x>0 por una del tipo \(x \geq m\), donde m>0 es una cantidad suficientemente pequeña. Entonces bastaría añadir la restricción \(x \geq my\).
Resumiendo, dada una variables continua con rango entre cero y u, el siguiente grupo de restricciones asocia o coonecta la variable x con su indicador y:
De todas formas, hay que decir que en la mayoría de las ocasiones es suficiente introducir la implicación que aparece en el primer punto anterior, lo cual se consigue con las restricciones:
4.2. Restricciones lógicas incluyendo variables.¶
Utilizando de forma conveniente las restricciones que asocian a una variable con su indicador, las restricciones lógicas más habituales se expresan como una restricción sencilla a sus indicadores.
4.2.1. Variables incompatibles.¶
Dos variables \(x_1\) y \(x_2\) son incompatibles si no se pueden cumplir a la vez las dos condiciones al mismo tiempo, es decir que por ejemplo es incompatible \(x_1>0\) y \(x_2>0\). Basta pensar en dos productos que no pueden salir al mercado simultáneamente, o que no pueden entrar simultáneamente en una mezcla. Entonces deben cumplirse las implicaciones \(x_1>0 \Rightarrow x_2=0\) y \(x_2>0 \Rightarrow x_1=0\). Para expresar estas implicaciones en forma de restricciones lineales sean \(u_1\) y \(u_2\) cotas superiores de \(x_1\) y \(x_2\) respectivamente ( si no se conocen cotas explícitas basta tomar una caantidad M>0 suficientemente grande). Entonces, se añaden las siguientes restricciones:
Y así se verifican las dos implicaciones \(x_1>0 \Rightarrow y_1=0 \Rightarrow y_2=0 \Rightarrow x_2=0\) y lo mismo para \(x_2>0\)
4.2.2. Máximo número de variables.¶
Dadas n variables con cotas \(0 \leq x_j \leq u_j, j=1,...,n\) la restricción lógica es que como mucho k de ellas pueden ser positivas ( por ejemplo, máximo número de componentes de una mezcla, máximo número de inversiones…) donde k es un entero 0<k<n. Asociando a cada variable son su indicador, bastaría añadir las restricciones.
4.2.3. Variables o expresiones discretas.¶
Una expresión discreta es una expresión lineal \(f(x_1,...,x_n)=\sum_{j=1}^{n} a_j x_j\), que sólo puede tomar alguno de los valores en un conjunto discreto {\(d_1,...,d_N \)}. En particular, si \(f(x_1,...x_n)=x_j\), es la variable \(x_j\) la que puede tomar un conjunto discreto de valores. Una formulación de esta condición puede ser la siguiente:
4.2.4. Variables semicontinuas.¶
Una variable continua con \(0\leq x \leq u\) puede tomar cualquier valor entre o y u. En cambio, una variable semicontinua puede tomar o bien el valor x=0 o bien si es x>0, debe ser \(x \geq m\). Basta pensar en cantidades mínimas que se pueden producir, o cantidades mínimas en una mezcla. Para modificar este tipo de variables basta añadir a su indicador y las siguientes restricciones:
De esta manera se tiene que si \(y=0 \Rightarrow x=0\) y si \(y=1 \Rightarrow x \geq m\) como queríamos.
4.2.5. Costos fijos.¶
Una de las condiciones de tipo lógico que más aparecen en la práctica se refiere a funciones de costo del siguiente tipo:
Aquí K es el costo fijo asociado a la variable x, y es el costo en que se incurre por producir cualquier cantidad del producto, mientras que \(cx\) es el coste variable. Este tipo de funciones de costo son no lineales, pues son incluso discontinuas en el origen. Para expresar este tipo de costo de forma lineal basta añadir el indicador y de la variable x, las restricciones
y en la función objetivo aparecería el término cx+Ky, si x>0 tiene que ser y=1, y el coste asociado es K+cx. En cambio, si x=0 en principio habría que añadir la restricción \(x \geq my\) para garantizar y=0 y el coste total sea 0. Sin embargo si K>0 en el mínimo va a dar siempre esta condición y no es preciso añadirla explícitamente.
Un modelo de programación lineal con costes fijos es un modelo de programación lineal 0-1 mixta de la forma:
En particular, el modelo de Flujo en Redes con Costes fijos, es el siguiente modelo de programación 0-1 mixto:
En este tipo de modelos habitualmente \(K_{ij}\) representa el coste fijo de construcción o utilización del arco (i,j), mientras que \(c_{ij}\) es el coste marginal. La función objetivo global calcula el balance óptimo entre los costes fijos y los costes variables. Como casos particulares de este modelo están los siguientes problemas: Mínimo árbol de comunicación, árbol de Steiner, problemas de lotes, problemas de localización y problemas de diseños de redes.
4.2.6. Otras condiciones lógicas incluyendo variables.¶
Combinando condiciones sencillas con los operadores lógicos (‘y’,’o’,’no’ e ‘implica’) se pueden llegar a construir condiciones lógicas complejas, que posteriormente habría que linealizar. Por ejemplo, supongamos que en un problema de mezclas con componentes A,B,C… nos piden las siguientes condicones:
1.- Si A está en la mezcla también debe estar B. (\(Y_A \leq Y_B\)).
2.- Si A está en la mezcla entonces o bien B ó bien C también deben estar. (\(Y_B+Y_C \geq Y_A\))
3.- Si A o B está en la mezcla entonces debe estar C o D O E. (\(Y_A+Y_B \leq 2(Y_C+Y_D+Y_E)\))
Para linealizar este tipo de condiciones lógicas hay que añadir a cada variable su indicador, asociarlos con restricciones del tipo (1) o (2), según convenga, y luego añadir una o varias restricciones de los indicadores.
4.2.7. Extensión de la restricción \(x \leq uy\) a varias variables.¶
La restricción \(x \leq uy\), donde las variables son \(x\geq0\) e \(y \epsilon \{0,1\}\), linealiza la implicación \(y=0, \Rightarrow x=0 \). En muchass ocasiones se tiene que linealizar la siguiente implicación:
POr ejemplo, supongamos que la variable \(y \epsilon \{0,1\}\) indica si se abre o no un almacén, mientras que las variables \(x_j \geq 0,j=0,1,...n \) indican las cantidades que se sirven desde el almacén a n clientes, siempre que se abra el almacén. Entonces esta implicación lógica se puede hacer de dos formas:
1.- Poniendo n restricciones \(x_j\leq u_jy, j=1,2...,n\), donde \(u_j\) es una coa superior de la variable \(x_j\). Llamaremos a esta forma la formulación desagregada.
2.- Poniendo una restricción \(x_1+x_2,...+x_n \leq uy\), donde u es una cota superior de \(x_1+x_2,...+x_n\). Llamaremos a esta forma la formulación agregada.
Muchos modelos de localización, empaquetamiento y diseño de redes hacen uso de estas restricciones.
4.2.8. Condiciones lógicas incluyendo restricciones o expresiones.¶
Existe otro tipo de condiciones lógicas que incluyen ciertas restricciones o expresiones sobre las variables. Un ejemplo podría ser: si se producen más de 2000 unidades de producto 1 entonces no deben producirse más de 1000 unidades entre los productos 2 y 3. Para modelizar este tipo de condiciones hay que introducir unas variables 0-1 adicionales que son los indicadores de las restricciones o expresiones.
Sea la restricción lineal o expresión \(f(x) \leq 0\), a la cual queremos asociar un indicador \(y \epsilon \{0,1\}\). Por ejemplo, si se tiene una restricción \(2x_1+3x_2+x_3\leq 7 \), basta con tomar \(f(x)=2x_1+3x_2+x_3-7 \leq 0 \). Para que y sea el indicador de \(f(x) \leq 0\) debe cumplirse que si y=1 entonces se tenga \(f(x) \leq 0\). Para conseguir esto, sea \(\bar{f}\) una cota superior de \(f(x)\). Si no se conoce una cota explícita basta tomar \(\bar{f} = M\), un número grande. Entonces basta añadir al modelo las restricciones:
Así, si y = 1 se tiene, como buscábamos que \(f(x) \leq 0 \), mientras que si y = 0, queda que \(fx) \leq \bar{f}\), que s una restricción redundante o inactiva.
Cuando la expresión es de la forma \(f(x) \geq 0\) basta tomar una cota inferior \( f(x) \geq \underline{f}\) y añadir:
Utilizando estos indicadores de forma conveniente se pueden linealizar muchos tipos de condiciones lógicas que incluyen expresiones .
4.2.9. Dicotomías o restricciones ‘al menos una de dos’.¶
Una dicotomía es una expresión lógica del tipo \(R_1 \lor R_2\) ( que se cumpla al menos una de las dos condiciones \(R_1\,o\, R_2\)), donde \(R_1\,y\,R_2\) son expresiones lógicas. En nuestro caso las expresiones \(R_i\) las pondremos siempre de la forma \(f_i(x) \leq 0\). Para linealizar la dicotomía \((f_1(x) \leq 0) \lor (f_2(x) \leq 0)\) basta calcular cotas superiores \(\overline{f_1}\,y\,\overline{f_2}\) y añadir los indicadores de \(y_1\,y\,y_2\) mediante las restricciones:
En el caso de una dicotomía se puede obtener el mismo resultado con una sola variable 0-1 poniendo:
Basta comprobar los dos casos: si y=1 queda \(f_1(x) \geq 0\) como buscábamos, y \(f_2 \geq \overline{f_2}\) que es una restricción redundante; y si y=0 queda \(f_1 \geq \overline{f_1} (redundante) y \)f_2(x) \geq 0$.
Si alguna de las expresiones que intervienen en la dicotomía son del tipo \(f_i(x) \leq 0\), una de dos, o se cambia la restricción a la forma señalada anteriormente, o bien se calculan cotas inferiores y se añaden las correspondientes restricciones del tipo \( \geq \).
4.2.10. Disyunciones o restricciones ‘al menos k de m’.¶
Sean m restricciones del tipo \(f_i(x) \leq 0 ;i=1,2,...m\) y buscamos linealizar la condición lógica: que se umplan al menos k de las me restricciones ( siendo k < m). Para esto basta calcular las m cotas superiores \( \overline{f_i}\,;i=1,2,...m\) e introducir los indicadores \(y \epsilon \{0,1\}\) mediante las restricciones:
4.2.11. Implicaciones o restricciones condicionales.¶
Dadas dos restricciones lógicas \(R_1\) y \(R_2\) la implicación \(R_1 \Rightarrow R_2\) indica simplemente que si se cumple \(R_1\) entonces debe cumplirse \(R_2\). Para linealizar una implicación, basta observar que \(R_1 \Rightarrow R_2\) es equivalente a la dicotomía \(R_2 \lor \thicksim R_1\), donde \(\thicksim\) es la negación de \(R_1\).
Así, la implicación \((f_1(x)\leq 0) \Rightarrow (f_2(x) \leq 0)\) se pone primero de la forma \((f_2(x)\leq 0) \lor (f_1(x) >0)\), y después se sustituye \((f_1(x)>0)\) por \(f_1(x) \geq \epsilon\), con \(\epsilon >0\), llegando a la dicotomía \((f_2(x) \leq 0) \lor (f_1(x) \geq \epsilon)\). Para linealizar esta dicotomía se calculan una cota superior \(\overline{f_2}\) de \(f_2(x)\) y una cota inferior \(\underline{f_1}\) de \(f_1(x)-\epsilon\) y se añaden las restricciones:
Para ve que estas restricciones modelizan la implicación basta observar que si se cumple \((f_1(x) \leq 0)\) entonces tiene que ser necesariamente \(y=1\) (por la segunda restricción) y entonces por la primera es \(f_2(x) \leq 0\)