1. 情景代入
大学毕业后，你继承了家里的工厂，成为了一名厂长。你的工厂能够生产 A、B、C 三种产品，生产三种产品会用到 a、b、c 三种原材料。你的工厂通过长期生产曾经摸索出生产每种产品所耗费的原料和单位产品的利润；你通过调取仓库库存，理解了可利用的各种原料的库存（如下表）。当初你须要制订一个生产打算，使你的工厂的总利润最大。
| 原料 \ 产品 | A | B | C | 库存 |
|---|---|---|---|---|
| a | 3 | 4 | 2 | 60 |
| b | 2 | 1 | 2 | 40 |
| c | 1 | 3 | 2 | 80 |
| 单位产品利润 | 2 | 4 | 3 |
2. 模型介绍
【定义】线性规划模型是在一系列等式或不等式约束条件下，是某个或多个指标函数达到最值的数学模型。
别怕，我也看不懂 ^o^，但咱们能够大略剖析一下：像每种原料的库存，就应该是属于一种 约束条件 ，因为当你的工厂用完了某种原材料，那么它将不能再生产任何须要该原材料的产品，即便其余原材料还有残余，此时你的工厂的生产就受到了束缚；其次咱们制订生产打算的指标是要取得最大的利润，所以利润就该当属于 指标函数 ，因为咱们在这个过程中是想取得利润函数的极大值。最初咱们的生产打算就是要确定生产多少产品 A、多少产品 B、多少产品 C 以取得最大利润，像这样的一系列生产数量，称为你对这个问题的 决策。
3. 模型的个别模式
- 决策变量：通常是所钻研的问题要求解的未知量。在你的工厂中，它示意了工厂将生产多少产品 A、多少产品 B、多少产品 C。
$$
X = (x_1, x_2, \cdots, x_n)^T
$$
- 指标函数：通常是所钻研的问题要求达到最大（最小）的那个指标的数学表达式，它是决策变量的函数，记为 $f(x)$。在你的工厂中，它就是你的利润函数。
- 约束条件：通常是所钻研问题的决策向量 $X$ 的限度条件，$X$ 容许取值的范畴记为 $D$，称为可行域，有 $X \in D$。$D$ 通常由一组对于决策变量 $X$ 的等式 $h_i(X) = 0$，和不等式 $g_j(X) \geq 0$ 或 $g_i(X) \leq 0$ 来界定。其中 $h_i$ 称为等式束缚，$g_i$ 称为不等式束缚。
线性规划模型次要就包含以上 3 个局部，其个别模式能够示意为：
$$
max(min) \; z = f(X)
$$
$$
s.t. \left\{
\begin{aligned}
h_i(X) &= 0, \quad (i = 1, 2, \cdots, p) \\
g_j(X) &\leq 0, \quad (j = p+1, p+2, \cdots, n) \\
\end{aligned}
\right.
$$
其中 $max(min)$ 示意对指标函数求最大值或最小值，$s.j. $ 示意受约束于 $(subject \ to)$。由数学布局模型的个别模式，可行域可表白为：
$$
D = \{X|h_i(X) = 0; \; g_j(X) \leq 0\}
$$
满足约束条件的解，即可行域 $D$ 中的点称为 可行解 ；使指标函数 $f(X)$ 达到最值的可行解，即可行域 $D$ 中使得指标函数 $f(X)$ 获得极值的点称为 最优解。
4. 模型的建设
咱们当初能够尝试解决在你的工厂中的生产打算的问题了，因为咱们当初并不能间接确定每种产品的产量，无妨设 $x_1, x_2, x_3$ 来别离示意 A、B、C 三种产品的产量，此时的三个变量称之为 决策变量。（贴心的再把表格贴一遍）
| 原料 \ 产品 | A | B | C | 库存 |
|---|---|---|---|---|
| a | 3 | 4 | 2 | 60 |
| b | 2 | 1 | 2 | 40 |
| c | 1 | 3 | 2 | 80 |
| 单位产品利润 | 2 | 4 | 3 |
因为仓库里每种原材料的库存是无限的，所以（1）咱们所生产的三种产品所耗费的某种原材料总计不能超过仓库的库存；（2）其次三种产品的产量均不应小于零。以上都是咱们的 约束条件 ，（3）在满足以上约束条件的同时，如果有一种生产打算能够使得你的工厂生产的 3 种产品所取得的利润和最大，你就找到了工厂生产的 最优解。由此咱们能够构建出以下模型：
$$
\left\{
\begin{aligned}
max \quad &z = 2x_1 + 4x_2 +3x_3 \\
s.t. \quad &3x_1 + 4x_2 + 2x_3 \leq 60 \\
&2x_1 + x_2 + 2x_3 \leq 40 \\
&x_1 + 3x_2 +2x_3 \leq 80 \\
&x_1, x_2, x_3 \geq 0 \\
\end{aligned}
\right.
$$
求解出满足所有限度条件的 $x_1, x_2, x_3$ 咱们就失去了 可行解 ，若在可行解中能够找到一组解使得你的工厂获利最大，咱们就找到了 最优解。
5. 模型的形象
咱们方才建设的模型，只解决了你的工厂里的生产打算问题，如果咱们要持续解决机床刀头磨损更换的问题，又或者要解决深海石油平台开采石油的问题，咱们就须要一个更具备一般性的模型。所以接下来咱们要对咱们的工厂模型进行形象。
-
指标函数：首先，对于每个线性规划模型，模型的目标都是要求解指标函数的最值，比方利润最大化，老本最小化。而且每个指标函数都是以决策变量为自变量。
$$
max(min) \; z = \sum\limits_{j = 1}^{n} c_j \cdot x_j
$$ -
约束条件：其次，模型中的每个决策变量均有肯定的束缚，如资源、工期、工夫等，其具体表现为决策变量的一些等式和不等式。
$$
s.t. \quad \sum\limits_{i = 1}^{m} \sum\limits_{j = 1}^{n} a_{ij} \cdot x_j \geq b_i \quad (\geq, \leq, =)
$$确定了指标函数和约束条件，线性模型的建模局部就实现了。
6. 模型的求解
求解线性规划模型有三种办法：单纯形法、图解法和软件求解法。
- 单纯形法：办法偏差于纯数学，个别不会波及。
-
图解法：通过在坐标系中做出约束条件来确定可行域的办法，因为超过三维的图形没法做出，所以该办法只能求解决策变量不大于三个的问题，个别不在建模中应用。
例如求解以下模型：$$
\left\{
\begin{aligned}
max \quad &z = 3x_1 + 4x_2 \\
s.t. \quad &4x_1 + 3x_2 \leq 60 \\
&2x_1 + 5x_2 \leq 60 \\
&x_1, x_2 \geq 0 \\
\end{aligned}
\right.
$$首先在坐标系中画出约束条件，确定可行域：
将指标函数当作直线的截距，平移到可行域的边缘拐点失去最优解 $z = 60$：
- MATLAB 求解：MATLAB 实用于所有线性规划模型，在建模中能够间接应用。在 MATLAB 中应用 $linprog()$ 函数求解。MATLAB 中规定线性规划的规范模式为：
$$
\min_x \; c^T x
$$
$$
s.t. \left\{
\begin{aligned}
& Ax \leq b \\
& Aeq \cdot x = beq \\
& lb \leq x \leq ub
\end{aligned}
\right.
$$
其中 $Ax \leq b$ 为不等式束缚，对应数学模型中的 $g_j(X)$；$Aeq \cdot x = beq$ 为等式束缚，对应数学模型中的 $h_i(X) = 0$，$lb \leq x \leq ub$ 为 $x$ 的上下界，示意决策向量 $x$ 的可行区间。$A$、$Aeq$ 均为矩阵，$x$、$b$、$beq$、$lb$、$ub$ 均为列向量，在叉乘之后能够示意多组约束条件。最初，Matlab 默认求解指标函数的最小值，所以能够将指标函数整体取负（即令 $c = -c$）来求的指标函数的最大值。
$linprog()$ 函数中一共包含上述所有 7 个参数：
$$
linprog(c,A,b,Aeq,beq,lb,ub)
$$
函数的返回值包含一个最优解 $x$，在 $x$ 处的指标函数值 $fval$：
$$
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
$$
应用以上办法，咱们尝试解决如下问题：
$$
\left\{
\begin{aligned}
max \quad &z = 0.4x_1 + 0.28x_2 + 0.32x_3 + 0.72x_4 + 0.64x_5 + 0.6x_6\\
s.t. \quad &0.01x_1 + 0.01x_2 + 0.01x_3 + 0.03x_4 + 0.03x_5 + 0.03x_6 \leq 850 \\
&0.02x_1 + 0.05x_4 \leq 700 \\
&0.02x_2 + 0.05x_5 \leq 100 \\
&0.03x_3 + 0.08x_6 \leq 900 \\
&x_j \geq 0, \quad (j = 1, 2, \cdots, 6)
\end{aligned}
\right.
$$
代码如下：
c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];
A=[0.01 0.01 0.01 0.03 0.03 0.03;
0.02 0 0 0.05 0 0;
0 0.02 0 0 0.05 0;
0 0 0.03 0 0 0.08];
b=[850;700;100;900];
Aeq=[];
beq=[];
lb=[0;0;0;0;0;0];
ub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub)其中，$minZ=cX$，$z$ 为 $cX$ 的求和的最小值，$c$ 为各项 $x$ 的系数；$AX≤b$，$A$、$X$、$b$ 均为数组，这是不等式约束条件，若没有不等式存在，则令 $A=[\;], b=[\;]$；$AeqX = beq$，$Aeq$、$beq$ 均为数组，为等式约束条件，$Aeq$ 为各项 $x$ 的系数，若没有等式约束则令 $Aeq=[\;], beq=[\;]$；$lb \leq X \leq ub$，是对变量 $X$ 的束缚；$x$ 为返回最优解；$fval$ 为 $x$ 处指标函数值。
输出 Matlab 失去后果：
2022/7/28
Levine