MATLAB 线性规划

什么是线性规划问题

线性规划问题是指在一组线性不等式约束条件下，求解一个线性目标函数的最大值或最小值的问题。

如何使用 MATLAB 解决线性规划问题

常见的线性规划问题通常类似于以下形式：

max⁡Z=4000x1+3000x2\begin{equation} \max \quad Z=4000 x_{1}+3000 x_{2} \end{equation}

 s.t. {2x1+x2≤10x1+x2≤8x2≤7x1,x2≥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}

其中，公式1为目标函数，公式2为约束条件。

为了便于求解，我们可以将公式1和公式2分别写成矩阵形式：

max⁡Z=[40003000]⋅[x1x2]\begin{equation} \max \quad Z=\begin{bmatrix} 4000 & 3000 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \end{equation}

 s.t. {[211101]⋅[x1x2]≤[1087]x1,x2≥0\begin{equation} \text { s.t. } \left\{ \begin{array}{c} \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}

为了统一最大目标函数问题和最小目标函数问题，我们将目标函数的符号取反，即：

min⁡−Z=[−4000−3000]⋅[x1x2]\begin{equation} \min \quad -Z=\begin{bmatrix} -4000 & -3000 \end{bmatrix} \cdot \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \end{equation}

公式5和公式4这种形式就满足 MATLAB 线性规划的标准形式：

min⁡xfTx such that {A⋅x≤b,Aeq⋅x=beq,lb≤x≤ub\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.

其中，fTxf^{T}x为目标函数，A为约束条件的系数矩阵，b为约束条件的常数项，Aeq为等式约束条件的系数矩阵，beq为等式约束条件的常数项，lb为变量的下界，ub为变量的上界。

问题转换成标准形式后，我们就可以使用 MATLAB 的 linprog 函数来求解了。

linprog 函数的语法为：

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

其中，x为求解得到的最优解，fval为最优解对应的目标函数值。

最开始的问题就可以用以下代码解决：

1
2
3
4
5
6
7
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; % 因为目标函数取反了，所以这里要取反

最后得出的结果为：

1
2
3
4
5
6
x =
    2.0000
    6.0000

fval =
    26000

附加题

让我们运用上文的方法求解以下线性规划问题：

max⁡Z=2x1+3x2+4x3\begin{equation} \max \quad Z=2 x_{1}+3 x_{2} + 4 x_{3} \end{equation}

 s.t. {2x1+x2+3x3≤36x1+x2≥8x1+x3≥10x1+x2−x3=4x1,x2,x3≥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}

首先，我们将问题转换成标准形式：

min⁡−Z=−[−2−3−4]⋅[x1x2x3]\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}

 s.t. {[213−1−10−10−1]⋅[x1x2x3]≤[36−8−10][11−1]⋅[x1x2x3]=[4]x1,x2,x3≥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}

然后即可代入求解：

1
2
3
4
5
6
7
8
9
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;

最后得出的结果为：

1
2
3
4
5
6
7
x =
    2.6667
    8.6667
    7.3333

fval =
    60.6667