线性规划最先在第二次世界大战时被提出，用于最大化资源的利用效率。其中的“规划”也是一个军事词汇，指按照既定的时刻表去执行任务或者用最佳方式做人员部署。线性规划问题的研究很快得到了大家的关注。

基本形式

线性规划的一般形式为：

\begin{array}{cl} \min _{x \in \mathbb{R}^{n}} & Z=CX=\sum\limits_{j=1}^n c^{\mathrm{T}} x, \\ \text { s.t. } & A x=b, \\ & G x \leqslant e, \end{array}

这样的线性规划问题可以通过一些方法转化为一下标准形线性规划问题(等式约束和决策变量非负)

\begin{array}{cl} \min _{x \in \mathbb{R}^{n}} & {Z=CX} , \\ \text { s.t. } & A x=b, \\ & x \geqslant 0, \\ &b_i\geqslant 0 \end{array}

$A$ 是 $m\times n$ 型矩阵，m是约束方程的个数，n是决策变量的个数（一般来说 $m<n, r(A)=m$ .
具体的转化方法包括:

目标函数是求最大值的问题，可以通过将目标函数的系数乘以“-1”来找最小值，即 $max\, f(x)$ 和 $min\, -f(x)$ 对应同一个解。
不等式约束条件可以通过引入松弛变量化为等式约束条件，例如对于不等式约束:

x_1+x_2+x_3\le 8

可以通过引入 $x_4=8-x_1-x_2-x_3\ge 0$ 来实现，即通过引入松弛变量 $x_4$ ，将原来的约束问题转化为:

\begin{align*} x_1+x_2+x_3+x_4=8\\ x_4\ge 0 \end{align*}

对于取值无约束的变量 $x_k$ ，可以通过引入两个有约束的变量来表示，如可令 $x_k=x_k^{'}-x_k^{''}$ ,其中 $x_k=x_k^{'}-x_k^{''}\ge 0$

解的概念和基本定理

考虑标准形线性规划的约束条件:

AX=b, X\ge 0

这里矩阵 $A$ 为 $m\times n$ 矩阵，从矩阵 $A$ 中抽取m列组成新矩阵，若得到的新的矩阵可逆，则认为该矩阵为对应线性规划问题的一个基，记为 $B$ , 称 $B$ 的列向量的为基向量，记为 $P_j(j=1, 2, \dots , m)$ 。

\begin{align*} &A=[B, N]\\ &|B|\ne 0 \\ &B=[P_1, P_2, P_3, \dots, P_m], \end{align*}

与基向量对应的变量 $x_j$ ( $j=1, 2, \dotsb, m$ )称为基变量,记为 $X_B=[x_1, x_2, \dots, x_m]^T$ , 其余的变量称为非基变量,记为 $X_N$ 。
接着令 $n-m$ 个非基变量为0，可以解得约束方程组的解，这里叫做约束方程组的基本解/基解：

\begin{align*} &X=[X_B^T, X_N^T]=[x_1, x_2, \dots, x_m, 0, \dots, 0]\\ &X_B=B^{-1}b \end{align*}

其中满足非负约束条件 $X\ge 0$ 的基解称为基本可行解/基可行解。

基可行解都是可行域的顶点

若最优解在基解中，那么该最优解也叫做基本最优解。
基可行解对应的基称为可行基。
基本最优解对应的基称为可行基。

当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。

凸集、凸组合、极点

线性规划的解的基本定理:

若可行域有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优。

若线性规划有最优解, 则最优值一定可以在可行解集合的某个极点上到达, 最优解就是极点的坐标向量.

线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解.

定理2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点（退化基本可行解时）。

若线性规划可行解K非空,则K是凸集.

迭代算法

图解法

。。。

单纯形法

单纯形法的基本思路是从某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），直到目标函数达到最优，对应的基可行解即为最优解。
单纯形法中可行解的变换是通过对增广矩阵的行变换实现的，无论是对约束条件还是目标函数进行行变换，都不会改变最优解的取值。
为了计算方便，一般通过构造单纯形表进行计算，每迭代一步构造一个新的单纯形表。
接下来根据老师ppt的一个例子进行说明:

\begin{equation*} \begin{aligned} &\max Z=3 x_{1}+4 x_{2} \\ &\left \{ \begin{array}{l} 2 x_{1}+x_{2}+x_{3}=40 \\ x_{1}+3 x_{2}+x_{4}=30 \\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{array}\right. \end{aligned} \end{equation*}

为了计算方便，一般取好求逆的矩阵作为基:

\begin{equation*} B_{1}=\left[\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right] \end{equation*}

进而解得初始基本可行解:

\begin{equation*} X^{(1)}=(0, 0, 40, 30)^{T} \end{equation*}

作出对应的单纯形表:

\begin{array}{|c|c|c|c|c|c|c|} \hline X_{B} & x_{1} & x_{2} & x_{3} & x_{4} & b & \theta_{i} \\ \hline x_{3} & 2 & 1 & 1 & 0 & 40 & 40\\ \hline x_{4} & 1 & 3 & 0 & 1 & 30 & 10\\ \hline \lambda_{j} & 3 & 4 & 0 & 0 & & \\ \hline \end{array}

表中 $X_B$ 一列表示选定的基变量， $\theta_i$ 表示确定换入变量 $x_j$ 后，根据 $\displaystyle\frac{b_i}{a_{ij}}$ 计算得来的， $\lambda_j$ 表示目标函数对应的系数。
接着，我们需要判断得到的解是不是最优解，这个时候应该看对应的 $\lambda$ ，就本题求得的基本可行解来说，通过观察可以发现如果我们适当减小 $x_3$ 或者 $x_4$ ，这样在相应的约束条件可以得到更大的 $x_1$ 或者 $x_2$ ，因为此时 $x_4$ 对应的 $\lambda$ 较大，因此如果将 $x_4$ 作为基变量，我们可以期望获得更大的目标函数值。那么究竟应该让哪个变量退出基变量呢？这个时候就需要结合已有的约束条件(这里对约束条件进行适当变形，以得到更好的观测效果):

\begin{align*} x_2=40-x_3(\text{解得}x_2\le 40)\\ x_2=\frac{30-x_4}{3}(\text{解得}x_2\le 10) \end{align*}

这里需要注意的是，我们要保证 $x_3, x_4$ 有一个要大于零（仍然作为基变量）的情况下最大化 $x_2$ ，因此我们其实要比较的就是 $x_3, x_4$ 哪一个退出基变量可以获得更大的 $x_2$ ，其实比较的也就是 $\displaystyle\frac{b_i}{a_{i2}}$ 的值，即写在 $\theta$ 位置的值。(如果取较大的范围，那么就会出现不满足约束条件的情况)

在比较 $\displaystyle\frac{b_i}{a_{i2}}$ 的值的时候，需要注意的是只对 $a_{ij}$ 大于0的值进行考虑，小于零的值不作为出基变量的参考依据，或者说 $a_{ij}<0$ 对应的基变量不会出基。

接着为了能够利用同样的方法进行比较，我们需要对原来的单纯形表通过行变换获得新的单纯形表，新的单纯形表应该以 $x_2, x_3$ 作为基变量，具体进行的行变换是将原来的单纯形表中第三行的值乘以 $\frac{1}{3}$ , 然后通过行变换将第一个行 $x_2$ 列的值化为0，并将 $\lambda$ 行 $x_2$ 列的值化为0，这个时候再看 $\lambda$ 是否存在大于零的值，如果仍存在大于零的值，则需要进一步进行调整基变量:

\begin{array}{|c|c|c|c|c|c|c|} \hline X_{B} & x_{1} & x_{2} & x_{3} & x_{4} & b & \theta_{i} \\ \hline x_{3} & 5 / 3 & 0 & 1 & -1 / 3 & 30 & 18 \\ \hline x_{2} & 1 / 3 & 1 & 0 & 1 / 3 & 10 & 30 \\ \hline \lambda_{j} & 5 / 3 & 0 & 0 & -4 / 3 & & \\ \hline \end{array}

再继续进行:

\begin{array}{|c|c|c|c|c|c|c|} \hline X_{B} & x_{1} & x_{2} & x_{3} & x_{4} & b & \theta_{i} \\ \hline x_{1} & 1 & 0 & 3 / 5 & -1 / 5 & 18 & \\ \hline x_{2} & 0 & 1 & -1 / 5 & -2 / 5 & 4 & \\ \hline \lambda_{j} & 0 & 0 & -1 & -1 & & \\ \hline \end{array}

在利用单纯形法解规划问题时，在选择出基变量时，一些特殊的情况是由于解的特殊情况导致的，这里加以解释:
(a) 若 $\lambda_{j} \leq 0 \quad(\mathrm{j}=1, 2 , \ldots, \mathrm{n})$ 得到最解;
(b) 某个 $\lambda_{k}>0$ 且 $a_{i k} \leq 0 \quad(i=1, 2, \ldots, \mathrm{m} )$ 则线性规划具有无界解。
© 若存在 $\lambda_{\mathrm{j}}>0$ 且 $a_{i j}(i=1, \ldots, \mathrm{m})$ 不全非正, 则进行换基;

单纯形法也可以用来求解最小值类型的规划问题，但需要注意的是求解目标函数为最小值的规划问题时在基变量的变换上与上述变换方法略有不同:

选择进基变量时，我们要找的 $\lambda$ 最小的负数，当所有的检验值都大于等于零说明当前解为基本最优解。
选择出基变量时，我们要将对应的比值最大的 $\theta_i$ 来作为出基变量的判断依据。

大M法

单纯形法求解规划问题的前提是标准型的系数矩阵中有单位矩阵，这在实际问题的求解过程中并不能保证。当这个条件不满足时，为了求解规划问题，我们需要人为添加人工变量来得到单位矩阵，进而构造出单位矩阵，大M法就是一种通过引入虚拟变量来求解线性规划问题的方法。
考虑下列的一个线性规划问题:

通过观察容易发现该问题虽然是标准型的规划问题，但是并不存在合适的单位阵作为基，因此可以考虑引入一个任意大的正数M来和两个人工变量 $x_6, x_7$ 对上述规划问题进行转化:

\begin{equation*} \begin{aligned} &\max Z=3 x_{1}+2 x_{2}-x_3-Mx_6-Mx_7 \\ &\left\{\begin{array}{l} -4 x_{1}+3x_{2}+x_{3}-x_4+x_6=4 \\ x_{1}-x_2+2 x_{3}+x_{5}=10 \\ 2x_{1}-2x_2+ x_{3}+x_{7}=1\\ x_{1}, x_{2}, x_{3}, x_{4}, x_5, x_6, x_7 \geq 0 \end{array}\right. \end{aligned} \end{equation*}

下边简单的对转换前后两个规划问题有相同的最优解进行说明:

首先观察目标函数，因为所有的变量都非负，而M任意大，所以只有当 $x_6=x_7=0$ 时上述问题才可能有最优解，而当 $x_6=x_7=0$ 时新规划问题和原规划问题的目标函数完全一致。
$x_6=x_7=0$ 时，约束条件也和原规划问题的约束条件完全一致。

以上两点说明引入M后规划问题对应的解并没有发生改变，接下来可以借助单纯形法对该规划问题的求解过程加以说明，为了计算方便，这里使用的单纯形表与原来的单纯形表有所区别，但是基本思路仍与原来保持一致。

只进行了一次变换的单纯形表的展示

与原来的单纯形表相比，新的单纯形表增加了 $C_j$ 行，这一行用来写新规划问题目标函数的系数矩阵，还在开头增加了 $C_B$ 列，用来书写基变量目标函数的对应系数，这两个的变动都是为了在求解检验值时能够更加方便的进行运算，在这样的单纯形表下， $\lambda_j$ 的取值就可以通过对应 $C_j$ 行的值减去（ $C_B$ 列和 $x_i(i=1, 2, \dots, n)$ 列的内积来得到）, 例如 $\lambda_{j1}=3-(-m\times 1+0\times 1+-M\times 2)=3-2M$ 求得。（本质上和通过行变换进行求解结果是一样的，这里只是起到了一个简化运算的作用，因为行变换并未改变目标函数的最优解，因此在更换基变量之后仍然可以借助 $C_j$ 行的进行行变换而不是像之前一样使用 $\lambda_j$ 进行行变换），通过观察 $\lambda_j$ 我们可以得到进基变量为 $x_3$ (M可以视为趋近正无穷的数字)，然后通过求比值得到出基变量为 $x_7$ ，因为 $x_7$ 为认为添加变量，因此一旦出基后它的系数我们就不再关心了，进而在下一步的运算过程中可以不考虑 $x_7$ 的系数变化.