单纯形法算法详解

文章发布时间:

最后更新时间:

文章总字数:
2.1k

预计阅读时间:
9 分钟

页面浏览: 加载中...

如果看不到本文中的公式，请手动刷新网页。

用处

单纯形法是一种线性规划迭代算法，能够在有限步内找到线性规划问题的最优解（如果解存在的话）。

算法步骤

以下述线性规划问题为例：

其中，第一行是线性目标，大括号里面的内容是约束条件。

化为标准型

  • 确定线性目标是求的max问题，如果是min问题，则将等号两边都乘以-1，从而转变为max问题。

  • 确定最后一行的每一个x都大于等于0，如果有小于等于的x，则将那个x变成两个大于等于0的数的相减。
    ​例如：如果，则可以化成。
    ​转换以后将最后一行变成，将最后一行以外约束条件里面的也变成。

  • 确定最后一行以外的约束条件都是，如果有，则不等号两边乘以-1从而变号为。

  • 单纯形法硬性要求后续约束条件化成的矩阵中存在单位矩阵，所以对于没有单位矩阵的情况，需要手动凑单位矩阵。除最后一行以外的约束条件有几行，就增加几个额外的大于等于0的变量用于凑单位矩阵。
    例如：上述线性规划问题凑完以后的结果为：

    增加了三个新的变量,这样不仅凑出了单位矩阵(后续解释)，而且还去掉了不等号。

  • 将其余每一行缺失的变量都用0补上，得到最终化为标准型的结果为：

列出初始单纯形表

\(c_{j}\) 2 3 0 0 0 \(\theta _{i}\)
\(c_{B}\) 基 b \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\)
0 \(x_{3}\) 8 1 2 1 0 0
0 \(x_{4}\) 16 4 0 0 1 0
0 \(x_{5}\) 12 0 4 0 0 1
\(\sigma_{j}\)

规则如下：

  1. 列数等于变量的个数。

  2. 行数等于大括号中多变量的式子的个数。

  3. 行的数字根据目标函数中各变量的系数找。

  4. 每个变量所在列的数字根据大括号中多变量式子中该变量的系数找。

  5. 找出变量下方已填写数字构成的矩阵中的单位矩阵，依次将单位矩阵对应的变量写在“基”那一列的下面。
  6. 将5中找到的变量上方的数字依次写在那一列的下面。
  7. 将大括号中多变量式子右侧数字依次填到b那一列的下面。

找出可行解

令“基”所在列的变量与b所在列的数字对应相等，再令其他变量等于0。

即。

求出检验数

\(c_{j}\) 2 3 0 0 0 \(\theta _{i}\)
\(c_{B}\) 基 b \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\)
0 \(x_{3}\) 8 1 2 1 0 0
0 \(x_{4}\) 16 4 0 0 1 0
0 \(x_{5}\) 12 0 4 0 0 1
\(\sigma_{j}\) 2 3 0 0 0

检验数计算公式如下：

例如：

判断最优解

观察一下这一行的数字看一下是否都0，

若这些数字都，则找到的可行解是最优解。

若这些数字有>0的，则该可行解不是最优解，需继续进行下一步。

获取入基变量

找到行最大的数字那一列对应的变量作为入基变量。

在本例中，此时的最大为3，其对应的变量是。

获取出基变量

求出,其中是入基变量对应的那一列。

若，则把的值填到表中；

若，则不用把的值填到表中；

若无意义，则不用把填到表中。

注意：若求出的都0，则该线性规划问题的解为无解解。

\(c_{j}\) 2 3 0 0 0 \(\theta _{i}\)
\(c_{B}\) 基 b \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\)
0 \(x_{3}\) 8 1 2 1 0 0 4
0 \(x_{4}\) 16 4 0 0 1 0 \(\times \)
0 \(x_{5}\) 12 0 4 0 0 1 3
\(\sigma_{j}\) 2 3 0 0 0

在本例中：

找到表中最小值对应“基”列的变量作为出基变量。

在本例中，最小的是，故其对应的变量作为出基变量。

绘制下一轮单纯形表

在原基础上对单纯形表进行扩展:

\(c_{j}\) 2 3 0 0 0 \(\theta _{i}\)
\(c_{B}\) 基 b \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\)
0 \(x_{3}\) 8 1 2 1 0 0 4
0 \(x_{4}\) 16 4 0 0 1 0 \(\times \)
0 \(x_{5}\) 12 0 4 0 0 1 3
\(\sigma_{j}\) 2 3 0 0 0
 
 
 
\(\sigma_{j}\)

处理出入基变量

找到上一轮中入基变量对应列和出基变量对应行交叉的数字m并填入新一轮的表中。(本轮中的m是4)

在新表中用(入基)上面的数字代替(出基)前面的数字，用代替，其余变量不变。(本例中用替换“基”中的)

\(c_{j}\) 2 3 0 0 0 \(\theta _{i}\)
\(c_{B}\) 基 b \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\)
0 \(x_{3}\) 8 1 2 1 0 0 4
0 \(x_{4}\) 16 4 0 0 1 0 \(\times \)
0 \(x_{5}\) 12 0 4 0 0 1 3
\(\sigma_{j}\) 2 3 0 0 0
0 \(x_{3}\)
0 \(x_{4}\)
3 \(x_{2}\) 4
\(\sigma_{j}\)

矩阵运算

对与b列组成的矩阵进行运算，将m变成1，同列其他元素变成0，形成一个新的矩阵，将该矩阵中的数字填入表格中对应的位置形成新的单纯新表。

\(c_{j}\) 2 3 0 0 0 \(\theta _{i}\)
\(c_{B}\) 基 b \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\)
0 \(x_{3}\) 8 1 2 1 0 0 4
0 \(x_{4}\) 16 4 0 0 1 0 \(\times \)
0 \(x_{5}\) 12 0 4 0 0 1 3
\(\sigma_{j}\) 2 3 0 0 0
0 \(x_{3}\) 2 1 0 1 0 -1/2
0 \(x_{4}\) 16 4 0 0 1 0
3 \(x_{2}\) 3 0 1 0 0 1/4
\(\sigma_{j}\)

找出可行解

和之前一样，得到可行解为：。

继续迭代

接下来继续计算检验数、判断最优解、获取入基/出基变量、绘制下一轮单纯形表、处理出入基变量、矩阵运算、找出可行解、计算检验数……

之后就是一直按照上述步骤进行迭代，直到检验数全部小于等于0，则说明此时可行解是最优解。

\(c_{j}\) 2 3 0 0 0 \(\theta _{i}\)
\(c_{B}\) 基 b \(x_{1}\) \(x_{2}\) \(x_{3}\) \(x_{4}\) \(x_{5}\)
0 \(x_{3}\) 8 1 2 1 0 0 4
0 \(x_{4}\) 16 4 0 0 1 0 \(\times \)
0 \(x_{5}\) 12 0 4 0 0 1 3
\(\sigma_{j}\) 2 3 0 0 0
0 \(x_{3}\) 2 1 0 1 0 -1/2 2
0 \(x_{4}\) 16 4 0 0 1 0 4
3 \(x_{2}\) 3 0 1 0 0 1/4 \(\times \)
\(\sigma_{j}\) 2 0 0 0 -3/4
2 \(x_{1}\) 2 1 0 1 0 -1/2 \(\times \)
0 \(x_{4}\) 8 0 0 -4 1 2 4
3 \(x_{2}\) 3 0 1 0 0 1/4 12
\(\sigma_{j}\) 0 0 -2 0 1/4
2 \(x_{1}\) 4 1 0 0 1/4 0
0 \(x_{5}\) 4 0 0 -2 1/2 1
3 \(x_{2}\) 2 0 1 1/2 -1/8 0
\(\sigma_{j}\) 0 0 -3/2 0 0

第四轮迭代中检验数全部小于等于0，所以计算结束。

此时可行解为。

即本线性规划问题的最优解为。

≡