企业官网建设流程全解析

说实话，运筹学学到线性规划这一章，“基变量”是很多人第一次觉得卡壳的地方。这个笔记我断断续续整理了快两周，今天借着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时，Ax=b的可行解不是有限的几个点，而是一个无穷集合。想象一下，一条直线在二维空间里是无数个点，一个平面在三维空间里也是无数个点，这些点都能满足等式约束，而线性规划就是在这些点里找出让z最大的那一个。

问题来了：怎么在无穷多个点里找最优解？如果直接暴力枚举，根本不可能。这时候就需要一个数学工具来“降维打击”，把一个连续无穷的问题，转换成有限可枚举的问题，这个工具就是“基”。基的概念把一个高维空间里的几何问题，转化为有限个代数结构的组合问题。

1.3 线性代数早就给过答案

其实“基”这个词本身就来自线性代数。在线性代数里，一个向量空间的基是一组线性无关的向量，它们能张成整个空间。在线性规划里，我们在系数矩阵A的m个行向量之外，考虑的是m个列向量。

从A的n个列向量里挑出m个线性无关的列，组成一个可逆的m阶方阵B，这个方阵就叫基矩阵。为什么必须是m个线性无关的列？因为只有这样才能保证这个方阵满秩，满秩矩阵才有逆，有了逆才能解出唯一的变量值。这就是整个“基”概念的线性代数底子：把大矩阵拆成“基部分”和“非基部分”，用可逆子矩阵来锁定一组变量的值。

2. 基、基变量、非基变量、基解：四兄弟一次认清

2.1 基矩阵与基变量

拿到一个线性规划标准形Ax=b之后，我们从系数矩阵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。原方程Ax=b就可以写成：

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这个非负约束。一个基解如果所有分量都是非负的，就叫基可行解。从几何上看，基可行解对应可行域的顶点，这是单纯形法可以搜索的候选点。

我在笔记上画过一张关系图：所有基可行解都是基解的子集，所有基解都是Ax=b解集的特殊子集。如果某个基解里有变量是负数，那就直接丢弃，它不是可行域里的合法点。单纯形法本质上就是从一个基可行解跳到另一个基可行解，直到找到最优的那一个。

2.4 基解的个数上限怎么算

从n个列向量里选m个线性无关的列，组合数是C(n,m)，但在这些组合里，有些可能是线性相关的，所以基解的个数最多不超过C(n,m)个。这个组合数给了我们一个重要直觉：本来连续无穷的可行解，经过“基”这个工具，就变成至多有限个候选顶点了。线性规划的几何直觉就是这么来的：最优解一定在某个顶点上，顶点可以由某个基解来刻画，所以只要穷举（或者聪明地搜索）有限个基解，就能找到最优。

我把几个概念整理过一个速查表：

3. 几何视角：基解为什么就是可行域的顶点

3.1 代数与几何的对应关系

线性规划的几何图像是在高维空间里，由一组线性不等式切割出来的凸多面体，目标函数在这个多面体上寻找最大值。代数上的“基解”和几何上的“顶点”是同一件事的两面。

先说顶点。在多面体里，顶点的定义是：一个点无法表示成其他两个不同点的凸组合。从几何直觉来看，顶点就是多面体的“角”。代数上为什么顶点会对应基解？因为在顶点处，必须有足够多的约束条件同时达到边界（取等号），这些边界约束联合起来把自由度锁死，只留下唯一一个点。

线性规划标准形的等式约束Ax=b，相当于把可行域限制在一个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

这里m=2，n=4，A矩阵是[[1,1,1,0],[1,2,0,1]]。显然，选取x3、x4作为初始基变量是最省事的，因为它们的列正好构成单位矩阵，B就是I，B^(-1)也是I。初始基可行解是x3=4，x4=5，x1=x2=0，目标函数z=0。

第一次迭代计算检验数：σ1 = 3 - (0,0) * B^(-1) * A1 = 3，σ2 = 2 - (0,0) * B^(-1) * A2 = 2。都是正数，选最大的x1进基。接着做比值检验：约束1中4/1=4，约束2中5/1=5，最小比值是4，所以x3离基。新的基是x1和x4。

更新基矩阵B = [[1,0],[1,1]]，B^(-1) = [[1,0],[-1,1]]，解出x1=4，x4=1，x2=x3=0，z=12。接着再算检验数，σ2 = 2 - (3,0) * [[1,0],[-1,1]] * [1,2]^T = 2 - 3 = -1，已经为负，说明x2进基不会增加目标函数，当前就是最优解。最终答案x1=4，x2=0，最优值12。

这个例子可以看出，基变量的换入换出不是随意的，每一步都是检验数和比值检验共同作用的结果，一个管“能不能变好”，一个管“变到哪个值就顶头了”。

5. 实操中最容易踩的坑与排查方法

5.1 坑一：把“基解”和“可行解”画等号

我最初做题的时候，求出一个基解就直接当作可行解用了，结果目标函数越算越离谱。根本原因在于没做非负检查。基解只是等式约束的解，如果不满足x >= 0，它就是不可行的，不能作为单纯形法的起点。

排查方法其实很简单：每求出一个基解，第一件事就是扫一眼所有分量，看有没有负数。如果有，直接放弃这个候选基。写代码的时候这个检查更要认真，因为代码不会像人一样自动注意到符号问题。

5.2 坑二：选基时忘了检查行列式是否为0

选基变量的时候，如果挑的m个列向量不是线性无关的，基矩阵B就不可逆，后面的计算全部失效。很多人因为初始基都是单位矩阵，就忽略了线性无关的检查，等到迭代几次后选了线性相关的列，整个计算炸掉。

排查方法：每次换入换出后，重新检查基矩阵的行列式。用代码实现时，一般直接调线性代数库求逆，如果抛出奇异矩阵异常，说明选基出问题了。

5.3 坑三：比值检验时忽略分母符号

比值检验的分母必须是正数。如果分母是0或负数，对应约束不会限制进基变量的增长，就不参与比值计算。我见过有人把所有分母都拿去除一遍，把负数也硬算进去，结果得到错误的离基变量，迭代路径直接跑偏。

正确做法是：只取分母大于0的约束做比值计算，最小正值那个就是离基变量。如果所有分母都不大于0，说明目标函数在该方向上无界，问题没有有限最优解。

5.4 坑四：对“离基变量”的误解

很多初学者总觉得“离基”就是把变量从问题里扔掉，不参与了。实际上离基变量并没有消失，它只是变成了非基变量，也就是强制取0值的变量。它在后续迭代里还有可能重新进基。我自己在做对各种变量关系图的时候，才把这一点彻底想通。

5.5 实操判断基变量的通用步骤

如果你拿到一个线性规划题，想知道“哪些变量是基变量”，操作顺序是这样的：

1. 把问题化成标准形（等号约束、非负变量、max目标）。
2. 写出A矩阵和b向量。
3. 从A矩阵里任选m个列，构造候选B矩阵。
4. 计算行列式det(B)，不等于0才合格。
5. 令对应的非基变量为0，解B * xB = b，得到基解。
6. 检查基解是否非负，若是则为基可行解。

这套步骤我在有段时间几乎每天跑一遍，后来直接形成了肌肉记忆。

6. 基变量概念为什么是整个线性规划的核心地基

6.1 基概念连接了对偶理论和灵敏度分析

线性规划不只是单纯形法，对偶问题、灵敏度分析、影子价格这些进阶内容，全都建立在基的框架上。看对偶问题就绕不开基解对应验证；影子价格的本质就是对偶变量的值，而对偶变量的求解刚好需要当前基矩阵的信息。灵敏度分析也是围绕最优基展开：如果某个约束系数变了，最优基是否保持不变，新的解怎么算。

6.2 内点法和单纯形法的区别也在这里

内点法走的是可行域内部逼近，不需要像单纯形法那样一个顶点一个顶点跳。但无论是哪类算法，最终求得的解都要能对应回某个基（在非退化的最优解情况下）。即使是现代求解器，判断最优解时也要找到最优基。理解了基变量，你才算真正进入了运筹学的语言体系，看论文、读教材才不费劲。

6.3 “基”这个概念的真正难点在于抽象程度

其实“基变量”本身不难，难的是从“无穷多解里选一个特殊情况来研究”这个思维。我们习惯了求解方程就是找到一个解，但线性规划里要找的是最优解，而最优解又在无穷多的候选中，于是需要一个办法制造出有限个候选。基就是做这件事的过滤器。想通了这一点，后面很多内容都顺了。

按我个人的学习安排，这轮笔记整理完，我紧接着把教材里关于退化、人工变量法和两阶段法的练习题过了一遍。建议你也这样：概念搞懂之后，马上上手算题，用实际手感来巩固认知。基变量这块如果只靠看，很难真正吃透。