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{使得} \ & 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
请注意，默认情况下，除非使用
bounds指定，否则lb = 0且ub = None。- 参数:
- 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将作为所有决策变量的界限。- method字符串
这是 'highs-ds' 的特定方法文档。 'highs'、'highs-ipm'、'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整数
执行的总迭代次数。这包括所有阶段的迭代。
- crossover_nit整数
对于 HiGHS 单纯形方法，这始终为
0。对于 HiGHS 内点方法，这是在交叉例程期间执行的原始/对偶推送次数。- ineqlinOptimizeResult
与不等式约束 b_ub 对应的解和敏感度信息。一个包含以下字段的字典
- residualnp.ndnarray
松弛变量（名义上为正）的值，
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整数
在任一阶段执行的最大迭代次数。默认值是平台上
int的最大可能值。- disp布尔值 (默认值:
False) 如果要在优化期间将优化状态的指示器打印到控制台，则设置为
True。- presolve布尔值 (默认值:
True) 预处理尝试识别微不足道的不可行性、识别微不足道的无界性，并在将问题发送到主求解器之前简化问题。通常建议保留默认设置
True；如果要禁用预处理，则设置为False。- time_limit浮点数
解决问题允许的最大时间（以秒为单位）；默认值是平台上
double的最大可能值。- dual_feasibility_tolerance双精度浮点数 (默认值: 1e-07)
用于 ‘highs-ds’ 的对偶可行性容差。
- primal_feasibility_tolerance双精度浮点数 (默认值: 1e-07)
用于 ‘highs-ds’ 的原始可行性容差。
- simplex_dual_edge_weight_strategy字符串 (默认值: None)
单纯形对偶边权重的策略。默认值
None会自动选择以下策略之一。'dantzig'使用丹齐格的原始策略，选择最负的缩减成本。'devex'使用 [15] 中描述的策略。steepest使用 [16] 中描述的精确最陡边策略。'steepest-devex'开始使用精确最陡边策略，直到计算成本过高或不精确，然后切换到 devex 方法。目前，
None总是选择'steepest-devex'，但随着新选项的出现，这可能会改变。- unknown_options字典
此特定求解器未使用的可选参数。如果
unknown_options为非空，则会发出警告，列出所有未使用的选项。
注释
方法 ‘highs-ds’ 是 C++ 高性能对偶修正单纯形实现 (HSOL) 的包装器 [13], [14]。方法 ‘highs-ipm’ 是 内点法的 C++ 实现的包装器 [13]；它具有交叉例程，因此与单纯形求解器一样准确。方法 ‘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.