经过之前的入门，我们来系统的看看运筹规划这门数学科学。
通过我们之前举的例子，我们知道是根据业务问题，列出符合业务需求的方程，然后求解这个方程，然后接下来要介绍的实际上是我们要解决一个问题的时候，往往将现有的问题变化成标准型。然后求解。下面我们就来看看如何转换标准型。
$$
max\ z=\sum_{j=1}^{n} c_{j}x_{j}
$$
受限条件
$$
\begin{cases}
\begin{align}
\sum_{j=1}^{n} a_{ij}x_{j}=b_{i} \\
x >=0
\end{align}
\end{cases}
$$
标准形式下，$b_i>0$，如果不是，就是等式两边同时乘以-1，当$b_i=0$，表示出现退化，需要单独讨论。
我们可以通过矩阵形式表示。
$$
\begin{cases}
\begin{align}
max\ z = CX \\
AX=b \\
X>=0 \\
\end{align}
\end{cases}
$$
A：约束条件 是m*n的矩阵
b：资源向量
C：价值向量
X：决策变量
举个例子
下面我们就来看看如何化简成标准形式。
$$
max\ z=2x_1+3x_2
$$
$$
\begin{cases}
\begin{align}
x_1+2x_2<=8\\
4x_1<=16 \\
4x_2<=12 \\
x_1,x_2>=0 \\
\end{align}
\end{cases}
$$
变成标准形式
$$
max\ z=2x_1+3x_2+0x_3+0x_4+0x_5
$$
$$
\begin{cases}
\begin{align}
x_1+2x_2+x_3<=8\\
4x_1+x_4<=16 \\
4x_2+x_5<=12 \\
x_1,x_2,x_3,x_4,x_5>=0 \\
\end{align}
\end{cases}
$$
这里添加松弛变量$x_3,x_4,x_5$,对应的系数为0。这里我们能看到添加的松弛变量都是大于0的，如果我们存在一个变量没有范围这样应该怎么办呢？
$$
min\ z=-x_1+2x_2-3x_3
$$
约束条件为
$$
\begin{cases}
\begin{align}
x_1+x_2+x_3<=7\\
x_1-x_2+x_3>=2 \\
-3x_1+x_2+2x_3=5 \\
x_1,x_2>=0,x_3无约束 \\
\end{align}
\end{cases}
$$
变为标准形式的时候，我们使用$x_4-x_5=x_3$.所以标准形式就如下。
$$
max\ z=-x_1-2x_2+3(x_4-x_5)+0x_6+0x_7
$$
$$
\begin{cases}
\begin{align}
x_1+x_2+(x_4-x_5)+x_6<=7\\
x_1-x_2+(x_4-x_5)-x_7>=2 \\
-3x_1+x_2+2(x_4-x_5)=5 \\
x_1,x_2,x_3,x_4,x_5,x_6,x_7>=0 \\
\end{align}
\end{cases}
$$
概念
接下来我们来介绍几个概念，方便我们以后来解释一些原理。首先我们来回溯一下基本型。
$$
max\ z=\sum_{j=1}^{n} c_j x_j \tag{1.0}
$$
$$
\begin{cases}
\begin{align}
\sum_{j=1}^{n} a_{ij}x_j=b_i \tag{1.1} \\
x_j>=0\\
\end{align} \tag{1.2}
\end{cases}
$$
可行解
上述条件的1.1 和 1.2的解 $X=(x_1,x_2,...x_n)^T$，就称为线性规划问题的可行解，如果能够使函数变成最大值，那么就是最优解。
基
我们假设A是约束方程组的约束系数 mn,其秩为m，B是矩阵A的mn阶非奇异子矩阵，就称B是线性规划问题的一个基。且有一个基，就有一个基解。
基可行解
满足1.2的解，就是基可行解
有用的定理
若线性规划存在可行域，那么可行域的
$$
D=\{X|\sum P_{i}X_j=b,x_j>=0\}
$$
就是一个凸集合。
如果可行域有界，线性规划问题的目标函数一定可以在其顶点上达到最优。
单纯形法例子
我们这里来举例一个使用单纯形法的例子，过程比较复杂，后面我们也会介绍一下比较通用的描述过程。
$$
max\ z = 2x_{1}+3x_{2}+0x_{3}+0x_{4}+0x_{5}
$$
$$
\begin{cases}
\begin{align}
x_{1}+2x_{2}+x_{3}=8 \\
4x_{1} + x_{4}=16 \\
4x_{2}+x_{5}=12 \\
\end{align}
\end{cases}
$$
约束方程的系数矩阵为
$$
\begin{equation}
A=(P_{1},P_{2},P_{3},P_{4},P_{5})=
\left(
\begin{array}{ccc}
1 & 2 & 1 & 0 & 0\\
4 & 0 & 0 & 1 & 0\\
0 & 4 & 0 & 0 & 1\\
\end{array}
\right)
\end{equation}
$$
构成一个基
$$
B=(P_3,P_4,P_5)
$$
对应的B的变量$x_{3},x_{4},x_{5}$为基变量，就能的到如下等式。
$$
\begin{cases}
\begin{align}
x_3=8-x_1-2x_2 \\
x_4=16-x_1 \\
x_5=12-4x_2 \\
\end{align} \tag{1.3}
\end{cases}
$$
另非基变量$x_1=x_2=0$，多的一个可行解。
$$
X_0=(0,0,8,16,12)^T
$$
一般选择系数最大的非基变量$x_2$作为还入变量，将它换入到基变量中，同时还要确定基变量中一个要换出来一个非基变量，可以按照如下的方法确定换出变量。
可以看公式1.3，当把$x_2$作为还入变量的时候，必须要确定一个换出变量，当$x_1=0$的时候，
$$
\begin{cases}
\begin{align}
x_3=8-2x_2 >=0 \\
x_4=16 >=0 \\
x_5=12-4x_2 >=0\\
\end{align} \tag{1.4}
\end{cases}
$$
由公式1.4能够看出，
$$
x_2=min(8/2,12/3)=3
$$
当$x_2=3$的时候，基变量$x_5=0$,这就决定我们要使用$x_2$替换$x_5$,为了求得$x_2,x_3,x_4$为基变量的一个基可行解和进一步分析问题，需要将公式1.3改写成如下。
$$
\begin{cases}
\begin{align}
x_3+2x_2=8-x_1 >=0 \\
x_4=16-4x_1 >=0 \\
4x_2=12-x_5 >=0\\
\end{align} \tag{1.5}
\end{cases}
$$
经过变换
$$
\begin{cases}
\begin{align}
x_3=2-x_1+\frac{1}{2}x_5 >=0 \\
x_4=16-4x_1 >=0 \\
x_2=4-\frac{1}{4}x_5 >=0\\
\end{align} \tag{1.6}
\end{cases}
$$
目标函数为
$$
Z=9+2x_1-\frac{3}{4}x_5
$$
另$x_1,x_5=0$,就获得另一个可行解
$$
X_1=(0,3,2,16,0)
$$
然后经过类似的迭代，直到我们求的最终解。