✅作者简介：人工智能专业本科在读，喜欢计算机与编程，写博客记录自己的学习历程。
🍎个人主页：
小嗷犬的个人主页
🍊个人网站：
小嗷犬的技术小站
🥭个人信条：为天地立心，为生民立命，为往圣继绝学，为万世开太平。
什么是线性规划问题
线性规划问题
是指在一组
线性不等式约束条件
下，求解一个
线性目标函数
的最大值或最小值的问题。
如何使用 MATLAB 解决线性规划问题
常见的线性规划问题通常类似于以下形式：
max
Z
=
4000
x
1
+
3000
x
2
\begin{equation} \max \quad Z=4000 x_{1}+3000 x_{2} \end{equation}
max
Z
=
4000
x
1
+
3000
x
2
s.t.
{
2
x
1
+
x
2
≤
10
x
1
+
x
2
≤
8
x
2
≤
7
x
1
,
x
2
≥
0
\begin{equation} \text { s.t. } \begin{cases} & 2 x_{1}+x_{2} \leq 10 \\ & x_{1}+x_{2} \leq 8 \\ & x_{2} \leq 7 \\ & x_{1}, x_{2} \geq 0 \end{cases} \end{equation}
s.t.
⎩
⎨
⎧
2
x
1
+
x
2
≤
10
x
1
+
x
2
≤
8
x
2
≤
7
x
1
,
x
2
≥
0
其中，公式1为目标函数，公式2为约束条件。
为了便于求解，我们可以将公式1和公式2分别写成矩阵形式：
max
Z
=
[
4000
3000
]
⋅
[
x
1
x
2
]
\begin{equation} \max \quad Z=\begin{bmatrix} 4000 & 3000 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \end{equation}
max
Z
=
[
4000
3000
]
⋅
[
x
1
x
2
]
s.t.
{
[
2
1
1
1
0
1
]
⋅
[
x
1
x
2
]
≤
[
10
8
7
]
x
1
,
x
2
≥
0
\begin{equation} \text { s.t. } \left\{ \begin{array}{} \begin{bmatrix} 2 & 1 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \leq \begin{bmatrix} 10 \\ 8 \\ 7 \end{bmatrix} \\ x_{1}, x_{2} \geq 0 \end{array} \right. \end{equation}
s.t.
⎩
⎨
⎧
2
1
0
1
1
1
⋅
[
x
1
x
2
]
≤
10
8
7
x
1
,
x
2
≥
0
为了统一最大目标函数问题和最小目标函数问题，我们将目标函数的符号取反，即：
min
−
Z
=
[
−
4000
−
3000
]
⋅
[
x
1
x
2
]
\begin{equation} \min \quad -Z=\begin{bmatrix} -4000 & -3000 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \end{equation}
min
−
Z
=
[
−
4000
−
3000
]
⋅
[
x
1
x
2
]
公式5和公式4这种形式就满足 MATLAB 线性规划的标准形式：
min
x
f
T
x
such that
{
A
⋅
x
≤
b
,
A
e
q
⋅
x
=
b
e
q
,
l
b
≤
x
≤
u
b
\min _{x} f^{T} x \text { such that } \left\{ \begin{array}{c} A \cdot x \leq b, &\\ { Aeq } \cdot x={ beq }, &\\ l b \leq x \leq u b & \end{array} \right.
x
min
f
T
x
such that
⎩
⎨
⎧
A
⋅
x
≤
b
,
A
e
q
⋅
x
=
b
e
q
,
l
b
≤
x
≤
u
b
其中，
f
T
x
f^{T}x
f
T
x
为目标函数，
A
为约束条件的系数矩阵，
b
为约束条件的常数项，
Aeq
为等式约束条件的系数矩阵，
beq
为等式约束条件的常数项，
lb
为变量的下界，
ub
为变量的上界。
问题转换成标准形式后，我们就可以使用 MATLAB 的
linprog
函数来求解了。
linprog
函数的语法为：
[x,fval] = linprog(f,A,b,Aeq,beq,lb,ub)
其中，
x
为求解得到的最优解，
fval
为最优解对应的目标函数值。
最开始的问题就可以用以下代码解决：
f = [-4000 -3000];
A = [2 1; 1 1; 0 1];
b = [10; 8; 7];
lb = [0; 0];
[x, fval] = linprog(f, A, b, [], [], lb, []);
fval = -fval; % 因为目标函数取反了，所以这里要取反
最后得出的结果为：
x =
2.0000
6.0000
fval =
26000
附加题
让我们运用上文的方法求解以下线性规划问题：
max
Z
=
2
x
1
+
3
x
2
+
4
x
3
\begin{equation} \max \quad Z=2 x_{1}+3 x_{2} + 4 x_{3} \end{equation}
max
Z
=
2
x
1
+
3
x
2
+
4
x
3
s.t.
{
2
x
1
+
x
2
+
3
x
3
≤
36
x
1
+
x
2
≥
8
x
1
+
x
3
≥
10
x
1
+
x
2
−
x
3
=
4
x
1
,
x
2
,
x
3
≥
0
\begin{equation} \text { s.t. } \left\{ \begin{array}{c} 2 x_{1}+x_{2}+3x_{3} \leq 36 &\\ x_{1}+x_{2} \geq 8 &\\ x_{1}+x_{3} \geq 10 &\\ x_{1}+x_{2}-x_{3} = 4 &\\ x_{1}, x_{2}, x_{3} \geq 0 & \end{array} \right. \end{equation}
s.t.
⎩
⎨
⎧
2
x
1
+
x
2
+
3
x
3
≤
36
x
1
+
x
2
≥
8
x
1
+
x
3
≥
10
x
1
+
x
2
−
x
3
=
4
x
1
,
x
2
,
x
3
≥
0
首先，我们将问题转换成标准形式：
min
−
Z
=
−
[
−
2
−
3
−
4
]
⋅
[
x
1
x
2
x
3
]
\begin{equation} \min \quad -Z=-\begin{bmatrix} -2 & -3 & -4 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} \end{equation}
min
−
Z
=
−
[
−
2
−
3
−
4
]
⋅
x
1
x
2
x
3
s.t.
{
[
2
1
3
−
1
−
1
0
−
1
0
−
1
]
⋅
[
x
1
x
2
x
3
]
≤
[
36
−
8
−
10
]
[
1
1
−
1
]
⋅
[
x
1
x
2
x
3
]
=
[
4
]
x
1
,
x
2
,
x
3
≥
0
\begin{equation} \text { s.t. } \left\{ \begin{array}{c} \begin{bmatrix} 2 & 1 & 3 \\ -1 & -1 & 0 \\ -1 & 0 & -1 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} \leq \begin{bmatrix} 36 \\ -8 \\ -10 \end{bmatrix} &\\ \begin{bmatrix} 1 & 1 & -1 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} = \begin{bmatrix} 4 \end{bmatrix} &\\ x_{1}, x_{2}, x_{3} \geq 0 & \end{array} \right. \end{equation}
s.t.
⎩
⎨
⎧
2
−
1
−
1
1
−
1
0
3
0
−
1
⋅
x
1
x
2
x
3
≤
36
−
8
−
10
[
1
1
−
1
]
⋅
x
1
x
2
x
3
=
[
4
]
x
1
,
x
2
,
x
3
≥
0
然后即可代入求解：
f = [-2 -3 -4];
A = [2 1 3; -1 -1 0; -1 0 -1];
b = [36; -8; -10];
Aeq = [1 1 -1];
beq = [4];
lb = [0; 0; 0];
[x, fval] = linprog(f, A, b, Aeq, beq, lb, []);
fval = -fval;
最后得出的结果为：
x =
2.6667
8.6667
7.3333
fval =
60.6667