线性规划基变量：从几何直觉到单纯形法换基全解析

今天复习线性规划，翻到3月3日的学习笔记，发现自己在“基变量”这个词上卡了整整一个下午。书上写着“从系数矩阵A中选m个线性无关的列，对应的变量叫基变量”，字面意思好懂，但一落到题目里就懵：这些列凭什么这么选？选出来有什么用？为什么单纯形表每换一次基，非基变量就换一批？如果你也有同样的困惑，这篇笔记应该能帮到你。运筹学里线性规划几乎绕不开“基”的概念，后面单纯形法、对偶理论、灵敏度分析全都建立在这块地基上，啃不透它，后面会越学越虚。我会从最直观的几何视角讲起，再配合一个完整例子手算到底，把“基变量”“非基变量”“离基变量”这些术语一次性聊透。

1. 先搞清楚：我们为什么要讨论“基”

很多教材一上来就甩定义，把基变量、基阵、基本可行解排成一排，学生只能硬背。我不太喜欢这种学法。一个概念如果不知道它要解决什么问题，背下来也是死的。所以先把问题本身摆出来。

1.1 线性规划标准形：从约束方程组说起

线性规划问题经过标准化之后，通常长这样：

目标函数：max（或min）z = c₁x₁ + c₂x₂ + … + cₙxₙ

约束条件： a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ = b₁ a₂₁x₁ + a₂₂x₂ + … + a₂ₙxₙ = b₂ … aₘ₁x₁ + aₘ₂x₂ + … + aₘₙxₙ = bₘ x₁, x₂, …, xₙ ≥ 0

写成矩阵形式就是：max cᵀx，s.t. Ax = b，x ≥ 0。

注意这里A是m行n列的矩阵，而且在实际问题中n通常大于m，也就是说方程个数少于变量个数。初中就学过，未知数比方程多时，方程组会有无穷多个解。

我一开始就想不通：既然有无穷多个解，怎么找最优解？难道要一个一个试？当然不行。但转念一想，线性规划比普通方程组多了一条“x ≥ 0”的非负约束，这条约束会把无穷解砍掉一大截，只留下一个有界的多面体区域。这个区域叫可行域，问题的本质就是在可行域里找一个点，让目标函数值最大或最小。

那可行域长什么样？二维情况下就是凸多边形，三维是凸多面体，高维虽然画不出来，但性质一样：它是个凸集，边界面是超平面。线性目标函数在这个凸集上的最优值，一定能在某个“角落”取到。这个“角落”在数学上叫极点，也就是顶点。

这个结论是整个线性规划的基石。它说明：我们不用遍历无穷多个可行解，只要检查可行域的顶点就够了。那问题就变成——怎么用代数方法找到这些顶点？

1.2 顶点、可行域与“基”的几何对应

顶点的几何含义是“不能再沿着任何直线段往两边走还在可行域内”的点。代数上怎么描述？你可以这么理解：一个n维空间里的点，要成为顶点，必须有足够多的约束条件“同时压住”它。

回到标准形Ax = b，这里有m个等式约束。n维变量要确定一个点，通常需要n个独立条件。m个等式已经占掉了m个条件，还剩下n-m个“自由度”。要想让点落在顶点上，就得再让n-m个变量取到边界值。在x ≥ 0的约束下，边界值就是0。

所以顶点的代数特征很清晰：把n-m个变量设为0，剩下的m个变量由m个等式唯一确定。这个“剩下m个变量”的选择，就是“基”的由来。选哪m个变量作为“主角”解出来，其余变量统统置零，得到的解就刻画了一个顶点。

拿生活中的事打个比方：你去拍一张合照，画面里有若干人，但你只关心其中几个人是否在C位。选谁站C位，决定了这张照片呈现出来的构图。“基变量”就像被选中站C位的那些人，非基变量则是被排除在构图外的背景。每次换一种选法，画面就变成了另一个顶点。

有了这个几何直觉，再去啃教材里的定义就不会晕了：基、基变量、非基变量、基本解、基本可行解，这套名词不过是在回答同一个问题——我们选了哪几个变量来代表当前这个顶点。

2. 基、基变量与非基变量的严格定义

直觉有了，接下来就得把定义逐字逐句掰开看。这部分会触及一些线性代数的内容，但我尽量讲得具体点。

2.1 触发我纠结的那三句话

教材上关于“基”的定义一般是这样三句话：

• 从系数矩阵A中取m个线性无关的列向量，组成一个m×m的可逆方阵B，称B为线性规划的一个基（基阵）。
• B中m个列向量对应的变量称为基变量，其余变量称为非基变量。
• 令所有非基变量等于0，解方程组Bx_B = b，得到的解称为基本解；如果基本解还满足x_B ≥ 0，就称为基本可行解。

我当初卡住的地方在第一句：为什么一定要“线性无关”？

你回想一下线性代数里的“基”的概念：一个向量空间里，选择一组线性无关的向量，就能张成整个空间。线性规划里的“基”是一模一样的逻辑——m个方程要唯一解出m个变量，这m个列向量必须线性无关，否则方程组要么无解要么无穷多解，根本得不出确定的候选顶点。

打个比方，你有一把钥匙上有几个齿，每个齿对应一个约束。如果几个齿完全平行、互相重复，那这把钥匙根本没法开锁。列向量线性无关，意味着每个约束提供的是独立信息，不会互相抵消。

基本解和基本可行解的区别也值得说清楚。基本解只要求“非基变量为0，能解出来”，不保证解出来的基变量是正数。而变量有非负约束，所以只有基变量全部非负的基本解，才是落在可行域里的解。这个区分很重要，因为在单纯形法的迭代中，我们从A矩阵里选基组的时候，不是随便选一组就能用，必须保证对应的基本解可行。

2.2 手算一个完整例子：挑基、算基本解

定义光看是不够的，必须动手算。拿一个经典例子：

max z = 2x₁ + 3x₂

s.t. x₁ + 2x₂ ≤ 8 4x₁ ≤ 16 4x₂ ≤ 12 x₁, x₂ ≥ 0

先标准化，把三个不等式分别加上松弛变量x₃、x₄、x₅：

x₁ + 2x₂ + x₃ = 8 4x₁ + x₄ = 16 4x₂ + x₅ = 12 x₁, x₂, x₃, x₄, x₅ ≥ 0

这里m=3（三个等式约束），n=5（五个变量），所以基变量永远是3个，非基变量是2个。A矩阵是3行5列：

从5列里选3列作为基，一共有C(5,3)=10种组合。我挑几组有代表性的算给你看。

第一组：选x₃、x₄、x₅作为基变量。这三列刚好是单位矩阵：

B = | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 1 |

令非基变量x₁=0，x₂=0，直接读出来：x₃=8，x₄=16，x₅=12。全部非负，所以这是一个基本可行解，对应顶点(0,0)，目标值z=0。

第二组：选x₂、x₃、x₄作为基变量。对应列是：

B = | 2 | 1 | 0 | | 0 | 0 | 1 | | 4 | 0 | 0 |

令非基变量x₁=0，x₅=0，解方程组： 2x₂ + x₃ = 8 x₄ = 16 4x₂ = 12

算出来x₂=3，x₃=2，x₄=16。全部非负，可行，对应顶点(0,3)，目标值z=9。

第三组：选x₂、x₄、x₅作为基变量。对应列：

B = | 2 | 0 | 0 | | 0 | 1 | 0 | | 4 | 0 | 1 |

令非基变量x₁=0，x₃=0，解方程组： 2x₂ = 8 x₄ = 16 4x₂ + x₅ = 12

算出来x₂=4，x₄=16，x₅=-4。这里x₅是负数，不满足非负约束，所以这是基本解，但不是基本可行解。它在几何上对应点(0,4)，但这个点跑到了可行域外面，因为4x₂ ≤ 12这条约束被违反了。

这三组例子已经把关键信息展示得很清楚：同样是“选3个变量当基变量”，有的可行有的不可行。单纯形法每一步做的事情，本质上就是在这些基之间跳来跳去，只保留可行的那些。

2.3 判断基变量的三个实用标准

做题时怎么快速判断哪些变量能当基变量？我总结了三条实用标准。

第一条：数量标准。基变量个数必须严格等于m。你不可能在一个3个等式约束的问题里选出4个基变量，那会变成超定方程组。反过来，少于m个也无法唯一确定顶点。

第二条：结构标准。选出的m个列必须线性无关。手算时最直接的方法是把选出的列组成方阵，算一下行列式是否为0；在实际单纯形表中，基变量对应的列经过行变换后应当是单位向量，也就是某一行是1、其它行是0的形式。

第三条：非负标准。即使一组列向量线性无关，解出来的基变量也可能出现负数。只有基变量全部≥0，对应的基本解才算基本可行解。这一步在单纯形表里体现为RHS列必须非负。

我在做题时习惯把这三条按顺序过一遍：先数个数，再看行列式，最后检查非负。三步都过了，这组基就是合法的“候选顶点”。

3. 单纯形法里的每一次换基：入基与离基变量

基的概念不是孤立存在的，它的主战场在单纯形法。单纯形法每一步都在换基：让一个非基变量变成基变量，同时让一个基变量变成非基变量。前者叫入基变量，后者叫出基变量，也就是网上经常搜到的“离基变量”。这一节把换基的完整逻辑讲清楚。

3.1 最小比值原则：为什么是它决定离基变量

单纯形法选入基变量时看的是检验数，也就是目标函数中该非基变量的边际贡献。如果增加某个非基变量能让目标值上升，就把它拉进基里；如果所有非基变量的边际贡献都不再有正收益，当前顶点就是最优解。

选谁入基相对直观，新手真正容易懵的是“选谁离基”。这里用最小比值原则：对入基变量xₖ，看约束方程组中每一行xₖ的系数aᵢₖ，如果aᵢₖ > 0，就用该行的RHS除以aᵢₖ，比值最小的那一行对应的基变量离基。

为什么只挑正系数？你想想，入基变量要从0开始增大，它对每个基变量会造成两种影响：如果aᵢₖ是正数，这个基变量会随着入基变量增大而减少；如果aᵢₖ是负数，基变量反而会增大。我们关心的是“哪个基变量会最先被压到0”。一旦某个基变量变成0，它就在边界上了，顶点条件达成，必须换人。所以只有正系数才可能把基变量“压低到0”，负系数只会让它更宽松，不构成限制。

换个几何说法：当前顶点沿着某条棱往前移动，最先撞上的那面墙决定还能走多远。最小比值就是那面墙的距离，撞墙时对应的基变量就是离基变量。

3.2 用刚才的例子走完三次换基

继续用上面的例子，我把三次换基完整走一遍。这个例子的可行域顶点分别是(0,0)、(0,3)、(2,3)、(4,2)、(4,0)，单纯形法会沿着其中一条路径爬到最优点(4,2)。

初始单纯形表：

我用的z行是移项后的形式（z - 2x₁ - 3x₂ = 0），所以哪个非基变量在z行里的负系数绝对值最大，哪个就优先入基。这里x₂对应-3，最负，选x₂入基。

然后算θ：第一行8/2=4，第三行12/4=3，第二行x₂系数为0不参与。最小比值是3，对应x₅行，所以x₅离基。注意这里不是选比值最大的x₃行，因为x₂增大到3之后，x₅就已经变成0了，如果坚持让x₂继续增大到4，第三行会变成4×4+x₅=12，x₅=-4，直接违反非负约束。

换基后得到新表：

此时基变量是x₃、x₄、x₂，对应顶点(0,3)，目标值z=9。z行还剩一个负系数-2（对应x₁），说明x₁入基还能继续改进目标。

算θ：x₃行2/1=2，x₄行16/4=4，x₂行x₁系数为0。最小比值是2，x₃离基。换基：

基变量是x₁、x₄、x₂，对应顶点(2,3)，目标值z=13。z行里x₅列是-0.25，说明x₅入基还能继续提升目标。

算θ：x₄行8/2=4，x₂行3/0.25=12，x₁行x₅系数为负，不参与。最小比值是4，x₄离基。换基：

此时z行所有系数都是非负的，没有可入基的变量了，达到最优。基变量是x₁、x₅、x₂，对应顶点(4,2)，目标值z=14。

复盘一下三次换基：

你看，松弛变量不是一直赖在基里的。x₅第一次就离基了，x₃第二次离基，最后剩下的基变量里甚至有x₅又回来了。这就是“基变量”会轮换的直接证据。

3.3 退化解与循环：基理论里的边界情况

正常情况下，每次换基目标值都会严格增加，但有一种特殊情况叫退化。当某个基变量本身取值是0时，最小比值计算可能出现θ=0，换基后目标值不变，只是在同一个几何顶点上换了基变量的表示方式。

退化会带来什么麻烦？理论上可能出现“循环”——单纯形法在几个基之间来回转圈，永远到不了最优解。实际应用中循环极罕见，但教材里爱提，因为这是理论上的漏洞。

有没有解决办法？有。最简单的是Bland规则：入基和出基都优先选下标最小的变量。这个规则虽然会牺牲一点效率，但能严格保证算法不循环。

手算时碰到退化不用慌，我一般会额外检查：如果θ出现0，说明当前基里有变量已经是0了，这时换基后目标值不变，先继续算下去，如果感觉在兜圈子，就改用Bland规则重新选一轮。

4. 学习“基”概念时容易踩的认知误区

概念学完之后，我回想自己曾经掉的坑，发现有三个误区特别常见，值得单独拎出来写一写。

4.1 误区一：松弛变量永恒是基变量

很多人学完标准化之后形成一种错觉：加了松弛变量，那松弛变量就一直是基变量，单纯形表里读出来的基变量永远是那批松弛变量。这是错的。

从上面的例子可以看得清清楚楚：初始基确实由三个松弛变量x₃、x₄、x₅组成，但迭代一轮之后x₅就出局了，第二轮x₃也出局了。松弛变量只是标准化时顺手引入的“临时工”，给单纯形法提供一个现成的初始单位阵，方便算法起步。一旦迭代开始，谁入基谁离基完全由检验数和最小比值决定，跟“是不是松弛变量”没有任何关系。

4.2 误区二：基变量越多越好

另一个常见误解是把“基变量”理解成“重要的变量”或“值比较大的变量”。基变量的个数是固定的，永远等于约束方程的个数m，不会因为某个变量更重要就多给一个位置。

非基变量也不等于“不重要的变量”。它只是当前顶点下被置零的变量，在另一个顶点可能就变成基变量了。比如上面例子里x₅第一次迭代离基，第三次迭代又入基，你能说它不重要吗？它只是在不同顶点扮演不同角色而已。

我自己的理解是：基变量更像“当前坐标系里用来锚定顶点的那几个坐标轴”，非基变量则是“被推到边界外的点”。换个顶点，坐标系就换了，角色自然跟着变。

4.3 误区三：只背步骤不懂“为什么选这个基”

第三个误区比较隐性：很多人能按单纯形表的流程算出答案，但问一句“为什么这一步选这个变量入基”“为什么换基后要把列变成单位向量”就答不上来。

单纯形表里每轮做的行变换，本质就是在解一个换元后的线性方程组。你把入基变量当成新的“关键未知量”，把离基变量的位置让给它，然后用高斯消元把表格整理成“基变量列恰好是单位向量”的标准形式。这不是什么神秘操作，就是解方程组的消元法在表格式算例里的体现。

所以下次算单纯形表时，别只盯着检验数，试着在每轮迭代后把基变量取出来，回代到原约束里验证一下，你立刻会发现：基变量取值恰好就是当前顶点的坐标，目标值也正好是z行的RHS。这套闭环一旦打通，单纯形法就不再是“背表”，而是一次次坐标切换。

5. 给新手的实操建议：怎么把“基”学扎实

最后分享几个我亲测有效的学习方法，能帮你把“基”这个概念从“背定义”变成“真的懂”。

5.1 动手从图形法出发，给单纯形表标出顶点坐标

我学到这里时，做过一件很笨但很有效的事：找一个只有两个决策变量的线性规划问题，先画图求出所有顶点，再手算单纯形表，每迭代一轮，就把当前基变量取值还原成坐标，标到图上。

比如刚才那个例子，画出来的可行域是个五边形，顶点包括(0,0)、(0,3)、(2,3)、(4,2)、(4,0)。单纯形法从(0,0)出发，先走到(0,3)，再走到(2,3)，最后走到(4,2)，刚好是在可行域边上“爬坡”。每一步的目标值分别是0、9、13、14，单调上升。

这样做一遍之后，你对“基”的理解会从代数层面沉到几何层面：原来换基就是换顶点，原来检验数就是判断哪个方向能爬坡，原来最小比值就是看前面多远处有墙。这套直觉建立起来，以后学对偶单纯形法、灵敏度分析都顺很多。

5.2 几道值得反复做的自测题

我给自己整理过一组自测题，每次复习都会重新做一遍。

第一题：给定一个2个约束、4个变量的标准形，A矩阵已知，判断哪些列组合构成基，哪些不构成，并说明理由。这道题练的是“线性无关”的判断能力。

第二题：画出上面那个例子的可行域，然后手动把每条约束对应的松弛变量取0的直线标出来，观察每个顶点有哪些松弛变量等于0。你会发现，顶点上被压到0的变量，恰好就是单纯形表里的非基变量。

第三题：构造一个退化问题，比如max z = 3x₁ + 2x₂，约束x₁ + x₂ ≤ 4，2x₁ + x₂ ≤ 8，x₁,x₂≥0。算一下它在某些顶点上会不会出现基变量取0的情况，然后思考：目标值在这个顶点上还有没有提升空间。

第四题：手算完一个小规模问题后，用代码验证结果。比如用Python的scipy.optimize.linprog跑一下，看看手算和程序算出来的最优解是否一致。这不是偷懒，而是用程序当“计算器”，把精力专注在理解算法本身上。

from scipy.optimize import linprog c = [-2, -3] A_ub = [[1, 2], [4, 0], [0, 4]] b_ub = [8, 16, 12] res = linprog(c, A_ub=A_ub, b_ub=b_ub, method='highs') print(res.x) # [4. 2.] print(-res.fun) # 14.0

这个例子跑出来正好是x₁=4、x₂=2、最优值14，和手算结果一致。用程序验证不是为了省事，而是让自己对手算过程更有信心。

我自己整个学下来的体会是：“基”这个概念的难点不在公式多复杂，而在它太抽象，单靠文字很难建立直觉。一旦你亲手算过几轮单纯形表、把每个基变量对应到图形上的顶点，这个坎就迈过去了。最后再分享一个小技巧：每次迭代结束，别急着算下一步，先盯着当前表里的基变量列看几秒，问自己“现在我在哪个顶点”“哪些约束被压紧了”“下一步我还能往哪个方向走”。这三个问题想清楚，单纯形法就真的变成你自己的工具了。