Linear Optimization(借助ortools)

优化问题的要素:

• objective，欲优化的量。比如某函数的最大值或最小值。
• constraints, 约束变量。基于问题的特定需求，对可行解进行约束。

线性优化用于计算一组线性关系建模问题的最优解。

谷歌提供的开源库Glop可用来求解该问题。

解决问题步骤:

• 创建变量
• 定义约束
• 定义目标函数
• 声明求解器
• 调用求解器
• 展示结果

eg1:

• objective: maximize(x+y)
• constraints:
  • 0 ≤ x ≤ 1
  • 0 ≤ y ≤ 2

复制代码from ortools.linear_solver import pywraplp def main(): solver = pywraplp.Solver('SolveSimpleSystem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING) # Create the variables x and y. x = solver.NumVar(0, 1, 'x') y = solver.NumVar(0, 2, 'y') # Create the objective function, x + y. objective = solver.Objective() objective.SetCoefficient(x, 1) objective.SetCoefficient(y, 1) objective.SetMaximization() # Call the solver and display the results. solver.Solve() print('Solution:') print('x = ', x.solution_value()) print('y = ', y.solution_value()) if __name__ == '__main__': main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from ortools.linear_solver import pywraplp
def main():
solver = pywraplp.Solver('SolveSimpleSystem',
pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
# Create the variables x and y.
x = solver.NumVar(0, 1, 'x')
y = solver.NumVar(0, 2, 'y')
# Create the objective function, x + y.
objective = solver.Objective()
objective.SetCoefficient(x, 1)
objective.SetCoefficient(y, 1)
objective.SetMaximization()
# Call the solver and display the results.
solver.Solve()
print('Solution:')
print('x = ', x.solution_value())
print('y = ', y.solution_value())
if __name__ == '__main__':
main()

运行得

复制代码Solution: x = 1.0 y = 2.0

1
2
3
4
5
Solution:
x =
1.0
y =
2.0

eg2:

• objective: maximize(3x + 4y)
• constraints:
  • x + 2y ≤ 14
  • 3x – y ≥ 0
  • x – y ≤ 2

复制代码"""Linear optimization example""" from ortools.linear_solver import pywraplp def main(): # Instantiate a Glop solver, naming it LinearExample. solver = pywraplp.Solver('LinearExample', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING) # Create the two variables and let them take on any value. x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x') y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y') # Constraint 1: x + 2y <= 14. constraint1 = solver.Constraint(-solver.infinity(), 14) constraint1.SetCoefficient(x, 1) constraint1.SetCoefficient(y, 2) # Constraint 2: 3x - y >= 0. constraint2 = solver.Constraint(0, solver.infinity()) constraint2.SetCoefficient(x, 3) constraint2.SetCoefficient(y, -1) # Constraint 3: x - y <= 2. constraint3 = solver.Constraint(-solver.infinity(), 2) constraint3.SetCoefficient(x, 1) constraint3.SetCoefficient(y, -1) # Objective function: 3x + 4y. objective = solver.Objective() objective.SetCoefficient(x, 3) objective.SetCoefficient(y, 4) objective.SetMaximization() # Solve the system. solver.Solve() opt_solution = 3 * x.solution_value() + 4 * y.solution_value() print('Number of variables =', solver.NumVariables()) print('Number of constraints =', solver.NumConstraints()) # The value of each variable in the solution. print('Solution:') print('x = ', x.solution_value()) print('y = ', y.solution_value()) # The objective value of the solution. print('Optimal objective value =', opt_solution) if __name__ == '__main__': main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""Linear optimization example"""
from ortools.linear_solver import pywraplp
def main():
# Instantiate a Glop solver, naming it LinearExample.
solver = pywraplp.Solver('LinearExample',
pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
# Create the two variables and let them take on any value.
x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')
y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')
# Constraint 1: x + 2y <= 14.
constraint1 = solver.Constraint(-solver.infinity(), 14)
constraint1.SetCoefficient(x, 1)
constraint1.SetCoefficient(y, 2)
# Constraint 2: 3x - y >= 0.
constraint2 = solver.Constraint(0, solver.infinity())
constraint2.SetCoefficient(x, 3)
constraint2.SetCoefficient(y, -1)
# Constraint 3: x - y <= 2.
constraint3 = solver.Constraint(-solver.infinity(), 2)
constraint3.SetCoefficient(x, 1)
constraint3.SetCoefficient(y, -1)
# Objective function: 3x + 4y.
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 4)
objective.SetMaximization()
# Solve the system.
solver.Solve()
opt_solution = 3 * x.solution_value() + 4 * y.solution_value()
print('Number of variables =', solver.NumVariables())
print('Number of constraints =', solver.NumConstraints())
# The value of each variable in the solution.
print('Solution:')
print('x = ', x.solution_value())
print('y = ', y.solution_value())
# The objective value of the solution.
print('Optimal objective value =', opt_solution)
if __name__ == '__main__':
main()

运行得

复制代码Number of variables = 2 Number of constraints = 3 Solution: x = 5.999999999999998 y = 3.9999999999999996 Optimal objective value = 33.99999999999999

1
2
3
4
5
6
7
8
Number of variables = 2
Number of constraints = 3
Solution:
x =
5.999999999999998
y =
3.9999999999999996
Optimal objective value = 33.99999999999999