用Python進行線性編程-魔扣目錄

使用谷歌OR-工具的數學優化指南

圖片由作者提供，表情符號由 OpenMoji(CC BY-SA 4.0)

線性編程是一種優化具有多個變量和約束條件的任何問題的技術。這是一個簡單但強大的工具，每個數據科學家都應該掌握。

想象一下，你是一個招募軍隊的戰略家。你有

三種資源。食物、木材和黃金
三個單位：?劍客，弓箭手，和馬兵。

騎士比弓箭手更強，而弓箭手又比劍客更強。下表提供了每個單位的成本和力量。

圖片由作者提供

現在我們有1200食物，800木材，600黃金。考慮到這些資源，我們應該如何最大化我們的軍隊的力量？

我們可以簡單地找到能效/成本比最好的單元，盡可能多地取用它們，然后用另外兩個單元重復這一過程。但這種 "猜測和檢查 "的解決方案甚至可能不是最優的......

現在想象一下，我們有數以百萬計的單位和資源：以前的貪婪策略很可能完全錯過了最佳解決方案。使用機器學習算法（如遺傳算法）來解決這個問題是可能的，但我們也不能保證解決方案是最優的。

幸運的是，有一種方法可以以最佳方式解決我們的問題：線性編程（或稱線性優化），它屬于 operations research(OR)的一部分。在這篇文章中，我們將用它來尋找劍客、弓箭手和騎兵的最佳數量，以建立具有最高力量的軍隊。

I. 求解器

在Python/ target=_blank class=infotextkey>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 programming
from ortools.linear_solver import pywraplp

# Create a solver using the GLOP backend
solver = pywraplp.Solver('Maximize army power', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

II.變量

我們使用GLOP創建了一個OR-Tools求解器的實例。現在，如何使用線性編程？我們要定義的第一件事是我們要優化的變量。

在我們的例子中，我們有三個變量：軍隊中的?劍士、弓箭手和馬兵的數量。OR-Tools接受三種類型的變量。

NumVar用于連續變量。
IntVar用于整數變量。
BoolVar用于布爾變量。

我們正在尋找單位的整數，所以讓我們選擇IntVar。然后我們需要為這些變量指定下限和上限。我們希望至少有0個單位，但我們并沒有真正的上限。所以我們可以說，我們的上界是無窮大（或任何我們永遠不會達到的大數字）。它可以被寫成。

讓我們把它翻譯成代碼。在OR-Tools中，Infinity被solver.infinity()所取代。除此以外，語法是非常直接的。

# Create the variables we want to optimize
swordsmen = solver.IntVar(0, solver.infinity(), 'swordsmen')
bowmen = solver.IntVar(0, solver.infinity(), 'bowmen')
horsemen = solver.IntVar(0, solver.infinity(), 'horsemen')

?? III.限制條件

我們定義了我們的變量，但約束條件也同樣重要。

也許與直覺相反的是，增加更多的約束條件有助于求解器更快地找到最優解。為什么會出現這種情況呢？把求解器想象成一棵樹：約束條件幫助它修剪分支，減少搜索空間。

在我們的案例中，我們可以用來生產單位的資源數量有限。換句話說，我們不能花費超過我們所擁有的資源：例如，用于招募單位的食物不能高于1200。木材（800）和黃金（600）的情況也是如此。

根據我們的表格，單位有以下成本。

1個劍客 = 60 + 20。
1弓箭手 = 80 + 10 + 40。
1個騎士=140 + 100。

我們可以為每個資源寫一個約束條件，如下所示。

在OR-Tools中，我們只需用solver.Add()將約束添加到我們的求解器實例中。

# Add constraints for each resource
solver.Add(swordsmen*60 + bowmen*80 + horsemen*140 <= 1200) # Food
solver.Add(swordsmen*20 + bowmen*10 <= 800) # Wood
solver.Add(bowmen*40 + horsemen*100 <= 600) # Gold

IV.目標

現在我們有了我們的變量和約束條件，我們要定義我們的目標（或目標函數）。

在線性編程中，這個函數必須是線性的（就像約束條件一樣），所以形式為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 results
if 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個騎兵（對不起，弓箭手！）。

讓我們來解讀這個結果。