线性规划笔记之单纯形法推导

假设一些食材的属性如下表所示：

假设分别购买这些食材 x 1 x_1 x1​, x 2 x_2 x2​, x 3 x_3 x3​, x 4 x_4 x4​, x 5 x_5 x5​, x 6 x_6 x6​斤, 则总开销为： 30 x 1 + 20 x 2 + 5 x 3 + 2 x 4 + 10 x 5 + 8 x 6 30x_1+20x_2+5x_3+2x_4+10x_5+8x_6 30x1​+20x2​+5x3​+2x4​+10x5​+8x6​。现在需要在满足维生素指数不小于100，美味指数不低于100，肥胖指数不超过30，以及总重不超过10斤的情况下组合出最省钱的菜单。则问题转化为： m i n 30 x 1 + 20 x 2 + 5 x 3 + 2 x 4 + 10 x 5 + 8 x 6 min 30x_1+20x_2+5x_3+2x_4+10x_5+8x_6 min30x1​+20x2​+5x3​+2x4​+10x5​+8x6​ subject to 10 x 3 + x 4 + 8 x 5 + 14 x 6 ≥ 100 10x_3+x_4+8x_5+14x_6≥100 10x3​+x4​+8x5​+14x6​≥100 15 x 1 + 12 x 2 + 5 x 3 + x 4 + 3 x 5 − 2 x 6 ≥ 100 15x_1+12x_2+5x_3+x_4+3x_5-2x_6≥100 15x1​+12x2​+5x3​+x4​+3x5​−2x6​≥100 8 x 1 + 3 x 2 + 5 x 4 + 4 x 5 ≤ 30 8x_1+3x_2+5x_4+4x_5≤30 8x1​+3x2​+5x4​+4x5​≤30 0 ≤ x 1 + x 2 + x 3 + x 4 + x 5 + x 6 ≤ 10 0≤x_1+x_2+x_3+x_4+x_5+x_6≤10 0≤x1​+x2​+x3​+x4​+x5​+x6​≤10 我们把这类目标函数以及约束条件均为线性关系式的简单组合优化问题成为线性规划。对于这类问题在高中应该还是接触得比较多的，当初老师应该都教过用作图法来求解，比如： 根据约束画出可行域（图中阴影部分），然后沿着等值线法向量（梯度方向）移动等值线达到极限位置（继续移动会出现空集），就可以最终取得最大或最小值。而这类问题的最优解往往都落于多边形可行域的顶点上。

自1947 年，面对美国制定空军军事规划时提出的问题，丹齐克( Dantzig)首次提出了单纯形法来解决这类极值问题的求解后，应用最广的线性规划通用解法就是单纯线性法，其基本思想时从一个基本可行解出发，不断移动到下一个能使目标函数值朝优化目标改善的基本可行解上，最终达到最优的基本可行解。因为基本可行解的个数有限，所以经过有限次转换必能得出问题的最优解。如果问题无最优解，我们也可以用单纯形法来判别。

对于一个线性规划问题(以下所有加粗字母表示矩阵或向量名)： 可通过引入新的变量，将其转换为松弛形式： 比如对于问题： 可转化为： 其矩阵形式： 即： 其中 x 1 x_1 x1​, x 2 x_2 x2​被称为非基变量 x N x_N xN​， x 3 x_3 x3​, x 4 x_4 x4​被称为基变量 x B x_B xB​。这些变量前面对应的系数矩阵可分别记为非基矩阵 N N N,和基矩阵 B B B。 假设一开始非基变量 x N = 0 x_N=0 xN​=0，则由（2）可得我们的初始的基本可行解为：

则此时的目标函数值： 其上 c B c_B cB​与 c N c_N cN​分别为 c c c中与基变量和非基变量对应的分向量。接下来要讨论如何从起始的基本可行解 x 0 x^0 x0出发，找到下一个能使目标函数值改善的基本可行解。 由式(2)可得： 将（3）代入（1）中得目标函数在某一可行解 x x x处的值为： 上式中， R R R代表非基变量的下标集合， z j = c B B − 1 p j z_j=c_BB^{-1}p_j zj​=cB​B−1pj​。我们可以看到只要选取合适的变量 x j x_j xj​，就可使上述函数值减小。前面提到，在设置初始基本可行解时，我们令所有非基变量 x N = 0 x_N=0 xN​=0；现在我们可以将其中的某一个非基变量 x k x_k xk​增大为正值其余保持为零，则函数值就会相应下降，而且 z j − c j z_j-c_j zj​−cj​越大，函数值也会下降越快： 此时： 由于要求 x B x_B xB​永远不小于0，因此由(6)可计算出 x k x_k xk​的取值范围为：

即将 x k x_k xk​取到所有 b i / p i k b_i/p_{ik} bi​/pik​ 的最小值的时候，函数值会下降最快。此时将对应的基变量x_Bi变为非基变量并赋值0。并用 x B i x_{Bi} xBi​对应的 p j p_j pj​来替换 p i p_i pi​。经过上述的替换后，目标函数值减少了 ( z k − c k ) x k (z_k-c_k ) x_k (zk​−ck​)xk​。我们只需不断重复上述过程直到所有的 ( z j − c j ) (z_j-c_j ) (zj​−cj​)为非正数，也即此时取正增大任意一个非基变量 x j x_j xj​都不能使函数值减少，说明已经找到了极小点。

举个栗子： 引入松弛变量， x 3 , x 4 , x 5 x_3, x_4, x_5 x3​,x4​,x5​: 进行第一次迭代： 令 x N = 0 x_N=0 xN​=0，由(3)： 由(1)计算出此时的函数值: 接下来通过对所有非基变量计算判别数 ( z j − c j ) (z_j-c_j ) (zj​−cj​)来检查是否已经抵达最优解，根据(4):

则此时最大非负判别数为3，对应第一组非基变量, k = 1 k=1 k=1， x 1 x_1 x1​为进基变量。根据(7): 则 i = 1 i=1 i=1, 那么 x B x_B xB​中第一个分量 x 3 x_3 x3​为离基变量。 用 p 1 p_1 p1​替换 p 3 p_3 p3​进行第二次迭代： 此时函数值： 判别数： k = 3 k=3 k=3,进基变量 x 3 x_3 x3​ i = 2 i=2 i=2,离基变量为 x B x_B xB​中第二个分量 x 4 x_4 x4​

用 p 3 p_3 p3​替换 p 4 p_4 p4​进行第三次迭代： 此时函数值： 判别数： 此时所有判别数均不为正，因此得到目标函数的最优解 x 1 = 4 , x 2 = 0 x_1=4,x_2=0 x1​=4,x2​=0，最优函数值 − 12 -12 −12 单纯形法实际上运行的效率不高。许多数学家在随后提出性能更佳的算法，如改进单纯形法、对偶单纯形法等。在此文中暂时不作讨论。