求解线性规划

scipy有直接求解线性规划的方法scipy.optimize.linprog.

求解线性规划指的是, 对于给定的目标函数, 在一系列线性等式和不等式的约束下, 最小化该目标函数, 得到目标函数在约束下的最小值, 以及该最小值对应的变量向量的值.

公式表示:

$$\begin{aligned} \min _{x} c^{T} x \\ \operatorname{such} \text { that } A_{u b} x & \leq b_{u b} \\ A_{e q} x &=b_{e q} \\ l \leq x & \leq u \end{aligned}$$

其中的$x$是要求解的变量, $x$, $c$, $b_{ub}$, $b_{eq}$, $l$, $u$都是向量, $A_{ub}$, $A_{eq}$是矩阵.

有两个点值得注意:

• 求解目标是最小化目标函数, 如果原目标是最大化目标函数, 必须进行转化

• 不等式约束的方向是固定的, 即上界不等式

入参

具体的出入参使用说明文档中更详细, 常用的有:

• c: 1D array

  目标函数的参数向量

• A_ub: 2D array, optional

  不等式约束的矩阵. 每行代表一个不等式的参数

• b_ub: 1D array, optional

  不等式约束的值向量. 每个元素表示一个不等式的上界, 即必须使用有上界的不等式

• A_eq: 2D array, optional

  恒等式约束的矩阵, 每行代表一个等式的参数

• b_eq: 1D array, optional

  等式约束的值向量, 每个元素表示一个等式的约束值

• bounds: sequence, optional

  约束变量向量$x$中的每个元素的可能值, bounds的长度与$x$向量长度相同. 每个元素是一个形如(min, max)的tuple, 代表这个元素的最小和最大值.

  另外如果一个元素没有约束, 用None指示, 或者只有单向边界, 如(0, None)表示该元素为非负值.

• method: {‘interior-point’, ‘revised simplex’, ‘simplex’}, optional

  求解方法, 默认为interior-point

出参

返回的结果以OptimizeResult对象承载, 通过使用其属性获取求解值, 常用的有:

• res.x: 1D array

  求解最后得到的解向量

• res.fun: float

  求解得到的目标函数的最小值

• res.success: bool

  求解结果