说实话运筹学学到线性规划这一章“基变量”是很多人第一次觉得卡壳的地方。这个笔记我断断续续整理了快两周今天借着3月3日的学习记录把这套概念彻底摊开讲一遍。如果你正在为“基”这个概念发愁或者单纯想搞明白单纯形法里那个入基、离基到底在折腾什么这篇文章应该能帮到你。内容不绕弯子直接从定义、几何意义、计算逻辑到实操踩坑全部捋清楚。1. 先从标准形说起为什么非要引入“基”这个概念1.1 标准形到底长什么样线性规划的标准形一般写成max z c1x1 c2x2 ... cnxn s.t. a11x1 a12x2 ... a1nxn b1 a21x1 a22x2 ... a2nxn b2 ... am1x1 am2x2 ... amnxn bm x1, x2, ..., xn 0用矩阵可以写得非常紧凑max z c^T x s.t. Ax b x 0其中A是m行n列的系数矩阵。这里有个前提条件就是m小于n也就是说约束方程的个数少于决策变量的个数。为什么非得是这个前提因为当方程个数少于未知数个数时这个方程组才有自由变量的空间才有“选择”的余地。如果m等于n那就是唯一解不存在优化的可能性如果m大于n系统通常是不可行的也没法讨论。我当初学的时候有个困惑课本上为什么动不动就提“假设A的秩为m”后来明白了这是在说系数矩阵里没有多余的方程都是有效约束。如果某些方程是其他方程的线性组合秩就会小于m这种情况虽然在实际建模里可能出现但标准形理论通常先假设它是满秩的。1.2 解空间太大需要一个“地图”当m小于n时Axb的可行解不是有限的几个点而是一个无穷集合。想象一下一条直线在二维空间里是无数个点一个平面在三维空间里也是无数个点这些点都能满足等式约束而线性规划就是在这些点里找出让z最大的那一个。问题来了怎么在无穷多个点里找最优解如果直接暴力枚举根本不可能。这时候就需要一个数学工具来“降维打击”把一个连续无穷的问题转换成有限可枚举的问题这个工具就是“基”。基的概念把一个高维空间里的几何问题转化为有限个代数结构的组合问题。1.3 线性代数早就给过答案其实“基”这个词本身就来自线性代数。在线性代数里一个向量空间的基是一组线性无关的向量它们能张成整个空间。在线性规划里我们在系数矩阵A的m个行向量之外考虑的是m个列向量。从A的n个列向量里挑出m个线性无关的列组成一个可逆的m阶方阵B这个方阵就叫基矩阵。为什么必须是m个线性无关的列因为只有这样才能保证这个方阵满秩满秩矩阵才有逆有了逆才能解出唯一的变量值。这就是整个“基”概念的线性代数底子把大矩阵拆成“基部分”和“非基部分”用可逆子矩阵来锁定一组变量的值。2. 基、基变量、非基变量、基解四兄弟一次认清2.1 基矩阵与基变量拿到一个线性规划标准形Axb之后我们从系数矩阵A里挑出m个线性无关的列向量这m个列拼成的m阶方阵B就是基矩阵。与这m个列对应的变量就叫基变量剩下的n-m个变量叫非基变量。举个例子假设一个标准形有3个约束方程、5个决策变量那就要从A矩阵里挑3个线性无关的列。如果你挑的是第1、第3、第5列那对应的x1、x3、x5就是基变量x2、x4是非基变量。注意这里选哪几列是有讲究的必须保证这m个列向量线性无关也就是它们构成的行列式值不为0。我一开始总是忽略“线性无关”这个条件觉得随便挑几列就行。后来做计算题的时候才意识到如果挑出的列是线性相关的基矩阵B的行列式直接为0后续也解不出来。判断线性无关最直接的办法就是算行列式是否等于0或者看列向量之间是否存在倍数关系。2.2 基解是怎么解出来的选定基矩阵B之后我们把系数矩阵A也拆成两块一块是B对应的部分另一块是N对应的部分。同样地决策变量也拆成基变量xB和非基变量xN。原方程Axb就可以写成B * xB N * xN b这里最关键的一步操作来了令所有非基变量xN等于0。为什么可以这样强制设置因为我们要得到的是一个有明确坐标的“候选解”而不是无穷集合里的一个一般表达式。把非基变量全部置为0之后方程就简化成B * xB b两边左乘B的逆矩阵xB B^(-1) * b基变量的值就出来了。这样得到的解x (xB, xN) (B^(-1)*b, 0)就叫基解。基解是一种极端的顶点式解它把所有自由度都压到了非基变量的0值上。2.3 基可行解为什么更重要基解只是代数意义上的解它不一定满足x 0这个非负约束。一个基解如果所有分量都是非负的就叫基可行解。从几何上看基可行解对应可行域的顶点这是单纯形法可以搜索的候选点。我在笔记上画过一张关系图所有基可行解都是基解的子集所有基解都是Axb解集的特殊子集。如果某个基解里有变量是负数那就直接丢弃它不是可行域里的合法点。单纯形法本质上就是从一个基可行解跳到另一个基可行解直到找到最优的那一个。2.4 基解的个数上限怎么算从n个列向量里选m个线性无关的列组合数是C(n,m)但在这些组合里有些可能是线性相关的所以基解的个数最多不超过C(n,m)个。这个组合数给了我们一个重要直觉本来连续无穷的可行解经过“基”这个工具就变成至多有限个候选顶点了。线性规划的几何直觉就是这么来的最优解一定在某个顶点上顶点可以由某个基解来刻画所以只要穷举或者聪明地搜索有限个基解就能找到最优。我把几个概念整理过一个速查表概念定义关键特性基矩阵BA中m个线性无关列构成的子方阵满秩可逆基变量与B列对应的m个变量取值由B^(-1)b确定非基变量其余n-m个变量取值为0基解令非基变量为0得到的Axb的解满足等式约束不一定满足非负约束基可行解所有分量非负的基解对应可行域顶点3. 几何视角基解为什么就是可行域的顶点3.1 代数与几何的对应关系线性规划的几何图像是在高维空间里由一组线性不等式切割出来的凸多面体目标函数在这个多面体上寻找最大值。代数上的“基解”和几何上的“顶点”是同一件事的两面。先说顶点。在多面体里顶点的定义是一个点无法表示成其他两个不同点的凸组合。从几何直觉来看顶点就是多面体的“角”。代数上为什么顶点会对应基解因为在顶点处必须有足够多的约束条件同时达到边界取等号这些边界约束联合起来把自由度锁死只留下唯一一个点。线性规划标准形的等式约束Axb相当于把可行域限制在一个m维的仿射子空间里。在这个子空间里再叠加x 0的非负约束就会形成一个有界的多面体。顶点处需要让n-m个变量同时取到0就是非基变量这样才能让顶点“顶”在可行域的边界交叉处。3.2 一个三维空间的具体想象假设你在二维平面上解一个线性规划它有两个变量x1和x2两个“多余”的变量x3和x4是松弛变量。四维空间里看不见但你可以把它想象成三维空间里的一个多面体。每个顶点所在的位置恰好是三条边界面的交点。代数的处理方式是令某个变量等于0来拿掉一个维度然后剩下的维度正好由等式约束确定一个交点。我之前写过这样一个类比把可行域想象成一片被木桩约束条件拉紧的帐篷布帐篷布的“顶点”就是支棱起来的地方。要算一个顶点在哪里你总是可以挑某些方向让它们完全“塌缩”所有非基变量为0剩下的方向直接由方程组锁死。这个“塌缩”的方向就是非基变量锁死的过程就是求逆。3.3 退化的情况也别忽略如果某个基可行解里有基变量的值是0这种情况叫退化解。退化意味着这个顶点有超过n-m个约束在起作用也就是说有多个基矩阵可能对应同一个几何顶点。退化在单纯形法里会引起迭代不进展的问题也就是出现“循环”这在实际计算工具箱里会有专门处理但初学者理解概念阶段主要知道关键点退化解不影响顶点与基解的对应关系只是存在多对一的情况。下一步几何上最关键的跳跃是为什么不用检查所有顶点因为单纯形法告诉我们从任意一个顶点出发沿着目标函数改进最快的方向跳到相邻顶点就一定能在有限步内找到最优解。这个“相邻顶点”的跳跃靠的就是基变量的替换——离基、入基这个下面详细讲。4. 单纯形法里的进基和离基到底在干什么4.1 从一个顶点走向相邻顶点单纯形法不是暴力枚举所有基解而是从一个初始的基可行解出发每次只替换一个基变量换入一个更有利于目标函数的变量同时换出一个不再起作用的变量。整个过程是在顶点图上的局部搜索每次都走到相邻顶点并且保证目标函数值不下降通常还会严格上升最终到达最优顶点。这里最核心的逻辑在于“只换一个变量”这件事。为什么一次只换一个几何上从当前顶点出发沿着一条边走到相邻顶点正好只需要把一个变量从基变量取正值变成非基变量取值0同时把另一个变量从非基变量变成基变量。一次只换一个才能保证路径是沿着多面体的边走的而不是穿越内部。4.2 进基变量的选择依据检验数每次迭代时算法要判断哪个非基变量值得被“拉”进基。这个判断靠的是检验数也叫判别数。对每个非基变量j计算检验数σ_j c_j - c_B^T * B^(-1) * A_j其中A_j是对应非基变量的列向量。在最大化问题里只要存在正的检验数就说明把这个变量从0变成正值能让目标函数继续变大。选谁进基最简单的规则是选检验数最大的那个。这个叫Dantzig规则。我实际操作时发现这个规则虽然简单但并不是计算效率最高的还有最小下标规则、最大改进量规则等。刚学习阶段用Dantzig规则最省心算出所有非基变量的检验数选最大的正数进基。4.3 离基变量的选择依据最小比值规则进基变量确定之后我们要决定当前哪个基变量被换出去。这个决策不靠检验数靠的是比值检验。假设进基变量是xk它在约束里对应的列向量是B^(-1)*Ak比值θ min{ (xB)_i / (B^(-1)Ak)_i其中分母大于0 }。为什么取最小比值因为要让新进基变量尽量增大但前提是其他基变量不能被顶成负数。取最小值正是为了找出第一个被“顶到0”的基变量它就变成离基变量退出基矩阵。这个过程可以这样理解一辆班车座位有限一个新乘客要上车必须有人到站下车。谁先到站哪个基变量先被顶到边界谁就下车。4.4 从一个实例看一次完整的入基离基过程来个具体的例子。设线性规划max z 3x1 2x2 s.t. x1 x2 x3 4 x1 2x2 x4 5 x1, x2, x3, x4 0这里m2n4A矩阵是[[1,1,1,0],[1,2,0,1]]。显然选取x3、x4作为初始基变量是最省事的因为它们的列正好构成单位矩阵B就是IB^(-1)也是I。初始基可行解是x34x45x1x20目标函数z0。第一次迭代计算检验数σ1 3 - (0,0) * B^(-1) * A1 3σ2 2 - (0,0) * B^(-1) * A2 2。都是正数选最大的x1进基。接着做比值检验约束1中4/14约束2中5/15最小比值是4所以x3离基。新的基是x1和x4。更新基矩阵B [[1,0],[1,1]]B^(-1) [[1,0],[-1,1]]解出x14x41x2x30z12。接着再算检验数σ2 2 - (3,0) * [[1,0],[-1,1]] * [1,2]^T 2 - 3 -1已经为负说明x2进基不会增加目标函数当前就是最优解。最终答案x14x20最优值12。这个例子可以看出基变量的换入换出不是随意的每一步都是检验数和比值检验共同作用的结果一个管“能不能变好”一个管“变到哪个值就顶头了”。5. 实操中最容易踩的坑与排查方法5.1 坑一把“基解”和“可行解”画等号我最初做题的时候求出一个基解就直接当作可行解用了结果目标函数越算越离谱。根本原因在于没做非负检查。基解只是等式约束的解如果不满足x 0它就是不可行的不能作为单纯形法的起点。排查方法其实很简单每求出一个基解第一件事就是扫一眼所有分量看有没有负数。如果有直接放弃这个候选基。写代码的时候这个检查更要认真因为代码不会像人一样自动注意到符号问题。5.2 坑二选基时忘了检查行列式是否为0选基变量的时候如果挑的m个列向量不是线性无关的基矩阵B就不可逆后面的计算全部失效。很多人因为初始基都是单位矩阵就忽略了线性无关的检查等到迭代几次后选了线性相关的列整个计算炸掉。排查方法每次换入换出后重新检查基矩阵的行列式。用代码实现时一般直接调线性代数库求逆如果抛出奇异矩阵异常说明选基出问题了。5.3 坑三比值检验时忽略分母符号比值检验的分母必须是正数。如果分母是0或负数对应约束不会限制进基变量的增长就不参与比值计算。我见过有人把所有分母都拿去除一遍把负数也硬算进去结果得到错误的离基变量迭代路径直接跑偏。正确做法是只取分母大于0的约束做比值计算最小正值那个就是离基变量。如果所有分母都不大于0说明目标函数在该方向上无界问题没有有限最优解。5.4 坑四对“离基变量”的误解很多初学者总觉得“离基”就是把变量从问题里扔掉不参与了。实际上离基变量并没有消失它只是变成了非基变量也就是强制取0值的变量。它在后续迭代里还有可能重新进基。我自己在做对各种变量关系图的时候才把这一点彻底想通。5.5 实操判断基变量的通用步骤如果你拿到一个线性规划题想知道“哪些变量是基变量”操作顺序是这样的把问题化成标准形等号约束、非负变量、max目标。写出A矩阵和b向量。从A矩阵里任选m个列构造候选B矩阵。计算行列式det(B)不等于0才合格。令对应的非基变量为0解B * xB b得到基解。检查基解是否非负若是则为基可行解。这套步骤我在有段时间几乎每天跑一遍后来直接形成了肌肉记忆。6. 基变量概念为什么是整个线性规划的核心地基6.1 基概念连接了对偶理论和灵敏度分析线性规划不只是单纯形法对偶问题、灵敏度分析、影子价格这些进阶内容全都建立在基的框架上。看对偶问题就绕不开基解对应验证影子价格的本质就是对偶变量的值而对偶变量的求解刚好需要当前基矩阵的信息。灵敏度分析也是围绕最优基展开如果某个约束系数变了最优基是否保持不变新的解怎么算。6.2 内点法和单纯形法的区别也在这里内点法走的是可行域内部逼近不需要像单纯形法那样一个顶点一个顶点跳。但无论是哪类算法最终求得的解都要能对应回某个基在非退化的最优解情况下。即使是现代求解器判断最优解时也要找到最优基。理解了基变量你才算真正进入了运筹学的语言体系看论文、读教材才不费劲。6.3 “基”这个概念的真正难点在于抽象程度其实“基变量”本身不难难的是从“无穷多解里选一个特殊情况来研究”这个思维。我们习惯了求解方程就是找到一个解但线性规划里要找的是最优解而最优解又在无穷多的候选中于是需要一个办法制造出有限个候选。基就是做这件事的过滤器。想通了这一点后面很多内容都顺了。按我个人的学习安排这轮笔记整理完我紧接着把教材里关于退化、人工变量法和两阶段法的练习题过了一遍。建议你也这样概念搞懂之后马上上手算题用实际手感来巩固认知。基变量这块如果只靠看很难真正吃透。