接续上一篇博客，分析一下旋转（pivot）操作的原理。

1. 简单情况

第一阶段目标是找可行解。例如：
$\left\{ \begin{array}{} x_1& = &x_3-1\tag1\\ x_2& = &x_3+2 \end{array} \right.${x1​x2​​==​x3​−1x3​+2​(1)
显然非基变量 $x_3=0$x3​=0 时，基变量 $x_1=-1$x1​=−1 不是可行解。于是，我们很自然想到让 $x_1$x1​ 与 $x_3$x3​ 旋转置换，即 $x_3 = x_1+1$x3​=x1​+1。于是有：
$\left\{ \begin{array}{} x_3& = &x_1+1\tag2\\ x_2& = &x_1+3 \end{array} \right.${x3​x2​​==​x1​+1x1​+3​(2)
单纯形方法总是假定方程式右边的变量（非基变量）取值为零，于是我们得到一组可行解$x_3=1,x_2=3,x_1=0$x3​=1,x2​=3,x1​=0。

上述旋转过程，实际上是用 $x_3 = x_1+1$x3​=x1​+1 取代了(1)式中的 $x_3$x3​。(1)式中有很多方程式，如果全部这样置换，我们可以预见：

• 当右边式中 $x_3$x3​ 的系数为正时，必然导致常数项增大，这对向可行解旋转是有利的。
• 当右边式中 $x_3$x3​ 的系数为负时，必然导致常数项减小，这对向可行解旋转是不利的。

因此，我们在旋转过程中必须考虑 $x_3$x3​ 的系数符号问题。

2. 当存在 $x_i$xi​ 系数为负的情况

$\left\{ \begin{array}{} x_1& = &-x_5+3\tag3\\ x_2&=&-x_5+2\\ x_3& = &x_5-1\\ x_4&=&x_5-2 \end{array} \right.$⎩⎪⎪⎨⎪⎪⎧​x1​x2​x3​x4​​====​−x5​+3−x5​+2x5​−1x5​−2​(3)
存在四种旋转方式：
$\begin{array}{} x_5&=&-x_1+3\tag4\\ x_5&=&-x_2+2\\ x_5&=&x_3+1\\ x_5&=&x_4+2 \end{array}$x5​x5​x5​x5​​====​−x1​+3−x2​+2x3​+1x4​+2​(4)
如何判断上述旋转的优劣？我们分别置换一下看看结果：

方案一：旋转 $x_5=-x_1+3$x5​=−x1​+3
$\left\{ \begin{array}{} x_5& = &-x_1+3\tag5\\ x_2&=&x_1-1&(*)\\ x_3& = &-x_1+2\\ x_4&=&-x_1+1 \end{array} \right.$⎩⎪⎪⎨⎪⎪⎧​x5​x2​x3​x4​​====​−x1​+3x1​−1−x1​+2−x1​+1​(∗)(5)
这次旋转导致(*)式退化，常数项由正数变为负数。

方案二：旋转 $x_5=-x_2+2$x5​=−x2​+2
$\left\{ \begin{array}{} x_1& = &x_2+1\tag6\\ x_5&=&-x_2+2\\ x_3& = &-x_2+1\\ x_4&=&-x_2 \end{array} \right.$⎩⎪⎪⎨⎪⎪⎧​x1​x5​x3​x4​​====​x2​+1−x2​+2−x2​+1−x2​​(6)
这次旋转很完美，把副常数项全部消除了。

方案三：旋转 $x_5=x_3+1$x5​=x3​+1

$\left\{ \begin{array}{} x_1& = &-x_3+2\tag7\\ x_2&=&-x_3+1\\ x_5& = &x_3+1\\ x_4&=&x_3-1 \end{array} \right.$⎩⎪⎪⎨⎪⎪⎧​x1​x2​x5​x4​​====​−x3​+2−x3​+1x3​+1x3​−1​(7)
这次旋转不完美，但也没有出现把正的常数项转换为负的这种“副作用”。

方案四：旋转 $x_5=x_4+2$x5​=x4​+2
$\left\{ \begin{array}{} x_1& = &-x_4+1\tag8\\ x_2&=&-x_4\\ x_3& = &x_4+1\\ x_5&=&x_4+2 \end{array} \right.$⎩⎪⎪⎨⎪⎪⎧​x1​x2​x3​x5​​====​−x4​+1−x4​x4​+1x4​+2​(8)
这次旋转也很完美。

3. 一般性讨论

一般来讲，如果当前基变量不对应可行解，则必然存在 $x_k$xk​ 符合下述条件：
$x_k=...+b_k,b_k&lt;0\tag9$xk​=...+bk​,bk​<0(9)
根据前面讨论的，出基变量对应的常数项不一定为负。这里，我们假设出基变量 $x_i$xi​，入基变量是 $u_j$uj​，对应方程式为：
$x_i=a_{ij}u_j+...+b_i, a_{ij}\ne0\tag{10}$xi​=aij​uj​+...+bi​,aij​̸​=0(10)
于是，旋转方程式为：
$u_j=\frac{x_i}{a_{ij}}-\frac{b_i}{a_{ij}}+...\tag{11}$uj​=aij​xi​​−aij​bi​​+...(11)
对于任意基变量 $x_r$xr​，我们有
$x_r=a_{rj}u_j+...+b_r\tag{12}$xr​=arj​uj​+...+br​(12)
把(11)式代入(12)式，得
$x_r=\frac{a_{rj}}{a_{ij}}x_i+...+(b_r-\frac{a_{rj}b_i}{a_{ij}})\tag{13}$xr​=aij​arj​​xi​+...+(br​−aij​arj​bi​​)(13)

于是我们得到选择 $i,j$i,j 的一个理想条件，对于所有的 $r$r，有：
$b_r-\frac{a_{rj}b_i}{a_{ij}}\ge0\tag{14}$br​−aij​arj​bi​​≥0(14)
然而，满足这样的条件的 $i,j$i,j 有时可能找不到，因为有可能仅仅通过一次旋转无法找到可行解。例如，$a_{rj}=0$arj​=0 时，(14)对常数项 $b_r$br​ 不会产生任何影响。可以想象，如果 $a_{rj}$arj​ 的绝对值足够小，选择 $x_j$xj​ 做入基变量很难改变 $x_r$xr​ 的常数项的正负符号。

4. 如何逐步旋转到可行解？

策略是按照当前基变量 $x_1,x_2,...,x_i,x_{x+1},...$x1​,x2​,...,xi​,xx+1​,... 的顺序，步步为营，逐步消除 $b_i\lt0$bi​<0 的情况。因此，如果 $b_1,b_2,...,b_{k-1}\ge0,b_k\lt0$b1​,b2​,...,bk−1​≥0,bk​<0,如果$x_i$xi​ 是出基变量，$u_j$uj​是入基变量，我们要求下面条件成立：

$b_r-\frac{a_{rj}b_i}{a_{ij}}\ge0,r\lt k\tag{15}$br​−aij​arj​bi​​≥0,r<k(15)

也就是说，在 $x_i$xi​ 出基时，换句话讲，在消除 $b_k\lt0$bk​<0 这种情况时，必须确保 $b_1,b_2,...,b_{k-1}$b1​,b2​,...,bk−1​ 这些常数项在旋转后仍然非负才行。

利用线性规划的几何解释，不难构造一个“困难”的例子。下面这个规划问题需要多次旋转才可能得到可行解：
$\left\{ \begin{array}{} x_3&amp; = &amp;2x_1-x_2-2\tag{16}\\ x_4&amp;=&amp;-x_1+2x_2-2\\ x_5&amp; = &amp;x_1-1\\ x_6&amp;=&amp;x_2-1 \end{array} \right.$⎩⎪⎪⎨⎪⎪⎧​x3​x4​x5​x6​​====​2x1​−x2​−2−x1​+2x2​−2x1​−1x2​−1​(16)
因为只有两个非基变量，最多旋转两次就可以得到可行解。

5. 实际情况更为复杂——对上一小节内容的否定

上一小节提出的“步步为营”的想法，实际上是行不通的。原因如下：假设非基变量$x_1=0,x_2=0$x1​=0,x2​=0时，基变量$x_3&gt;0,x_4&lt;0$x3​>0,x4​<0。如果$x_4=0$x4​=0与$x_1=0$x1​=0或$x_2=0$x2​=0的交点都落在$x_3&lt;0$x3​<0的区域，因此，按照第4小节的方法，无法找到入基变量。

因此，在第一阶段旋转时，第$i$i行旋转消除$b_i&lt;0$bi​<0时，或许会引起一定的副作用，造成某个$j&lt;i$j<i在旋转之后$b_j&lt;0$bj​<0。看一下下面这个例子：

$\left\{ \begin{array}{} x_3=a_{31}x_1+a_{32}x_2+10\\ \tag{17} x_4=a_{41}x_1+a_{42}x_2-20 \end{array} \right.${x3​=a31​x1​+a32​x2​+10x4​=a41​x1​+a42​x2​−20​(17)

对应图像如下：

$x_4$x4​ 与 $x_1$x1​ 或 $x_2$x2​ 交换，都会导致 $x_3$x3​ 移出可行域。这个例子还隐含一种可能性，旋转操作有可能陷入死循环。

可以采用一个简单的处理策略解决这个问题，如果 $b_1,b_2,...,b_{k-1}\ge0,b_k\lt0$b1​,b2​,...,bk−1​≥0,bk​<0,如果$x_i$xi​ 是出基变量，$u_j$uj​是入基变量，随机选择 $j$j 使得 $a_{kj}&gt;0$akj​>0，我们要求下面条件成立：
$i \le k\\ a_{ij} \ne 0\\ \mathbf{if} \ i&lt;k \ \mathbf{then}\ a_{ij}&lt;0\ \mathbf {else} \ a_{ij} &gt; 0$i≤kaij​̸​=0if i<k then aij​<0 else aij​>0
然后，第 $i$i 行应该是使得第 $j$j 列中 $b_i/a_{ij}$bi​/aij​ 最大的那一行，因为 $b_i$bi​ 和 $a_{ij}$aij​ 符号相反，所以也可以说第 $i$i 行应该是使得第 $j$j 列中 $|b_i/a_{ij}|$∣bi​/aij​∣ 最小的那一行。

这个方法有换个关键点：

1. 随机选择 $j$j: 可以减少出现旋转过程死循环的可能性。
2. $b_i/a_{ij}$bi​/aij​ 最大：既然无法保证（15）式 $b_r-\frac{a_{rj}b_i}{a_{ij}}\ge0,r\lt k$br​−aij​arj​bi​​≥0,r<k 总是成立，我们可以在第 $j$j 列选择让$b_r-\frac{a_{rj}b_i}{a_{ij}}$br​−aij​arj​bi​​ 最大的那一行出基。

---

参考资料
三言两语讲清楚线性规划单纯形方法
线性规划两阶段求解方法
线性规划第一阶段入基变量和出基变量选择的细节讨论