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 指定。

参数:

c1-D 数组: 线性目标函数的系数，需要使其最小化。
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 的对应元素。
bounds序列，可选: (min, max) 对的序列，用于 x中的每个元素，定义该决策变量的最小值和最大值。使用 None 表示没有界限。默认情况下，界限为 (0, None)（所有决策变量为非负）。如果提供了单个元组 (min, max)，则 min 和 max 作为所有决策变量的界限。
methodstr: 这是有关“high-ipm”的方法特定文档。 ‘highs-ipm’、‘highs-ds’、‘interior-point’ (默认)、‘revised simplex’和‘simplex’ (遗留)也可用。

返回:

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。此数量通常也称为“松弛”。
边界np.ndarray: 目标函数对不等式约束右侧的灵敏度（偏导数），b_ub。

等式线性优化结果

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

残差np.ndarray: 等式约束条件 (一般为零) 的残差，b_eq - A_eq @ x。
边界np.ndarray: 目标函数对等式约束右侧的灵敏度（偏导数），b_eq。

下界，上界OptimizeResult

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

残差np.ndarray: 数量（x - lb（下界）或ub - x（上界））的（标称正）值。
边界np.ndarray: 目标函数对下界和上界bounds的灵敏度（偏导数）。

另请参见

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

选项:

——-
maxiterint: 在任一阶段执行的最大迭代数。对于‘highs-ipm’，这并不包括交叉迭代的数目。默认值为平台上int的最大可能值。
dispbool（默认值：False）: 如果要在优化期间将优化状态的指示器打印到控制台，则将其设置为True。
presolvebool（默认值：True）: Presolve尝试识别平凡不可行之处、平凡无界之处并简化问题，然后再将其发送到主求解器。通常建议保留默认设置True；如果要禁用 presolve，则将其设置为False。
time_limitfloat: 求解问题分配的最大时间（秒）；默认值为平台上double的最大可能值。
dual_feasibility_tolerance双（默认值：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’ 是 interior-point method[13] 的 C++ 实现的包装器；它具有交叉例程，因此它与单纯形求解器的精度相同。方法 ‘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