用Python进行线性编程
使用谷歌OR-工具的数学优化指南
图片由作者提供，表情符号由 OpenMoji(CC BY-SA 4.0)
线性编程是一种优化具有多个变量和约束条件的任何问题的技术。这是一个简单但强大的工具，每个数据科学家都应该掌握。
想象一下，你是一个招募军队的战略家。你有
三种资源。食物、木材和黄金
三个单位：️剑客，弓箭手，和马兵。
骑士比弓箭手更强，而弓箭手又比剑客更强。下表提供了每个单位的成本和力量。
图片由作者提供
现在我们有1200食物，800木材，600黄金。考虑到这些资源，我们应该如何最大化我们的军队的力量？
我们可以简单地找到能效/成本比最好的单元，尽可能多地取用它们，然后用另外两个单元重复这一过程。但这种 "猜测和检查 "的解决方案甚至可能不是最优的......
现在想象一下，我们有数以百万计的单位和资源：以前的贪婪策略很可能完全错过了最佳解决方案。使用机器学习算法（如遗传算法）来解决这个问题是可能的，但我们也不能保证解决方案是最优的。
幸运的是，有一种方法可以以最佳方式解决我们的问题：线性编程（或称线性优化），它属于 operations research(OR)的一部分。在这篇文章中，我们将用它来寻找剑客、弓箭手和骑兵的最佳数量，以建立具有最高力量的军队。
◆ 一. 求解器
在Python中，有不同的线性编程库，如多用途的SciPy、适合初学者的PuLP、详尽的Pyomo，以及其他许多库。
今天，我们将使用 Google OR-Tools，它对用户非常友好，带有几个预包装的求解器，可以通过以下方式运行本教程中的代码 Google Colab notebook.
如果安装不成功，请重新启动内核并再试一次：它有时会失败。¯\_(ツ)_/¯
!python -m pip install --upgrade --user -q ortools所有这些库都有一个隐藏的好处：它们作为接口，可以用不同的求解器使用同一个模型。解算器如 Gurobi, Cplex，或 SCIP有他们自己的API，但是他们所创建的模型是与特定的求解器相联系的。
OR-Tools允许我们使用一种抽象的（而且是相当pythonic的）方式来为我们的问题建模。然后我们可以选择一个或几个求解器来找到一个最佳解决方案。因此，我们建立的模型是高度可重复使用的
图片由作者提供
OR-Tools带有自己的线性规划求解器，称为GLOP（谷歌线性优化包）。它是一个开源项目，由谷歌的运筹学团队创建，用C++编写。
其他求解器也是可用的，比如SCIP，这是一个优秀的非商业求解器，创建于2005年，并更新和维护至今。我们也可以使用流行的商业选项，如Gurobi和Cplex。然而，我们需要将它们安装在OR-Tools之上，并获得适当的许可（这可能相当昂贵）。现在，让我们试试GLOP。
# Import OR-Tools wrapper for linear programmingfrom ortools.linear_solver import pywraplp# Create a solver using the GLOP backendsolver = pywraplp.Solver('Maximize army power', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)◆ 二.变量
我们使用GLOP创建了一个OR-Tools求解器的实例。现在，如何使用线性编程？我们要定义的第一件事是我们要优化的变量。
在我们的例子中，我们有三个变量：军队中的️剑士、弓箭手和马兵的数量。OR-Tools接受三种类型的变量。
NumVar用于连续变量。
IntVar用于整数变量。
BoolVar用于布尔变量。
我们正在寻找单位的整数，所以让我们选择IntVar。然后我们需要为这些变量指定下限和上限。我们希望至少有0个单位，但我们并没有真正的上限。所以我们可以说，我们的上界是无穷大（或任何我们永远不会达到的大数字）。它可以被写成。
让我们把它翻译成代码。在OR-Tools中，Infinity被solver.infinity()所取代。除此以外，语法是非常直接的。
# Create the variables we want to optimizeswordsmen = solver.IntVar(0, solver.infinity(), 'swordsmen')bowmen = solver.IntVar(0, solver.infinity(), 'bowmen')horsemen = solver.IntVar(0, solver.infinity(), 'horsemen')◆ 三.限制条件
我们定义了我们的变量，但约束条件也同样重要。
也许与直觉相反的是，增加更多的约束条件有助于求解器更快地找到最优解。为什么会出现这种情况呢？把求解器想象成一棵树：约束条件帮助它修剪分支，减少搜索空间。
在我们的案例中，我们可以用来生产单位的资源数量有限。换句话说，我们不能花费超过我们所拥有的资源：例如，用于招募单位的食物不能高于1200。木材（800）和黄金（600）的情况也是如此。
根据我们的表格，单位有以下成本。
1个剑客 = 60 + 20。
1弓箭手 = 80 + 10 + 40。
1个骑士=140 + 100。
我们可以为每个资源写一个约束条件，如下所示。
在OR-Tools中，我们只需用solver.Add()将约束添加到我们的求解器实例中。
# Add constraints for each resourcesolver.Add(swordsmen*60 + bowmen*80 + horsemen*140 <= 1200) # Foodsolver.Add(swordsmen*20 + bowmen*10 <= 800) # Woodsolver.Add(bowmen*40 + horsemen*100 <= 600) # Gold◆ 四.目标
现在我们有了我们的变量和约束条件，我们要定义我们的目标（或目标函数）。
在线性编程中，这个函数必须是线性的（就像约束条件一样），所以形式为ax + by + cz + d。在我们的例子中，目标很明确：我们想招募具有最高力量的军队。表格给了我们以下的力量值。
1个剑客=70。
1个弓箭手=95。
1个骑士=230。
军队力量的最大化相当于每个单位的力量之和的最大化。我们的目标函数可以写成。
一般来说，只有两种类型的目标函数：最大化或最小化。在OR-Tools中，我们用以下方式声明这个目标 solver.Maximize()或 solver.Minimize().
solver.Maximize(swordsmen*70 + bowmen*95 + horsemen*230)然后我们就完成了!对任何线性优化问题进行建模有三个步骤。
用下限和上限 声明要优化的变量。
为这些变量 添加约束。
定义最大化或最小化的 目标函数。
现在已经很清楚了，我们可以要求求解器为我们找到一个最佳解决方案。
◆ 五、优化!
计算最优解是通过 solver.Solve() .这个函数返回一个状态，可以用来检查解决方案是否确实是最优的。
让我们以最佳的军队配置来打印我们能得到的最高总能效
status = solver.Solve()# If an optimal solution has been found, print resultsif status == pywraplp.Solver.OPTIMAL:
print('================= Solution =================')
print(f'Solved in {solver.wall_time():.2f} milliseconds in {solver.iterations()} iterations')
print()
print(f'Optimal power = {solver.Objective().Value()} power')
print('Army:')
print(f' - ️Swordsmen = {swordsmen.solution_value()}')
print(f' - Bowmen = {bowmen.solution_value()}')
print(f' - Horsemen = {horsemen.solution_value()}')else:
print('The solver could not find an optimal solution.')================= Solution =================
Solved in 87.00 milliseconds in 2 iterations
Optimal power = 1800.0 power
Army:
- ️Swordsmen = 6.0000000000000036
- Bowmen = 0.0
- Horsemen = 5.999999999999999
很好!解算器找到了一个最优解：我们的军队总兵力为1800，有6个剑士和6个骑兵（对不起，弓箭手！）。
让我们来解读这个结果。
解算器决定采取最大数量的骑兵（6，因为我们只有600，而且他们每个人都要花费100）。
剩余的资源用于剑客：我们还有1200-6*140=360食物，这就是为什么解算器选择6剑客的原因 。
我们可以推断出，骑兵是最好的单位，而弓箭手是最差的，因为他们根本没有被选中。
好的，但有一点很奇怪：这些数字不是圆的，尽管我们指定要整数（IntVar）。那么发生了什么？
不幸的是，回答这个问题需要深入研究线性编程......为了在这个介绍中保持简单，让我们说这是因为GLOP的原因。解算器有我们必须考虑到的特性，而GLOP并不处理整数。这又证明了建立可重复使用的模型不仅仅是方便。
我们将解释为什么GLOP会有这种奇怪的行为，以及如何在 "我的 "中修复它。
总结
我们通过这个例子看到了任何线性优化问题的五个主要步骤。
选择一个求解器：在我们的案例中，为了方便，我们选择了GLOP。
声明变量：要优化的参数是剑士、弓箭手和骑兵的数量。
宣布约束条件：这些单位中的每一个都有成本。总成本不能超过我们有限的资源。
定义目标：要最大化的标准是这支军队的总力量。它也可以是其他的东西，比如单位的数量。
优化。GLOP在不到一秒钟的时间内找到了这个问题的最佳解决方案。
图片由作者提供
这是线性规划的主要好处：算法给我们一个保证，即找到的解决方案是最优的（有一定误差）。这种保证很强大，但也有代价：模型可能非常复杂，以至于求解器需要花费数年（或更多）的时间来找到一个最优解。在这种情况下，我们有两个选择。
我们可以在一定时间后停止求解器（并可能得到一个次优答案）。
我们可以使用像遗传算法这样的元启发式方法，在短时间内计算出一个优秀的解决方案。
来源：
https://www.toutiao.com/article/7085420150341599781/?log_from=2a0ac2c70c9e1_1656998759688
“IT大咖说”欢迎广大技术人员投稿，投稿邮箱：aliang@itdks.com
IT大咖说 | 关于版权
由“IT大咖说（ID：itdakashuo）”原创的文章，转载时请注明作者、出处及微信公众号。投稿、约稿、转载请加微信：ITDKS10（备注：投稿），茉莉小姐姐会及时与您联系！
感谢您对IT大咖说的热心支持！