个人数学建模算法库之线性规划模型

模型描述

$$\begin{gathered} minz=f^{T}x(1) \\ s.t.\{\begin{array}{ll}Ax\le b& (2)\\ Aeq\cdot x=beq& (3)\\ lb\le x\le ub& (4)\end{array} \\ f、x、b、beq、lb、ub均为列向量 \\ f称为价值向量,b称为资源向量 \\ lb为决策变量的下界,ub为决策变量的上界 \\ A、Aeq为矩阵 \end{gathered}$$

• (1)为目标函数，$minz$ 称为最优值

• $x$的分量称为决策变量

• (2),(3),(4)为约束条件，用$s.t.$（subject to) 表示

• (2)为不等式约束条件;(3)为等式约束条件;(4)为上下界约束条件

• 满足约束条件的解$x=(x_1,x_2,\cdot \cdot \cdot ,x_n)$ 称为线性规划的可行解

• 可行解中使得目标函数达到最值的解称为最优解

Matlab代码

基于求解器

将模型化为标准形式，直接使用函数

[x,fval] = linprog(f,A,b)
[x,fval] = linprog(f,A,b,Aeq,beq)
[x,fval] = linprog(f,A,b,Aeq,beq,lb,ub)
1
2
3

• x为最优解
• fval为目标函数的最优值

如:

$$\begin{gathered} maxz=2x_1+3x_2-5x_3 \\ s.t.\{\begin{array}{l}{x}_1+x_2+x_3=7\\ 2x_1-5x_2+x_3\ge 10\\ x_1+3x_2+x_3\le 12\\ x_1,x_2,x_3\ge 0\end{array} \end{gathered}$$

化为标准形式:

$$\begin{gathered} min-z=-2x_1-3x_2+5x_3 \\ s.t.\{\begin{array}{l}-2x_1+5x_2-x_3\le -10\\ x_1+3x_2+x_3\le 12\\ x_1+x_2+x_3=7\\ 0\le x_1,x_2,x_3\end{array} \end{gathered}$$

则
$$f=\left[\begin{array}{c}-2\\ -3\\ 5\end{array}\right],x=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]$$

$$A=\left[\begin{array}{ccc}-2& 5& -1\\ 1& 3& 1\end{array}\right],b=\left[\begin{array}{c}-10\\ 12\end{array}\right]$$

$$Aeq=\left[\begin{array}{ccc}1& 1& 1\end{array}\right],beq=[7]$$
$$lb=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$$
故编写代码如下:

clc,clear

% 目标函数
f = [-2; -3; 5] ;

% 不等式约束
A=[-2 5 -1; 1 3 1];
b=[-10; 12];

% 等式约束
Aeq=[1, 1, 1];
beq= 7;

% 上下界约束
lb=[0; 0; 0];

% 求解
[x,zmin]=linprog(f,A,b,Aeq,beq,lb);
zmax=-zmin;

% 展示结果
display(x);
display(zmax);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Optimal solution found.


x =

    6.4286
    0.5714
         0


zmax =

   14.5714
1
2
3
4
5
6
7
8
9
10
11
12
13

基于问题

先建立线性规划的问题模型,决策变量,再添加限制条件,最后进行求解

clc,clear

% 建立问题
prob = optimproblem('ObjectiveSense','max');

% 创建决策变量
x=optimvar('x',3,'LowerBound',0);

% 目标函数
prob.Objective = 2*x(1)+3*x(2)-5*x(3);

% 约束条件
prob.Constraints.con1 = x(1)+x(2)+x(3)==7;
prob.Constraints.con2 = 2*x(1)-5*x(2)+x(3)>=10;
prob.Constraints.con3 = x(1)+3*x(2)+x(3)<=12;

% 求解
[result,zmin]=solve(prob);
zmax=-zmin;

% 展示结果
display(result.x);
display(zmax);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Solving problem using linprog.

Optimal solution found.

    6.4286
    0.5714
         0


zmax =

   14.5714
1
2
3
4
5
6
7
8
9
10
11
12

Python代码

Scipy库

# 导库
from scipy import optimize
import numpy as np

# 目标函数
c = np.array([-2, -3, 5])  # 可用行向量表示列向量

#不等式约束
A = np.array([[-2, 5, -1], [1, 3, 1]])
b = np.array([-10, 12])

# 等式约束
Aeq = np.array([[1, 1, 1]])
beq = np.array([7])

# 上下界约束
lb = [0, 0, 0]
ub = [None, None, None]
bounds = np.array(list(zip(lb, ub)))   # 各个决策变量的(左界,右界)元组组成的数组

# 求解
result = optimize.linprog(c, A, b, Aeq, beq, bounds)
x=result.x
zmax=-result.fun
print(result)
print(f"最优解:{x}\n最优值:{zmax}")
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
26

 con: array([1.80712245e-09])
     fun: -14.571428565645084
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([-2.24599006e-10,  3.85714286e+00])
  status: 0
 success: True
       x: array([6.42857143e+00, 5.71428571e-01, 2.35900788e-10])
最优解:[6.42857143e+00 5.71428571e-01 2.35900788e-10]
最优值:14.571428565645084
1
2
3
4
5
6
7
8
9
10

• fun为目标函数的最优值
• x为最优解

Plup库

# 导库
import pulp
import numpy as np

# 初始化线性规划问题模型
pro = pulp.LpProblem()

# 创建决策变量
lb = [0, 0, 0]
ub = [None, None, None]
bounds = np.array(list(zip(lb, ub)))
x = np.array([
    pulp.LpVariable(f'x{i}',
                    lowBound=bounds[i - 1][0],
                    upBound=bounds[i - 1][1]) for i in [1, 2, 3]
])

#建立目标函数
c = np.array([-2, -3, 5])
pro += pulp.lpDot(c, x)

# 不等式约束
A = np.array([[-2, 5, -1], [1, 3, 1]])
b = np.array([-10, 12])
for i in range(len(A)):
    pro += (pulp.lpDot(A[i], x) <= b[i])  # 添加限制条件

# 等式约束
Aeq = np.array([[1, 1, 1]])
beq = np.array([7])
for i in range(len(Aeq)):
    pro += (pulp.lpDot(Aeq[i], x) == beq[i])

#求解
pro.solve()

#输出结果
print(pro)
print(f'最优值：{-pulp.value(pro.objective)}')  
print(f'最优解：{[pulp.value(var) for var in x]}')
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

• pro.objective为最优解
• x代表决策变量数组([x1,x2,x3]),使用pulp.value查看x中各决策变量的值

NoName:
MINIMIZE
-2*x1 + -3*x2 + 5*x3 + 0
SUBJECT TO
_C1: - 2 x1 + 5 x2 - x3 <= -10

_C2: x1 + 3 x2 + x3 <= 12

_C3: x1 + x2 + x3 = 7

VARIABLES
x1 Continuous
x2 Continuous
x3 Continuous

最优值：14.57142851
最优解：[6.4285714, 0.57142857, 0.0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17