在本文中,我们将了解优化问题以及如何用 Python 解决它。优化的目的是从大量的备选方案中选择问题的最优解决方案。
另请阅读:如何用 Python 编写 Android 应用程序?
最优化问题
让我们看一个使用优化的简单案例场景。假设一家面包店每天生产 1000 包面包,每包包含 10 块面包。为了量化产量,每批面包都使用精确数量的小麦、酵母等成分来制备。
在某个财务季度,公司决定削减生产成本,同时不影响面包的质量或尺寸。管理层决定将每个面包的对角线长度减少 1 英寸,虽然不易观察到,但在大规模生产时会产生广泛的影响。
所以现在,生产小尺寸面包所需的小麦和酵母的精确数量的要求使其成为一个优化问题。良好的优化结果可以降低投入成本,同时保持理想的面包尺寸。
与所有优化问题一样,这个任务中存在问题的部分需要一些与所有编程语言相似的基本要素:
解决方案——您想要改进的量。
此时此刻最重要的解决方案是尽可能地削减成本。您必须陈述一种方法,该方法可以针对优化问题估计可行的结果,同时将解决方案保持在所需的限制范围内。
计算可能解的方法称为目标函数。在面包尺寸问题中,目标函数将告诉您在准备一批尺寸减小的新鲜面包时需要多少小麦和酵母。
目标函数旨在为任何问题提供最大的价值(这里的“最大”是指价值要么最高,要么最低,根据问题的需要),面包维度问题是最小化的,所以最终的结果将提供解决方案的最大价值,意味着最低价值。
约束是目标函数结果的限制,它依赖于问题的需要,这意味着,在需要最高/最低值的问题中,约束充当最终限制,解决方案无法跨越。
例如,制作一批面包所需的最低原材料数量将起到约束作用,这意味着每批面包需要的小麦和酵母的最低限度。最小化解决方案无法估计低于该阈值的结果。
可行的解决方案可以满足问题的所有要求,但不一定是最优的。确定目标和约束是解决优化问题的第一步。
使用 python 解决优化问题
让我们用 Python 来解决优化问题。优化主要有以下三种:
- 线性优化
这是从一组参数中搜索最佳可能解决方案的过程。
- 整数优化
当问题涉及的参数不止一个并且涉及整数或布尔参数时,它就成为可以通过整数优化解决的问题。
- 约束优化
如果问题涉及非常大的参数集,并且需要从该大的约束集中找到解决方案,那么它就变成了约束优化问题。
下面是使用整数优化解决的最大化问题的示例。
最大化问题是一种整数优化问题,其中为某些参数提供约束,并通过将这些约束转换为线性方程然后求解来计算可行的解决方案。我们将为下面的方程找到一个可行的解。
等式为:3a+6b+2c <= 50
4a- 6b + 8c <= 45
3a + b – 5c <= 37
这里我们需要最大化 3*a + 2*b + 2*c
解决最大化问题的主要阶段:
每种语言中设置和解决问题的基本程序都是相同的:
- 导入您需要的库。
- 对求解器进行声明。
- 变量和参数声明。
- 标记将用于实现目标的方法。
- 调用求解器并输出结果。
解决这个问题的基本步骤是:
进口
from ortools.linear_solver import pywraplp |
求解器声明
solver = pywraplp.Solver.CreateSolver( 'SCIP' ) |
这是一种使用 ortools 计算问题的方法。
SCIP:它是用于解决混合非线性问题的工具箱或工具的参数。
Pywraplp:由于ortools基于c++,因此它需要一个包装器才能在python上工作。Pywrappl 就是那个包装器。
定义变量和约束
# a, b, and c are non-negative integer variables. a = solver.IntVar(0.0, solver.infinity(), 'a') b = solver.IntVar(0.0, solver.infinity(), 'b') c = solver.IntVar(0.0, solver.infinity(), 'c') |
约束将根据方程定义。例如,第一个方程 3a+6b+2c <= 50 将定义为:
cons_in1 = solver.Constraint(-solver.infinity(), 50) cons_in1.SetCoefficient(vara, 3) cons_in1.SetCoefficient(varb, 6) cons_in1.SetCoefficient(varc, 2) |
目标函数:
我们需要最大化的方程是 3*a + 2*b + 2*c。下面的代码显示了为该方程创建目标函数的步骤。
obj_prog = solver.Objective() obj_prog.SetCoefficient(vara, 3 ) obj_prog.SetCoefficient(varb, 2 ) obj_prog.SetCoefficient(varc, 2 ) obj_prog.SetMaximization() |
调用求解器并打印最终结果
solver.Solve() # Print segment of program print ( 'Highest objective function value = %d' % solver.Objective().Value()) print () for variable in [vara, varb, varc]: print ( '%s = %d' % (variable.name(), variable.solution_value())) |
最终代码:
from ortools.linear_solver import pywraplp def Maximizationproblem(): solver = pywraplp.Solver.CreateSolver( 'SCIP' ) vara = solver.IntVar( 0.0 , solver.infinity(), 'vara' ) varb = solver.IntVar( 0.0 , solver.infinity(), 'varb' ) varc = solver.IntVar( 0.0 , solver.infinity(), 'varc' ) # 3*a + 6*b + 2*c <= 50 cons_in1 = solver.Constraint( - solver.infinity(), 50 ) cons_in1.SetCoefficient(vara, 3 ) cons_in1.SetCoefficient(varb, 6 ) cons_in1.SetCoefficient(varc, 2 ) # 4*a - 6*b + 8*c <= 45 cons_in2 = solver.Constraint( - solver.infinity(), 45 ) cons_in2.SetCoefficient(vara, 4 ) cons_in2.SetCoefficient(varb, - 6 ) cons_in2.SetCoefficient(varc, 8 ) # 3*a + b - 5*c <= 37 cons_in3 = solver.Constraint( - solver.infinity(), 37 ) cons_in3.SetCoefficient(vara, 3 ) cons_in3.SetCoefficient(varb, 1 ) cons_in3.SetCoefficient(varc, - 5 ) # [END constraints] # [objective segment of program] obj_prog = solver.Objective() obj_prog.SetCoefficient(vara, 3 ) obj_prog.SetCoefficient(varb, 2 ) obj_prog.SetCoefficient(varc, 2 ) obj_prog.SetMaximization() # Calling solver solver.Solve() # Print segment of program print ( 'Highest objective function value = %d' % solver.Objective().Value()) print () for variable in [vara, varb, varc]: print ( '%s = %d' % (variable.name(), variable.solution_value())) Maximizationproblem() |
输出
Highest objective function value = 42 vara = 12 varb = 2 varc = 1 Process finished with exit code 0 |
结论
在本文中,我们了解了不同类型的优化以及如何在 Python 中实现这些优化。我们还了解了 ortools 和 python 包装器。此外,我们还看到了一个完整的工作代码,可以最大化一组三个线性方程中的方程。本文将有助于理解 Python 中的优化并为学习者打下基础。
参考
https://developers.google.com/optimization/introduction/python