21基本模型 n∈S,这里下标1表示1范数，即各分量绝对值之和。记 Un=in -Folli 则有A=0,ll1=1。由于{y|1=1)为紧集，一定存在收敛子列{，记极限为 如，由连续仍有A0=0,下面说明0是S的一个方向。 先说明如≥0。若0的某个分量<0，根据授限定义可知对充分大的i有t<-=婴 然而，根据定义 kat Tot+lk -oll t<ot-kge 当点充分大时工kt<0,与xk∈S矛盾。 进一步地，由A0=0与≥0，可计算知对任何工∈S有x+A0∈S,入≥0，从而0是S的 方向。 下面说明方向集合非空时极方向集合非空且有限。 3.由于S中要求x≥0，由定义可知S的方向d必须满足≥0。根据上一部分证明，可记标准化 方向集合（由条件，其中的d均为不同的方向） D={d1d=1,Ad=0,d≥0} 由于这个集合也能写成{x|A0x=0,x≥0}的形式，且无界时由上一部分证明非空，其极点必 然存在有限。从而只需证明D的极点对应S的不同极方向。 若d不是S的极方向，存在d1不同于d2,X1,2≥0使得d=x1d山+2d。记 == 则有 d∈D,d∈D,d=ld山ld+A2lldl1 而由于d1,d所有分量非负，，2非负，有 1=lldll IAidi+2d2ll1 =Ailldill+alldall 从而取入=lld得 d=d+(1-) 从而d不是D的校点。 反过来，若d不是D的极点，存在d1≠d2,入∈(0,1)使得d=d1+(1-)d2,根据D中不 同元素是S的不同方向即可知d不是S的极方向。 4.右推左由方向定义与S是凸集可得证，下面考虑左推右。我们进行归纳证明：当x为一维向量 时，或S为空，或S为单点集，或S={|x≥0以，满足要求。下面假设x是n-1维向量时满 足，考虑n维时。 根据上一问，由于D有界（∑：d=1且20必然有界）且凸，其任何点可以写成极点的凸组合 也即任何方向都可以写成极方向的凸组合。于是，表示中的第二项即代表任何一个方向。假设S 所有极点的凸组合构成S0,我们只需证明，对任何x生S0存在0∈S0,有d山=二∈D 这样就有x=0+lx-ol1do。 若否，对任何x0,由于d已满足do1=1与Ad=0,其若不是方向，只能有小于0的分量
2.1 基本模型 xn ∈ S，这里下标 1 表示 1 范数，即各分量绝对值之和。记 yn = xn − x0 ∥xn − x0∥1 则有 Ayn = 0, ∥yn∥1 = 1。由于 {y | ∥y∥1 = 1} 为紧集，yn 一定存在收敛子列 {yki }，记极限为 y0，由连续仍有 Ay0 = 0，下面说明 y0 是 S 的一个方向。 先说明 y0 ≥ 0。若 y0 的某个分量 y0t < 0，根据极限定义可知对充分大的 i 有 ykit < −ϵ = y0t 2 。 然而，根据定义 xkit = x0t + ∥xki − x0∥1ykit < x0t − kiϵ 当 ki 充分大时 xkit < 0，与 xki ∈ S 矛盾。 进一步地，由 Ay0 = 0 与 y0 ≥ 0，可计算知对任何 x ∈ S 有 x + λy0 ∈ S, λ ≥ 0，从而 y0 是 S 的 方向。 下面说明方向集合非空时极方向集合非空且有限。 3. 由于 S 中要求 x ≥ 0，由定义可知 S 的方向 d 必须满足 d ≥ 0。根据上一部分证明，可记标准化 方向集合 (由条件，其中的 d 均为不同的方向) D = d | X i di = 1, Ad = 0, d ≥ 0 由于这个集合也能写成 {x | A0x = b0, x ≥ 0} 的形式，且无界时由上一部分证明非空，其极点必 然存在有限。从而只需证明 D 的极点对应 S 的不同极方向。 若 d 不是 S 的极方向，存在 d1 不同于 d2，λ1, λ2 ≥ 0 使得 d = λ1d1 + λ2d2。记 d ′ 1 = d1 ∥d1∥1 , d′ 2 = d2 ∥d2∥1 则有 d ′ 1 ∈ D, d′ 2 ∈ D, d = λ1∥d1∥1d ′ 1 + λ2∥d2∥1d ′ 2 而由于 d1, d2 所有分量非负，λ1, λ2 非负，有 1 = ∥d∥1 = ∥λ1d1 + λ2d2∥1 = λ1∥d1∥1 + λ2∥d2∥1 从而取 λ = λ1∥d1∥1 得 d = λd′ 1 + (1 − λ)d ′ 2 从而 d 不是 D 的极点。 反过来，若 d 不是 D 的极点，存在 d1 ̸= d2，λ ∈ (0, 1) 使得 d = λd1 + (1 − λ)d2，根据 D 中不 同元素是 S 的不同方向即可知 d 不是 S 的极方向。 4. 右推左由方向定义与 S 是凸集可得证，下面考虑左推右。我们进行归纳证明：当 x 为一维向量 时，或 S 为空，或 S 为单点集，或 S = {x | x ≥ 0}，满足要求。下面假设 x 是 n − 1 维向量时满 足，考虑 n 维时。 根据上一问，由于 D 有界 ( P i di = 1 且 d ≥ 0 必然有界) 且凸，其任何点可以写成极点的凸组合， 也即任何方向都可以写成极方向的凸组合。于是，表示中的第二项即代表任何一个方向。假设 S 所有极点的凸组合构成 S0，我们只需证明，对任何 x /∈ S0 存在 x0 ∈ S0，有 d0 = x−x0 ∥x−x0∥1 ∈ D， 这样就有 x = x0 + ∥x − x0∥1d0。 若否，对任何 x0，由于 d0 已满足 ∥d0∥1 = 1 与 Ad0 = 0，其若不是方向，只能有小于 0 的分量。 14
2.1基木模型 记 0=max{r0+Ad∈S 由x∈S,0≥lx-xol1,而由于do有小于0分量，A0必然存在。并记1=0+od0,并假 设其第m个分量为0（根据定义必然有分量为0）。注意到，x能在0与1连线段上，所以x1亦 不能写成x)+1)d的形式，否则可直接表示出工1。 记S=Sn{x|n=0。由1存在可知非空，且满足S的条件，下面证明S的极点集与方向 集恰好是S的极点集与方向集与{rxm=0以，{d|d=0)的交集。根据定义，S1的方向是S 的方向的子集，从而S的极点、极方向一定是S的板点、授方向（更大的集合中无法表示，更小 的集合中必然无法表示)。反过来，若S1有极点s,若其能写成Aa+(1-入)b,a,b∈S,入∈(0,1)， 根据ap之0，bp≥0，p=0可知ap=p=0,a,b∈S,从而只有a=b=s。对授方向证明类似 由于五1无法在S中被表示成x+A四，其无法在S1中被表示成+A)。然而，考虑 S={r1(a1,,ap-1,ap+1…,an)z=b,x20} 其极点、板方向与S1去除第p个分量后完全对应，于是x1去除第P个分量后无法在S:中被表 示。但是，x是n一1维向量，这与归纳假设矛盾。 2.13解的存在性 确定可行域的性质之后，就可以考察线性规划问题解的情况。假设可行域极点为x①)到x因，极 方向为四到d0,则任何可行点可以写为∑：Ax回+∑j4d,∑：A=1,A,山之0。将其代入标准 型中，得到需要最小化的cx成为 ∑(cPxo)+∑4(c2a (2.2) 在可行域非空时，存在唯一解或无穷多解称为模型存在最优解，而可行域为空或目标函数可达一∞ 称为最优解不存在。 定理2.9（线性规划向题解的性质） 在式(2.2)中，标准形式线性规划模型最优解存在当且仅当所有c26)≥0。进一步地，在最优 解存在时，一定在某个极点处能取到最优。 证明若某个)<0，当山增大时x可任意减小，因此解不存在。根据式子形式可知 ∑A(ezo)+∑4，(ca)≤∑(c2r)≤minc'x0 当且仅当出全为0，入在cTx回最小的i处为1，其余为0时可取到最优解。 至从几何来看，我性规划问题相当于用某平面进行平移，寻找与可行城有交时截距的最小值。于是，存 在最优解等价于不能在变小方向无限平移，而如果能存在，一定会在某顶点取到。从这个几何看法可 以发现，即使并未化为标准形式，如果能直观看到极点与极方向，仍然会满足上述性质。 白练习2.3对可行域 1.S={红eR2|x1≥0，x2≥0,1+x2≥1} 2.T={∈R2|x1+2x2≥0，x2-x120,x2≤1} 分别求解线性规划问题min-2r1-x2
2.1 基本模型 记 λ0 = max λ {x0 + λd0 ∈ S} 由 x ∈ S，λ0 ≥ ∥x − x0∥1，而由于 d0 有小于 0 分量，λ0 必然存在。并记 x1 = x0 + λ0d0，并假 设其第 p1 个分量为 0(根据定义必然有分量为 0)。注意到，x 能在 x0 与 x1 连线段上，所以 x1 亦 不能写成 x (1) 0 + λ (1)d (1) 的形式，否则可直接表示出 x1。 记 S1 = S ∩ {x | xp1 = 0}。由 x1 存在可知非空，且满足 S 的条件，下面证明 S1 的极点集与方向 集恰好是 S 的极点集与方向集与 {x | xp1 = 0}, {d | dp1 = 0} 的交集。根据定义，S1 的方向是 S 的方向的子集，从而 S 的极点、极方向一定是 S1 的极点、极方向 (更大的集合中无法表示，更小 的集合中必然无法表示)。反过来，若 S1 有极点 s，若其能写成 λa + (1 − λ)b, a, b ∈ S, λ ∈ (0, 1)， 根据 ap ≥ 0, bp ≥ 0, sp = 0 可知 ap = bp = 0，a, b ∈ S1，从而只有 a = b = s。对极方向证明类似。 由于 x1 无法在 S 中被表示成 x (1) 0 +λ (1)d (1)，其无法在 S1 中被表示成 x (1) 0 +λ (1)d (1)。然而，考虑 S − 1 = {x − | (a1, . . . , ap−1, ap+1, . . . , an)x − = b, x− ≥ 0} 其极点、极方向与 S1 去除第 p 个分量后完全对应，于是 x1 去除第 p 个分量后无法在 S − 1 中被表 示。但是，x − 是 n − 1 维向量，这与归纳假设矛盾。 2.1.3 解的存在性 确定可行域的性质之后，就可以考察线性规划问题解的情况。假设可行域极点为 x (1) 到 x (k)，极 方向为 d (1) 到 d (l)，则任何可行点可以写为 P i λix (i) + P j µjd (j) , P i λi = 1, λi , µj ≥ 0。将其代入标准 型中，得到需要最小化的 c T x 成为 X i λi(c T x (i) ) +X j µj (c T d (j) ) (2.2) 在可行域非空时，存在唯一解或无穷多解称为模型存在最优解，而可行域为空或目标函数可达 −∞ 称为最优解不存在。 定理 2.9 (线性规划问题解的性质) ♡ 在式 (2.2) 中，标准形式线性规划模型最优解存在当且仅当所有 c T d (j) ≥ 0。进一步地，在最优 解存在时，一定在某个极点处能取到最优。 证明 若某个 c T d (j) < 0，当 µj 增大时 c T x 可任意减小，因此解不存在。根据式子形式可知 X i λi(c T x (i) ) +X j µj (c T d (j) ) ≤ X i λi(c T x (i) ) ≤ min i c T x (i) 当且仅当 µj 全为 0，λ 在 c T x (i) 最小的 i 处为 1，其余为 0 时可取到最优解。 从几何来看，线性规划问题相当于用某平面进行平移，寻找与可行域有交时截距的最小值。于是，存 在最优解等价于不能在变小方向无限平移，而如果能存在，一定会在某顶点取到。从这个几何看法可 以发现，即使并未化为标准形式，如果能直观看到极点与极方向，仍然会满足上述性质。 练习 2.3 对可行域 1. S := {x ∈ R 2 | x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 1} 2. T := {x ∈ R 2 | x1 + 2x2 ≥ 0, x2 − x1 ≥ 0, x2 ≤ 1} 分别求解线性规划问题 min −2x1 − x2。 15
2.2单纯形法 1.作图可发现平面上S的极点为(0,1)，(1,0)，极方向为(0,1)，(1,0)，因此计算得解在(1,0)，最优 位-2。 2.作图可发现平面上T的极点为(0,0)，(-2,1)，(1,1)，因此计算得解在(1,1)，最优值-3。 从解的性质证明过程中可以得到，线性规划问题只有三种可能结果：可行域为空，无界（即对任何 M∈R,存在x使得cx<M,或最优解存在。 2.2单纯形法 2.2.1可行基解 根据上方的推导，想求解线性规划问题，只需要在极点处进行即可，于是，我们需要寻找极点的 更多性质。极点的定义可以说是从几何上得到的，因此在这节进行一些代数上的推导。 首先，对于标准型中的等式约束Ax=b,可以进行化简：假设A有某些行向量线性相关，不妨设 有=∑1入，这时若1=∑>1，则第一个约束可以被其他约束推出，从而可以删去；否 则产生了两个互相矛盾的等式约束，可行域为空，无意义。综合可不妨假设Am×m是行满秩的，由此 其存在阶数为m的可逆子方阵。 假设第B,B2,,B列构成的子方阵可逆，可形式上将A分块成(BN),其中B包含了上方 B,的列，同时将工对应分块为 EN 空由于实际上B的行并不连续排列，这是一个形式上的分块。 直接将等式约束代人，可得BxB+NrN=b,于是B=B1b-B-NN。这也就意味着，如 此分块后，等式约束中事实上只有xN的部分是自由的，剩下的xB中分量可以由N解出来。 定义210（基解、可行基解 对于任何可能的B的选取，令xN=0,则x= B-16 ,这祥的x称为方程组的一个基解，对 0 应的B称为基矩阵。xB的各分量称为基变量，xN称为非变量。 若这时的工又满足工≥0，即Bb≥0，则称为可行基解，对应有可行基矩阵与可行基变量。品 至（可行）基解的定义只与方程A红=b有关，仍然与目标函数无关。 h练习2.4将S:={x∈R21≥0，≥0，x1+x221化为标准型，并计算全部可行基解。与之前计 算出的极点集合比较。 解令g=西1+-1，则标准型为x≥0，西1+2-x3=1,基解有(1,0,0)，(0,1,0)，(0,0，-1)，前两 个为可行基解，与之前所算出的极点一一对应。 接下来我们将看到，对于化为标准形式的线性规划问题，上面从代数角度计算出的可行基解与几 何角度得到的极点集合是一致的： 定理2.1山（可行基解与极点等价性） 对于标准形式线性规划问题的可行城S={红|Ax=b,x≥0}，假设A是行满秩的，则S的极 点集合与可行基解集合相同
2.2 单纯形法 解 1. 作图可发现平面上 S 的极点为 (0, 1),(1, 0)，极方向为 (0, 1),(1, 0)，因此计算得解在 (1, 0)，最优 值 −2。 2. 作图可发现平面上 T 的极点为 (0, 0),(−2, 1),(1, 1)，因此计算得解在 (1, 1)，最优值 −3。 从解的性质证明过程中可以得到，线性规划问题只有三种可能结果：可行域为空，无界 (即对任何 M ∈ R，存在 x 使得 c T x < M)，或最优解存在。 2.2 单纯形法 2.2.1 可行基解 根据上方的推导，想求解线性规划问题，只需要在极点处进行即可，于是，我们需要寻找极点的 更多性质。极点的定义可以说是从几何上得到的，因此在这节进行一些代数上的推导。 首先，对于标准型中的等式约束 Ax = b，可以进行化简：假设 A 有某些行向量线性相关，不妨设 有 a T 1 = P i>1 λia T i ，这时若 b1 = P i>1 λibi，则第一个约束可以被其他约束推出，从而可以删去；否 则产生了两个互相矛盾的等式约束，可行域为空，无意义。综合可不妨假设 Am×n 是行满秩的，由此 其存在阶数为 m 的可逆子方阵。 假设第 B1, B2, . . . , Bm 列构成的子方阵可逆，可形式上将 A 分块成 B N ，其中 B 包含了上方 Bi 的列，同时将 x 对应分块为 xB xN ! 。 由于实际上 B 的行并不连续排列，这是一个形式上的分块。 直接将等式约束代入，可得 BxB + NxN = b，于是 xB = B−1 b − B−1NxN。这也就意味着，如 此分块后，等式约束中事实上只有 xN 的部分是自由的，剩下的 xB 中分量可以由 xN 解出来。 定义 2.10 (基解、可行基解) ♣ 对于任何可能的 B 的选取，令 xN = 0，则 x = B−1 b 0 ! ，这样的 x 称为方程组的一个基解，对 应的 B 称为基矩阵。xB 的各分量称为基变量，xN 称为非基变量。 若这时的 x 又满足 x ≥ 0，即 B−1 b ≥ 0，则称为可行基解，对应有可行基矩阵与可行基变量。 (可行) 基解的定义只与方程 Ax = b 有关，仍然与目标函数无关。 练习 2.4 将 S := {x ∈ R 2 | x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 1} 化为标准型，并计算全部可行基解。与之前计 算出的极点集合比较。 解 令 x3 = x1 + x2 − 1，则标准型为 x ≥ 0, x1 + x2 − x3 = 1，基解有 (1, 0, 0),(0, 1, 0),(0, 0, −1)，前两 个为可行基解，与之前所算出的极点一一对应。 接下来我们将看到，对于化为标准形式的线性规划问题，上面从代数角度计算出的可行基解与几 何角度得到的极点集合是一致的： 定理 2.11 (可行基解与极点等价性) ♡ 对于标准形式线性规划问题的可行域 S = {x | Ax = b, x ≥ 0}，假设 A 是行满秩的，则 S 的极 点集合与可行基解集合相同。 16
22单绝形法 证明假设y是极点，根据凸集表示定理中的证明，若B1,,B是y的非零分量，则A的第B1,,B 列线性无关。由于A至多m列线性无关，必然有k≤m,这就说明了y是基解，而极点是可行点，于 是y是可行基解。 假设是可行基解，若存在班，，入∈(0,1)使彩=A班+(1-A2,设班= 功N (这里B,N分块与y一致)。由于 AhN+(1-入)pN=0.入∈(0.1)，功>0,2≥0 可得必须1N=2N=0,而根据A1=A班=b,计算又可以证明班B=2B=B-b,从而 =现=，得证。 结合这个定理与凸集表示定理，可以得到很多有用的结论。例如，通过标准形式可行域非空必存 极点可以推出： 命题2.2（可行基解存在性定理 若线性规划问题有可行解，则必有可行基解。 而根据最优解存在时必能在极点取到即知 命题2.13（线性规划问题解的性质田 在线性规划问题最优解存在时，一定在个可行基解能取到最优。 2.2.2主要过程 上一节的讨论后，我们已经说明，只需婴在可行基解处寻找最优解。因此，单纯形算法的基本思想 就是通过可行基解间不断迭代来找到最优的可行基解。这一节，我们先考虑最优判定与转轴运算，也 即找到下一个可行基解的过程。以下假设Amn,即B为m×m阶方阵，N为m×n一m阶。 根据xB=B-1b-B-1NxN,将c也对应划分为cB与Cw后，可直接计算出目标函数z=CExB十 cN=cB-1b+(C以-B-1N)rw。在c-召B-1N的每个分量都≥0时，由于可行解要求 rN≥0，在xN=0时即取到了最小值cB-1b。记0=c雷B-1b,=c日B-1a,即有： 定理214（最优解判定） 取定个可行基解工= B-16 、0)后，若对应的B,N满灵-≥0巧∈,则即为问题 优解。 9 证明直接计算z=0+(c-c写B-1N)EN=0+∑N(C-)之20得结论。 反之，若最优解性质不成立，一定存在某个P∈N使？一p<0。这时，适当增加印会使：更 小（注意增加也意味者对应改变B的分量。由于：=0十∑，9一出，若可以无限制增 大，z会趋于负无穷，于是在解存在时，工，增大必然引起xB的某个分量减小，而临界值即为工B的某 个分量恰好减小到0。这时，xN中的x,分量增加到正，而xB中原本为正的分量减小到了0，非零分 量仍然最多m个，因此得到的仍然是可行基解，这个过程就称为一次转轴运算
2.2 单纯形法 证明 假设 y 是极点，根据凸集表示定理中的证明，若yB1 , . . . , yBk 是 y 的非零分量，则A 的第 B1, . . . , Bk 列线性无关。由于 A 至多 m 列线性无关，必然有 k ≤ m，这就说明了 y 是基解，而极点是可行点，于 是 y 是可行基解。 假设 y 是可行基解，若存在 y1, y2, λ ∈ (0, 1) 使 y = λy1 + (1−λ)y2，设 y1 = y1B y1N ! , y2 = y2B y2N ! (这里 B, N 分块与 y 一致)。由于 λy1N + (1 − λ)y2N = 0, λ ∈ (0, 1), y1 ≥ 0, y2 ≥ 0 可得必须 y1N = y2N = 0，而根据 Ay1 = Ay2 = b，计算又可以证明 y1B = y2B = B−1 b，从而 y1 = y2 = y，得证。 结合这个定理与凸集表示定理，可以得到很多有用的结论。例如，通过标准形式可行域非空必存 极点可以推出： 命题 2.12 (可行基解存在性定理) ♠ 若线性规划问题有可行解，则必有可行基解。 而根据最优解存在时必能在极点取到即知： 命题 2.13 (线性规划问题解的性质 II) ♠ 在线性规划问题最优解存在时，一定在某个可行基解能取到最优。 2.2.2 主要过程 上一节的讨论后，我们已经说明，只需要在可行基解处寻找最优解。因此，单纯形算法的基本思想 就是通过可行基解间不断迭代来找到最优的可行基解。这一节，我们先考虑最优判定与转轴运算，也 即找到下一个可行基解的过程。以下假设 Am×n，即 B 为 m × m 阶方阵，N 为 m × n − m 阶。 根据 xB = B−1 b−B−1NxN，将 c 也对应划分为 cB 与 cN 后，可直接计算出目标函数 z = c T B xB + c T N xN = c T BB−1 b + (c T N − c T BB−1N)xN。在 c T N − c T BB−1N 的每个分量都 ≥ 0 时，由于可行解要求 xN ≥ 0，在 xN = 0 时即取到了最小值 c T BB−1 b。记 z0 = c T BB−1 b, zj = c T BB−1aj，即有： 定理 2.14 (最优解判定) ♡ 取定某个可行基解 x = B−1 b 0 ! 后，若对应的 B, N 满足 cj − zj ≥ 0, ∀j ∈ N，则 x 即为问题最 优解。 证明 直接计算 z = z0 + (c T N − c T BB−1N)xN = z0 + P j∈N (cj − zj )xj ≥ z0 得结论。 反之，若最优解性质不成立，一定存在某个 p ∈ N 使 cp − zp < 0。这时，适当增加 xp 会使 z 更 小 (注意增加 xp 也意味着对应改变 xB 的分量)。由于 z = z0 + P j∈N (cj − zj )xj，若 xp 可以无限制增 大，z 会趋于负无穷，于是在解存在时，xp 增大必然引起 xB 的某个分量减小，而临界值即为 xB 的某 个分量恰好减小到 0。这时，xN 中的 xp 分量增加到正，而 xB 中原本为正的分量减小到了 0，非零分 量仍然最多 m 个，因此得到的仍然是可行基解，这个过程就称为一次转轴运算。 17
2.2单纯形法 第法2.15（单纯形法） 初始化 确定初始可行基划分B.N.并计算B=B一1b。 2.最优判定 计算向量w=(BT)lcB,对所有j∈N计算名=wTaj。若c≥对-切j∈N成立， 则当前可行基解已是最优解，最优值为如6，算法终止。否则，选择一个？一<0的 p∈N进入下一步。 3.镂轴送算 计算向量物=B-1ap。若≤0，则问题无有界解，算法终止。 否则，找出r使得△=票是所有碧，咖>0中的最小位. 更新基变量：令n=△，xB=EB-△，这里B为原来的分量，更新后xB,由△定义 成为0。 更新B,N:将B原本的第r列aB,用ap替换，并将p从N中移入B中下标，B从B中 移入N中下标。 算法中细化了转轴运算的过程，下面说明其正确性 定理2.16转轴运算正确性) 当上方算法中≤0时，问题不存在有界解；否则，转轴运算进行一步更新后，得到的仍然是 可行基解，且目标画数值减少了（-p)△。 证明当xp增加6，xN其他分量保持为0时，由于要满足xB=B-1b-B-1NxN,可得xB=B-b一 B-lap6,而函数值z=20-(p-p)5。 若p=B-1ap≤0，则6无论如何增加，正B都增大，工B≥0仍满足，于是函数值可无限减小，无 有界解 否则，转轴运算取出的△满足△≤B-,t>0,这时化简可知(B-1b:-(B-1a2h△≥0 另一方面，≤0时(B-b)-(B-1ap)△≥(B-1b:≥0（由于B=B-1b是可行基解的一部分），综 合可知B-1b-B-1a,△≥0，由更新过程，更新后EB每个分量仍然≥0。 于是，我们证明了更新后的x满足B,分量变成0，P分量增加为正数，且所有分量仍然≥0，Ar=b 仍成立，因此仍然是可行基解。另一方面，函数值减小了0-(（一C)△）=(p-C)△. 注意到，△=，由选取过程可知>0，而为了确认函数值是否真的减少，还需要考虑B-b 的零分量。 定义2.17（非退化可行基解） 当可行基解满足工B=B一b>0时，其称为非退化的，否则其有分量为0，称为退化的。 若迭代过程保持非退化，单纯形法具有良好的收敛性： 定理2.18（单纯形法有限收敛性） 若线性规划问题可以求出初始可行基解，且转轴运算中每步的可行基解都非退化，则有限次选 代后要么找到最优解，要么识别出问题无有界解，从而算法终止
2.2 单纯形法 算法 2.15 (单纯形法) ♠ 1. 初始化 确定初始可行基划分 B, N，并计算 xB = B−1 b。 2. 最优判定 计算向量 w = (BT ) −1 cB，对所有 j ∈ N 计算 zj = w T aj。若 cj ≥ zj 对一切 j ∈ N 成立， 则当前可行基解已是最优解，最优值为 w T b，算法终止。否则，选择一个 cp − zp < 0 的 p ∈ N 进入下一步。 3. 转轴运算 计算向量 yp = B−1ap。若 yp ≤ 0，则问题无有界解，算法终止。 否则，找出 r 使得 ∆ = xBr ypr 是所有 xBi ypi , ypi > 0 中的最小值。 更新基变量：令 xp = ∆，xB = xB − yp∆，这里 B 为原来的分量，更新后 xBr 由 ∆ 定义 成为 0。 更新 B, N：将 B 原本的第 r 列 aBr 用 ap 替换，并将 p 从 N 中移入 B 中下标，Br 从 B 中 移入 N 中下标。 算法中细化了转轴运算的过程，下面说明其正确性： 定理 2.16 (转轴运算正确性) ♡ 当上方算法中 yp ≤ 0 时，问题不存在有界解；否则，转轴运算进行一步更新后，得到的仍然是 可行基解，且目标函数值减少了 (zp − cp)∆。 证明 当 xp 增加 δ，xN 其他分量保持为 0 时，由于要满足 xB = B−1 b − B−1NxN，可得 xB = B−1 b − B−1apδ，而函数值 z = z0 − (zp − cp)δ。 若 yp = B−1ap ≤ 0，则 δ 无论如何增加，xB 都增大，xB ≥ 0 仍满足，于是函数值可无限减小，无 有界解。 否则，转轴运算取出的 ∆ 满足 ∆ ≤ (B−1 b)i ypi , ∀ypi > 0，这时化简可知 (B−1 b)i − (B−1ap)i∆ ≥ 0。 另一方面，ypi ≤ 0 时 (B−1 b)i − (B−1ap)i∆ ≥ (B−1 b)i ≥ 0 (由于 xB = B−1 b 是可行基解的一部分)，综 合可知 B−1 b − B−1ap∆ ≥ 0，由更新过程，更新后 xB 每个分量仍然 ≥ 0。 于是，我们证明了更新后的 x 满足 Br 分量变成 0，p 分量增加为正数，且所有分量仍然 ≥ 0，Ax = b 仍成立，因此仍然是可行基解。另一方面，函数值减小了 z0 − ((zp − cp)∆) = (zp − cp)∆。 注意到，∆ = xBr ypr ，由选取过程可知 ypr > 0，而为了确认函数值是否真的减少，还需要考虑 B−1 b 的零分量。 定义 2.17 (非退化可行基解) ♣ 当可行基解满足 xB = B−1 b > 0 时，其称为非退化的，否则其有分量为 0，称为退化的。 若迭代过程保持非退化，单纯形法具有良好的收敛性： 定理 2.18 (单纯形法有限收敛性) ♡ 若线性规划问题可以求出初始可行基解，且转轴运算中每步的可行基解都非退化，则有限次迭 代后要么找到最优解，要么识别出问题无有界解，从而算法终止。 18