scipy.optimize.

linprog#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)[源代码]#

线性规划：最小化受线性等式和不等式约束的线性目标函数。

线性规划解决以下形式的问题

\[\begin{split}\min_x \ & c^T x \\ \mbox{使得} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

其中 \(x\) 是决策变量的向量；\(c\)、\(b_{ub}\)、\(b_{eq}\)、\(l\) 和 \(u\) 是向量；\(A_{ub}\) 和 \(A_{eq}\) 是矩阵。

或者，它是

最小化
```
c @ x
```

使得

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

请注意，默认情况下 lb = 0 且 ub = None。可以使用 bounds 指定其他边界。

参数:

c一维数组

要最小化的线性目标函数的系数。

A_ub二维数组，可选

不等式约束矩阵。A_ub 的每一行都指定了 x 上线性不等式约束的系数。

b_ub一维数组，可选

不等式约束向量。每个元素都表示 A_ub @ x 相应值的上限。

A_eq二维数组，可选

等式约束矩阵。A_eq 的每一行都指定了 x 上线性等式约束的系数。

b_eq一维数组，可选

等式约束向量。A_eq @ x 的每个元素必须等于 b_eq 的相应元素。

bounds序列，可选

为 x 中的每个元素定义的 (min, max) 对的序列，用于定义该决策变量的最小值和最大值。如果提供单个元组 (min, max)，则 min 和 max 将用作所有决策变量的边界。使用 None 表示没有边界。例如，默认边界 (0, None) 表示所有决策变量均为非负数，而 (None, None) 对表示根本没有边界，即允许所有变量为任何实数。

method字符串，可选

用于解决标准形式问题的算法。支持以下方法。

旧版方法已弃用，将在 SciPy 1.11.0 中删除。

callback可调用对象，可选

如果提供了回调函数，则该函数将在算法的每次迭代中至少调用一次。回调函数必须接受单个 scipy.optimize.OptimizeResult，该对象包含以下字段

x一维数组

当前解向量。

fun浮点数

目标函数 c @ x 的当前值。

success布尔值

当算法成功完成时为 True。

slack一维数组

松弛的（名义上为正）值，b_ub - A_ub @ x。

con一维数组

等式约束的（名义上为零）残差，b_eq - A_eq @ x。

phase整数

正在执行的算法阶段。

status整数

表示算法状态的整数。

0：优化按名义进行。

1：达到迭代限制。

2：问题似乎不可行。

3：问题似乎无界。

4：遇到数值困难。

nit整数

当前迭代次数。

message字符串

算法状态的字符串描述符。

HiGHS 方法当前不支持回调函数。

options字典，可选

求解器选项的字典。所有方法都接受以下选项

maxiter整数: 要执行的最大迭代次数。默认值：请参阅特定于方法的文档。
disp布尔值: 设置为 True 可打印收敛消息。默认值：False。
presolve布尔值: 设置为 False 可禁用自动预处理。默认值：True。

除 HiGHS 求解器之外的所有方法也都接受

tol浮点数

一个公差，用于确定残差何时“足够接近”于零而被视为精确的零。

autoscale布尔值

设置为 True 可自动执行平衡。如果约束中的数值相差几个数量级，请考虑使用此选项。默认值：False。

rr布尔值

设置为 False 可禁用自动冗余删除。默认值：True。

rr_method字符串

用于在预处理后识别和删除等式约束矩阵中的冗余行的方法。对于具有密集输入的问题，可用于删除冗余的方法为

SVD:: 在矩阵上重复执行奇异值分解，基于与零奇异值对应的左奇异向量中的非零值来检测冗余行。当矩阵接近满秩时，速度可能很快。
pivot:: 使用 [5] 中提出的算法来识别冗余行。
ID:: 使用随机插值分解。识别矩阵转置中未在矩阵的满秩插值分解中使用的列。
None:: 如果矩阵接近满秩，即矩阵秩与行数之差小于 5，则使用 svd。如果不是，则使用 pivot。此默认行为可能会更改，恕不另行通知。

默认值：None。对于具有稀疏输入的问题，将忽略此选项，并且使用 [5] 中提出的基于枢轴的算法。

有关特定于方法的选项，请参阅 show_options('linprog')。

x0一维数组，可选

决策变量的猜测值，将由优化算法进行细化。此参数目前仅由 ‘修订单纯形’ 方法使用，并且只有当 x0 表示基本可行解时才可以使用。

integrality一维数组或整数，可选

指示每个决策变量的整数约束类型。

0 : 连续变量；无整数约束。

1 : 整数变量；决策变量必须是 bounds 内的整数。

2 : 半连续变量；决策变量必须在 bounds 内，或者取值 0。

3 : 半整数变量；决策变量必须是 bounds 内的整数，或者取值 0。

默认情况下，所有变量都是连续的。

对于混合整数约束，请提供形状为 c.shape 的数组。要从较短的输入推断每个决策变量的约束，该参数将使用 numpy.broadcast_to 广播到 c.shape。

此参数目前仅由 ‘highs’ 方法使用，否则将被忽略。

返回:

resOptimizeResult

一个 scipy.optimize.OptimizeResult，包含以下字段。请注意，这些字段的返回类型可能取决于优化是否成功，因此建议在依赖其他字段之前检查 OptimizeResult.status。

x一维数组

在满足约束条件的同时，使目标函数最小化的决策变量的值。

fun浮点数

目标函数 c @ x 的最优值。

slack一维数组

松弛变量的（名义上为正）值，b_ub - A_ub @ x。

con一维数组

等式约束的（名义上为零）残差，b_eq - A_eq @ x。

success布尔值

当算法成功找到最优解时为 True。

status整数

表示算法退出状态的整数。

0 : 优化成功终止。

1：达到迭代限制。

2：问题似乎不可行。

3：问题似乎无界。

4：遇到数值困难。

nit整数

所有阶段执行的总迭代次数。

message字符串

算法退出状态的字符串描述。

另请参阅

show_options: 求解器接受的其他选项。

注释

本节介绍可以通过 ‘method’ 参数选择的可用求解器。

‘highs-ds’ 和 ‘highs-ipm’ 分别是 HiGHS 单纯形和内点法求解器的接口 [13]。‘highs’（默认）在这两者之间自动选择。它们是 SciPy 中最快的线性规划求解器，特别是对于大型稀疏问题；这两个中哪个更快取决于具体问题。当 HiGHS 方法支持 callback 时，其他求解器是遗留方法，将被删除。

方法 ‘highs-ds’ 是 C++ 高性能对偶修正单纯形实现（HSOL）的包装器 [13], [14]。方法 ‘highs-ipm’ 是内点法 C++ 实现的包装器 [13]；它具有交叉例程，因此它与单纯形求解器一样准确。方法 ‘highs’ 在两者之间自动选择。对于涉及 linprog 的新代码，我们建议显式选择这三个方法值之一。

1.6.0 版本中新增。

方法 ‘interior-point’ 使用 [4] 中概述的原始对偶路径跟踪算法。此算法支持稀疏约束矩阵，并且通常比单纯形方法更快，特别是对于大型稀疏问题。但是请注意，返回的解可能比单纯形方法的解略微不准确，并且通常不会与约束定义的多元体的顶点对应。

1.0.0 版本中新增。

方法 ‘修订单纯形’ 使用 [9] 中描述的修订单纯形方法，除了基础矩阵的因式分解 [11]（而不是其逆）被有效地维护并用于求解算法每次迭代中的线性系统。

1.3.0 版本中新增。

方法 ‘单纯形’ 使用 Dantzig 单纯形算法的传统全表实现 [1], [2]（不是 Nelder-Mead 单纯形）。此算法包含用于向后兼容和教育目的。

0.15.0 版本中新增。

在应用 ‘interior-point’、‘修订单纯形’ 或 ‘单纯形’ 之前，基于 [8] 的预求解过程会尝试识别微不足道的可行性问题、微不足道的无界性以及潜在的问题简化。具体而言，它会检查：

A_eq 或 A_ub 中的零行，表示微不足道的约束；
A_eq 和 A_ub 中的零列，表示无约束变量；
A_eq 中的单列，表示固定变量；以及
A_ub 中的单列，表示简单边界。

如果预求解发现问题是无界的（例如，无约束且无界的变量具有负成本）或不可行的（例如，A_eq 中的零行对应于 b_eq 中的非零值），则求解器将以相应的状态代码终止。请注意，一旦检测到任何无界迹象，预求解就会终止；因此，当问题实际上不可行时，可能会将问题报告为无界（但尚未检测到不可行）。因此，如果知道问题是否真的不可行很重要，请使用选项 presolve=False 再次求解问题。

如果在预求解的单次遍历中既未检测到不可行性，也未检测到无界性，则在可能的情况下会收紧边界，并从问题中删除固定变量。然后，会删除 A_eq 矩阵的线性相关行（除非它们表示不可行性），以避免主求解例程中的数值困难。请注意，也可能会删除（在规定公差范围内）几乎线性相关的行，这在极少数情况下可能会改变最优解。如果担心这种情况，请消除问题表述中的冗余，并使用选项 rr=False 或 presolve=False 运行。

这里可以进行一些潜在的改进：应该实现 [8] 中概述的其他预求解检查，应该多次运行预求解例程（直到无法进行进一步的简化），并且应该在冗余删除例程中实现 [5] 中的更多效率改进。

预求解后，通过将（收紧的）简单边界转换为上限约束、为不等式约束引入非负松弛变量，以及将无界变量表示为两个非负变量之间的差，将问题转换为标准形式。或者，可以通过均衡 [12] 自动缩放问题。所选算法求解标准形式问题，后处理例程将结果转换为原始问题的解。

参考文献

[1]

Dantzig, George B., Linear programming and extensions. Rand Corporation Research Study Princeton Univ. Press, Princeton, NJ, 1963

[2]

Hillier, S.H. 和 Lieberman, G.J. (1995), “Introduction to Mathematical Programming”, McGraw-Hill, 第 4 章。

[3]

Bland, Robert G. 单纯形方法的新有限旋转规则。Operations Research 数学 (2), 1977: pp. 103-107。

[4]

Andersen, Erling D. 和 Knud D. Andersen。“用于线性规划的 MOSEK 内点优化器：同质算法的实现”。高性能优化。Springer US, 2000. 197-232。

[5] (1,2,3)

Andersen, Erling D. “查找大规模线性规划中的所有线性相关行”。Optimization Methods and Software 6.3 (1995): 219-227。

[6]

Freund, Robert M. “基于牛顿方法的线性规划的原始对偶内点方法”。未发表的课程笔记，2004 年 3 月。可于 2017 年 2 月 25 日在 https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf 获取

[7]

Fourer, Robert. “通过内点法求解线性规划”。未发表的课程笔记，2005 年 8 月 26 日。可于 2017 年 2 月 25 日在 http://www.4er.org/CourseNotes/Book%20B/B-III.pdf 获取

[8] (1,2)

Andersen, Erling D. 和 Knud D. Andersen。“线性规划中的预求解”。Mathematical Programming 71.2 (1995): 221-245。

[9]

Bertsimas, Dimitris 和 J. Tsitsiklis。“线性规划导论”。Athena Scientific 1 (1997): 997。

[10]

Andersen, Erling D. 等人。大规模线性规划内点方法的实现。HEC/日内瓦大学，1996 年。

[11]

Bartels, Richard H. “单纯形方法的稳定”。Journal in Numerische Mathematik 16.5 (1971): 414-434。

[12]

Tomlin, J. A. “关于缩放线性规划问题”。Mathematical Programming Study 4 (1975): 146-166。

[13] (1,2,3)

Huangfu, Q., Galabova, I., Feldmeier, M. 和 Hall, J. A. J. “HiGHS - 用于线性优化的高性能软件”。https://highs.dev/

[14]

Huangfu, Q. 和 Hall, J. A. J. “对偶修正单纯形法的并行化”。Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

示例

考虑以下问题

\[\begin{split}\min_{x_0, x_1} \ -x_0 + 4x_1 & \\ \mbox{使得} \ -3x_0 + x_1 & \leq 6,\\ -x_0 - 2x_1 & \geq -4,\\ x_1 & \geq -3.\end{split}\]

该问题并非以 linprog 接受的形式呈现。这很容易解决，只需将“大于”不等式约束转换为“小于”不等式约束，方法是将两边都乘以因子 \(-1\)。还要注意，最后一个约束实际上是简单的界限 \(-3 \leq x_1 \leq \infty\)。最后，由于对 \(x_0\) 没有界限，我们必须显式指定界限 \(-\infty \leq x_0 \leq \infty\)，因为变量的默认值是非负数。将系数收集到数组和元组后，此问题的输入为

>>> from scipy.optimize import linprog
>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bounds = (None, None)
>>> x1_bounds = (-3, None)
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])
>>> res.fun
-22.0
>>> res.x
array([10., -3.])
>>> res.message
'Optimization terminated successfully. (HiGHS Status 7: Optimal)'

边际值（又名对偶值/影子价格/拉格朗日乘数）和残差（松弛变量）也是可用的。

>>> res.ineqlin
  residual: [ 3.900e+01  0.000e+00]
 marginals: [-0.000e+00 -1.000e+00]

例如，由于与第二个不等式约束相关的边际值为 -1，我们预计如果我们将一个小的量 eps 添加到第二个不等式约束的右侧，目标函数的最优值将减少 eps

>>> eps = 0.05
>>> b[1] += eps
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.05

此外，由于第一个不等式约束的残差为 39，我们可以在不影响最优解的情况下将第一个约束的右侧减少 39。

>>> b = [6, 4]  # reset to original values
>>> b[0] -= 39
>>> linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds]).fun
-22.0