En las siguientes secciones, podrás comenzar a usar las herramientas del operador OR para Python:
- ¿Qué es un problema de optimización?
- Resuelve un problema de optimización en Python
- Más ejemplos de Python
- Identifica el tipo de problema que quieres resolver
¿Qué es un problema de optimización?
El objetivo de la optimización es encontrar la mejor solución para un problema de un amplio conjunto de soluciones posibles. (A veces, estarás satisfecho con encontrar una solución factible; las herramientas OR también pueden hacerlo).
Este es un problema de optimización típico. Supongamos que una empresa de transporte entrega paquetes a sus clientes mediante una flota de camiones. Todos los días, la empresa debe asignar paquetes a los camiones y, luego, elegir una ruta para que cada camión entregue los paquetes. Cada asignación posible de paquetes y rutas tiene un costo, según la distancia total de viaje de los camiones y posiblemente otros factores. El problema es elegir las asignaciones de paquetes y rutas que tienen el menor costo.
Como todos los problemas de optimización, este tiene los siguientes elementos:
El objetivo: la cantidad que deseas optimizar. En el ejemplo anterior, el objetivo es minimizar el costo. Para configurar un problema de optimización, debes definir una función que calcule el valor del objetivo para cualquier solución posible. Esto se denomina función objetivo. En el ejemplo anterior, la función objetiva calcularía el costo total de cualquier asignación de paquetes y rutas.
Una solución óptima es aquella para la que el valor de la función objetiva es el mejor. ("Muy bueno" puede ser un máximo o un mínimo).
Las restricciones: restricciones sobre el conjunto de soluciones posibles, según los requisitos específicos del problema. Por ejemplo, si la empresa de transporte no puede asignar paquetes superiores a un peso determinado a los camiones, esto impone una restricción para las soluciones.
Una solución posible es aquella que cumple con todas las restricciones determinadas para el problema, sin ser óptima.
El primer paso para resolver un problema de optimización es identificar el objetivo y las restricciones.
Resolver un problema de optimización en Python
A continuación, se muestra un ejemplo de un problema de optimización y cómo configurarlo y resolverlo en Python.
Un ejemplo de optimización lineal
Una de las áreas de optimización más antiguas y más usadas es la optimización lineal (o la programación lineal), en la que la función objetiva y las restricciones se pueden escribir como expresiones lineales. Aquí hay un ejemplo simple de este tipo de problema.
Maximiza 3x + y
sujeto a las siguientes restricciones:
- 0 ≤
x
≤ 1 - 0 ≤
y
≤ 2 x + y
≤ 2
La función objetiva de este ejemplo es 3x + y
.
Tanto la función objetiva como las restricciones se proporcionan mediante expresiones lineales, lo que hace que este sea un problema lineal.
Pasos principales para resolver el problema
En cada idioma, los pasos básicos para configurar y resolver un problema son los mismos:
- Importa las bibliotecas requeridas,
- Declara el solucionador
- Crea las variables,
- Definir las restricciones,
- Define la función objetiva,
- Invoca el solucionador y
- Muestra los resultados.
Programa de Python
En esta sección, se explica un programa de Python que configura y resuelve el problema.
A continuación, se indican los pasos que debes seguir:
- Importa las bibliotecas requeridas.
from ortools.init.python import init from ortools.linear_solver import pywraplp
- Declara el solucionador.
# Create the linear solver with the GLOP backend. solver = pywraplp.Solver.CreateSolver("GLOP") if not solver: print("Could not create solver GLOP") return
pywraplp
es un wrapper de Python para el solucionador de C++ subyacente. El argumento"GLOP"
especifica GLOP, el solucionador de problemas lineal de las herramientas OR. - Crea las variables.
# Create the variables x and y. x_var = solver.NumVar(0, 1, "x") y_var = solver.NumVar(0, 2, "y") print("Number of variables =", solver.NumVariables())
- Define las restricciones.
Las primeras dos restricciones,
0
≤x
≤1
y0
≤y
≤2
, ya están establecidas por las definiciones de las variables. En el siguiente código, se define la restricciónx + y
≤2
:infinity = solver.infinity() # Create a linear constraint, x + y <= 2. constraint = solver.Constraint(-infinity, 2, "ct") constraint.SetCoefficient(x_var, 1) constraint.SetCoefficient(y_var, 1) print("Number of constraints =", solver.NumConstraints())
El métodoSetCoefficient
establece los coeficientes dex
yy
en la expresión de la restricción. - Define la función objetiva.
# Create the objective function, 3 * x + y. objective = solver.Objective() objective.SetCoefficient(x_var, 3) objective.SetCoefficient(y_var, 1) objective.SetMaximization()
El métodoSetMaximization
declara que se trata de un problema de maximización. - Invoca el solucionador y muestra los resultados.
print(f"Solving with {solver.SolverVersion()}") result_status = solver.Solve() print(f"Status: {result_status}") if result_status != pywraplp.Solver.OPTIMAL: print("The problem does not have an optimal solution!") if result_status == pywraplp.Solver.FEASIBLE: print("A potentially suboptimal solution was found") else: print("The solver could not solve the problem.") return print("Solution:") print("Objective value =", objective.Value()) print("x =", x_var.solution_value()) print("y =", y_var.solution_value())
Completar programa
A continuación, se muestra el programa completo.
from ortools.init.python import init
from ortools.linear_solver import pywraplp
def main():
print("Google OR-Tools version:", init.OrToolsVersion.version_string())
# Create the linear solver with the GLOP backend.
solver = pywraplp.Solver.CreateSolver("GLOP")
if not solver:
print("Could not create solver GLOP")
return
# Create the variables x and y.
x_var = solver.NumVar(0, 1, "x")
y_var = solver.NumVar(0, 2, "y")
print("Number of variables =", solver.NumVariables())
infinity = solver.infinity()
# Create a linear constraint, x + y <= 2.
constraint = solver.Constraint(-infinity, 2, "ct")
constraint.SetCoefficient(x_var, 1)
constraint.SetCoefficient(y_var, 1)
print("Number of constraints =", solver.NumConstraints())
# Create the objective function, 3 * x + y.
objective = solver.Objective()
objective.SetCoefficient(x_var, 3)
objective.SetCoefficient(y_var, 1)
objective.SetMaximization()
print(f"Solving with {solver.SolverVersion()}")
result_status = solver.Solve()
print(f"Status: {result_status}")
if result_status != pywraplp.Solver.OPTIMAL:
print("The problem does not have an optimal solution!")
if result_status == pywraplp.Solver.FEASIBLE:
print("A potentially suboptimal solution was found")
else:
print("The solver could not solve the problem.")
return
print("Solution:")
print("Objective value =", objective.Value())
print("x =", x_var.solution_value())
print("y =", y_var.solution_value())
print("Advanced usage:")
print(f"Problem solved in {solver.wall_time():d} milliseconds")
print(f"Problem solved in {solver.iterations():d} iterations")
if __name__ == "__main__":
init.CppBridge.init_logging("basic_example.py")
cpp_flags = init.CppFlags()
cpp_flags.stderrthreshold = True
cpp_flags.log_prefix = False
init.CppBridge.set_flags(cpp_flags)
main()
Cómo ejecutar el programa
Puedes ejecutar el programa anterior de la siguiente manera:
- Copia y pega el código anterior en el archivo nuevo y guárdalo como
program.py
. - Abre una ventana de comandos y cambia al directorio en el que guardaste
program.py
. En el símbolo del sistema, ingresa:python relative/path/to/program.py
donderelative/path/to/
es la ruta de acceso al directorio en el que guardaste el programa.
El programa muestra los valores de x
y y
que maximizan la función objetivo:
Solution:
x = 1.0
y = 1.0
Más ejemplos de Python
Para obtener más ejemplos de Python que ilustran cómo resolver varios tipos de problemas de optimización, consulta Ejemplos.
Identificar el tipo de problema que deseas resolver
En el mundo, existen muchos tipos diferentes de problemas de optimización. Para cada tipo de problema, existen diferentes enfoques y algoritmos para encontrar una solución óptima.
Antes de comenzar a escribir un programa para resolver un problema de optimización, debes identificar con qué tipo de problema se trata y, luego, elegir un solucionador adecuado: un algoritmo para encontrar una solución óptima.
A continuación, encontrarás una breve descripción general de los tipos de problemas que resuelven las herramientas del operador OR y vínculos a las secciones de esta guía que explican cómo resolver cada tipo de problema.
- Optimización lineal
- Optimización de restricciones
- Optimización de números enteros mixtos
- Tarea
- Programación
- Empaquetado
- Enrutamiento
- Flujos de red
Optimización lineal
Como aprendiste en la sección anterior, un problema de optimización lineal es uno en el que la función objetivo y las restricciones son expresiones lineales en las variables.
El solucionador principal de las herramientas OR para este tipo de problema es el solucionador de optimización lineal, que en realidad es un wrapper para varias bibliotecas diferentes destinadas a la optimización de números enteros mixtos y a las bibliotecas de terceros.
Más información sobre la optimización lineal
Optimización de números enteros mixtos
Un problema de optimización de números enteros mixtos es aquel en el que se requiere que algunas o todas las variables sean números enteros. Un ejemplo es el problema de asignación, en el que se necesita asignar un grupo de trabajadores a un conjunto de tareas. Para cada trabajador y tarea, se define una variable cuyo valor es 1 si ese trabajador está asignado a la tarea en cuestión y 0 en el caso contrario. En este caso, las variables solo pueden tomar los valores 0 o 1.
Más información sobre la optimización de números enteros mixtos
Optimización de restricciones
La optimización de restricciones, o programación de restricciones (CP), identifica soluciones posibles a partir de un gran conjunto de candidatos, en las que el problema se puede modelar en términos de restricciones arbitrarias. La CP se basa en la viabilidad (encontrar una solución factible) en lugar de en la optimización (encontrar una solución óptima) y se centra en las restricciones y las variables, en lugar de la función objetiva. Sin embargo, la CP se puede usar para resolver problemas de optimización con solo comparar los valores de la función objetiva para todas las soluciones posibles.
Más información sobre la optimización de restricciones
Assignment
Los problemas de asignación implican la asignación de un grupo de agentes (por ejemplo, trabajadores o máquinas) a un conjunto de tareas, en el que hay un costo fijo para asignar cada agente a una tarea específica. El problema es encontrar la tarea con el menor costo total. Los problemas de asignación son, en realidad, un caso especial de problemas de flujo de red.
Más información sobre las asignaciones
Empaquetado
El empaquetado de contenedores se refiere al problema de empaquetar un conjunto de objetos de diferentes tamaños en contenedores con distintas capacidades. El objetivo es empaquetar la mayor cantidad posible de objetos, sujeto a la capacidad de los contenedores. Un caso especial de esto es el problema de Knapsack, en el que solo hay un contenedor.
Más información sobre el empaquetado en contenedores
Programación
Los problemas de programación implican la asignación de recursos para realizar un conjunto de tareas en momentos específicos. Un ejemplo importante es el problema de la tienda de trabajo, en el que varios trabajos se procesan en varias máquinas. Cada trabajo consiste en una secuencia de tareas que deben realizarse en un orden determinado y cada tarea debe procesarse en una máquina específica. El problema es asignar un programa para que todos los trabajos se completen en el menor intervalo de tiempo posible.
Más información sobre la programación
Enrutamiento
Los problemas de enrutamiento implican encontrar las rutas óptimas para que una flota de vehículos atraviese una red, definida por un grafo dirigido. El problema de asignar paquetes a camiones de reparto, que se describe en la sección ¿Qué es un problema de optimización?, es un ejemplo de un problema relacionado con el enrutamiento. Otro es el problema del vendedor que viaja.
Más información sobre el enrutamiento
Flujos de red
Muchos problemas de optimización se pueden representar con un grafo dirigido que consta de nodos y arcos dirigidos entre ellos. Por ejemplo, los problemas de transporte, en los que los productos se envían a través de una red ferroviaria, se pueden representar con un gráfico en el que los arcos son líneas ferroviarias y los nodos son centros de distribución.
En el problema de flujo máximo, cada arco tiene una capacidad máxima que se puede transportar por él. El problema es asignar la cantidad de bienes que se enviarán en cada arco para que la cantidad total que se transporte sea lo más grande posible.