本頁面由 Cloud Translation API 翻譯而成。

開始使用 Python 適用的 OR-Tools

下列各節將協助您開始使用 Python 適用的 OR-Tools：

什麼是最佳化問題？
解決 Python 中的最佳化問題
其他 Python 範例
確定您想要解決的問題類型

什麼是最佳化問題？

最佳化的目標是透過眾多可能的解決方案找出最佳解決方案。(有時您會滿意找到任何可行的解決方案；或者，OR 工具也能滿足您的需求)。

這是常見的最佳化問題。假設某家貨運公司使用卡車運送給客戶，公司每天都必須將包裹指派給卡車，然後為每個卡車選擇路徑來遞送包裹。視卡車的總行駛距離和其他因素而定，每個可能的包裹和路線指派作業都會產生費用。問題是選擇費用最低的套件和路徑指派作業。

如同所有最佳化問題，這個問題具有下列要素：

目標：要最佳化的數量。在上述範例中，目標是盡可能降低費用。如要設定最佳化問題，您必須定義函式，針對任何可能的解決方案計算目標值。這就是「目標函式」。在上述範例中，目標函式會計算任何套件和路徑指派作業的總費用。

「最佳」解決方案是指目標函式的值最佳。(「最佳」可能是最大值或最小值)。
限制：根據問題的特定需求，限制一組可能的解決方案。舉例來說，如果貨運公司無法將指定權重以上的包裹指派給卡車，就會對解決方案設下限制。

「可行」的解決方案是指能夠滿足問題的所有指定限制，卻又無法達到最佳狀態的方法。

解決最佳化問題的第一步，就是找出目標和限制。

解決 Python 中的最佳化問題

接下來，我們會舉例說明最佳化問題，並示範如何在 Python 中設定及解決問題。

線性最佳化範例

線性最佳化 (或線性程式設計) 是最舊且最廣泛使用的最佳化領域之一，其中目標函式與限制可以寫成線性運算式。以下是這類問題的簡單範例。

將 3x + y 最大化，但必須遵守下列限制：

0 ≤ x ≤ 1
0 ≤ y ≤ 2
x + y ≤ 2

本例中的目標函式為 3x + y。目標函式和限制都是由線性運算式提供，因此為線性問題。

解決問題的主要步驟

每種語言的基本步驟都是相同的：

匯入必要的程式庫
宣告解題工具。
建立變數
定義限制條件
定義目標函式
叫用解題工具
顯示結果。

Python 程式

本節將逐步說明 Python 程式，以設定並解決問題。

步驟如下：

匯入必要程式庫。

from ortools.init.python import init
from ortools.linear_solver import pywraplp

宣告解題工具。

# Create the linear solver with the GLOP backend.
solver = pywraplp.Solver.CreateSolver("GLOP")
if not solver:
    print("Could not create solver GLOP")
    return

pywraplp 是基礎 C++ 解題工具的 Python 包裝函式。引數 "GLOP" 會指定 GLOP，即 OR-Tools 線性解題器。

建立變數。

# Create the variables x and y.
x_var = solver.NumVar(0, 1, "x")
y_var = solver.NumVar(0, 2, "y")

print("Number of variables =", solver.NumVariables())

定義限制。前兩個限制條件 0 &leq; x ≤ 1 和 0 &leq; y ≤ 2 已由變數的定義設定。以下程式碼定義了限制 x + y &leq; 2：

infinity = solver.infinity()
# Create a linear constraint, x + y <= 2.
constraint = solver.Constraint(-infinity, 2, "ct")
constraint.SetCoefficient(x_var, 1)
constraint.SetCoefficient(y_var, 1)

print("Number of constraints =", solver.NumConstraints())

方法 SetCoefficient 會在限制條件的運算式中設定 x 和 y 的係數。

定義目標函式。

# Create the objective function, 3 * x + y.
objective = solver.Objective()
objective.SetCoefficient(x_var, 3)
objective.SetCoefficient(y_var, 1)
objective.SetMaximization()

SetMaximization 方法宣告此情況是最大化問題。

叫用解題工具並顯示結果。

print(f"Solving with {solver.SolverVersion()}")
result_status = solver.Solve()
print(f"Status: {result_status}")
if result_status != pywraplp.Solver.OPTIMAL:
    print("The problem does not have an optimal solution!")
    if result_status == pywraplp.Solver.FEASIBLE:
        print("A potentially suboptimal solution was found")
    else:
        print("The solver could not solve the problem.")
        return

print("Solution:")
print("Objective value =", objective.Value())
print("x =", x_var.solution_value())
print("y =", y_var.solution_value())

完成計畫

完整計畫如下所示。

from ortools.init.python import init
from ortools.linear_solver import pywraplp


def main():
    print("Google OR-Tools version:", init.OrToolsVersion.version_string())

    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        print("Could not create solver GLOP")
        return

    # Create the variables x and y.
    x_var = solver.NumVar(0, 1, "x")
    y_var = solver.NumVar(0, 2, "y")

    print("Number of variables =", solver.NumVariables())

    infinity = solver.infinity()
    # Create a linear constraint, x + y <= 2.
    constraint = solver.Constraint(-infinity, 2, "ct")
    constraint.SetCoefficient(x_var, 1)
    constraint.SetCoefficient(y_var, 1)

    print("Number of constraints =", solver.NumConstraints())

    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x_var, 3)
    objective.SetCoefficient(y_var, 1)
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    result_status = solver.Solve()

    print(f"Status: {result_status}")
    if result_status != pywraplp.Solver.OPTIMAL:
        print("The problem does not have an optimal solution!")
        if result_status == pywraplp.Solver.FEASIBLE:
            print("A potentially suboptimal solution was found")
        else:
            print("The solver could not solve the problem.")
            return

    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x_var.solution_value())
    print("y =", y_var.solution_value())

    print("Advanced usage:")
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")


if __name__ == "__main__":
    init.CppBridge.init_logging("basic_example.py")
    cpp_flags = init.CppFlags()
    cpp_flags.stderrthreshold = True
    cpp_flags.log_prefix = False
    init.CppBridge.set_flags(cpp_flags)
    main()

執行程式

您可以按照下列步驟執行上述程式：

複製上述程式碼並貼到新檔案中，然後儲存為 program.py。
開啟指令視窗，然後切換至您儲存 program.py 的目錄。在命令提示字元中輸入：
```
python relative/path/to/program.py
```
，其中 relative/path/to/ 是您儲存程式的目錄路徑。

程式會傳回可將目標函式最大化的 x 和 y 值：

Solution:
x =  1.0
y =  1.0

確定您想要解決的問題類型

世上有許多不同類型的最佳化問題，每種問題都有不同的方法和演算法，能找出最佳解決方案。

在開始編寫能夠解決最佳化問題的程式之前，您需要先找出要解決的問題類型，然後選擇適當的「解決方案」；這是用來找出最佳解決方案的演算法。

以下簡單介紹 OR 工具本身的問題類型，並提供本指南中各問題的解決步驟連結。

線性最佳化
限制最佳化
混合整數最佳化
作業
排程
包裝
轉送
網路流程

線性最佳化

如上一節所述，線性最佳化問題是指目標函式和限制在變數中的線性運算式。

在 OR-Tools 中，這類問題的主要解題器是線性最佳化解題工具，它其實是數個不同程式庫的線性和混合整數最佳化包裝函式，包括第三方程式庫。

進一步瞭解線性最佳化

混合整數最佳化

混合整數最佳化問題是指部分或所有變數必須為整數。其中一個例子就是「指派問題」，其中一組工作站必須指派給一組工作。如果將指定的工作站指派給特定工作，您可以為每個工作站和工作定義一個變數，其值為 1，否則為 0。在本例中，變數只能採用 0 或 1 值。

進一步瞭解混合整數最佳化

限制最佳化

限制最佳化或限製程式設計 (CP) 會從極大量的候選項目中找出可行的解決方案，並根據任意限制來建模問題。CP 是以可行性 (尋找可行的解決方案) 為基礎，而不是最佳化 (尋找最佳解決方案)，其重心在於限制和變數，而非客觀功能。不過，CP 還是可以用來解決最佳化問題，只要比較所有可行解決方案的客觀函式值即可。

進一步瞭解限制最佳化