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
请注意,除非使用
bounds
指定,否则默认情况下lb = 0
且ub = None
。- 参数:
- c1-D array
要最小化的线性目标函数的系数。
- A_ub2-D array, optional
不等式约束矩阵。
A_ub
的每一行指定x
上的线性不等式约束的系数。- b_ub1-D array, optional
不等式约束向量。每个元素表示
A_ub @ x
对应值的上限。- A_eq2-D array, optional
等式约束矩阵。
A_eq
的每一行指定x
上的线性等式约束的系数。- b_eq1-D array, optional
等式约束向量。
A_eq @ x
的每个元素必须等于b_eq
的对应元素。- boundssequence, optional
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 array
在满足约束条件的同时使目标函数最小化的决策变量值。
- funfloat
目标函数
c @ x
的最优值。- slack1D array
松弛变量的(名义上为正的)值,
b_ub - A_ub @ x
。- con1D array
等式约束的(名义上为零的)残差,
b_eq - A_eq @ x
。- successbool
当算法成功找到最优解时为
True
。- statusint
表示算法退出状态的整数。
0
: 优化成功终止。1
: 达到迭代或时间限制。2
: 问题似乎不可行。3
: 问题似乎无界。4
: HiGHS 求解器遇到问题。- messagestr
算法退出状态的字符串描述。
- nitint
执行的总迭代次数。这包括所有阶段的迭代。
- crossover_nitint
对于 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
- 选项:
- ——-
- maxiterint
在任一阶段中执行的最大迭代次数。默认值为平台上
int
的最大可能值。- dispbool (default:
False
) 如果要在优化期间将优化状态指示器打印到控制台,则设置为
True
。- presolvebool (default:
True
) 预求解尝试在将问题发送到主求解器之前,识别微不足道的不可行性,识别微不足道的无界性,并简化问题。通常建议保留默认设置
True
;如果要禁用预求解,则设置为False
。- time_limitfloat
分配给解决问题的最大时间(秒);默认值为平台上
double
的最大可能值。- dual_feasibility_tolerancedouble (default: 1e-07)
‘highs-ds’ 的对偶可行性容差。
- primal_feasibility_tolerancedouble (default: 1e-07)
‘highs-ds’ 的原始可行性容差。
- simplex_dual_edge_weight_strategystr (default: 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’ 是 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.