单纯形法的理解
- 理解单纯形法之前必须要知道一下若干定理或者知识。
- 对于 A x = b , A : m ∗ n , x : n ∗ 1 , b : n ∗ 1 Ax=b,\quad A:m*n,\quad x:n*1,\quad b:n*1 Ax=b,A:m∗n,x:n∗1,b:n∗1，可以写成下列形式：
A x = ( A 1 , A 2 , . . . A n ) ( x 1 x 2 . . . x n ) = A 1 x 1 + A 2 x 2 + . . . + A n x n = b Ax=(A^1,A^2,…A^n)(\begin{aligned}x_1\\x_2\\…\\x_n\end{aligned})=A^1x_1+A^2x_2+…+A^nx_n=b Ax=(A1,A2,...An)(x1x2...xn)=A1x1+A2x2+...+Anxn=b
也就是说 b b b时 A A A的列向量的线性组合，线性组合的系数就是 A x = b Ax=b Ax=b方程组的一个解。 - 对于线性优化：
m i n ( c T x ) A x = b ∀ x i ≥ 0 min(c^Tx)\\ Ax=b\\ \forall x_i\ge0 min(cTx)Ax=b∀xi≥0
其最优解一定满足下面的形式（basic solution）：（同时，满足下述形式的basic solution不一定是最优的）
x = ( x 1 ≥ 0 , x 2 ≥ 0 , . . . . x m ≥ 0 , x m + 1 = 0 , x m + 2 = 0 , . . x n = 0 ) x=(x_1\ge0,x_2\ge0,….x_m\ge0,x_{m+1}=0,x_{m+2}=0,..x_n=0) x=(x1≥0,x2≥0,....xm≥0,xm+1=0,xm+2=0,..xn=0)
前面的m个数值对应基向量 B B B的解，后面代表非基向量的解。（至于为什么，查资料）
判断是否是最优解
回归到我们最初的目的，最小化 f f f的值。我们在上述的 ( 3 ) (3) (3)式中得到一个basic solution，那么这个basic solution是否是最优解呢？这时我们需要看 ( 4 ) (4) (4)式，前面项是常数项，只考虑后面的那一项。
( c N T − c B T B − 1 N ) x N = σ m + 1 x m + 1 + σ m + 2 x m + 2 + . . . σ n x n (5) (c_N^T-c_B^TB^{-1}N)x_N=\sigma_{m+1}x_{m+1}+\sigma_{m+2}x_{m+2}+…\sigma_{n}x_{n}\tag{5} (cNT−cBTB−1N)xN=σm+1xm+1+σm+2xm+2+...σnxn(5)
1. 如果对于 ∀ σ i > 0 , i ∈ ( m + 1 , n ) \forall \sigma_i\gt0, i\in (m+1,n) ∀σi>0,i∈(m+1,n)，那么想要满足 f f f最小，就必须令 x m + 1 , x m + 2 , . . . , x n x_{m+1},x_{m+2},…,x_n xm+1,xm+2,...,xn都是0，一旦有一个非零， f f f就会变大。因为我们 ( 3 ) (3) (3)中得到的解 G G G恰好满足 x m + 1 , x m + 2 , . . . , x n x_{m+1},x_{m+2},…,x_n xm+1,xm+2,...,xn都是零，而且是基本解，所以G也是最优解。
2. 如果存在 σ i ≤ 0 , i ∈ ( m + 1 , n ) \sigma_i\le0,i\in (m+1,n) σi≤0,i∈(m+1,n)，我们只要让对应的 x i > 0 x_i>0 xi>0，就能使 ( 4 ) (4) (4)式变得更小。那么此时的G就不是最优解，因为G对应的 x i = 0 x_i=0 xi=0，所以他不是最优解。
找出入基
承接上文，假设G不是最优解。也就是存在 σ i ≤ 0 , i ∈ ( m + 1 , n ) \sigma_i\le0,i\in (m+1,n) σi≤0,i∈(m+1,n)。也就是说，当 x i > 0 x_i>0 xi>0时，目标函数 f f f可以更小。也就是说（根据文章开头的引理2）， x i x_i xi对应的列向量应该时基向量（只有基向量对应的解才应该时大于等于0的）。所以应该把 x i x_i xi对应的列向量换进基向量的矩阵中。那么问题来了，如果存在多个 σ i \sigma_i σi小于0，到底应该换哪个呢？
按理说，换哪个都是可以的。但是我们的目标是更快的求出最小的 f f f，也就是让 f f f下降的最快，显然，在x等值的情况下， σ i \sigma_i σi越小， σ i x \sigma_ix σix越小， f f f也就下降的越快，因此，入基所对应的应该是
σ m + i = m i n ( σ m + 1 , σ m + 2 , . . . σ n ) 且 σ m + i ≤ 0 (6) \sigma_{m+i}= min(\sigma_{m+1},\sigma_{m+2},…\sigma_n) 且\sigma_{m+i}\le0\tag{6} σm+i=min(σm+1,σm+2,...σn)且σm+i≤0(6)
也就是矩阵A中的第 m + i m+i m+i列（也是N中的第 i i i列: N i N_i Ni）应该是基向量。
找出出基
既然找到了入基 N i N_i Ni，怎么找到出基呢？回顾上面的内容，我们找到了一个basic solution G，但G不是最优解。虽然不是最优解，但仍然是一个可行解，仍然满足：
A G = A [ x B , x N = 0 ] T = [ B , N ] [ x B , x N = 0 ] T = B x B T + N ∗ 0 = B x B T = b 也 就 是 B x B T = b (7) AG=A[x_B,x_N=0]^T=[B,N][x_B,x_N=0]^T=Bx_B^T+N*0=Bx_B^T=b\\ 也就是Bx_B^T=b\tag{7} AG=A[xB,xN=0]T=[B,N][xB,xN=0]T=BxBT+N∗0=BxBT=b也就是BxBT=b(7)
这是根据公式 ( 3 ) (3) (3)得到的(这里的 x B x_B xB特指非最优解G中的 x B x_B xB)。
同时，我们由公式 ( 6 ) (6) (6)得到，入基对应的列向量为 N i N_i Ni。考虑到B是基向量，那么其他任意向量都可以由B的列向量的线性组合来表示（上述的引理1）。那么列向量 N i N_i Ni也不例外，所以存在唯一向量 y y y满足下面式子
N i = y 1 B 1 + y 2 B 2 + . . . + y m B m = B y (8) N_i=y_1B_1+y_2B_2+…+y_mB_m=By\tag{8} Ni=y1B1+y2B2+...+ymBm=By(8)
所以PPT中的 B y = N i By=N_i By=Ni就是这么来的。（为什么唯一呢？因为B满秩）
在basic solution G中，我们知道 N i N_i Ni对应的系数是0，也就是b和 N i N_i Ni是没有关系的。但是根据上面的讨论，当 x i > 0 x_i>0 xi>0时，目标函数 f f f可以取得更小，我们假设 N i N_i Ni对应的系数为 ξ > 0 \xi>0 ξ>0。那么如何把b重新表示为 B 和 N i B和N_i B和Ni的线性组合呢？我们只需要将（9）中的第二个式子乘以 ξ \xi ξ，再将第一个式子减去第二个式子就可以了。
ξ B y = ξ N i B x B T − ξ B y = b − ξ N i 从 而 有 ： B ( x B T − ξ y ) + ξ N i = b (10) \xi By=\xi N_i\\ Bx_B^T-\xi By=b-\xi N_i\\ 从而有：B(x_B^T-\xi y)+\xi N_i=b\tag{10} ξBy=ξNiBxBT−ξBy=b−ξNi从而有：B(xBT−ξy)+ξNi=b(10)
所以就得到了PPT中的式子。
那么这个式子是什么意思呢。首先明确一下， x B T x_B^T xBT时 1 ∗ m 1*m 1∗m的向量，y也是 1 ∗ m 1*m 1∗m的向量， ξ \xi ξ时大于0的标量。
那么这个式子不就是B的列向量和 N i N_i Ni的线性组合吗。我们由（10）得到：
令 x B T − ξ y = t , t 时 1 ∗ m 的 行 向 量 B t + ξ N i = b 从 而 有 : b = t 1 B 1 + t 2 B 2 + . . . + t m B m + ξ N i (11) 令x_B^T-\xi y = t,t时1*m的行向量\\ Bt+\xi N_i=b\\ 从而有:b=t_1B_1+t_2B_2+…+t_mB_m+\xi N_i\tag{11} 令xBT−ξy=t,t时1∗m的行向量Bt+ξNi=b从而有:b=t1B1+t2B2+...+tmBm+ξNi(11)
但是我们知道最优解一定是basic solution（引理1），basic solution的特征由（2）给出。也就是说，basic solution中，基向量对应的解是m个大于等于0的分量。我们已知 ξ > 0 \xi>0 ξ>0，则 ξ \xi ξ是对应基向量的解的一个分量（线性组合的系数就是解）。所以对于 t 1 , t 2 , . . . , t m t_1,t_2,…,t_m t1,t2,...,tm，不可能都大于0，若都大于0，则含有 m + 1 m+1 m+1个正数分量了，与引理矛盾。
那么既然 t 1 , t 2 , . . . , t m t_1,t_2,…,t_m t1,t2,...,tm不可能都大于0，那么可不可以存在 t i < 0 t_i<0 ti<0呢？不可能，因为我们的约束条件要求 x i ≥ 0 x_i\ge 0 xi≥0。
而 t = x B T − ξ y t=x_B^T-\xi y t=xBT−ξy，所以:
t ≥ 0 x B T − ξ y ≥ 0 ξ ≤ x B T y 又 因 为 最 小 的 t 要 等 于 0 ， 所 以 ξ = m i n { ( x B T ) j y j ∣ y j > 0 } t\ge0\\ x_B^T-\xi y \ge 0\\ \xi \le \frac{x_B^T}{y}\\ 又因为最小的t要等于0，所以\\ \xi = min\{\frac{(x_B^T)_j}{y_j}|y_j>0\} t≥0xBT−ξy≥0ξ≤yxBT又因为最小的t要等于0，所以ξ=min{
yj(xBT)j∣yj>0}
这样就满足了 t j = 0 t_j=0 tj=0，也就是第j列并非基向量，需要换出去。到此，入基和出基均已经得到。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/204822.html原文链接：https://javaforall.net
