scipy.optimize.linprog¶

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='interior-point', callback=None, options=None, x0=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序列，可选

一系列的 (min, max) 中每个元素的对 x ，定义该决策变量的最小值和最大值。使用 None 以表明没有边界。默认情况下，界限为 (0, None) (所有决策变量都是非负的)。如果单个元组 (min, max) 被提供，则 min 和 max 将作为所有决策变量的界限。

method字符串，可选

用于解决标准型问题的算法。 'highs-ds' ， 'highs-ipm' ， 'highs' ， 'interior-point' (默认)， 'revised simplex' ，以及 'simplex' (传统)是受支持的。

callback可调用，可选

如果提供了回调函数，则算法的每次迭代至少会调用一次回调函数。回调函数必须接受单个 scipy.optimize.OptimizeResult 由以下字段组成：

X一维阵列

当前解向量。

有趣的浮动

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

成功布尔尔

True 当算法成功完成时。

松弛一维阵列

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

圆锥体一维阵列

等式约束的(标称为零)残差， b_eq - A_eq @ x 。

相位集成

正在执行的算法的阶段。

状态集成

表示算法状态的整数。

0 ：名义上进行优化。

1 ：已达到迭代限制。

2 问题似乎是不可行的。

3 ：问题似乎是无界的。

4 ：遇到了数字上的困难。

NIT集成: 当前迭代号。
消息应力: 算法状态的字符串描述符。

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

optionsDICT，可选

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

最大值集成: 要执行的最大迭代次数。默认值：请参阅特定于方法的文档。
显示布尔尔: 设置为 True 若要打印收敛消息，请执行以下操作。默认值： False 。
预解布尔尔: 设置为 False 要禁用自动预解决，请执行以下操作。默认值： True 。

除HIGS解算器之外的所有方法也接受：

公差浮动

一种公差，它确定残差何时“足够接近”于零，从而被认为恰好为零。

自动缩放布尔尔

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

RR布尔尔

设置为 False 要禁用自动冗余删除，请执行以下操作。默认值： True 。

rr_method字符串

用于在预解算后从等式约束矩阵中标识和删除冗余行的方法。对于输入密集的问题，可用于删除冗余的方法包括：

“SVD”：: 对矩阵重复执行奇异值分解，基于对应于零个奇异值的左奇异向量中的非零来检测冗余行。当矩阵接近满秩时可能很快。
“Pivot”：: 使用中提供的算法 [5] 以标识冗余行。
“id”：: 使用随机化插值分解。标识矩阵的满秩插值分解中未使用的矩阵转置的列。
无：: 如果矩阵接近满秩，即矩阵秩与行数之差小于5，则使用“Svd”。如果不是，则使用“Pivot”。此默认行为可能会更改，恕不另行通知。

默认值：无。对于输入稀疏的问题，将忽略此选项，并使用中提供的基于透视的算法 [5] 是使用的。

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

x0一维阵列，可选

决策变量的猜测值，用优化算法进行精化。此参数当前仅由“修订后的单纯型”方法使用，并且只有在以下情况下才能使用 x0 表示基本可行解决方案。

退货

resOptimizeResult

A scipy.optimize.OptimizeResult 由以下字段组成：

X一维阵列

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

有趣的浮动

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

松弛一维阵列

松弛变量的(标称为正)值， b_ub - A_ub @ x 。

圆锥体一维阵列

等式约束的(标称为零)残差， b_eq - A_eq @ x 。

成功布尔尔

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

状态集成

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

0 ：优化已成功终止。

1 ：已达到迭代限制。

2 问题似乎是不可行的。

3 ：问题似乎是无界的。

4 ：遇到了数字上的困难。

NIT集成

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

消息应力

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

参见

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

注意事项

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

'highs-ds' 和 'highs-ipm' 是HIGH单纯形法和内点法求解器的接口 [13], 分别为。 'highs' 自动在两者之间进行选择。这些是SciPy中最快的线性规划解算器，特别是对于大型稀疏问题；这两个中哪一个更快取决于问题。 'interior-point' 是默认设置，因为在最近添加高点解算器之前，它是最快、最健壮的方法。 'revised simplex' 对于它所解决的问题，它比内点更准确。 'simplex' 是遗留方法，包含它是为了向后兼容和教育目的。

方法 highs-ds 是C++高性能双重修订单工实现(HSOL)的包装器 [13], [14]. 方法 highs-ipm 是C++实现的 i n前面-p oint m 方法 [13]; 它的特点是交叉例程，因此它与单纯形求解器一样精确。方法 最高纪录 自动在两者之间进行选择。有关涉及以下内容的新代码 linprog ，我们建议显式选择这三个方法值之一。

1.6.0 新版功能.

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

1.0.0 新版功能.

方法 修正单纯形 使用修改后的单纯形法，如中所述 [9], 除了因式分解 [11] 在算法的每一次迭代中，有效地维护和使用基矩阵的(而不是其逆矩阵)来求解线性系统。

1.3.0 新版功能.

方法单工使用Dantzig单纯形算法的传统全表实现 [1], [2] ( not 内尔德-米德单纯形)。包含此算法是为了向后兼容和教育目的。

0.15.0 新版功能.

在申请之前 interior-point ， 修正单纯形 ，或单工，这是一个基于以下条件的预解算过程 [8] 试图找出琐碎的不可行性、琐碎的无界性和潜在的问题简单化。具体地说，它检查：

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

如果PRESOVE显示问题是无界的(例如，无约束和无界的变量具有负成本)或不可行(例如， A_eq 中的非零值对应 b_eq )，求解器将终止，并显示相应的状态代码。请注意，一旦检测到任何无边界的迹象，预解算就会终止；因此，可能会报告问题是无边界的，而实际上问题是不可行的(但尚未检测到不可行)。因此，如果知道问题是否实际上是不可行的很重要，请使用选项再次解决问题 presolve=False 。

如果在预解的单次传递中既没有检测到不可行，也没有检测到无界，则在可能的情况下收紧边界，并且从问题中去除固定变量。然后，线性相关的行 A_eq 删除矩阵(除非它们表示不可行)，以避免主要求解例程中的数值困难。请注意，也可以删除几乎线性相关的行(在规定的容差范围内)，这在极少数情况下可能会更改最佳解决方案。如果这是一个问题，请从您的问题描述中消除冗余，并使用选项运行 rr=False 或 presolve=False 。

此处可以进行几个潜在的改进：中概述的其他解决前检查 [8] 应实现预解算例程，则应多次运行预解算例程(直到不能进行进一步简化为止)，更多的效率改进来自 [5] 应在冗余删除例程中实现。

预解后，通过将(收紧的)简单界转化为上界约束，引入不等式约束的非负松弛变量，并将无界变量表示为两个非负变量之间的差值，将问题转化为标准形式。或者，通过平衡自动调整问题的比例 [12]. 所选择的算法解决了标准形式问题，并且后处理例程将结果转换为原始问题的解。

参考文献

1: 乔治·B·丹齐格著，“线性规划与扩展”。普林斯顿大学兰德公司研究研究。出版社，普林斯顿，新泽西州，1963年
2: 李国民(1995)，“数学规划导论”，麦格劳-希尔出版社，第4章。
3: 单纯形法的新的有限旋转规则。运筹学数学(2)，1977年：第103-107页。
4: 题名/责任者：Aleason，and Knud D.Andersen，and Knud D.Andersen.“用于线性规划的MOSEK内点优化器：齐次算法的一种实现。”高性能优化。斯普林格美国，2000年。197-232。
5(1,2,3): 作者：Erling D.“在大规模线性规划中查找所有线性相关行。”优化方法和软件6.3(1995)：219-227。
6: 作者：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: 富勒，这是罗伯特。“用内点法解线性规划”未出版的课程笔记，2005年8月26日。2017年2月25日可在http://www.4er.org/CourseNotes/Book%20B/B-III.pdf上查看
8(1,2): 题名/责任者：Aleason，and Knud D.Andersen，and Knud D.Andersen.“线性规划中的预求解。”“数学规划”71.2(1995)：221-245。
9: 题名/责任者：A.“线性规划导论”“雅典娜科学”1(1997)：997。
10: Andersen，Erling D.等人。大规模线性规划的内点法实现。高等商学院/日内瓦大学，1996年。
11: 作者：Richard H.“单纯形法的稳定化。”“Numerische数学杂志”16.5(1971)：414-434。
12: 作者：J.A.“关于比例线性规划问题。”数学规划研究4(1975)：146-166。
13(1,2,3): 首页--期刊主要分类--期刊细介绍--期刊题录与文摘--期刊详细文摘内容“High-用于线性优化的高性能软件。”在https://www.maths.ed.ac.uk/hall/HiGHS/#guide上访问2020年4月16日
14: 黄福，Q.和Hall，J.A.J.“将对偶修正单纯形法并行化。”数学规划计算，10(1)，119-142,2018。DOI：10.1007/s12532-0170130-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\) ，因为默认情况下变量为非负数。将系数收集到数组和元组中后，此问题的输入为：

>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bounds = (None, None)
>>> x1_bounds = (-3, None)
>>> from scipy.optimize import linprog
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])

请注意，的默认方法是 linprog 是“内点”，本质上是近似的。

>>> print(res)
     con: array([], dtype=float64)
     fun: -21.99999984082494 # may vary
 message: 'Optimization terminated successfully.'
     nit: 6 # may vary
   slack: array([3.89999997e+01, 8.46872439e-08] # may vary
  status: 0
 success: True
       x: array([ 9.99999989, -2.99999999]) # may vary

如果你需要更高的精确度，可以试试“修正后的单纯形”。

>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='revised simplex')
>>> print(res)
     con: array([], dtype=float64)
     fun: -22.0 # may vary
 message: 'Optimization terminated successfully.'
     nit: 1 # may vary
   slack: array([39.,  0.]) # may vary
  status: 0
 success: True
       x: array([10., -3.]) # may vary

您可以使用 options 参数，例如，以限制最大迭代次数。

>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds],
...               options={'maxiter': 4})
>>> print(res)
    con: array([], dtype=float64)
    fun: -21.35207150630407 # may vary
message: 'The iteration limit was reached before the algorithm converged.'
    nit: 4
  slack: array([37.19406046,  0.5727398 ])
 status: 1
success: False
      x: array([ 9.4021973 , -2.98746855])

root(method=‘df-sane’)

linprog(method=‘simplex’)