运筹学单纯形法(运筹学单纯形法例题)

1、上一节中运筹学0101——线性规划，我们给出了线性规划的概念与一些相关的性质，最后通过凸集的性质证明出了，最优解一定在凸集的顶点上，但在顶点个数过多时，如何找到最优解又便成了一件麻烦的事情，所以本节介绍一种实用的方法——单纯形法。单纯形：维空间内有+1个顶点的多面体。例如0维空间内的点，1维空间内的线段，2维空间内的三角形，高维也是以此类推。也许从物理的角度很难想象高维空间是什么样子的，但这不是我们问题的关键，我们只需从数学角度理解，每当往向量组内加一组线性无关的向量，向量组的维度便增加一。

2、也可以把维度理解为对应矩阵的秩。单纯形法分为下面几个步骤：①初始基可行解的确定，②求出基可行解，③最优性检验，④换基变量⑤迭代运算。这样直接看步骤写出来一定很难以理解，它的内在思路是这样的，首先我们可以确定一组基，然后通过这一组基求出基可行解。这是①②步的工作，当我们求出了基可行解之后，我们还需要判断它是不是最优解，这就是第③步的工作最优性检验。

3、假设我们检验后知道，所求的解是最优解，那运气确实很好，倘若不是也没有关系，我们就进入第四步换基变量。这样就可以求出新的一组基可行解，再进行最优性检测，直到找到最优解为止，这叫做迭代运算。下面通过一个例子来说明单纯形法的是如何工作的。我们直接给出线性规划的标准型：。

4、①初始基可行解的确定：。先写出系数矩阵为，(非负条件不写在内)。

5、可见这个矩阵是5*3维的，根据上一节所讲的知识我们需要找一个3*3维的非奇异子矩阵，观察到他的后三列列向量是相互独立的，可以构成一组基，所对应的基变量分别是。这时在约束条件上进行变换，把基变量分别表示出来，此时基变量表达式带入目标函数之中有：，目标函数之中基变量的系数均为零，此时我们只改变非基变量，就可以得到不同的基可行解。如当令均等于0时此时就得到了一个基可行解。