【python数据分析】用scipy.optimize.linprog实现线性规划

小半 • 2022年12月19日下午4:31 • Python • 阅读 363

因为近期要参加一个建模比赛，没有安装MATLAB，所以熟悉下算法的python实现，本篇为用scipy.optimize.linprog线性规划。

函数文档参考scipy.optimize.linprog — SciPy v1.8.0 Manual

线性规划主要解决下面这种问题：

$\underset{x}{min} c^{T}x \\ s.t. \begin{cases} & \ Ax\leq b\\ & \ Aeq\cdot x=beq \\ & \ lb \leq x \leq ub \end{cases}$ （第一次用LaTex，公式做的不好看，不是这样要转化一下，如求最大值）

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method=’simplex’, callback=None, options=None)

其中，c是价值向量；A_ub和b_ub对应线性不等式约束；A_eq和b_eq对应线性等式约束；bounds对应公式中的lb和ub，决策向量的下界和上界；method是求解器的类型，如单纯形法；其他的参数暂时不用。

例题1:

$min f=-1\times x_{0} + 4\times x_{1}\\ s.t.\begin{cases} & -3\times x_{0} +1\times x_{1} \leq 6 \\ & 1\times x_{0} + 2\times x_{1} \leq 4 \\ & x_{1} \geq -3 \end{cases}$

用scipy.optimize.linprog计算

from scipy.optimize import linprog
C = [-1,4] 
A = [[-3,1],[1,2]]
b = [6,4]
X0_bounds = [None,None]
X1_bounds = [-3,None]
res = linprog(C,A,b,bounds=(X0_bounds,X1_bounds))
print(res)

     fun: -22.0
 message: 'Optimization terminated successfully.'
     nit: 1
   slack: array([39.,  0.])
  status: 0
 success: True
       x: array([10., -3.])

最优解为-22，x0=10，x1=-3.

例题2:

如果是求最大值

$max f=-1\times x_{0} + 4\times x_{1}\\ s.t.\begin{cases} & -3\times x_{0} +1\times x_{1} \leq 6 \\ & 1\times x_{0} + 2\times x_{1} \leq 4 \\ & x_{1} \geq -3 \end{cases}$

我们转化为

$min -f=1\times x_{0} + -4\times x_{1}\\ s.t.\begin{cases} & -3\times x_{0} +1\times x_{1} \leq 6 \\ & 1\times x_{0} + 2\times x_{1} \leq 4 \\ & x_{1} \geq -3 \end{cases}$

用scipy.optimize.linprog计算

from scipy.optimize import linprog
C = [1,-4] 
A = [[-3,1],[1,2]]
b = [6,4]
X0_bounds = [None,None]
X1_bounds = [-3,None]
res = linprog(C,A,b,bounds=(X0_bounds,X1_bounds))
print(res)

     fun: -11.428571428571429
 message: 'Optimization terminated successfully.'
     nit: 2
   slack: array([0., 0.])
  status: 0
 success: True
       x: array([-1.14285714,  2.57142857])

最优解为11.428571428571429，x0=-1.14285714，x1=2.57142857。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/63093.html