python数学建模--求解线性规划问题的若干种方法_python线性规划模型求解

本博客参考：《python数学实验与建模》

线性规划案例1

m a x   z = − 2 x 1 − x 2 { − x 1 + x 2 ≤ 1 , x 1 + x 2 ≥ 2 , x 1 − 2 x 2 ≤ 4 , x 2 ≥ 0 x 1 + 2 x 2 = 3.5 max \ z=-2x_1-x_2\\

$$\begin{cases} -x_1+x_2\leq 1,\\ x_1+x_2\geq2,\\ x_1-2x_2\leq 4,\\ x_2\geq0\\ x_1+2x_2=3.5& \end{cases}$$ max z=−2x1​−x2​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​−x1​+x2​≤1,x1​+x2​≥2,x1​−2x2​≤4,x2​≥0x1​+2x2​=3.5​​
本线性规划案例求解得到的最优解应为$x_1=0.5,x_2=1.5$,目标函数最优值为2.5，下面我们通过下面方法分别实现求解最优值的过程

解法一：linprog()函数

标准化
m i n   z = 2 x 1 + x 2 { − x 1 + x 2 ≤ 1 , − x 1 − x 2 ≤ − 2 , x 1 − 2 x 2 ≤ 4 , − x 2 ≤ 0 x 1 + 2 x 2 = 3.5 min \ z=2x_1+x_2\\

$$\begin{cases} -x_1+x_2\leq 1,\\ -x_1-x_2\leq-2,\\ x_1-2x_2\leq 4,\\ -x_2\leq0\\ x_1+2x_2=3.5& \end{cases}$$ min z=2x1​+x2​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​−x1​+x2​≤1,−x1​−x2​≤−2,x1​−2x2​≤4,−x2​≤0x1​+2x2​=3.5​​
代码

from scipy.optimize import linprog

# 目标函数系数
c = [2, 1]
# 不等式约束，系数
A = [[-1, 1],
     [-1, -1],
     [1, -2]]
b = [[1], [-2], [4]]
# 等式约束，系数
Aeq = [[1, 2]]
beq = [3.5]

res = linprog(c, A, b, Aeq, beq)
print(res.fun, res.x)
>>> 2.5 array([0.5,2.5])
# print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果

解法二：minimize()函数

标准化
m i n   z = 2 x 1 + x 2 { − x 1 + x 2 ≤ 1 , − x 1 − x 2 ≤ − 2 , x 1 − 2 x 2 ≤ 4 , − x 2 ≤ 0 x 1 + 2 x 2 = 3.5 min \ z=2x_1+x_2\\

$$\begin{cases} -x_1+x_2\leq 1,\\ -x_1-x_2\leq-2,\\ x_1-2x_2\leq 4,\\ -x_2\leq0\\ x_1+2x_2=3.5& \end{cases}$$ min z=2x1​+x2​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​−x1​+x2​≤1,−x1​−x2​≤−2,x1​−2x2​≤4,−x2​≤0x1​+2x2​=3.5​​

注意，minimize()函数需要将线性规划问题标准化为指定的形式，这样在定义不等式系数的时候才不会出现错误

代码

from scipy.optimize import minimize
import numpy as np

# 目标函数系数
c = np.array([2, 1])
# 不等式约束系数
A = np.array([[-1, 1],
              [-1, -1],
              [1, -2],
              [0, -1]])
b = np.array([1, -2, 4, 0])
# 目标函数
obj = lambda x: np.dot(c, x)
# 约束条件汇总，ineq代表不等式，eq代表等式
cons = ({'type': 'ineq', 'fun': lambda x: b - A @ x},
        {'type': 'ineq', 'fun': lambda x: np.array([0, 1]) @ x},
        {'type': 'eq', 'fun': lambda x: 3.5 - np.array([1, 2]) @ x})
# 约束空间     
bd = [(0, None), (0, None)]
# 注意：此处传入约束条件时要将形参和实参一一对应，否则可能报错
res = minimize(obj, np.ones(2) * 20, constraints=cons, bounds=bd)
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果

注意：

1. 向minimize()函数中传入约束条件时要将形参和实参一一对应，否则可能报错
2. 该函数使用过程中定义了很多函数，注意区别

解法三：cvxpy库

import cvxpy as cp
import numpy as np

# 定义变量
x = cp.Variable(2)
c = np.array([2, 1])
# obj=cp.Minimize(cp.sum(cp.multiply(c,x)))
# 目标函数
obj = cp.Minimize(cp.sum(x @ c))
b = np.array([1, -2, 4])
# 不等式约束系数
A = np.array([[-1, 1],
              [-1, -1],
              [1, -2]])
cons = [
    A @ x <= b,# 注意乘法运算过程中*,@,multiply()函数三者的区别
    #   cp.sum(A@x)<=b,
    x[0] + x[1] * 2 == 3.5,
    # cp.multiply(np.array([0,2]),x)==3.5,
    x[1] >= 0
]
prob = cp.Problem(obj, cons)
prob.solve(solver='GLPK_MI', verbose=True)
print(prob.value, x.value)
print(prob)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

运行结果

注意：

1. 乘法运算过程中*,@,multiply()函数三者的区别，涉及矩阵、向量、标量之间的相乘关系，处理不好很让人抓狂！建议读者查阅一下三者的区别

解法四：cvxopt库

from cvxopt import matrix, solvers

# 目标函数系数
c = matrix([2., 1])
# 不等式系数
A = matrix([[-1., 1], [-1., -1.], [1, -2], [0, -1]]).T
b = matrix([1., -2, 4, 0])
# 等式系数
Aeq = matrix([1., 2], (1, 2))# 这个地方笔者没弄明白
beq = matrix(3.5)

sol = solvers.lp(c, A, b, Aeq, beq)
print(sol['x'], sol['primal objective'])
print(sol)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行结果

1. 一个小报错：
   raise TypeError("‘A’ must be a dense or sparse ‘d’ matrix "
   TypeError: ‘A’ must be a dense or sparse ‘d’ matrix with 2 columns
   原因：使用该库求解，matix矩阵中的数据都需要时浮点数，之前Aeq=matrix([1, 2], (1, 2))，报了这个错误，修改后恢复正常
2. 注意：
   （1）matix矩阵中的数据:浮点型
   （2） 不等式系数矩阵的转置

小总结

总的来说，笔者觉得使用linprog()函数求解简单的线性规划问题比其他几种方法代码简洁得多，也更容易上手。
其他几种解法比较容易报错，特别是在约束条件的定义上，稍微不注意，代码运行后就会报错或者得到错误的结果（关于其他几种方法使用过程中需要注意的方法方面笔者已经标注在了每种方法的下方）