2.2单绝形法 证明当迭代过程非逃化时，每一步：的减少量正>0，因此每步找到的可行基解不同，又由 于可行基解个数有限，必然会在找到某个后终止（可能找到最优或发现无有界解）。 2.2.3初始化过程 上一部分讨论了单纯形算法的主要过程，不过有一个问题尚未解决，也即如何找到初始可行基解。 两阶段法的思路是，先找到某辅助问题的最优解，再作为原问题初始可行基解进行计算。 算法2190两阶段法) 对问题{mincTr|A缸=b,x≥0}，考虑如下问题： min 1y s.t.Ar+y=b x20,别≥20 其中1代表每个分量都是1的向量，y为m阶向量。 以 进行单形法选代（注意化为标准型的过程已经保证了b≥0），若选代到的最优 b 解满足y=0,则此时的工为原问题可行基解，否则原问题不存在可行解。 证明1T即对y各个分量求和，而由于y之0，当且仅当y=0时其能取到最小值，此时A=b,x之0， 因此x即为可行解。反之，最小值时若！≠0，则说明可行解x不存在。 下面说明存在解时的x为可行基解。扩充！后，矩阵A事实上成为了(A,而单纯形法找到 的可行基矩阵是从(AI）中选出了可逆的m列，又由于此时y=0,选出的m列必然在前n列之中 因此一定对应A的可行基划分（或从分量角度，找到的最优解一定至多m个分量非零，且全部为x的 分量，因此是原问额可行共解)。 两阶段法的弊端在于，相当于要求解两个独立的线性规划问题，且对前一问题求解的信息只用来 选取可行基解，没有进一步使用。大M法对此作出了改进： 算法2.20（大M法 对问题{minc2x|Ar=b,x≥0，考虑如下问题： min cTr+M(1Ty) s.t.Ar+y=b x≥0，y20 其中1代表每个分量都是1的向量，y为m阶向量，M为取定的某充分大的数。 割=0，且x为原问题最优解。 直观上看，对于足够大的M,的“权重”是很大的，因此只要存在任何非零分量，都会导致 cTx+M(1T)无法取到最小。而当y=0时，取到最小即等价于x取到原问题的最优解。 对于M的具体取值，可以这么来看：假设在Ax=b变为Ax=b-y时，cx的最小值为f)
2.2 单纯形法 证明 当迭代过程非退化时，每一步 z 的减少量 (zp−cp)xBr ypr > 0，因此每步找到的可行基解不同，又由 于可行基解个数有限，必然会在找到某个后终止 (可能找到最优或发现无有界解)。 2.2.3 初始化过程 上一部分讨论了单纯形算法的主要过程，不过有一个问题尚未解决，也即如何找到初始可行基解。 两阶段法的思路是，先找到某辅助问题的最优解，再作为原问题初始可行基解进行计算。 算法 2.19 (两阶段法) ♠ 对问题 {min c T x | Ax = b, x ≥ 0}，考虑如下问题： min 1T y s.t. Ax + y = b x ≥ 0, y ≥ 0 其中 1 代表每个分量都是 1 的向量，y 为 m 阶向量。 以 x y ! = 0 b ! 进行单纯形法迭代 (注意化为标准型的过程已经保证了 b ≥ 0)，若迭代到的最优 解满足 y = 0，则此时的 x 为原问题可行基解，否则原问题不存在可行解。 证明 1 T y 即对 y 各个分量求和，而由于 y ≥ 0，当且仅当 y = 0 时其能取到最小值，此时 Ax = b, x ≥ 0， 因此 x 即为可行解。反之，最小值时若 y ̸= 0，则说明可行解 x 不存在。 下面说明存在解时的 x 为可行基解。扩充 y 后，矩阵 A 事实上成为了 A I ，而单纯形法找到 的可行基矩阵是从 A I 中选出了可逆的 m 列，又由于此时 y = 0，选出的 m 列必然在前 n 列之中， 因此一定对应 A 的可行基划分 (或从分量角度，找到的最优解一定至多 m 个分量非零，且全部为 x 的 分量，因此是原问题可行基解)。 两阶段法的弊端在于，相当于要求解两个独立的线性规划问题，且对前一问题求解的信息只用来 选取可行基解，没有进一步使用。大 M 法对此作出了改进： 算法 2.20 (大 M 法) ♠ 对问题 {min c T x | Ax = b, x ≥ 0}，考虑如下问题： min c T x + M(1 T y) s.t. Ax + y = b x ≥ 0, y ≥ 0 其中 1 代表每个分量都是 1 的向量，y 为 m 阶向量，M 为取定的某充分大的数。 以 x y ! = 0 b ! 进行单纯形法迭代，在 M 充分大时，若原问题最优解存在，则迭代到的结果中 y = 0，且 x 为原问题最优解。 直观上看，对于足够大的 M，y 的“权重”是很大的，因此只要存在任何非零分量，都会导致 c T x + M(1 T y) 无法取到最小。而当 y = 0 时，取到最小即等价于 x 取到原问题的最优解。 对于 M 的具体取值，可以这么来看：假设在 Ax = b 变为 Ax = b − y 时，c T x 的最小值为 f(y)， 19
22单纯形法 则只需要让M>maXy0O,就可以保证满足上述的条件。于是，我们只需要估算b进行一定 “扰动”时最小值的变化量，而这会在后文灵敏度分析的部分解决 2.2.4单纯形表 单纯形表是单纯形方法的一种直观算法，目的是将单纯形法的过程用矩阵消元运算进行直观表现。 具体来说，对于某个取定的可行基划分B,N,单纯形表是一个(m+1)×(n+1)维矩阵（最上方一行 为表头)： EB IN RHS Im B-IN B-1b 05-90 若最下方一行前n个分量均≤0，则最后一个分量即为最小值。更进一步地，由于B-1B=1m: j∈B时-G组合为cB-lB-c召=0，单纯形表事实上的形式为 RHS B-1A B-16 cBB-1A-cT cBB-ib/ 而转轴运算即为通过行变换，将最末行与上方某行的倍数相加，使某大于0的元素变为0，为0的元 素变为非零 由p=B-1p,单纯形表的上方部分B-1A即为每个i对应的。由此得到单纯形表的计算过 算法2.21（单纯形表） 1.初始化 从某个初始的 B-1A B-1b） cBB-1A-cT chB-16 开始。 2.最优判定 若CB-1A-cT≤0，则右下角元素为最优解，最优解时的x可观察左侧，若最后一列外 的某列只有一个元素为1，其他为0，则这列的列数即为xB对应分量，1所在的这行的最 右元素为其值。不在xB分量中的元素值全为0。否则，在CB-1A一CT找一个大于0的 元素，设列数为p,进入转轴运算。 3.转抽运算 若第D列除最下方元素外均<0，则问题无有界解，算法终止。 否则，找出r使得△=是所有，>0中的最小值。这里即为除最后一行外 每行最后一列的元素与第卫列元素之比。 更新单纯形表：将第r行同除以，再将每行（含最后一行）减去第r行的倍数，使得第卫 列只有第r行为1，其他均为0。 证明为了证明这个算法与之前的单纯形法等价，需要观察转轴运算部分的减去倍数的过程。 对最后一行，实际上减去的是第r行的倍，因此需要证明的是 (=-cj)new=(zj-ej)-(B-1A)c2 0
2.2 单纯形法 则只需要让 M > maxy̸=0 |f(y)−f(0)| 1T y ，就可以保证满足上述的条件。于是，我们只需要估算 b 进行一定 “扰动”时最小值的变化量，而这会在后文灵敏度分析的部分解决。 2.2.4 单纯形表 单纯形表是单纯形方法的一种直观算法，目的是将单纯形法的过程用矩阵消元运算进行直观表现。 具体来说，对于某个取定的可行基划分 B, N，单纯形表是一个 (m + 1) × (n + 1) 维矩阵 (最上方一行 为表头)： xB xN RHS Im B−1N B−1 b 0 zj − cj z0 若最下方一行前 n 个分量均 ≤ 0，则最后一个分量即为最小值。更进一步地，由于 B−1B = Im， j ∈ B 时 zj − cj 组合为 c T BB−1B − c T B = 0，单纯形表事实上的形式为： x RHS B−1A B−1 b c T BB−1A − c T c T BB−1 b 而转轴运算即为通过行变换，将最末行与上方某行的倍数相加，使某大于 0 的元素变为 0，为 0 的元 素变为非零。 由 yp = B−1ap，单纯形表的上方部分 B−1A 即为每个 i 对应的 yi。由此得到单纯形表的计算过 程： 算法 2.21 (单纯形表) ♠ 1. 初始化 从某个初始的 B−1A B−1 b c T BB−1A − c T c T BB−1 b ! 开始。 2. 最优判定 若 c T BB−1A − c T ≤ 0，则右下角元素为最优解，最优解时的 x 可观察左侧，若最后一列外 的某列只有一个元素为 1，其他为 0，则这列的列数即为 xB 对应分量，1 所在的这行的最 右元素为其值。不在 xB 分量中的元素值全为 0。否则，在 c T BB−1A − c T 找一个大于 0 的 元素，设列数为 p，进入转轴运算。 3. 转轴运算 若第 p 列除最下方元素外均 ≤ 0，则问题无有界解，算法终止。 否则，找出 r 使得 ∆ = xBr ypr 是所有 xBi ypi , ypi > 0 中的最小值。这里 xBi ypi 即为除最后一行外 每行最后一列的元素与第 p 列元素之比。 更新单纯形表：将第 r 行同除以 ypr，再将每行 (含最后一行) 减去第 r 行的倍数，使得第 p 列只有第 r 行为 1，其他均为 0。 证明 为了证明这个算法与之前的单纯形法等价，需要观察转轴运算部分的减去倍数的过程。 对最后一行，实际上减去的是第 r 行的 zp−cp ypr 倍，因此需要证明的是 (zj − cj )new = (zj − cj ) − (B −1A)rj zp − cp ypr 20
22单绝形法 (cBB-1b)nce cBB-1b-(B-16)c2 根据定义，Bem=(aB,,aB,-,ap,B+1,aBm),于是直接计算可知B-1Bncw为I的第 列替换为n的结果。由此进一步计算得（注意B-B-1=(I-B-1Bmcw)B) (-G)mew-(-cS)=(c塔r)T-c雷)Bn+cB(Bn-B-l)a (cp -eB.)eT Bata;+(eB.-chyp)eT Bndaj (cp -cByp)er Bneway 由伴随矩阵，Bn的第r行与B-l的第r行事实上只相差detB/det Bnew=(detB-Bnev)1= 倍，而eB-1a)=(B-1A)r,第一个式子得证。对第二个式子，将ay换为b后完全相同展开得结 对其余行，由于只进行了行变换，也即B-1(Ab)成为了PB-1(Ab),相当于只需要验证 PB-1=B。在行变换后，xB除了第r个分量外所在的列均无变化（它们的第r行为0，减0的倍数 不会引起变化)，而第p列变为了只有第r行1，其他为0，因此与原来的第B1,,B,-1,B,+1,,Bm 列可拼出Im,这即说明了PB一Be=I，于是PB一=B- 实际操作中，大M法常与单纯形表结合使用。由于其相当于将A增广为了（A),初始可行基 划分选取I的部分，CB=M·1T,于是起始的单纯形表即为： y RHS M(1TA)-c 0 M(1T6) 练习2.5用大M法构造单纯形表求解以下线性规划问题： min x1+22-3x3 5.t.x1-2c2+x3≤11 2x1+x2-4r3≥3 E1-2x3=1 1,2,3≥0 解记4=11-+22-3,5=21+2-43-3，则其标准形式的等式约桌为 /1-2110 /11 21-40-1 =3 10-200 1 于是构造的单纯形表为 4x5功的RHS 1 -2 1 1 11 1 -1 3 1 -2 1 1 4M-1-M-1-5M+3M-M 15M 变形计算可最终得解为工1=9,2=1,3=4，最优值为-2。 从最坏情况看，单形法并不是多项式时间算法，而是指数时问第法，因为其可能追历所有可行热
2.2 单纯形法 (c T BB −1 b)new = c T BB −1 b − (B −1 b)r zp − cp ypr 根据定义，Bnew = (aB1 , . . . , aBr−1 , ap, aBr+1 , . . . , aBm)，于是直接计算可知 B−1Bnew 为 I 的第 r 列替换为 yp 的结果。由此进一步计算得 (注意 B−1 new − B−1 = (I − B−1Bnew)B−1 new) (zj − cj )new − (zj − cj ) = ((c new B ) T − c T B)B −1 newaj + c T B(B −1 new − B −1 )aj = (cp − cBr )e T r B −1 newaj + (cBr − c T Byp)e T r B −1 newaj = (cp − c T Byp)e T r B −1 newaj 由伴随矩阵，B−1 new 的第 r 行与 B−1 的第 r 行事实上只相差 det B/ det Bnew = (det B−1Bnew) −1 = y −1 pr 倍，而 e T r B−1aj = (B−1A)rj，第一个式子得证。对第二个式子，将 aj 换为 b 后完全相同展开得结 果。 对其余行，由于只进行了行变换，也即 B−1 A b 成为了 P B−1 A b ，相当于只需要验证 P B−1 = B−1 new。在行变换后，xB 除了第 r 个分量外所在的列均无变化 (它们的第 r 行为 0，减 0 的倍数 不会引起变化)，而第 p 列变为了只有第 r 行 1，其他为 0，因此与原来的第 B1, . . . , Br−1, Br+1, . . . , Bm 列可拼出 Im，这即说明了 P B−1Bnew = I，于是 P B−1 = B−1 new。 实际操作中，大 M 法常与单纯形表结合使用。由于其相当于将 A 增广为了 A I ，初始可行基 划分选取 I 的部分，cB = M · 1 T，于是起始的单纯形表即为： x y RHS A I b M(1 T A) − c 0 M(1 T b) 练习 2.5 用大 M 法构造单纯形表求解以下线性规划问题： min x1 + x2 − 3x3 s.t. x1 − 2x2 + x3 ≤ 11 2x1 + x2 − 4x3 ≥ 3 x1 − 2x3 = 1 x1, x2, x3 ≥ 0 解 记 x4 = 11 − x1 + 2x2 − x3, x5 = 2x1 + x2 − 4x3 − 3，则其标准形式的等式约束为 1 −2 1 1 0 2 1 −4 0 −1 1 0 −2 0 0 x = 11 3 1 于是构造的单纯形表为 x1 x2 x3 x4 x5 y1 y2 y3 RHS 1 −2 1 1 1 11 2 1 −4 −1 1 3 1 −2 1 1 4M − 1 −M − 1 −5M + 3 M −M 15M 变形计算可最终得解为 x1 = 9, x2 = 1, x3 = 4，最优值为 −2。 从最坏情况来看，单纯形法并不是多项式时间算法，而是指数时间算法，因为其可能遍历所有可行基 21
23对偶理论 解。而针对线性规划问题的算法已有不少多项式时问的结果，例如： 。最先在理论上证明线性规划问题恒在多项式时问内可解的鞘球算法。 。可替代单纯形法的有效方法内点法。它亦可被推广并应用到不限于线性规划的更一般问题，会在 之后详述。 2.3对偶理论 23.1对偶问题定义 对于线性规划问题，可以定义它的对偶，而通过研究线性规划与其对偶的性质，能得到更多的理 论结果。为了进行对偶问题的定义，需要另一种“标准形式”： 定理2.22（线性规划的对偶基本形式） 线性规划问题总可以等价为如下的形式 min cr 8.t.Ar2b (LP) x≥0 共中Cx为n维向量，A为m×n阶矩阵，b为m维向量 证明先化为LPN的形式，而Ax=b即为Ar≥b,-Ax≥-b,于是可以写成 4( 定义2.23（线性规划问题的对偶问题） 对于线性规划问题LP),定义其对偶为 max bTw s.t.ATw≤c (DP) "≥0 其中w为m维向量。 从约束与目标函数的对应，即可以看出对偶的关系。在讨论对偶问题与原问题的对应性质之前，我 们先关注形式上的一些结果： 五练习2.6计算如下问题的对偶 1.min-be8.t.-ATw≥-c,w≥0 2.mincTr s.t.Ax≥b,-Ar≥-b,x≥0 1.注意到min-bTw与max T等效，这个问题事实上是计算对偶问题的对偶。结采为 max -cT'z s.t.-Ax s-b,20 即 mineT s.t.Ax≥b,x≥0 于是对偶问题的对偶就是原问题
2.3 对偶理论 解。而针对线性规划问题的算法已有不少多项式时间的结果，例如： 最先在理论上证明线性规划问题恒在多项式时间内可解的椭球算法。 可替代单纯形法的有效方法内点法。它亦可被推广并应用到不限于线性规划的更一般问题，会在 之后详述。 2.3 对偶理论 2.3.1 对偶问题定义 对于线性规划问题，可以定义它的对偶，而通过研究线性规划与其对偶的性质，能得到更多的理 论结果。为了进行对偶问题的定义，需要另一种“标准形式”： 定理 2.22 (线性规划的对偶基本形式) ♡ 线性规划问题总可以等价为如下的形式： min c T x s.t. Ax ≥ b x ≥ 0 (LP) 其中 c, x 为 n 维向量，A 为 m × n 阶矩阵，b 为 m 维向量。 证明 先化为LP-N的形式，而 Ax = b 即为 Ax ≥ b, −Ax ≥ −b，于是可以写成 A −A ! x ≥ b −b ! 。 定义 2.23 (线性规划问题的对偶问题) ♣ 对于线性规划问题 (LP)，定义其对偶为 max b T w s.t. AT w ≤ c w ≥ 0 (DP) 其中 w 为 m 维向量。 从约束与目标函数的对应，即可以看出对偶的关系。在讨论对偶问题与原问题的对应性质之前，我 们先关注形式上的一些结果： 练习 2.6 计算如下问题的对偶： 1. min −b T w s.t. −AT w ≥ −c, w ≥ 0 2. min c T x s.t. Ax ≥ b, −Ax ≥ −b, x ≥ 0 解 1. 注意到 min −b T w 与 max b T w 等效，这个问题事实上是计算对偶问题的对偶。结果为 max −c T x s.t. −Ax ≤ −b, x ≥ 0 即 min c T x s.t. Ax ≥ b, x ≥ 0 于是对偶问题的对偶就是原问题。 22
2.3对偶理论 2.这个问题事实上就是标准型的对偶，直接计算可以得到 max{b01-bT2}s.t.ATw1-AT2≤cw1,2≥0 其中1,2都是m维向量。由于1≥0,2≥0，可以将1-2看作无约束的W,即 max bTw s.t.ATw≤c 这就是标准型的对偶结果。 2.3.2对偶定理 下面，记x与分别为问题(LP)与(DP)的某一可行解，x与w为对应问题的最优解，讨论对 偶的性质。 定理2,24（扇对偶定理） 2.cTT>bTw*bTw<crr* 3.==cTr',bTw=bw' 4.ninc'x=-oo→力w 证明当a≥0时，若s≥t,由于每个分量对应成立大于等于，作正组合仍有sTa≥tPa。由此， cTx>(ATx=心Ax=(Ax)T如>bT如，第一个式子得证。由于对任何可行解都成立，当x或 取到一边最优解时仍成立，第二个式子得证。于是，当c工=bw时，假设取到的不是最大值 则会有bW>CTx,矛盾，类似可知cTx取到的一定是最小值，第三个式子得证。最后，若cTz最小 值无界，则任何心都无法满足cx≥对任何工成立，只能不存在可行解，第四个式子的另一边 同理。 本质来说，弱对偶定理可以被第一条'x≥概括，而这也体现出了对偶问题的价值：只要找 到两个问题具有某种对应关系(cTx=四)的解，就一定找到了互相的最优解。从此出发，还可以得 到其他有用的结论： 定理225（最优解存在性定理 若(LP)与DP)都有可行解，则它们都有最优解。 证明分剥记为0与，由弱对偶定理，任何可行解x满足cx≥，于是函数cx有下界。这 就排除了LP)问题可行域为空与无界的情况，从而必须有最优解，对(DP)同理。 结合存在性定理，可以证明完整的对偶定理： 定理2.26（对偶定理） 若(LP)与DP)一方有最优解，则另一方亦有最优解，且最优值一致。 证引记=加-8园可写出问奥均标参彩大，共中等式片来为（台一月（同=人思西为 (A-）的第j列，S在原有列后均应扩充0。设原问题最优解x,,对应可行基分解为B,N,根 据之前推导有c3B-1a5-Cy≤0
2.3 对偶理论 2. 这个问题事实上就是标准型的对偶，直接计算可以得到 max{b T w1 − b T w2} s.t. AT w1 − A T w2 ≤ c, w1, w2 ≥ 0 其中 w1, w2 都是 m 维向量。由于 w1 ≥ 0, w2 ≥ 0，可以将 w1 − w2 看作无约束的 w，即 max b T w s.t. AT w ≤ c 这就是标准型的对偶结果。 2.3.2 对偶定理 下面，记 x 与 w 分别为问题 (LP) 与 (DP) 的某一可行解，x ∗ 与 w ∗ 为对应问题的最优解，讨论对 偶的性质。 定理 2.24 (弱对偶定理) ♡ 1. c T x ≥ b T w 2. c T x ≥ b T w ∗ , bT w ≤ c T x ∗ 3. c T x = b T w ⇒ c T x = c T x ∗ , bT w = b T w ∗ 4. min c T x = −∞ ⇒ ∄ w max b T w = +∞ ⇒ ∄ x 证明 当 a ≥ 0 时，若 s ≥ t，由于每个分量对应成立大于等于，作正组合仍有 s T a ≥ t T a。由此， c T x ≥ (AT w) T x = w T Ax = (Ax) T w ≥ b T w，第一个式子得证。由于对任何可行解都成立，当 x 或 w 取到一边最优解时仍成立，第二个式子得证。于是，当 c T x = b T w 时，假设 b T w 取到的不是最大值， 则会有 b T w ′ > cT x，矛盾，类似可知 c T x 取到的一定是最小值，第三个式子得证。最后，若 c T x 最小 值无界，则任何 w 都无法满足 c T x ≥ b T w 对任何 x 成立，只能不存在可行解 w，第四个式子的另一边 同理。 本质来说，弱对偶定理可以被第一条 c T x ≥ b T w 概括，而这也体现出了对偶问题的价值：只要找 到两个问题具有某种对应关系 (c T x = b T w) 的解，就一定找到了互相的最优解。从此出发，还可以得 到其他有用的结论： 定理 2.25 (最优解存在性定理) ♡ 若 (LP) 与 (DP) 都有可行解，则它们都有最优解。 证明 分别记为 x0 与 w0，由弱对偶定理，任何可行解 x 满足 c T x ≥ b T w0，于是函数 c T x 有下界。这 就排除了 (LP) 问题可行域为空与无界的情况，从而必须有最优解，对 (DP) 同理。 结合存在性定理，可以证明完整的对偶定理： 定理 2.26 (对偶定理) ♡ 若 (LP) 与 (DP) 一方有最优解，则另一方亦有最优解，且最优值一致。 证明 记 y = Ax − b，则可写出问题 (LP) 的标准形式，其中等式约束为 A −I x y ! = b。记 aj 为 A −I 的第 j 列，cj 在原有列后均应扩充 0。设原问题最优解 x ∗ , y∗，对应可行基分解为 B, N，根 据之前推导有 c T BB−1aj − cj ≤ 0。 23