linprog(method=’highs-ds’)#

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{such that} \ & 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序列，可选: x 中每个元素的 (min, max) 成对序列，定义该决策变量的最小值和最大值。使用 None 表示没有界限。默认情况下，界限为 (0, None) （所有决策变量均为非负）。如果提供了单个元组 (min, max)，那么 min 和 max 将作为所有决策变量的界限。
methodstr: 这是特定于方法 'highs-ds' 的文档。也可以使用 ‘highs’、‘highs-ipm’、‘interior-point’（默认）、‘revised simplex’ 和 ‘simplex’（旧版）。

返回:

resOptimizeResult

由以下字段组成的 scipy.optimize.OptimizeResult

x1D 数组

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

funfloat

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

slack1D 数组

松弛变量（标称正值）的值，b_ub - A_ub @ x。

con1D 数组

等式约束的残差（标称零值），b_eq - A_eq @ x。

successbool

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

statusint

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

0 ：优化成功终止。

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

2 ：问题似乎不可行。

3 ：问题似乎无界。

4 ：HiGHS 求解器遇到问题。

messagestr

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

nitint

执行的总迭代次数。这包括所有阶段中的迭代次数。

crossover_nitint

对于 HiGHS 单纯形法，此值始终为 0。对于 HiGHS 内点法，这是在交错例程期间执行的原对偶推动次数。

ineqlinOptimizeResult

与不等式约束对应的解和灵敏度信息，b_ub。指定所有字段的字典

残差np.ndnarray: 松弛变量的（通常为正）值，b_ub - A_ub @ x。此数量通常也称为“松弛”。
Marginalnp.ndarray: 目标函数对不等式约束右手边的敏感度（偏导数），b_ub.

eqlinOptimizeResult

与等式约束对应的解和灵敏度信息，b_eq。指定所有字段的字典

残差np.ndarray: 等式约束的残差（标称零值），b_eq - A_eq @ x。
Marginalnp.ndarray: 目标函数对不等式约束右手边的灵敏度（偏导数），b_eq.

lower, upperOptimizeResult

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

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

请参见

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

选项:

——-

maxiterint

在任一阶段执行的最大迭代次数。默认值为平台上int可能的最大值。

dispbool (默认:False)

如果要在优化过程中将优化状态指示符打印到控制台，则设为True。

presolvebool (默认:True)

预求解尝试识别琐碎不可行性、识别琐碎无界性和在将问题发送到主求解器之前对其进行简化。通常建议保持默认设置True；如果要禁用预求解，请设为False。

time_limitfloat

解决问题分配的最大时间（以秒为单位）；默认值是平台上 double 可用的最大值。

dual_feasibility_tolerancedouble（默认值为：1e-07）

‘highs-ds’ 的对偶可行度容差。

primal_feasibility_tolerancedouble（默认值为：1e-07）

‘highs-ds’ 的原始可行度容差。

simplex_dual_edge_weight_strategystr（默认值为：None）

单纯形对偶边权值策略。默认值 None 自动选择以下一项。

'dantzig' 使用 Dantzig 的原始策略选择最负约简成本。

'devex' 使用 [15] 中描述的策略。

steepest 使用 [16] 中描述的确切最陡峭边策略。

'steepest-devex' 从确切的最陡峭边策略开始，直到计算成本太高或不够精确，然后切换到 devex 方法。

目前，None 始终选择 'steepest-devex'，但可能会随着新选项的出现而发生变化。

unknown_optionsdict

此特定求解器不使用的可选参数。如果 unknown_options 为空，则会发出警告，列出所有未使用的选项。

说明

方法 ‘highs-ds’ 是 C++ 高性能对偶修正单纯形实现（HSOL） [13]、[14] 的包装器。方法 ‘highs-ipm’ 是一个 i 内点-p 法 method[13] 的 C++ 实现的包装器；它具有一个交叉例程，因此它和单纯形求解器一样精确。方法 ‘highs’ 自动在两者之间进行选择。对于涉及 linprog 的新代码，我们建议明确选择这三个方法值中的一个，而不是 ‘interior-point’（默认）、‘revised simplex’ 和 ‘simplex’（传统）。

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

参考

[13] (1,2)

Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. “HiGHS - high performance software for linear optimization.” https://highs.dev/

[14]

Huangfu, Q. and Hall, J. A. J. “Parallelizing the dual revised simplex method.” Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

[15]

Harris, Paula MJ. “Pivot selection methods of the Devex LP code.” Mathematical programming 5.1 (1973): 1-28.

[16]

Goldfarb, Donald, and John Ker Reid. “A practicable steepest-edge simplex algorithm.” Mathematical Programming 12.1 (1977): 361-371.