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()

运行得

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()

运行得

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