linprog(method=’highs’)#
- 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将用作所有决策变量的界限。- method字符串
这是‘highs’方法的特定文档，它会在‘highs-ds’和‘highs-ipm’之间自动选择。还提供了‘interior-point’（默认）、‘revised simplex’和‘simplex’（旧版）。
- integrality一维数组或整数，可选
指示每个决策变量的整数约束类型。
0: 连续变量；无整数约束。1: 整数变量；决策变量必须是边界内的整数。2: 半连续变量；决策变量必须在边界内或取值为0。3: 半整数变量；决策变量必须是边界内的整数或取值为0。默认情况下，所有变量都是连续的。
对于混合整数约束，提供形状为c.shape的数组。若要从较短输入推断每个决策变量的约束，将使用np.broadcast_to将参数广播到c.shape。
当前仅
'highs'方法使用此参数，其他方法会忽略它。
- 返回:
- resOptimizeResult
由这些字段组成的
scipy.optimize.OptimizeResult- x一维数组
使目标函数最小化且满足约束条件的决策变量的值。
- fun浮点数
目标函数
c @ x的最佳值。- slack一维数组
闲置变量（名义上为正）的值，
b_ub - A_ub @ x。- con一维数组
（理论为零）等式约束的残差，
b_eq - A_eq @ x。- successbool
True当算法成功找到一个最优解时。- statusint
表示算法退出状态的一个整数。
0: 优化成功终止。1: 达到迭代或时间限制。2: 问题似乎不可行。3: 问题似乎是无界的。4: HiGHS 求解器遇到了问题。- messagestr
算法退出状态的字符串描述符。
- nitint
执行的总迭代数。对于 HiGHS 单纯形方法，这包括所有阶段中的迭代。对于 HiGHS 内点法，这不包括交叉迭代。
- crossover_nitint
对于 HiGHS 内点法，在交叉例程期间执行的主/对偶推动次数。对于 HiGHS 单纯形方法，这是
0。- 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
目标函数的边界的灵敏度（偏导数）。
另请参见
有关其余参数的文档，请参阅
scipy.optimize.linprog- 选项:
- ——-
- maxiterint
在任一阶段执行的最大迭代次数。对于‘highs-ipm’，这不包括交叉迭代次数。默认值是平台上最大的可能
int值。- dispbool (default:
False) 如果要在优化期间将优化状态的指标打印到控制台，则设置为
True。- presolvebool (default:
True) Presolve 尝试识别微不足道的不可行性、识别微不足道的无限性，并在将其发送到主求解器之前简化问题。通常建议保留默认设置
True；如果要禁用 presolve，则设置为False。- time_limitfloat
解决问题时允许的最大时间（以秒为单位）；默认值是平台上
double最大的可能值。- dual_feasibility_tolerancedouble (default: 1e-07)
对于‘highs-ds’的双重可行性容差。将其与
primal_feasibility_tolerance的最小值用于‘highs-ipm’的可行性容差。- primal_feasibility_tolerancedouble (default: 1e-07)
对于‘highs-ds’的主可行性容差。将其与
dual_feasibility_tolerance的最小值用于‘highs-ipm’的可行性容差。- ipm_optimality_tolerancedouble (default:
1e-08) 对于‘highs-ipm’的最优容差。允许的最小值为 1e-12。
- simplex_dual_edge_weight_strategystr (default: None)
单纯形对偶边缘权重的策略。默认情况下，
None自动选择以下选项之一。'dantzig'使用丹齐希的原始策略选择最小的约简成本。'devex'使用 [15] 中描述的策略。steepest使用 [16] 中描述的准确的最陡边缘策略。'steepest-devex'从准确的最陡边缘策略开始，直到计算变得过于昂贵或不准确，然后切换到德夫克斯方法。目前，
None始终选择'steepest-devex'，但随着新选项的出现，这一点可能会发生变化。- mip_rel_gapdouble (默认值：None)
MIP 求解器的终止准则：当原始目标值与对偶目标边界的差距（按原始目标值缩放）<= mip_rel_gap 时，求解器将终止。
- unknown_optionsdict
此特定求解器不使用的可选参数。如果
unknown_options非空，则会发出一个警告，列出所有未使用选项。
笔记
方法 ‘highs-ds’ 是 C++ 高性能对偶修订单纯形实现 (HSOL) [13]、[14] 的包装器。方法 ‘highs-ipm’ 是一个 C++ 实现的i内p点m方法的包装器 [13]；它具有交叉例程，因此其准确性与单纯形求解器相当。方法 ‘highs’ 在这两者之间自动选择。对于涉及
linprog的新代码，我们建议显式选择这三个方法值中的一个，而不是 ‘interior-point’（默认）、‘revised simplex’ 和 ‘simplex’（旧版）。结果字段 ineqlin、eqlin、lower 和 upper 都包含 marginals，即目标函数相对于每个约束条件右侧的部分导数。这些偏导数也称为“拉格朗日乘数”、“对偶值”和“影子价格”。marginals 的符号约定与许多非线性求解器产生的拉格朗日乘数相反。
参考资料