SciPy解决线性规划问题

scipy.optimize.linprog可以解决线性规划问题

标准模型: \[ \min_x \ z= c^T x, \\ \mbox{s.t.} \ \begin{cases} A x \leq b,\\ A_{eq} x = b_{eq},\\ l \leq x \leq u . \end{cases} \] 其中\(A\)\(A_{eq}\)分别是不等约束和等号约束的系数矩阵,\(l\)\(u\)是上下界向量

用法:

linprog(c, A=None, b=None, Aeq=None, beq=None, bounds=None)

前5个参数对应标准模型,bounds是一个由(li,ui)组成的序列,表示每个xi的边界

boundsNone时,默认下界全为0,上界全为正无穷

返回的对象记为res,具有以下属性:

res.fun为目标函数的最小值,res.x为最优解

示例: \[ \min_x \ z= -x_1+4x_2, \\ \mbox{s.t.} \ \begin{cases} -3x_1+x_2 \leq 6,\\ x_1+2x_2 \leq 4,\\ x_2 \geq -3 . \end{cases} \]

两种方式求解:

1
2
3
4
5
6
7
8
9
10
11
12
from scipy.optimize import linprog
import numpy as np
c = [-1, 4]
A = [[-3, 1], [1, 2]]
b = [6, 4]
bounds = [[None, None], [-3, None]]
# A = [[-3, 1], [1, 2], [0, -1]]
# b = [6, 4, 3]
# bounds = [[None, None], [None, None]] # 与bounds=None区别
res = linprog(c, A, b, None, None, bounds)
print(res.fun)
print(res.x)

输出:

1
2
-21.99999984082492
[ 9.99999989 -2.99999999]