高等工程数学 —— 第五章 （1）线性规划与单纯形法

高等工程数学 —— 第五章 （1）线性规划与单纯形法

线性规划标准型

• 这里 $min$ $c^{T}x$是目标函数，$Ax=b$是约束条件

转换规则：

看道例题吧：

下面我们讨论的问题都需要化成标准形式。

单纯形法

这个你看原理就感觉贼烦，简直单纯刑法！

B站发现个宝藏视频：传送门

看不懂来打我！就喜欢这种把学生当傻子般的讲课方式。这个表格画的更全一点。

不过我看的时候发现有个地方和书上的不一样，就是求判别数的时候视频里的步骤取相反数就是高工老师讲的结果。咱也不知道为啥，那就反过来吧。

例：

首先转化成标准型：

然后我们将约束条件中的系数照抄到这个表格中：

把右侧填上约束条件的数值：

然后我们去找表中的单位矩阵，并把能够组成单位矩阵的$x$去写在左侧作为基变量：

好了，到了和视频不一样的地方了。这里先看括号里的值，括号里的值是目标函数里的对应系数。然后我们算${\sigma }_j=(c_{B1}\cdot x_{j1}+c_{B2}\cdot x_{j2}+\cdots )-c_{j1}$。例如：这里第一个就是 $（0\times 3+0\times -2+0\times -4）-1=-1$
求最优目标函数值，就是$(x_{j1}\cdot b_1+x_{j2}\cdot b_2+\cdots )$.例如，这里是 $（0\times 7+0\times 12+0\times 10）=0$

上述得到的${\sigma }_j$不全为负数，所以继续下面的操作，我们选取主元：

让主元为1后把所在列的其他向量化为0，这里$x_2$是入基变量，$x_5$是出基变量，我们将其交换位置。然后，重复上面的操作计算${\sigma }_j$发现不全为负数，之后继续找主元。

不断重复上面的操作，直到${\sigma }_j$全为负数。

两阶段法

有时候会出现我们找不到单位矩阵的情况。例如：

• 可见这里只有$x_4$一个基向量。即只有单位矩阵中的第一列$(1,0,0{)}^T$

解决办法如下：

例：

这样就可以找到单位矩阵并确定基向量$x_4$,$x_6$,$x_7$

用单纯法的步骤求解：

第一阶段结束后我们就发现单位矩阵出现了：

正常求解：

大M法

也是当没有基变量时引入几个$x$来帮助构造。