- Piloto
- Copiloto
import matplotlib.pyplot as plt
import numpy as np
from optlang import Model, Variable, Constraint, Objective
from plot_opt import region_plot, plot_LP
Programación lineal (Linear Programming y Mixed Integer Linear Programming)¶
Programación lineal¶
Definición¶
Un problema de optimización consiste en encontrar el punto $(x_1,\dots,x_n)$ de $\mathbb{R}^n$ para el que una función objetivo $f(x_1,\dots,x_n)$ alcanza su máximo absoluto, pero cumpliendo ciertas restricciones, que pueden ser igualdades $g_1(x_1,\dots,x_n)=c_1$ o desigualdades $g_2(x_1,\dots,x_n)<=c_2$.
Un problema de programación lineal es un problema de optimización en el que tanto la función objetivo como las restricciones son todas funciones lineales.
Por ejemplo $$ \begin{split} \text{Max: } & x + y \\ \text{Such that: } & x + 2y \leq 4\\ \text{} & 5x - y \leq 8\\ \text{} & x,y \geq 0 \end{split} $$
Región factible¶
Las restricciones delimitan el conjunto de soluciones aceptables, que se denomina región factible. Al apilar inecuaciones, tomamos la intersección de varios semiplanos, que delimitan una región del espacio $\mathbb{R}^n$.
x = Variable('x',lb=0)
y = Variable('y',lb=0)
constraints = [
Constraint(x+2*y, ub=4),
Constraint(5*x-y, ub=8)
]
region_plot(constraints,(x,-1,4), (y,-1,4))
Plantear el problema de optimización con restricciones¶
obj = Objective(x+y, direction='max')
model = Model(name='My model')
model.objective = obj
model.add(constraints)
status = model.optimize()
print("status:", model.status)
print("objective value:", model.objective.value)
for var_name, var in model.variables.items():
print(var_name, "=", var.primal)
Dibujamos el resultado¶
Dibujamos la región factible en azul, la solución óptima en rojo, y dibujamos en verde el conjunto de puntos de todo el plano donde la función objetivo toma el valor óptimo. Observamos que sólo hay un punto con el valor óptimo dentro de la región factible.
plt.figure(figsize=(6,6))
plot_LP(model, (x,-1,4), (y,-1,4))
Ejercicio 1¶
Repite el ejemplo del principio de la clase, pero añadiendo nuevas restricciones. Por ejemplo, añade:
$$ \begin{split} \text{Max: } & x + y \\ \text{Such that: } & x + 2y \leq 4\\ & 5x - y \leq 8\\ & y \leq 1.5\\ & x,y \geq 0 \end{split} $$o
$$ \begin{split} \text{Max: } & x + y \\ \text{Such that: } & x + 2y \leq 4\\ & 5x - y \leq 8\\ & x \leq 1.5\\ & x,y \geq 0 \end{split} $$Dibuja el resultado final e interpreta la solución.
Ejercicio 2¶
Repite el ejemplo del principio de la clase, con la misma región factible, pero con la función objetivo $x+2y-2$. Dibuja el resultado final:
$$ \begin{split} \text{Max: } & x + 2y -2 \\ \text{Such that: } & x + 2y \leq 4\\ \text{} & 5x - y \leq 8\\ \text{} & x,y \geq 0 \end{split} $$
Segundo apartado del ejercicio 2¶
- Responded a la pregunta: ¿Hay una solución óptima al problema, o hay más de una?
- Describid el conjunto de todas los puntos de la región factible donde se alcanza el valor óptimo con la mayor precisión posible. Una persona que no haya visto el dibujo debería ser capaz de dibujar el conjunto de forma exacta.
Ejercicio 4¶
Plantea un MILP con un conjunto de restricciones inviables que definen el conjunto vacío: ningún punto del plano las verifica. ¿Cómo responde el software al plantear el problema, y al resolverlo?
Ejercicio 5¶
Modeliza y resuelve el ejemplo del transporte de carbón de la wikipedia:
Glosario en inglés¶
- problema de optimización: optimization problem
- función objetivo: objective function
- restricciones: constraints
- problema de programación lineal: linear programming problem
- función lineal: linear function
- región convexa: convex region
- región factible: feasible region
- región acotada: bounded region
Para aprender más¶
- Programación lineal en Wikipedia
- Linear programming in Wikipedia (un poco más completo).
- Linear programming in Sage