运筹学——单纯形方法

1单纯形方法线性规划基本定理. 给定线性规划的标准形式如下： max cTx (1)s.t. Ax = b, x 0, (2) 其中 A 是秩为 m 的 mn 阶矩阵, b 0. i) 如果存在可行解, 则存在基可行解; ii) 如果存在最优解, 则存在最优的基可行解. 这个定理将求解线性规划的任务变成为搜索基可行解。因为对有 n 个变量和 m 个约束问题，基可行解最多不超过下面的数： ()= !()!定理(顶点和基解等价). 设 K 是包括所有满足(2)的 n 维向量 x 的凸多面体。则向量 x是凸多面体 K 的一个顶点当且仅当 x 是一个基可行解。 线性规划中的问题根据线性规划基本定理，解线性规划只需要在约束凸多面体的所有顶点上寻找最优解。因此，我们需要考虑的问题有： 1. 怎样找到一个基可行解？ 2. 判别基可行解是否最优解。 3. 从非最优的基可行解找到另一个基可行解，使目标函数值增大。 4. 如果问题无最优解，能发现一族可行解，使目标函数无上限。 对于我们前面提出的四个问题，单纯形方法能解决其中的问题 2-4。换句话说，单纯形方法要求一个已知的基可行解。 当从非最优的基可行解找到另一个基可行解时，为了保证目标函数值增大，单纯形方法还要求如下的假定，这引入了下面的概念：退化解和非退化解：设 x 0 = B 1b, 0是一个基可行解，如果有基变量的取值是 0，即B 1b 中有分量等于零，则称基可行解 x 0 是退化的。否则，称 x 0 是非退化的。 非退化假定：假设线性规划的每个基可行解都是非退化的。 2给定线性规划的标准形式如下： max cTx (1)(LP) s.t. Ax = b, (2)x 0, (3)其中 A 是行满秩的 mn 阶矩阵, b 0. 单纯形方法是在已知一个基可行解的情况下，寻找线性规划的最优基可行解的算法。强调一下：单纯形方法就是在已知一个基可行解的情况下，寻找线性规划的最优基可行解。 单纯性方法直接能解决问题 2-4。而问题 1 可以使用辅助线性规划来解决。我们首先来解决问题 2。 对线性规划(LP)，假设知道一个基可行解 x0。因此，就有一个可行基 B，假设 B 由约束系数矩阵 A 的前面 m 列构成，对应的基变量用 xB 表示， xD 表示非基变量。这样，我们就可以将决策变量 x，价值系数 c 和约束矩阵 A 分块成x = xB, xD， c = cB, cD和 A = B, D。于是，线性规划可以被写成下面的形式： max +s.t. BxB + DxD = b, (4)xB, xD 0. 基可行解 x0 就是在约束方程(4) 中令非基变量 xD = 0 得到的结果。因为基 B 是可逆矩阵，所以有 。0=1单纯形方法怎么判断基可行解 x0 = B1b, 0是否是最优的基可行解呢？我们从约束方程(4)解出所有的基变量 xB ，用非基变量 xD 表示，得到xB = B1b B1DxD, (5) 把由(5)表示的基变量代入到目标函数中，就有=+=(11)+整理后得到 =1+(1)3当非基变量 xD = 0 时，得到 。(0)=1我们令 = (m+1, , n) = 。 1这里 是行向量，并且正好是用非基变量表示的目标函数中所有变量的系数。而目标函数可以写成 nmTBxxbcz.11我们看到，如果有某个 j 0，取非基变量 xj 0，则目标函数值= z(x 0) + j xj z(x0)。这样得到的一个 x 还是可行解吗？在非退化假定下，我们可以从方程(5)中得到这样的一个可行解。我们回头看看方程(5)xB = B1b B1DxD, (5) 因为基可行解都是非退化的，所以 B1b 0。当 xj 0 充分小时，可以保证 xB 0。因此，可以得到一个可行解 x 具有非基变量 xj 0。从而有 z(x) = z(x0) + j xj z(x0)。由于当 j 0 时，存在可行解 x 使得目标函数值比在基可行解 x0 处的目标函数值更大，所以 x0 不是最优解。这样，我们得到单纯形方法的最优性判据。 最优性判据：如果存在 j 0 (m +1 j n)，则基可行解 x0 不是最优解；如果 0，则 x0 是最优解；其中 = (m+1, , n) = 。 1因为根据 j (j =m +1, , n)的符号可以判别基可行解 x0 是否是最优解，所以，人们称 j 为检验数。现在“判别基可行解 x0 是否是最优解 ”的问题 2 已经被解决。通过检查检验数 j (j =m +1, , n)的符号，可以确定 x0 是否是最优解。 我们还看到，当 x0 不是最优解时，在非退化假定下，可以从基可行解 x0 找到一个可行解 x 使目标函数值增加。那么，可以从基可行解 x0 找到另一个基可行解 x1 使目标函数值增加吗？回答是肯定的。现在，我们回头看看方程(5)的两种表示形式：xB = B1b B1DxD, (5-1) 和 xB + B1DxD = B1b. (5-2) 令 G = B1D = (gij) = (gm+1, , gn)是 m(nm)矩阵。则方程(5-2)可以写成xB + GxD = B1b 或 xB + gm+1 xm+1 + gn xn = B1b当 q 0 (m +1 q n)时，我们令其他非基变量等于零，得到xB + gq xq = B1b.4写成元素的形式是 x1 + g1q xq = 1,xp + gpq xq = p,xm + gmq xq = m,其中 = (1, 2, , m)T = B1b 0，我们让非基变量 xq 0 尽可能大，保证 x1 , , xm 都非负，则 xq 可以取到多大的值呢？ 显然当xq = mini /giq | giq 0, 1 i m = p /gpq (6)时，有 xp = 0 (1 p m)。而 xq p /gpq 时，x p 0 求的。 我们同时看到，如果所有的 giq 0, i = 1, , m, 则随着 xq 的增大，所有 xi 都增大。而在其他非基变量等于零时，目标函数是 qTBxbcz1于是 z 将随着 xq 增大而无限增大。这样，前面提出的问题 3. 从非最优的基可行解找到另一个基可行解，使目标函数值增大。4. 如果问题无最优解，能发现一族可行解，使目标函数无上限。 都被解决了。我们有了无界解的判别和找到一个使目标函数值增大的新基可行解方法如下： 无界解判别：如果 q 0 并且所有 giq 0, i = 1, , m, 则线性规划无最优解，目标函数可以无限增大。否则，令 xq = mini /giq | giq 0, 1 i m = p /gpq (6)则有 xp = 0，得到一个新的基可行解， xq 是这个基可行解的新的基变量， xp 成为非基变量。5到目前为止，我们已经解决了问题 2-4。因此，如果知道一个基可行解，那么，我们能判别这个基可行解是否是最优解；如果不是最优解，则存在某个检验数 q 0；如果所有 giq 0, i = 1, , m，则该线性规划无最优解，目标函数可以无限增大；否则，计算比值 min(i /giq | giq 0, 1 i m = p /gpq,令 xq = p /gpq，计算所有变量 xi, i = 1, , m，的值，此时必定有 xp = 0, 从而得到一个新的基可行解，在这个基可行解中，x q 是新的基变量，x p 成为非基变量。 这就是单纯形方法。 单纯形方法步骤记 G = B1D = (gij) = (gm+1, , gn)，是方程(5)中非基变量的 m(nm)系数矩阵， = (m+1, , n)是检验数行， = (1, 2, , m)T = B1b。步骤 1. 如果 j 0, j = m +1, , n, 则 x0 是最优解，算法终止。步骤 2. 假设 q 0 (m +1 q n)，判别 giq 的符号。如果所有的 giq 0 (i = 1, , m)，则线性规划无最优解，目标函数值可以无限增大，算法终止。否则转步骤3。步骤 3. 计算比值 mini /giq | giq 0, 1 i m = p /gpq,得到行标 p 对应的基变量 xp，令列标 q 对应的非基变量 xq 取公式(6)中的值，其他非基变量仍然取零值，计算出所有变量的取值，则得到一个新的基可行解，在这个新的基可行解中，x q 是新的基变量，x p 是新的非基变量。设新的基为 B，计算出新的 和 G 转步骤1。在单纯形算法中，由于原来基可行解中的非基变量 xq 成为新基可行解中的基变量，所以人们称 xq 为进基变量，同理， xp 被称为离基变量。于是，单纯形算法又可以被描述为：步骤 1 (最优性判别). 如果 j 0, j = m +1, , n, 则 x0 是最优解，算法终止。 步骤 2 (无界解判别 ). 对 q 0 (m +1 q n)，判别 giq 的符号。如果所有的 giq 0，i =1, , m， 则线性规划无最优解，目标函数值可以无限增大，算法终止。 步骤 3 (确定进基变量). 选择某个 q 0 对应的非基变量 xq 为进基变量(新基变量)。 步骤 4 (确定离基变量). 计算比值 mini /giq | giq 0, 1 i m = p /gpq, 6则行标 p 对应的基变量 xs (xp)为离基变量(新非基变量)。步骤 5 (计算新基和新基可行解). 计算新的基 B(还用原来的字母表示)，新基可行解，新检验数 和新非基变量在约束方程(5)中的系数 G，转步骤 1。单纯形表我们看到，当基变量被解出来用非基变量表示时，原来的线性规划可以被写成： max z = z0 + m+1xm+1 + + nxn s.t. x1 + g1, m+1 xm+1 + + g1n xn = 1, x2 + g2, m+1 xm+1 + + g2n xn = 2, .xm + gm, m+1 xm+1 + + gmn xn= m, x1, x2, , xm, xm+1, , xn 0,其中 = (1, 2, , m