1−γ−1γ1……e（γ）−1=1−γ−1 - 《计算机科学与工程的代数、拓扑、微分和优化理论》

第四十五章单体法 45.1单纯形算法背后的思想由于Dantzig提出的单纯形算法适用于标准形式的线性规划（P），其中约束条件由a x=b和x≥0给出，矩阵m×n为秩m，目标函数c 7→cx。该算法要么报告（p）没有可行解，要么（p）没有边界，要么生成最优解。在几何上，该算法在多面体P（A，B）中逐点爬升，试图提高目标函数的值。由于顶点对应于基本可行解，因此单纯形算法实际上适用于基本可行解。回想一下，一个基本可行解X是一个可行解，其中有一个子集k 1，…，n的大小m，这样，由指数属于k的a的列组成的矩阵ak是线性无关的，并且x j=0表示所有j/∈k。我们还让 j>（x）是一组索引 j>（x）=j∈1，…，n xj>0，因此，对于一个与k有关的基本可行解x，我们有j>（x）k。实际上，根据命题44.2，可行解x是一个基本可行解，如果aj>（x）的列是线性无关的。如果j>（x）对所有基本可行解x都有基数m，那么simplex算法在每一步都会取得进展，这意味着它将严格增加目标函数的值。不幸的是，对于某些基本可行解，（x）（x）=4。有两种方法可以形成包含第四列的一组两个线性无关的列。给出了一个基本可行的解X，它与M的一个子集K有关，因为矩阵AK的列是线性无关的，通过滥用语言，我们把AK的列称为X的基。如果u是（p）的一个顶点，即（p）的一个基本可行解，在“正常模式”下，单纯形算法试图沿着一条边从顶点u移动到相邻顶点v（带有u，v∈p（a，b）rn），它对应于一个基本可行解，其b将一个基本向量a k替换为k∈k，将另一个非基本向量a j替换为一些j/∈k，从而提高目标函数的值。让我们用一个例子来演示这个过程。例45.2。设（p）为下列标准形式的线性程序。最大化x1+x2 从属于 −x1+x2+x3=1 x1+x4=3 x2+x5=2 x1≥0，x2≥0，x3≥0，x4≥0，x5≥0。矩阵A和向量B由下式给出： .

图45.1：与实施例45.2相关的平面H多面体。最初的基本可行解是起源。单纯形算法首先沿水平橙色线移动到顶点U1处的可行解。然后沿垂直红线移动，得到最优可行解u2。与基k=3,4,5对应的向量u0=（0,0,1,3,2）是一个基本可行解，目标函数的对应值为0+0=0。由于K=3,4,5对应的列（a3、a4、a5）是线性独立的，我们可以将a1和a2表示为

自从 1a3+3a4+2a5=au0=b，对于任何θ∈r，我们有 B=1A3+3A4+2A5−θA1+θA1 =1A3+3A4+2A5−θ（−A3+A4）+θA1 =θa1+（1+θ）a3+（3−θ）a4+2a5，和 b=1a3+3a4+2a5−θa2+θa2=1a3+3a4+2a5−θ（a3+a5）+θa2=θa2+（1−θ）a3+3a4+（2−θ）a5。在第一种情况下，向量（θ，0,1+θ，3−θ，2）是一个可行的解，iff 0≤θ≤3，目标函数的新值是θ。在第二种情况下，向量（0，θ，1−θ，3,2−θ，1）是一个可行的解iff 0≤θ≤1，目标函数的新值也是θ。考虑第一个案例。很自然地，我们会问是否可以通过设置（θ，0,1+θ，3−θ，2）的坐标中的一个为零来获得另一个顶点并增加目标函数，在这种情况下，通过选择θ=3来获得第四个顶点。这就产生了与基（a1，a3，a5）相对应的可行解（3，0，4，0，2），因此确实是一个基本可行解，目标函数的改进值等于3。请注意，A4离开了基准（A3、A4、A5），A1进入了新的基准（A1、A3、A5）。我们现在可以用基（a1，a3，a5）来表示a2和a4，这很容易，因为我们已经用（a3，a4，a5）来表示a1和a2了，a1和a4被交换了。这种步骤称为旋转步骤。我们得到 A2=A3+A5 A4=A1+A3。然后我们用u1=（3,0,4,0,2）和基（a1，a3，a5）重复这个过程。我们有 B=3A1+4A3+2A5−θA2+θA2 =3A1+4A3+2A5−θ（A3+A5）+θA2 =3A1+θA2+（4−θ）A3+（2−θ）A5， B=3A1+4A3+2A5−θA4+θA4=3A1+4A3+2A5−θ（A1+A3）+θA4=（3−θ）A1+（4−θ）A3+θA4+2A5。在第一种情况下，点（3，θ，4−θ，0,2−θ）是一个可行的解iff 0≤θ≤2，目标函数的新值为3+θ。在第二种情况下，点（3−θ，0,4−θ，θ，2）是一个可行的解iff 0≤θ≤3，目标函数的新值为3−θ。为了增加目标函数，我们必须选择第一种情况并选择θ=2。然后得到可行解u2=（3，2，2，0，0），对应于基（a1，a2，a3），是一个基本可行解。目标函数的新值为5。接下来，我们用基础（a1，a2，a3）表示a4和a5。同样，这很容易做到，因为我们刚刚交换了A5和A2（一个旋转步骤），我们得到 . 我们用u2=（3,2,2,0,0）和基（a1，a2，a3）重复这个过程。我们有 B=3A1+2A2+2A3−θA4+θA4 =3A1+2A2+2A3−θ（A1+A3）+θA4 =（3−θ）A1+2A2+（2−θ）A3+θA4，和 B=3A1+2A2+2A3−θA5+θA5=3A1+2A2+2A3−θ（A2−A3）+θA5=3A1+（2−θ）A2+（2+θ）A3+θA5。在第一种情况下，点（3−θ，2,2−θ，θ，0）是一个可行的解iff 0≤θ≤2，目标函数的值是5−θ。在第二种情况下，点（3,2−θ，2+θ，0，θ）是一个可行的解iff 0≤θ≤2，目标函数的值也是5−θ。因为我们必须有θ≥0才能有一个可行的解，所以没有办法增加目标函数。在这种情况下，我们得到了一个最优解，在我们的情况下，u2=（3,2,2,0,0），目标函数的最大值等于5。我们还可以将单纯形算法应用于顶点u0=（0,0,1,3,2）和向量（0，θ，1θ，1），这是一个可行的解决方案，iff 0≤θ≤1，具有新的目标函数值。选取θ=1，得到了与基（a2，a4，a5）相对应的可行解（0，1，0，3，1），这实际上是一个顶点。目标函数的新值为1。然后我们用获得的基础（a2，a4，a5）表示a1和a3。 A1=A4−A3 a3=a2−a5，用（0,1,0,3,1）和基（a2，a4，a5）重复该过程。再经过三个步骤，我们就能得到最佳解u2=（3,2,2,0,0）。让我们回到例子45.1的线性程序，目标函数x2，其中矩阵a和向量b由 . 回想一下，u0=（0,0,0,2）是一个退化的基本可行解，目标函数的值为0。与实施例45.1相关的H多面体的平面图见图45.2。

图45.2：与实施例45.1相关的平面H多面体。最初的基本可行解是起源。单纯形算法沿着倾斜的橙色线移动到三角形的顶点。选择基础（A3、A4）。然后我们有了

我们得到 B=2A4−θA1+θA1 =2A4−θ（−A3+A4）+θA1 =θa1+θa3+（2−θ）a4， b=2a4−θa2+θa2=2a4−θa3+θa2 =θa2−θa3+2a4。在第一种情况下，点（θ，0，θ，2−θ）是可行解iff 0≤θ≤2，目标函数的值为0，在第二种情况下，点（0，θ，−θ，2）是可行解iffθ=0，目标函数的值为θ。但是，由于在第二种情况下必须有θ=0，所以也没有办法增加目标函数。结果表明，为了使单纯形算法所考虑的情况尽可能互相排斥，因为在第二种情况下，目标函数值的θ系数为非零，即1，我们应该选择第二种情况。我们必须选择θ=0，但是我们可以交换向量a3和a2（因为a2进来了，a3有系数−θ，这就是θ必须为零的原因），我们得到了基本可行解u1=（0,0,0,2）和新的基（a2，a4）。请注意，这个基本可行解与之前的相同顶点（0,0,0,2）对应，但基础已经改变。向量 a1和a3可以用基（a2，a4）表示为

我们现在用u1=（0,0,0,2）和基（a2，a4）重复这个过程，我们得到 B=2A4−θA1+θA1 =2a4−θ（−a2+a4）+θa1=θa1+θa2+（2−θ）a4，和 B=2A4−θA3+θA3=2A4−θA2+θA3 =−θa2+θa3+2a4。在第一种情况下，点（θ，θ，0,2−θ）是可行解iff 0≤θ≤2，目标函数的值是θ，在第二种情况下，点（0，−θ，θ，2）是可行解iffθ=0，目标函数的值是θ。为了增加目标函数，我们必须选择第一种情况并选择θ=2。得到了可行解u2=（2，2，0，0），其对应基为（a1，a2），目标函数值为2。矢量a3和a4以基（a1，a2）表示为 a3=a2 a4=a1+a3，我们用u2=（2，2，0，0）和基（a1，a2）重复这个过程。我们得到 B=2A1+2A2−θA3+θA3=2A1+2A2−θA2+θA3 =2A1+（2−θ）A2+θA3，和 B=2A1+2A2−θA4+θA4=2A1+2A2−θ（A1+A3）+θA4=（2−θ）A1+2A2−θA3+θA4。在第一种情况下，点（2,2−θ，0，θ）是可行解iff 0≤θ≤2，目标函数的值是2−θ，在第二种情况下，点（2−θ，2，−θ，θ）是可行解iffθ=0，目标函数的值是2。这一次没有办法改进目标函数，我们得到了目标函数最大值为2的最优解u2=（2,2,0,0）。现在让我们考虑一个无限线性程序的例子。例45.3。设（p）为下列标准形式的线性程序。最大化x1取决于 x1−x2+x3=1 −x1+x2+x4=2 x1≥0，x2≥0，x3≥0，x4≥0。矩阵A和向量B由下式给出： . 与基k=3,4对应的向量u0=（0,0,1,2）是一个基本可行解，目标函数的对应值为0。向量a1和a2用基（a3，a4）表示 A1=A3-A4 A2=−A3+A4。从u0=（0,0,1,2）开始，我们得到 b=a3+2a4−θa1+θa1 =a3+2a4−θ（a3−a4）+θa1 =θa1+（1−θ）a3+（2+θ）a4， b=a3+2a4−θa2+θa2=a3+2a4−θ（−a3+a4）+θa2=θa2+（1+θ）a3+（2−θ）a4。

图45.3：与实施例45.3相关的平面H多面体。最初的基本可行解是起源。单纯形算法首先沿水平靛蓝线移动到顶点（1,0）处的基本可行解。通过沿橙色箭头θ（1,1）参数化的边界线移动，可以得到任何最优可行解。在第一种情况下，点（θ，0,1−θ，2+θ）是可行解iff 0≤θ≤1，目标函数的值是θ，在第二种情况下，点（0，θ，1+θ，2−θ）是可行解iff 0≤θ≤2，目标函数的值是0。为了增加目标函数，我们必须选择第一种情况，并选择θ=1。我们得到了与基（a1，a4）对应的可行解u1=（1，0，0，3），因此它是一个基本可行解，目标函数的值为1。向量a2和a3是根据基（a1，a4）通过下式给出的。 . 用u1=（1,0,0,3）重复这个过程，我们得到 b=a1+3a4−θa2+θa2 =a1+3a4−θ（−a1）+θa2=（1+θ）a1+θa2+3a4，和 b=a1+3a4−θa3+θa3=a1+3a4−θ（a1+a4）+θa3=（1−θ）a1+θa3+（3−θ）a4。

在第一种情况下，点（1+θ，θ，0,3）是所有θ≥0的可行解，如果为1+θ，则目标函数的值；在第二种情况下，点（1-θ，0，θ，3-θ）是可行解，如果为0≤θ≤1，则目标函数的值为1-θ。这一次，我们的处境是（1+θ，θ，0,3）=（1,0,0,3）+θ（1,1,0,0），θ≥0 在可行解集合中形成无限射线，目标函数1+θ在此射线上不受上述限制。这表明我们的线性规划虽然可行，但是无界的。现在让我们描述一下单纯形算法的一般步骤。 45.2一般的单纯形算法我们假设我们已经有了一个初始顶点U0。这个顶点对应于一个基为k0的基本可行解。稍后我们将证明，总是可以找到线性规划（P）的基本可行解是标准形式，或者检测（P）没有可行解。单纯形算法的思想是：给定一对（u，k）由基本可行解u和u的基k组成，找到另一对（u+，k+）由另一个基本可行解u+和u+的基k+组成，这样通过删除一些基本索引k−∈k从k中得到k+。并加入一些非基本指标j+∈/k，使目标函数的值增加（最好严格）。交换向量ak和aj+的步骤称为旋转步骤。假设u是一个给定的顶点，对应于一个基本可行解的基k，由于与指数k∈k对应的m向量ak是线性无关的，它们构成了一个基，因此对于每一个非基j/∈k，我们写下 aj=xγkjak.（）钾钾我们让它成为向量。实际上，由于矢量依赖于k，为了非常精确，我们应该用（γkj）k表示它的分量，但是为了简化符号，我们通常写γkj而不是（γkj）k（除非出现混淆）。稍后我们将解释如何有效地计算系数γkj。因为u是一个可行的解，我们有u≥0和au=b，也就是说，（）对于每一个输入基k的候选非基j/∈k，我们试图找到一个新的顶点u（θ），它改进了目标函数，为此我们在方程（）中加−θaj+θaj=0到b，然后用方程（）的右边替换−θaj中aj的出现。泰恩

因此，出现在上述方程右侧的向量u（θ）由 J u i−θγi，如果i∈k u（θ）i=θ，如果i=j 0，如果i/∈k j 自动满足约束条件au（θ）=b，该向量是一个可行的解iff θ≥0且Uk≥θγkj，所有k∈k。显然θ=0是一个解，如果，然后我们得到了0≤θ≤θj的一系列可行解，u（θ）的目标函数的值为 . 因为目标函数的潜在变化是

θ≥0，如果Cj−pk∈kγkjck≤0，则目标函数不能增加。然而，如果某些j+∈/k为0，如果θj+>0，则可以通过选择任何θ>0严格增加目标+函数，使θ≤θj，因此选择θ=θj+，自然会使u（θ）的至少一个系数为零，这也会使目标函数的增加最大化。在这种情况下（以下情况（b2）），我们得到一个新的可行解u+=u（θj+）。现在，如果θj+>0，那么有一些指数k∈k，这样的−0，所以我们可以为离开基K的向量ak选择这样的指数k−。我们声称k+=（k−−k−）j+是基。这是因为与ak列相关的系数不是零（实际上是0），所以方程（），即 aj+=γkj+−ak−+xγkj+ak， K∈K−K− 得出方程，这些方程表明，向量（m，sincek）k∈k+所跨越的子空间是相同的。然而，K+也有M元素，它必须是一个基础。因此，k是维数m的基础，因此该子空间具有维数auk+）k=∈kuand，向量（θj+）是基本的（A）可行的解决方案。上述情况是最常见的，但也可能出现其他情况。接下来，我们将讨论所有可能发生的情况。案例（a）。对于所有的j/∈k，我们都有0，然后证明u是一个最优解。否则，我们是在案例（b）中。案例（b）。对于一些j/∈k（不一定唯一），我们有Cj−pk∈kγkjck>0。有三个子类。案例（B1）。如果对于上面的一些j/∈k，我们也有0代表所有k∈k，因为Uk≥0代表所有k∈k，这对θ没有限制，并且目标函数在上面是无界的。示例45.3证明了这一点，其中k=3,4和j=2，因为案例（B2）。存在一些指数j+∈/k，因此同时 0，这意味着目标函数可能是

增加；（2）存在一些k∈k+，使得γkj+>0，对于每一个暗示θj>0。如果我们选择θ=θj+其中，

0，然后Uk>0，那么可行的解决方案u+由 +=uθj+−θj+γij+ifif i i∈=kj+i 用户界面 0，如果i/∈k j+ 是p（a，b）的顶点。如果我们选取任何指数k−k，使之为+，那么 K+=（K−K−）J+是U+的基础。矢量aj进入新的基k+，矢量ak-离开旧的基k。这是一个关键步骤。目标函数严格增加。示例45.2证明了这一点，其中k=3,4,5，j=1，k=4，然后 0），其中=1。因为=3，新的最佳溶液变为U+=（3,0,1−3（−1），3−3（1），2−3（0））=（3,0,4,0,2）。案例（B3）。有一些指数j/∈k，使得cj−pk∈kγkjck>0，对于满足上述性质的每一个指数j/∈k，我们同时拥有 (1) Cj−pk∈kγkjck>0，表示目标函数可能增加； (2) 有一些k∈k，这样γkj>0，uk=0，这意味着θj=0。因此，目标函数不变。在这种情况下，u是一个退化的基本可行解。我们可以将u+=u关联为一个新的基k+，如下所示：选取任何指数j+∈/k，这样 Cj+−xγkj+ck>0，钾钾以及任何指数k−∈k，使得，设k+=（k−k−−）j+。与案例（b2）一样，矢量aj+进入新的基k+，矢量ak离开旧的基k。这是一个关键步骤。然而，由于θj+=0，目标函数没有变化。示例45.1证明了这一点，其中k=3、4、j=2和k=3。很容易证明在（a）种情况下，基本可行解u是最优解，而在（b1）种情况下，线性规划是无界的。我们已经证明了在（b2）情况下，向量u+及其基k+构成一个基本可行解，并且在（b3）情况下的证明是相似的。有关详细信息，请参阅CIARLET[41]（第10章）。通过引入以下集合，可以方便地重新解释所考虑的各种情况：，和 . 那么很容易看出以下等价物成立：箱（A）⇒B=∅，箱（B）⇒B=6∅ 箱（b1）⇒b1=6∅ 壳体（b2）⇒b2=6∅ 箱（B3）⇒B3=6∅。此外，案例（a）和（b）、案例（b1）和（b3）、案例（b2）和（b3）是互斥的，而案例（b1）和（b2）不是互斥的。如果情况（b1）和情况（b2）同时出现，我们选择情况（b1），即线性程序（p）是无界的，并终止算法。下面是一些关于这个方法的评论。在（b2）情况下，即算法最常遵循的路径，必须对θj+>0（k+中的新索引）的索引j+∈/k做出各种选择。同样地，对于指数k−k离开k，必须做出各种选择，但这些选择通常不那么重要。同样地，在（b3）情况下，必须为进入k+的新指数j+∈/k做出各种选择。在（b2）和（b3）情况下，做出此类选择的标准称为透视规则。只有当u是退化顶点时，情况（b3）才会出现。但即使U退化，当γkj>0时，当Uk>0时，也可能出现情况（b2）。也可能发生u是非退化的，但由于（b2）的结果，新顶点u+退化，因为至少有两个分量，并且对于某些不同的k1，k2∈k消失。事例（a）和（b1）对应于算法终止的情况，并且事例（b2）在单纯形算法执行期间只能出现有限次数，因为目标函数严格地从顶点增加到顶点，并且只有有限多个顶点。因此，如果在任何初始基本可行解U0上启动单纯形算法，则可能出现三种互斥情况之一： (1) 有一个有限的事例（b2）和/或事例（b3）出现的序列，以事例（a）的出现结束。最后一个顶点是最优解。这是在示例45.1和45.2中发生的。 (2) 有一个有限的事例（b2）和/或事例（b3）出现的序列，以事例（b1）的出现结束。我们认为这个问题是无限的，因此没有解决的办法。这是在示例45.3中发生的。 (3) 有一个有限的事例（b2）和/或事例（b3）出现的序列，后跟一个无限的事例序列（b3）。如果发生这种情况，算法将访问某个基两次。这就是所谓的循环现象。在这一点上，算法最终没有得出结论。尽管在实践中很少出现这样的情况，但也有一些例子说明自行车运动的发生。CHVATAL[40]中给出了这样一个例子；见第3章，第31-32页，例如在某个轴规则下，七个变量和三个方程在六次迭代后循环的例子。第三种可能性可以通过选择合适的支点规则来避免。其中两条规则是布兰德规则和词典编纂规则；见chvatal[40]（第3章，34-38页）。布兰德的规则是：选择符合条件的入局指数j+∈/k中最小的一个，同样选择符合条件的出局指数k−k中最小的一个。可以证明，如果将布兰德法则选为支点法则，则不会发生循环。证明是非常技术性的；见Chvatal[40]（第3章，第37-38页），Matousek和Gardner[120]（第5章，定理5.8.1），以及Papadimitriou和Steiglitz[130]（第2.7节）。因此，假设给出了一些初始的基本可行解，并使用合适的支点规则（如布兰德规则），单纯形算法总是终止，要么生成最优解，要么报告线性程序是无边界的。不幸的是，布兰德的规则是最慢的中枢规则之一。枢轴规则的选择极大地影响了单纯形算法所经历的枢轴步骤的数量。我们不打算在这里解释各种中枢规则。我们简单地提到了以下规则，将读者引向马托塞克和加德纳[120]（第5章，第5.7节）或第43.1节中引用的文本。

最大系数，或但丁法则。
最大增幅。
最陡的边缘。
布兰德的规则。
随机边缘。最陡的边缘规则是最流行的规则之一。我们的想法是最大化比率 . 随机边规则在所有符合条件的索引中随机选取输入基向量的索引j+∈/k。现在让我们回到单纯形算法的初始化问题。我们使用定理44.7证明过程中引入的线性程序（pb）。考虑线性程序（p2）最大化cx，以ax=b且x≥0为准，以标准形式表示，其中a是m×n阶矩阵。首先，观察约束条件是方程，我们可以确保b≥0，因为每个方程aix=bi，其中bi<0可以被−aix=−bi替换。下一步是以标准形式引入线性程序（pb）最大化受试者其中ab和xb由 . 因为我们假设b≥0，向量xb=（0n，b）是（pb）的可行解，实际上是一个基本可行解，因为与指数n+1相关的矩阵，…，n+m是单位矩阵im。此外，由于所有I的Xi超过0，目标函数-（xn+1＋···+xn+m）被限制在0以上。如果我们用一个防止循环的支点规则来执行单纯形算法，从基本可行解（0n，d）开始，因为目标函数是以0为界的，那么单纯形算法以由一些基本可行解（如（u，w）给出的最优解终止，其中urn和w rm。在定理44.7的证明中，对于每一个可行解u∈p（a，b），向量（u，0m）是（pb）的最优解。因此，如果w=06，那么p（a，b）=∅，因为对于每个可行解u∈p（a，b），向量（u，0m）将产生目标函数−（xn+1+····+xn+m）等于0的值，但（u，w）将产生严格的负值，因为w=0.6

45.3。如何高效地执行旋转步骤否则，=0，u是（p2）的可行解。由于（）是（p）的基本可行解，因此与u的非零分量对应的列是线性无关的。u的一些坐标可以等于0，但由于a具有秩m，我们可以添加a的列以获得与u相关的基k，u实际上是（p2）的基本可行解。在线性程序pb上运行单纯形算法，得到线性程序p2的初始可行解（u0，k0），称为单纯形算法的第一阶段。在线性规划（p2）上运行具有初始可行解（u0，k0）的单纯形算法称为单纯形算法的第二阶段。如果线性规划（p2）的可行解很容易得到，则跳过第一阶段。有时，在第一阶段结束时，已经得到（p2）的最优解。总之，我们证明了以下事实值得记录。提案45.1.对于任何线性程序（p2）最大化cx，以ax=b且x≥0为准，在标准格式中，如果a是m×n矩阵，秩m和b≥0，则考虑标准格式的线性程序（pb）。最大化−（xn+1+····+xn+m），以abxb=b和xb≥0为准。具有防止循环的透视规则的单纯形算法从（pb）的基本可行解xb=（0n，b）开始，以最优解（u，w）结束。 (1) 如果w=06，则p（a，b）=∅，即线性规划（p2）没有可行解。 (2) 如果w=0，那么p（a，b）=6，u是（p2）的一个基本可行解，与一些基k有关。命题45.1表明，由方程组a x=b和不等式x≥0定义的多面体p（a，b）是否是可判定的。这个决策过程使用了simplex算法的一个防故障版本（防止循环），并且证明它总是终止并返回一个答案是非常重要的。 45.3如何有效地执行旋转步骤我们现在简要讨论如何从基本可行解（u，k）中计算（u+，k+）。为了避免应用置换矩阵，最好允许基k是一个索引序列，可能是无序的。因此，对于任意m×n矩阵a（m≤n）和任意序列k=（k1，k2，·····，km），矩阵ak表示m×m矩阵，其中i列为a的k ith列，同样，对于任意向量u∈rn（resp）。任意线性形式c（rn）），向量uk rm（线性形式ck（rm））是向量，其第i个条目是u（resp）中的kith条目。第i项是c）中kith项的线性项。对于每一个非基j/∈k，我们有，所以向量由，也就是说，通过解系统 akγkj=aj.（γ）要非常精确，因为矢量γkj依赖于k，它的分量应该用（γkj）ki表示，但正如我们前面所说，为了简化符号，我们写的不是（γkj）ki。为了确定哪种情况适用（（a）、（b1）、（b2）、（b3）），我们需要计算所有j/∈k的cj−pk∈kγkjck。为此，观察 . 如果我们写βk=cka−k1，那么，我们发现，βk>是系统βk>=（a−k1）>c>k的解，这意味着βk>是系统的解。 .（β）注：由于u是（p）的一个基本可行解，所以所有j/∈k都有uj=0，所以u是方程akuk=b的解，因此u的目标函数的值为cu=ckuk=cka−k1b，这一事实将在46.2节中起到至关重要的作用，说明n单纯形算法以线性规划（P）的最优解终止，然后它也产生了对偶线性规划（D）的最优解。假设我们有一个基本可行解u，u的基k，我们也有矩阵ak及其逆a−k1（可能是隐式的），以及a>k的逆（a>k）−1（可能是隐式的）。下面是单纯形算法迭代步骤的描述，几乎完全遵循chvatal（chvatal[40]，第7章，框注7.1）。（修正）单纯形法的迭代步骤 45.3。如何高效地执行旋转步骤第1步。计算所有j/∈k的cj−pk∈kγkjck=cj−βkaj，为此，计算βk>作为系统的解。 a>kβk>=c>k。如果所有j/∈k的cj−βkaj≤0，停止并返回最优解u（情况（a））。第2步。如果出现（b）种情况，则使用一个轴规则来确定哪个指数j+∈/k应输入新的基k+（条件cj+−βkaj+>0应保持）。第3步。为此计算最大值，求解线性系统 . 第4步。如果最大值为0，则停止并报告线性程序（P）未绑定（案例（B1））。 J+ 第5步。如果maxj+，并使用一个支点规则来确定哪个索引k∈kγk>0，则使用allk−k∈kkksu的比率，这样计算θ应保留k（情况（b2））。如果max=0，则使用一个轴规则来确定哪个索引k−应该保留基k（案例（B3））。第6步。将U、K和AK更新为U+和K+以及AK+。在这一步骤中，给定k=（k1，…，k，…，km）序列指定的基k，其中k−=k，则k+是通过将k’替换为输入索引j+，得到的序列，因此k+=（k1，…，j+，…，km）替换为“th slot”中的j+。向量u很容易更新。为了从AK计算AK+，我们利用AK和AK+只有一列不同，即“第j列aj+”，由线性组合给出。 . 为了简化符号，表示并回忆一下k−=k。如果k=（k1，…，km），那么ak=[ak1··········+aim]，因为ak+是替换 AK在AJ列，我们有 AK+=[AK1····AJ+···AIM]=[AK1···AKγ···AIM]=AKE（γ），式中，e（γ）是从单位矩阵im中通过用γ替换其第n列得到的以下可逆矩阵： 1γ1_ …   1γ−1 E（γ）=γ。   γ+1 1 1_   ……γm 1 由于0，矩阵e（γ）是可逆的，很容易检查其逆矩阵是否由 1−γ−1γ1……e（γ）−1=1−γ−1 - 1℃， −γ-1γ+1 1 ……γ -γ`-1γm 1 计算起来很便宜。我们也有 . 因此，如果AK和A−K1可用，那么AK+和可以根据AK和A−K1以及形式E（γ）的矩阵便宜地计算。然后，系统（γ）找到向量γkj可以很便宜地解决。自从

和（a>k+）−1=（a>k）−1（e（γ）>）−1，矩阵和（也可以从a>k，（a>k）−1和形式e（γ）>的矩阵中廉价计算。因此，寻找线性形式βk的系统（β）也可以廉价地求解。形式e（γ）的矩阵称为eta矩阵；见chvatal[40]（第7章）。证明了单纯形算法S步后得到的矩阵AKS可以写成 AKS=AKS−1ES 对于一些ETA矩阵，因此AKS可以写成产品 AKS=e1e2···es s eta矩阵。这种分解称为eta分解。ETA因子分解可用于反转AKS或迭代求解AKSγ=AJ+形式的系统。哪个方法更有效取决于EI的稀疏性。总之，从（u，k）中找到下一个基本可行解（u+，k+）的方法很便宜。我们只是想让读者了解一下这些技巧。为了有效地实现单纯形方法，我们向读者介绍了有关线性规划的文本。特别是，修改后的单纯形法在chvatal[40]、Papadimitriou和Steiglitz[130]、Bertsimas和Tsitiklis[21]和vanderbei中介绍。〔175〕。

45.4使用tableaux的单纯形算法我们现在描述一种表示单纯形算法的形式主义，即（完全）tableaux。这是所有书籍中使用的传统形式主义，模小变化。Tableau形式主义的一个特别好的特点是，可以使用基本行操作来更新Tableau，这与将矩阵缩减为行的梯队形式（rref）过程中使用的操作相同。不同的是选择轴的标准。由于Cj−ckγkj的数量在确定Aj列应作为基础的过程中起着关键作用，因此使用符号Cj表示，这称为变量xj的降低成本。降低的成本实际上取决于k，所以要非常精确，我们应该用（ck）j表示它们，但为了简化表示法，我们编写cj而不是（ck）j。我们将很快看到（ck+）i是如何用（ck）i计算的。观察执行单纯形算法下一步所需的数据是 (1) 当前的基本解决方案UK及其基础K=（k1，…，km）。 (2) 降低的成本cj=cj−cka−k1aj=cj−ckγk j，对于所有j/∈k。 (3) 所有j/∈k的向量，允许我们表达每一个。所有这些信息都可以打包成（m+1）×（n+1）矩阵，称为（完整）表，其组织如下：网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误
······ 可以方便地将第一行视为第0行，第一列视为第0列。第0行包含目标函数的当前值和降低的成本。第0列（除顶部条目外）包含当前基本解决方案UK的组件，其余列（除顶部条目外）包含向量γkj。观察到与k中指数j对应的γkj构成单位矩阵im的置换。该条目称为Pivot元素。一个表格连同新的基础k+=（k-k-）j+包含计算新的UK+、新的γkj+和新的降低成本（ck+）j所需的所有数据。如果我们将m×n矩阵定义为矩阵=[γk1······γkn]，其jth列为γkj，c为行向量c=（c1····c n），则上表用简略的形式表示网络错误网络错误网络错误网络错误我们现在证明，表格的更新可以使用基本行操作来执行，这与将矩阵缩减成行的梯队形式（RREF）过程中使用的操作相同。如果k=（k1，…，km），j+是输入基向量的索引，k−=k是离开基的列的索引，如果k+=（k1，…，k-1，j+，k`+1，…，km），sincej ak+= J ，新列γk+根据旧列γk使用（γ）和方程式计算。 . 因此，矩阵+由给出。 . 但是矩阵是这样的网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误

将row乘以1（轴的倒数），使row和column j+上的条目等于1。
从第一行减去（标准化的）第行，对于i=1，………………………………………………………，m。正是这些基本的行操作将的第列减少到了标识矩阵im的第列。因此，此步骤与将矩阵转换为行缩减梯队的过程在矩阵的第列执行的步骤序列相同。唯一的区别是选择轴的标准。由于新的基本解决方案UK+由给出，我们已经 . 这意味着U+是通过应用与完全相同的基本行操作从英国获得的。因此，正如将矩阵简化为rref的过程一样，我们可以对矩阵[uk]应用基本行操作，该矩阵由表的第1行，…，m组成。一旦得到新的矩阵+，新的降低成本由以下命题给出。 45.2号提案。给定任何标准形式的线性程序（p2）最大化cx，以ax=b且x≥0为准，其中a是m×n矩阵的秩m，如果（u，k）是（p2）的基本（不可行）解，如果k+=（k−k−）j+，其中k=（k1，…，km）和k−k，那么对于i=1，…，n我们有 . 使用降低的成本表示法，上述方程为 . 证据。在不损失一般性和简化符号的情况下，假设k=（1，…，m），并为j+写j，为km写j。因为，和ak+=ake（γkj），我们有，哪里网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误其中第一栏包含γs。由于ck+=（c1，…，c-1，cj，c`+1，…，cm），我们有，和

因此，如要求。因为（）是的第几行，我们看到45.2号命题表明，（？）其中表示的第`-行，是轴。这意味着，ck+是通过基本行操作获得的，该操作包括首先将第行标准化，将其除以轴，然后从ck中减去（ck）j+×标准化行。正是这些行操作使成本降低（ck）j+0。备注：很容易看出我们也有 ck+=c−ck+_+。我们在第45.2节中看到，在J+列进入和K-列离开的旋转步骤之后，目标函数的变化由下式得出：，哪里如果我们用zk表示目标函数ckuk的值，那么我们可以看到 . 这意味着，目标函数的新值zk+是通过将第行标准化，除以轴得到的，然后将（ck）j+×标准化第行的第零项乘以（ck）j+，加到第0行的第零项得到的。在更新降低的成本时，我们从第0行减去而不是增加（ck）j+×标准化行。这建议将−zk存储为第0行上的第0个条目，而不是zk，因为所有条目行0都由相同的基本行操作更新。因此，从现在开始，我们使用表格的表格网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误
······ simplex算法首先通过选择Cj>0的某个列来选择传入列j+，然后通过考虑0（沿着列j+）的比率来选择传出列k-，并选择k-来实现这些比率的最小值。下面是对Papadimitriou和Steiglitz[130]的一个例子使用基本行操作的单纯形算法的说明（第2.9节）。例45.4。考虑线性程序最大化−2x2−x4−5x7 x1+x2+x3+x4=4 x1+x5=2 x3+x6=3 3x2+x3+x7=6 x1、x2、x3、x4、x5、x6、x7≥0。我们得到了基本可行解u=（0,0,0,4,2,3,6），其中k=（4,5,6,7）。由于ck=（−1,0,0、−5）和c=（0、−2,0、−1,0,0−5），第一个表是网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误由于cj=cj−ckγkj，第0行是通过从c=（0、−2,0、−1,0、0、−5）减去−1×第1行和−5×第4行得到的。让我们选择J+=1列作为传入列。我们有比率（对于列1上的正条目） 4/1，2/1，因为最小值是2，所以我们把输出列选为k−=5列。枢轴1用红色表示。新的基础是k=（4,1,6,7）。接下来，我们应用行操作将列1减少到标识矩阵I4的第二个向量。为此，我们从第1行减去第2行。我们有看台网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误为了计算新的降低的成本，我们希望将c1设置为0，因此我们应用相同的行操作，并从第0行中减去第2行以获得表au。网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误接下来，选择J+=3列作为传入列。我们有比率（对于第3列的正条目） 2/1，3/1，6/1，因为最小值是2，所以我们把输出列选为k−=4列。支点1用红色表示，新基础为k=（3,1,6,7）。接下来，我们应用行操作将列3减少到标识矩阵I4的第一个向量。为此，我们从第3行和第4行中减去第1行，得到表格：网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误 - 为了计算新的降低的成本，我们要将c3设置为0，所以我们从第0行减去6×第1行，得到表格网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误 - 接下来我们选择j+=2作为输入列。我们有比率（对于第2列） 2/1，4/2，因为最小值是2，所以我们把输出列选为k−=3列。支点1用红色表示，新基础为k=（2,1,6,7）。接下来，我们应用行操作将列2减少到标识矩阵I4的第一个向量。为此，我们将第1行添加到第3行，并从第4行减去2×第1行，得到表格：网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误 −− 为了计算新的降低的成本，我们要将c2设置为0，所以我们从第0行减去8×第1行，得到表格网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误 −− 唯一可能的输入列对应于j+=5。我们有比率（对于第5列的正条目） 2/1，0/3，因为最小值是0，所以我们把输出列选为k−=7列。支点3用红色表示，新基础为k=（2,1,6,5）。由于最小值为0，基k=（2,1,6,5）退化（事实上，对应于索引5的分量为0）。接下来，我们应用行操作将第5列减少到标识矩阵I4的第四个向量。为此，我们将第4行乘以1/3，然后将标准化的第4行添加到第1行，并将标准化的第4行从第2行中减去，得到表AU：网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误 −− 为了计算新的降低的成本，我们希望将c5设置为0，所以我们从第0行减去13×第4行，得到表网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误 −− 唯一可能的输入列对应于j+=3。我们有比率（对于第3列的正条目） 2/（1/3）=6，2/（2/3）=3，3/1=3，因为最小值是3，所以我们把输出列选为k−=1列。支点2/3用红色表示，新基础为k=（2,3,6,5）。接下来，我们应用行操作将列3减少到标识矩阵I4的第二个向量。为此，我们将第2行乘以3/2，将第1行减去（1/3）×标准化第2行，将第3行减去标准化第2行，并将（2/3）×标准化第2行加到第4行，得到表格：网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误为了计算新的降低的成本，我们希望将c3设置为0，因此我们从第0行减去（2/3）×第2行以得到表网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误网络错误由于所有降低的成本都小于等于0，我们得到了最优解，即（0,1,3,0,2,0,0,0,0），最优值为−2。单纯形算法从一个基本可行解到另一个基本可行解的级数对应于多面体P顶点的访问，这些顶点与图45.4所示线性程序的约束有关。

图45.4：与通过Tableau方法优化的线性程序相关的多面体P。红色箭头路径跟踪单纯形方法从原点到顶点（0,1,3）的进程。最后，如果需要运行simplex算法的第一阶段，在simplex算法以最优解（）和基k终止的情况下，一些ui=0，那么基k包含与需要的松弛变量对应的基本列aj的索引。被逐出基地。这很容易通过执行一个涉及其他列j+的旋转步骤来实现，这些列j+对应于一个原始变量（不是松弛变量），其中（γk）ji+=06。在这一步中，（γk）ji+<0或（ck）j+≤0都无关紧要。如果原始矩阵A没有多余的方程，那么这样的步骤总是可能的。否则，（γk）ji=0表示所有非松弛变量，因此我们检测到第i个方程是多余的，我们可以删除它。 Tableau方法的其他介绍见Bertsimas和Tsitiklis[21]和Papadimitriou和Steiglitz[130]。 45.5单纯形法的计算效率最后，我们对单纯形算法的效率作一些评论。在实践中，Dantzig观察到，对于m<50和m+n<200的线性程序，单纯形算法通常需要小于3m/2的迭代，但最多需要3m的迭代。这一事实与最近用更大的程序进行的经验实验相一致，这些程序表明数字迭代是以3米为界的。因此，1972年，克莱和明蒂发现了一个线性程序，其中有n个变量和n个方程，其中dantzig的simplex算法的透视规则需要2n-1次迭代。本程序（摘自Chvatal[40]，第47页）转载如下：最大化受试者

对于i=1，…，n和j=1，…，n。如果p=max（m，n），那么，就更糟的情况而言，对于所有当前已知的透视规则，simplex算法在p中具有指数复杂性。然而，正如我们前面所说的，在实践中，诸如klee-minty示例之类的令人讨厌的示例似乎很少，并且迭代次数似乎是l。单位：m。单纯形算法在多项式时间内以m为单位运行的轴规则（透视规则）是否仍然是一个悬而未决的问题。 Hirsch推测认为存在一些支点规则，使得simplex算法在o（p）步骤中找到最优解。到目前为止，由于Kalai和Kleitman，已知的最好的边界是m1+lnn=（2n）lnm。有关此主题的更多信息，请参见马托塞克和加德纳[120]（第5.9节）和贝尔茨马斯和齐齐克利斯[21]（第3.7节）。研究人员研究了如果使用随机支点规则，在预期支点步数上找到上限的问题。已经找到了大于2米的界限（当然不是多项式）。

45.5。单纯形法的计算效率理解线性编程的复杂性，特别是单纯形算法，仍然在进行中。感兴趣的读者可参考Matousek和Gardner[120]（第5章，第5.9节），了解一些要点。在下一节中，我们将考虑确定一组约束a x≤b和x≥0是否具有解的重要理论标准。