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

二. 變量

我們使用 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')

三. 限制條件

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

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

在我們的案例中，我們可以用來生產單位的資源數量有限。換句話說，我們不能花費超過我們所擁有的資源：例如，用於招募單位的食物不能高於 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

四. 目標

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

在線性編程中，這個函數必須是線性的（就像約束條件一樣），所以形式爲 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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/cc6_uccG-k6xXs2RLlBrDQ