运筹学（OR部分）
运筹学线性规划知识
这里介绍一下线性规划模型，线性规划求解思想，以及线性规划的单纯形法
以一个例子来看一下线性规划模型：
（一）线性规划模型
例:某工厂在计划期间内要安排生产A，B两种产品，已知生产单位产品所需设备台时以及两种原材料（1，2）的消耗，如下表所示，所有的资源（设备，原材料都是有限制的）问：如何安排使工厂获利最多？
| 产品A | 产品B | ||
| 设备 | 1 | 2 | 8台时 |
| 原材料1 | 4 | 0 | 16吨 |
| 原材料2 | 0 | 4 | 12吨 |
| 利润 | 2 | 3 |
首先，可以把它的模型写出来。
step1:设变量（看哪些变量是需要决策的，这里要求决策的是产品A，B的产量），所以设产品A，B的产量分别为 x_1 和 x_2 .
step2:定目标（目标是什么？目标是想要获利最多）
\max z=2 x_{1}+3 x_{2}
step3:找约束
\left\{\begin{aligned} x_{1}+2 x_{2} & \leq 8 \\ 4 x_{1} & \leq 16 \\ 4 x_{2} & \leq 12 \\ x_{1}, x_{2} \geq 0 \end{aligned}\right.
（求解的预备知识）：
例1:求最大问题（一元）
\begin{aligned} \max & z=2-3 x \\ & \text { s.t. } x \geq 0 \end{aligned}
显然，x前面的系数为负数，x的值又为非负，当x的值从0开始慢慢增大的时候，目标函数z的值在慢慢的减少，这里我们要求z的最大值，所以当x=0为最优解，这时目标函数的值z=2。这里的x=0在边界处，可以称在顶点处达到最优解。
例2:求最大问题（多元）
\begin{aligned} \max & z=2-3 x_{1}-2 x_{2} \\ & \text { s.t. } x_{1}, x_{2} \geq 0 \end{aligned}
这里也是要求x1,x2是非负，在平面上的区域在第一象限。同样的，这里目标函数里的x1,x2前面的系数都为负值，当x1,x2的值从0开始慢慢增大的时候，目标函数z的值同样也在慢慢的减少，这里我们要求z的最大值，所以当x1=x2=0的时候解为最优解，目标函数的值z=2。也是在顶点出达到最优解。
所以，发现规律了吗？
推广到一般的情况，在我们求带约束的最优化问题的时候，如果 目标函数里变量的系数都小于0时 ，当 约束条件都是非负约束 的时候，当 将这些变量都取0（都在顶点处）时目标函数取得最优值 ，否则目标函数一定会严格小于2.
例3:求解线性方程组
\left\{\begin{array}{l} x_{1}+x_{2}+x_{3}=4 \\ x_{1}-x_{2}+2 x_{3}=6 \end{array}\right.
观察一下这个方程组，这里有2个方程3个未知数。众所周知，2个方程只能解出2个未知数，所以我们可以将其中1个未知数看成参数变量，只要这个参数变量的值定下来了，另外2个变量的值也就能完全定下来了。
我们这里将 x_3 看成一个参数变量来求解 x_1 和 x_2 。由1式+2式，1式-2式可得：
\left\{\begin{array}{l} 2 x_{1}+3 x_{3}=10 \\ 2 x_{2}-x_{3}=-2 \end{array}\right.
化简：
\left\{\begin{array}{l} x_{1}+\frac{3}{2} x_{3}=5 \\ x_{2}-\frac{1}{2} x_{3}=-1 \end{array}\right.
解得（这里的 x_3 是可以任意取值的）
\left\{\begin{array}{l} x_{1}=5-\frac{3}{2} x_{3} \\ x_{2}=-1+\frac{1}{2} x_{3} \end{array}\right.
x_1,x_2 在 x_3 取定之后， x_1,x_2 便确定了。 x_1,x_2 的取值依赖于 x_3
在线性规划里面，将右边这种类型的变量称为非基变量，依赖非基变量左边的这些变量称为基变量。解线性方程组就是把变量分成2部分，一个放在左边，一个放在右边，左边不重复的只留一个变量。用矩阵来看的话，直接可以将系数写进去：
\left(\begin{array}{llll} 1 & 1 & 1 & 4 \\ 1 & -1 & 2 & 6 \end{array}\right) \sim\left(\begin{array}{llll} 2 & 0 & 3 & 10 \\ 0 & 2 & -1 & -2 \end{array}\right) \sim\left(\begin{array}{llll} 1 & 0 & \frac{3}{2} & 5 \\ 0 & 1 & -\frac{1}{2} & -1 \end{array}\right)
总结：解方程的方法，将基变量放在等号左边，非基变量放在等号右边，基变量的系数矩阵为单位矩阵。解方程的过程就是矩阵的初等行变换，直到变化到出现单位矩阵就相当于解出来了。（单位矩阵所对应的变量就是基变量，非单位矩阵所对应的列的变量为非基变量）。
（二）线性规划求解思想
回到我们想求解的这个线性规划问题：
\max z=2 x_{1}+3 x_{2}
\left\{\begin{aligned} x_{1}+2 x_{2} & \leq 8 \\ 4 x_{1} & \leq 16 \\ 4 x_{2} & \leq 12 \\ x_{1}, x_{2} \geq 0 \end{aligned}\right.
联想前面例1，例2的求解最大值的问题以及例3的求解线性方程组的问题，把它结合到这个问题里面来。有需要注意的是，中间的这三个式子不是等号，是不等式组。我们想着把它化成等号便可利用例3的方法来进行求解了。
那么，该如何化成等号呢？
第一个不等式 x_1 加上 2x_2 还差一些就等于8，那么我们令这个还差的一些为 x_3 （一个非负变量），这样不等号就可以转换为等号了。同理给第二个不等式左边加上非负变量 x_4 ，第三个不等式左边加上非负变量 x_5 得到：
\max z=2 x_{1}+3 x_{2}+0 x_{3}+0 x_{4}+0 x_{5}
\left\{\begin{array}{l} x_{1}+2 x_{2}+x_{3}=8 \\ 4 x_{1}+x_{4}=16 \\ 4 x_{2}+x_{5}=12 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geq 0 \end{array}\right.
这个大括号里面的内容称为标准型。
我们现在想想如何来解这个方程组，5个未知数3个方程，所以要将2个变量看作参数变量来求解另外3个变量。现在考虑把 x_1,x_2,x_5 解出来，将 x_1,x_2,x_5 作为基变量放在左边， x_3,x_4 作为非基变量放在右边。（并用 x_3,x_4 这两个非基变量替换掉目标函数中的基变量 x_1,x_2,x_5 ）得到它的等价问题：
\max z=14-\frac{1}{2} x_{3}-\frac{1}{8} x_{4}
\left\{\begin{array}{l} x_{1}+\frac{1}{4} x_{4}=4 \\ x_{2}+\frac{1}{2} x_{3}-\frac{1}{8} x_{4}=2 \\ x_{5}-2 x_{3}+\frac{1}{2} x_{4}=4 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geqslant 0 \end{array}\right.
这个形式是不是就十分熟悉了？回想一下对应例3中，这里目标函数的变量 x_3,x_4 对应的系数全为负数，并且 x_3,x_4 的约束条件又必须为正值，于是同理当 x_3=x_4=0 时这个函数有最优解 z=14 。中间的3个等号的作用仅仅是用来确定 x_1,x_2,x_5 的值，当 x_3=x_4=0 时 x_1,x_2,x_5 都为等式右端项,即 x_1=4,x_2=2,x_5=4 。
总结一下就是：
但在解决这个问题时，我们是猜测将 x_1,x_2,x_5 做为基变量，一般来说我们很难猜测这个问题。那么有没有一整套的流程，只有我们将流程走完了，就能将问题求解出来呢？
回到刚刚的问题：
\max z=2 x_{1}+3 x_{2}+0 x_{3}+0 x_{4}+0 x_{5}
\left\{\begin{array}{l} x_{1}+2 x_{2}+x_{3}=8 \\ 4 x_{1}+x_{4}=16 \\ 4 x_{2}+x_{5}=12 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geq 0 \end{array}\right.
这里我们加入新变量 x_3,x_4,x_5 其实明显就是构成了单位矩阵，我们将 x_3,x_4,x_5 定为初始基，非基变量 x_1,x_2 。当非基变量取0的时候将 x_1=0,x_2=0 带进目标函数 z=0 显然不是最优的，因为 x_1,x_2 前面的系数大于0。我们将目标函数中非基变量前面的系数叫做 检验数。最优性判断：检验数小于0。
现在看一下这个问题里面 x_2 的系数值大于 x_1
然后接着出基入基一全套操作直至将所有非基变量前面的系数都变为负数就可以啦！
\max z=14-\frac{1}{2} x_{3}-\frac{1}{8} x_{4}
\left\{\begin{array}{l} x_{1}+\frac{1}{4} x_{4}=4 \\ x_{2}+\frac{1}{2} x_{3}-\frac{1}{8} x_{4}=2 \\ x_{5}-2 x_{3}+\frac{1}{2} x_{4}=4 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geqslant 0 \end{array}\right.
嗯嗯，假装已经完美的变成了这种形式了。（这不，已经可以判断最优了）
好了，总算到单纯形法最重要的一步了！
就是将上面的一系列操作变成一个表格来写。。。
（三）线性规划的单纯形法
想要求解的问题是这个：
\max z=2 x_{1}+3 x_{2}+0 x_{3}+0 x_{4}+0 x_{5}
\left\{\begin{array}{l} x_{1}+2 x_{2}+x_{3}=8 \\ 4 x_{1}+x_{4}=16 \\ 4 x_{2}+x_{5}=12 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geq 0 \end{array}\right.
这时候我们来建一个初始单纯形表：
这里的检验数如何计算呢？我们想将基变量对应的检验数全为0
检验数计算方法：
这里目标函数中基变量所对应的系数已经全为0了，所以这里没有变化。
这里检验数有2个，一个2，一个3。我们选择增长幅度最大的，于是我们选择检验数3所对应的 x_2 那一列,用b的值处以 x_2 得到 \theta_{i} （看变量 x_2 最多可以增加到多大还能满足条件）的值，如下图所示：
这里得到 \theta_{i} 的值分别为4，无意义，3，于是定 x_2 的增长幅度为3，这时 x_5 对应的值变为了0（也就是指 x_2 入基， x_5 出基），于是我们要把 x_2 这列化成单位矩阵（0，0，1），通过初等行变换就可以了。
然后接着计算检验数，这里 x_1 对应的检验数大于0，所以我们这次令 x_1 进行增长，满足条件的情况下最多可以增长到2，这时对应的 x_3 的值为0（也就是 x_1 入基， x_3 出基）
一直出基入基循环往复。。。。直到所有非基变量对应的检验数都为负数。
计算步骤：
step1:计算最大检验数 c_{j}-z_{j}
step2:找最大检验数（结束条件：直接所有最大检验数都小于等于0）
step3:计算 \theta_{i} 的值（结果为正）
step4:找到最小的比值 \theta_{i} （无意义的比值不考虑）进行初等行变换，重新进行单纯形表的计算
（完）
