经过之前的入门，我们来系统的看看运筹规划这门数学科学。
通过我们之前举的例子，我们知道是根据业务问题，列出符合业务需求的方程，然后求解这个方程，然后接下来要介绍的实际上是我们要解决一个问题的时候，往往将现有的问题变化成标准型。然后求解。下面我们就来看看如何转换标准型。

$$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 \tag{1.2} \\ \end{align} \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} \tag{1.2}

约束方程的系数矩阵为

A=(P_1,P_2,P_3,P_4,P_5)= \begin{equation} \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} \end{cases} \tag{1.3}

另非基变量$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} \end{cases} \tag{1.4}

由公式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} \end{cases} \tag{1.5}

经过变换

\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} \end{cases} \tag{1.6}

目标函数为

$$Z=9+2x_1-\frac{3}{4}x_5$$

另$x_1,x_5=0$,就获得另一个可行解

$$X_1=(0,3,2,16,0)$$

然后经过类似的迭代，直到我们求的最终解。