11. Programación entera.#
Un problema de programación lineal entera (PLE) consiste en un problema de optimización de una función lineal en presencia de restricciones lineales con la condición añadida de que alguna o todas sus variables han de ser enteras. A continuación vamos a resolver un problemas de programación lineal con variables binarias.
Problema. Una empresa está planificando la inversión a realizar en los próximos 3 trimestres en 5 proyectos de investigación. En la siguiente tabla aparece detallado el presupuesto disponible por trimestre, la inversión que se debe realizar por proyecto y trimestre y el beneficio que se espera obtener con cada proyecto. Todos los datos aparecen en millones de euros.
| Trimestre | ||||||
Proyecto |
1 |
2 |
3 |
Beneficio |
||
————————- |
—- |
—- |
—- |
———– |
||
1 |
5 |
1 |
8 |
20 |
||
2 |
4 |
7 |
10 |
40 |
||
3 |
3 |
9 |
2 |
20 |
||
4 |
7 |
4 |
1 |
15 |
||
5 |
8 |
6 |
10 |
30 |
||
Presupuesto |
25 |
25 |
25 |
|||
Se desa conocer los proyectos en los que se debe invertir para maximizar el beneficio obtenido.
Obsérvese que no buscamos la cantidad a invertir en cada proyecto puesto que esta cantidad es fija y sólo depende delproyecto elegido. La única decisión que debemos tomar es si invertimos o no en un proyecto u otro con el fin de obtener el mayor beneficio posible sin superar el presupuesto disponible. Consideramos entonces las siguiente variables binarias
Entonces el modelo matemático a resolver sería el siguiente:
sujeto a
Todas las variables presentes en este problema están restringidas a tomar los valores 0 ó 1 y por lo tanto estaremos en presencia de un problema de Programación 0-1 o binario. La solución a este problema sería en invertir en todos los proyectos salvo el 5 y obtener así un beneficio de 95 millones de euros. Veamos a continuación cómo lo resolvemos con O’Cean.
Lo primero es importar el módulo correspondiente y después definir las variables binaria
from dimod import ConstrainedQuadraticModel, Binary
#Definimos las variables bianrias
x1 = Binary("x1")
x2 = Binary("x2")
x3 = Binary("x3")
x4 = Binary("x4")
x5 = Binary("x5")
A continuación instanciamos una clase de ConstrainedQuadraticModel()y definimos la función objetivo:
cqm = ConstrainedQuadraticModel()
objetive = -20*x1-40*x2-20*x3-15*x4-30*x5
cqm.set_objective(objetive)
Una vez definida la función objetivo, se procede a indicar las restricciones que debemos tener en cuenta para resolver el problema.
cqm.add_constraint(5*x1+4*x2+3*x3+7*x4+8*x5<=25, label="R1")
cqm.add_constraint(x1+7*x2+9*x3+4*x4+6*x5<=25, label="R2")
cqm.add_constraint(8*x1+10*x2+2*x3+x4+10*x5<=25, label="R3")
'R3'
Ahora ya tan sólo tenemos que utilizar un solver para resolver el problema planteado.
Cell In[5], line 1
Ahora ya tan sólo tenemos que utilizar un solver para resolver el problema planteado.
^
SyntaxError: invalid syntax
from dwave.system import LeapHybridCQMSampler
sampler = LeapHybridCQMSampler()
sampleset = sampler.sample_cqm(cqm)
feasible_sampleset = sampleset.filter(lambda d: d.is_feasible)
print(feasible_sampleset.first)
Sample(sample={'x1': 1.0, 'x2': 1.0, 'x3': 1.0, 'x4': 1.0, 'x5': 0.0}, energy=-95.0, num_occurrences=1, is_satisfied=array([ True, True, True]), is_feasible=True)
Como podemos ver el resultado obtenido es el que inicialmente habíamos comentado, es decir se eligen los primeros cuatro proyectos y se descarta el quinto.
Pero podríamos imponer más restricciones a nuestro problema, como pueden ser las siguientes:
a) Se debe invertir como mucho en tres proyectos.
b) Se debe invertir o en el proyecto 1 o en el proyecto 5 (o en ambos)
c) Si se invierte en el proyecto 4 se debe invertir en el 3
d) Si se invierte en los proyecto 2 ó 3 se debe invertir en el proyecto 5
Estas condiciones las debemos trasladar a formulaciones matemáticas de la siguiente manera:
a) \(x_{1}+x_{2}+x_{3}+x_{4}+x_{5}\le 3\)
b) \(x_{1}+x_{5}\ge1\)
c) \(x_3 \ge x_4\)
d) \(x_2+x_3 \le x_5\)
El implementar todas estas condiciones en nuestro modelo, se hace de una forma fácil. Por ejemplo implementemos la condición reflejada en el aparatdo a). Se haría de la siguiente manera:
# se debe invertir como mucho en tres proyectos
cqm.add_constraint(x1+x2+x3+x4+x5<=3, label="R4")
'R4'
sampler = LeapHybridCQMSampler()
sampleset = sampler.sample_cqm(cqm)
feasible_sampleset = sampleset.filter(lambda d: d.is_feasible)
print(feasible_sampleset.first)
Sample(sample={'x1': 0.0, 'x2': 1.0, 'x3': 1.0, 'x4': 0.0, 'x5': 1.0}, energy=-90.0, num_occurrences=1, is_satisfied=array([ True, True, True, True]), is_feasible=True)
12. Programación entera mixta.#
Como ampliación de un problema de programación de variables 0-1, a continuación vamos a resolver un problema donde se mezclan variables 0-1 con variables de tipo entero.
Problema. Una pequeña empresa puede producir 4 tipos de artículos y estima que para el próximo período podrá vender todo lo que fabrica de los productos 1 y 3, pero como mucho tendrá demanda para 30 unidades del producto 2 y 10 del producto 4. La empresa tiene capacidad para producir un máximo de 110 artículos de cualquier tipo y combinación. A continuación se detalla el coste de producción por unidad producida, el coste fijo de producción y el precio de venta unitario de cada artículo.
Producto |
Coste de |
Coste fijo |
P.V.P |
|---|---|---|---|
1 |
300 |
60 |
450 |
2 |
450 |
20 |
650 |
3 |
500 |
70 |
600 |
4 |
200 |
60 |
450 |
Formular el modelo matemático para determinar las unidades que se deben producir de cada artículo para maximizar los beneficios de la empresa.
Si consideramos únicamente las variables \(x_i\) = unidades del producto i que debe fabricar el próximo período, la función de beneficios no se podrá formular de una forma correcta. Téngase en cuenta que los costes fijos no dependen de la cantidad producida, sino de la decisión de producir o no producir. Necesitamos por lo tanto variables que hagan referencia a esta decisión. Estas variables serán de tipo binario, y se definirán de la siguiente manera:
Con estas consideraciones, se podría formular el problema de la siguiente manera:
Sujeto a:
La solución óptima a este problema va a ser la siguiente
\(\begin{array}{c} x_{1}=70,\ x_{2}=30,\ x_{3}=0,\ x_{4}=10\\ y_{1}=y_{2}=y_{3}=y_{4}=0 \end{array}\)
Y entonces, claramente no se va a respetar la relación entre variables de producción y variables de decisión ya que estamos produciendo sin incurrir en ningún coste fijo. Esto es debido a que no se ha incluido ninguna relación matemática entre estos dos tipos de variables, esto es, no aparece reflejada la condición: “si \(x_i>0\) entonces ha de ser \(y_i=1\)”. Sea M una constante arbitrariamente grande y consideremos las restricciones:
Si estas desigualdades son añadidas al modelo aseguramos que \(y_i=1\) siempre que \(x_i \gt 0\). Téngase en cuenta que en caso contrario, obligatoriamente \(x_i=0\). De esta manera, si hay producción del artículo i obligatoriamente se incurre en el coste fijo asociado. No obstante, estas desigualdades pueden ser modificadas: si \(y_i=1\), la restricción \(x_i \le My_i\) se traduce en \(x_i \le M\), siendo M una constante suficientemente grande. Teniendo esto presente, el problema se debe formular de la siguiente manera:
Sujeto a:
Teniendo en cuenta todo esto procedemos a formular el problema para que se pueda resolver con O’Cean.
Importamos las clases que necesitamos
from dimod import ConstrainedQuadraticModel, Integer, Binary
Definimos las variables correspondientes:
x1= Integer("x1")
x2= Integer("x2", upper_bound=30)
x3= Integer("x3")
x4= Integer("x4", upper_bound=10)
y1= Binary("y1")
y2= Binary("y2")
y3= Binary("y3")
y4= Binary("y4")
Definimos la función objetivo
cqm = ConstrainedQuadraticModel()
objetive = -150*x1-200*x2-100*x3-250*x4+60*y1+20*y2+70*y3+60*y4
cqm.set_objective(objetive)
Añadimos las correspondientes restricciones
cqm.add_constraint(x1+x2+x3+x4 <= 110, label="R1")
# observar que las variables deben estar a la izquierda del signo <=
# Si no lo hacemos así, obtendremos un error
cqm.add_constraint(x1-110*y1<=0, label="R2")
cqm.add_constraint(x2-30*y2<=0, label="R3")
cqm.add_constraint(x3-110*y3<=0, label="R4")
cqm.add_constraint(x4-10*y4<=0, label="R5")
'R5'
Ahora resolvemos
from dwave.system import LeapHybridCQMSampler
sampler = LeapHybridCQMSampler()
sampleset = sampler.sample_cqm(cqm)
print(sampleset.first)
Sample(sample={'x1': 73.0, 'x2': 30.0, 'x3': 0.0, 'x4': 10.0, 'y1': 1.0, 'y2': 1.0, 'y3': 0.0, 'y4': 0.0}, energy=-19370.0, num_occurrences=1, is_satisfied=array([ True, True, True, False, False]), is_feasible=False)
Podemos observa que la solución anterior no es factible, y por lo tanto debemos establecer el filtro correspondiente, para obtener esa solución factible de la siguiente manera
feasible_sampleset = sampleset.filter(lambda d: d.is_feasible)
print(feasible_sampleset.first)
Sample(sample={'x1': 70.0, 'x2': 30.0, 'x3': 0.0, 'x4': 10.0, 'y1': 1.0, 'y2': 1.0, 'y3': 0.0, 'y4': 1.0}, energy=-18860.0, num_occurrences=1, is_satisfied=array([ True, True, True, True, True]), is_feasible=True)
Supongamos ahora que el fabricante impone las siguientes restricciones:
a) Si se produce del artículo 1 se debe producir del artículo 2.
b) Si se produce del artículo 4 no debe producirse nada del artículo 3
c) Se debe producir obligatoriamente de los artículos 2,3 y 4
d) Si se producen más de 30 unidades del artículo 1, se deben producir al menos 10 unidades del artículo 2
e) Si se producen más de 30 unidades del artículo 1, se deben producir como mucho 10 unidades del artículo 2
Veamos a continuación, cómo poder incorporar estas restricciones con fórmulas matemáticas.
a) Debemos expresar que si \(x_1\) > 0 entonces \(x_2\) > 0, con desigualdad estricta. Entonces para introducir esta consideración se deben incorporar dos números M y m que permitan la siguiente restricción: \(x_1\le My_1\) y \(x_2 \ge my_1\). De esta manera se tiene que si \(x_1>0\) entonces \(y_1=1\) y por lo tanto \(x_2\ge m\).
b) Se debe verificar que si \(x_4>0\) entonces \(x_3=0\) o lo que es equivalente: si \(y_4=1\) entonces \(y_3=0\). Por lo tanto no puede darse el caso que ambas variables tomen el valor de 1 y por lo tanto la restricción sería la siguiente: \(y_3+y_4 \le 1\).
c)El producir obligatoriamente algún artículo de los tipos 2, 3, 4 es equivalente a incorporar la restricción: \(y_2+y_3+y_4=3\).
d) Se debe reflejar que si \(x_1 > 30\) entonces \(x_2 \ge 10\). En este caso necesitamos una variable binaria más que haga referencia al hecho de producir más de 30 unidades del artículo 1, puesto que la variable \(y_1\) sólo indica si hay o no producción del artículo 1. Por lo tanto definimos esta variable auxiliar de la siguiente manera:
Entonces la condición de que \(x_1>30\) queda clara de la siguiente manera: \(x_1-30 \le Mz\), siendo M una constante suficientemente grande. Obsérvese que si \(x_1>30\) no puede ser z=0 ya que en este caso, la restricción \(x_1-30 \le Mz\) es equivalente a \(x_1-30 \le 0\). Ahora basta añadir \(x_2 \ge 10z\) con \(z \in {0,1}\) y entonces si z=1 entonces \(x_2 \ge 10\).
e) La condición es equivalente a que si \(x_1 > 30 \) entonces \(x_2 \le 10\). Igualmente se toma
y \(x_1-30 \le Mz\) con M constante suficientemente grande, y entonces se añade la desigualdad \(x_2-10 \le M(1-z)\) con \(z \in {0,1}\).