此页面由 Cloud Translation API 翻译。

适用于 Python 的 OR 工具使用入门

以下各部分将帮助您开始使用适用于 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 工具线性求解器。

创建变量。

# 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 的值，用于最大限度提高目标函数：