linprog(method='highs-ipm')#

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)

线性规划：使用 HiGHS 内点求解器最小化受线性等式和不等式约束的线性目标函数。

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

\[\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) 对的序列，定义该决策变量的最小值和最大值。使用 None 表示没有边界。默认情况下，边界为 (0, None) （所有决策变量都是非负的）。如果提供了单个元组 (min, max)，则 min 和 max 将作为所有决策变量的边界。
methodstr: 这是 'highs-ipm' 的特定方法文档。 'highs-ipm', 'highs-ds', 'interior-point' (默认), '修正单纯形', 和 '单纯形' (旧版) 也是可用的。

返回值:

resOptimizeResult

一个 scipy.optimize.OptimizeResult，包含以下字段

x一维数组

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

fun浮点数

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

slack一维数组

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

con一维数组

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

success布尔值

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

status整数

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

0 : 优化成功终止。

1 : 达到迭代次数或时间限制。

2 : 问题似乎不可行。

3 : 问题似乎无界。

4 : HiGHS 求解器遇到了问题。

message字符串

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

nit整数

执行的总迭代次数。对于 HiGHS 内点法，这不包括交叉迭代。

crossover_nit整数

在 HiGHS 内点法的交叉例程中执行的原始/对偶推送的次数。

ineqlinOptimizeResult

与不等式约束 b_ub 对应的解和灵敏度信息。一个由以下字段组成的字典

residualnp.ndarray: 松弛变量的（名义上为正）值，b_ub - A_ub @ x。此数量通常也称为“松弛”。
marginalsnp.ndarray: 目标函数相对于不等式约束 b_ub 的右侧的灵敏度（偏导数）。

eqlinOptimizeResult

与等式约束 b_eq 对应的解和灵敏度信息。一个由以下字段组成的字典

residualnp.ndarray: 等式约束的（名义上为零）残差，b_eq - A_eq @ x。
marginalsnp.ndarray: 目标函数相对于等式约束 b_eq 的右侧的灵敏度（偏导数）。

lower, upperOptimizeResult

与决策变量 bounds 的下限和上限相对应的解和灵敏度信息。

residualnp.ndarray: 数量 x - lb （下限）或 ub - x （上限）的（名义上为正）值。
marginalsnp.ndarray: 目标函数相对于下限和上限 bounds 的灵敏度（偏导数）。

另请参见

有关其余参数的文档，请参见 scipy.optimize.linprog

选项:

-----
maxiter整数: 在任一阶段执行的最大迭代次数。对于 ‘highs-ipm’，这不包括交叉迭代的次数。默认值是平台上 int 的最大可能值。
dispbool (默认值: False): 如果要在优化过程中将优化状态的指示器打印到控制台，则设置为 True。
presolvebool (默认值: True): 预求解尝试识别微不足道的不可行性、识别微不足道的无界性，并在将其发送到主求解器之前简化问题。通常建议保持默认设置 True；如果禁用预求解，则设置为 False。
time_limitfloat: 解决问题分配的最大时间（以秒为单位）；默认值是平台上 double 的最大可能值。
dual_feasibility_tolerancedouble (默认值: 1e-07): 此值和 primal_feasibility_tolerance 的最小值用于 ‘highs-ipm’ 的可行性容差。
primal_feasibility_tolerancedouble (默认值: 1e-07): 此值和 dual_feasibility_tolerance 的最小值用于 ‘highs-ipm’ 的可行性容差。
ipm_optimality_tolerancedouble (默认值: 1e-08): ‘highs-ipm’ 的最优性容差。允许的最小值是 1e-12。
unknown_optionsdict: 此特定求解器未使用的可选参数。如果 unknown_options 非空，则会发出警告，列出所有未使用的选项。

备注

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

结果字段 ineqlin、eqlin、lower 和 upper 都包含 marginals，或目标函数相对于每个约束右侧的偏导数。这些偏导数也称为“拉格朗日乘数”、“对偶值”和“影子价格”。 marginals 的符号约定与许多非线性求解器产生的拉格朗日乘数的符号相反。

参考文献

[13] (1,2)

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