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

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

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

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

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

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

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

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

1、这个基可行解的实际意义是有利润的产品1，2均未被生产，故利润也为0。这一个基可行解对应的顶点处无法取到最优解。所以我们要换下一个顶点找。

2、我们可以通过分析解析式来推出顶点需要怎么换。我们看目标函数的表达式：，非基变量的系数为正，表示只要非基变量增加，也会增加，代表并没有达到最优解。同时这样系数为正的表达式并无法反应出约束条件对的影响，所以我们要想办法去换元，使变量的系数都为负，然后式子中的那个常数就为最优解。

3、顺着这个思路我们来对我们的式子变换，我们先选择正系数最大的变量，把它转换为其他变量。我们称当，有，由非负条件，我们换基时也要保证变量≥0。

4、所以，此时均满足非负条件。此时为换出基变量。

5、所以现在我们要做的事情就是把所有的换为。输入基变量换为输出基变量。原有式子做简单的变换就达到了互换的目的。