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}\) 是矩阵。

或者，那是：

• minimize

  c @ x
  

• 使得

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

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

参数:

c一维数组

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

A_ub2-D 数组, 可选

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

b_ub1-D 数组，可选

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

A_eq2-D 数组, 可选

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

b_eq1-D 数组，可选

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

边界序列，可选

x 中每个元素的 (min, max) 对序列，定义了该决策变量的最小值和最大值。如果提供了一个单一的元组 (min, max)，那么 min 和 max 将作为所有决策变量的界限。使用 None 表示没有界限。例如，默认界限 (0, None) 表示所有决策变量都是非负的，而 (None, None) 对表示完全没有界限，即所有变量都可以是任何实数。

方法str, 可选

用于解决标准形式问题的算法。支持 ‘highs’ (默认), ‘highs-ds’, ‘highs-ipm’, ‘interior-point’ (遗留), ‘revised simplex’ (遗留), 和 ‘simplex’ (遗留)。遗留方法已被弃用，并将在 SciPy 1.11.0 中移除。

回调可调用，可选

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

x一维数组

当前的解向量。

乐趣浮动

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

成功布尔

True 当算法成功完成时。

slack一维数组

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

con一维数组

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

阶段整数

正在执行的算法阶段。

状态整数

一个表示算法状态的整数。

0 : 优化正常进行。

1 : 迭代次数达到上限。

2 : 问题似乎是不可行的。

3 : 问题似乎是无界的。

4 : 遇到的数值困难。

nit整数

当前迭代次数。

消息str

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

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

选项dict, 可选

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

maxiter整数

要执行的最大迭代次数。默认值：参见特定方法的文档。

disp布尔

设置为 True 以打印收敛消息。默认值：False。

预解布尔

设置为 False 以禁用自动预解。默认值：True。

除 HiGHS 求解器外，所有方法也接受：

tol浮动

一个容差，用于确定残差何时“足够接近”零，可以被视为精确为零。

自动缩放布尔

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

rr布尔

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

rr_method字符串

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

SVD:

对矩阵重复执行奇异值分解，根据与零奇异值对应的左奇异向量中的非零元素检测冗余行。当矩阵接近满秩时，可能会很快。

pivot:

使用 [5] 中提出的算法来识别冗余行。

ID

使用随机插值分解。识别矩阵转置中未在矩阵的满秩插值分解中使用的列。

None:

如果矩阵接近满秩，即矩阵的秩与行数之差小于五，则使用“svd”。否则，使用“pivot”。此默认行为可能会在没有事先通知的情况下更改。

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

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

x01-D 数组，可选

猜测决策变量的值，这些值将由优化算法进行细化。此参数目前仅由 ‘revised simplex’ 方法使用，并且只有在 x0 表示一个基本可行解时才能使用。

完整性1-D 数组或整数，可选

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

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

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

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

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

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

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

此参数目前仅由 'highs' 方法使用，其他情况下被忽略。

返回:

res优化结果

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

x一维数组

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

乐趣浮动

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

slack一维数组

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

con一维数组

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

成功布尔

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

状态整数

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

0 : 优化成功终止。

1 : 迭代次数达到上限。

2 : 问题似乎是不可行的。

3 : 问题似乎是无界的。

4 : 遇到的数值困难。

nit整数

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

消息str

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

参见

show_options

求解器接受的附加选项。

注释

本节描述了可通过 ‘method’ 参数选择的可用求解器。

‘highs-ds’ 和 ‘highs-ipm’ 分别是 HiGHS 单纯形法和内点法求解器的接口 [13]。’highs’`（默认）会在这两者之间自动选择。这些是 SciPy 中最快的线性规划求解器，特别是在处理大型、稀疏问题时；这两者中哪一个更快取决于具体问题。其他求解器（’interior-point’、’revised simplex’` 和 ‘simplex’）是遗留方法，将在 SciPy 1.11.0 中移除。

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

Added in version 1.6.0.

方法 interior-point 使用原始-对偶路径跟踪算法，如 [4] 中所述。该算法支持稀疏约束矩阵，并且通常比单纯形方法更快，特别是对于大型稀疏问题。然而，需要注意的是，返回的解可能比单纯形方法的解稍微不精确，并且通常不会对应于由约束定义的多面体的顶点。

Added in version 1.0.0.

方法 revised simplex 使用修订的单纯形法，如 [9] 所述，不同的是，它有效地维护并使用基矩阵的因子分解 [11]，而不是其逆矩阵，来在算法的每次迭代中求解线性系统。

Added in version 1.3.0.

方法 simplex 使用的是Dantzig单纯形算法的传统全表实现 [1] ， [2] （不是 Nelder-Mead单纯形）。该算法包含在内是为了向后兼容和教育目的。

Added in version 0.15.0.

在应用 interior-point、revised simplex 或 simplex 之前，基于 [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]

丹齐格，乔治·B.，《线性规划及其扩展》。兰德公司研究报告，普林斯顿大学出版社，新泽西州普林斯顿，1963年。

[2]

Hillier, S.H. 和 Lieberman, G.J. (1995), “数学规划导论”, McGraw-Hill, 第4章。

[3]

Bland, Robert G. 新的单纯形法有限枢轴规则。运筹学数学 (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. “在大规模线性规划中寻找所有线性相关行。” 《优化方法与软件》 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. “线性规划中的预处理.” 数学规划 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. “单纯形法的稳定化。” 《数值数学杂志》16.5 (1971): 414-434.

[12]

Tomlin, J. A. “关于线性规划问题的缩放。” 《数学规划研究》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. “并行化对偶修正单纯形法。” 《数学规划计算》, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

示例

Try it in your browser!

考虑以下问题：

\[\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

Go BackOpen In Tab