今天复习线性规划翻到3月3日的学习笔记发现自己在“基变量”这个词上卡了整整一个下午。书上写着“从系数矩阵A中选m个线性无关的列对应的变量叫基变量”字面意思好懂但一落到题目里就懵这些列凭什么这么选选出来有什么用为什么单纯形表每换一次基非基变量就换一批如果你也有同样的困惑这篇笔记应该能帮到你。运筹学里线性规划几乎绕不开“基”的概念后面单纯形法、对偶理论、灵敏度分析全都建立在这块地基上啃不透它后面会越学越虚。我会从最直观的几何视角讲起再配合一个完整例子手算到底把“基变量”“非基变量”“离基变量”这些术语一次性聊透。1. 先搞清楚我们为什么要讨论“基”很多教材一上来就甩定义把基变量、基阵、基本可行解排成一排学生只能硬背。我不太喜欢这种学法。一个概念如果不知道它要解决什么问题背下来也是死的。所以先把问题本身摆出来。1.1 线性规划标准形从约束方程组说起线性规划问题经过标准化之后通常长这样目标函数max或minz 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ᵀxs.t. Ax bx ≥ 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这里m3三个等式约束n5五个变量所以基变量永远是3个非基变量是2个。A矩阵是3行5列x₁x₂x₃x₄x₅约束112100约束240010约束304001从5列里选3列作为基一共有C(5,3)10种组合。我挑几组有代表性的算给你看。第一组选x₃、x₄、x₅作为基变量。这三列刚好是单位矩阵B | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 1 |令非基变量x₁0x₂0直接读出来x₃8x₄16x₅12。全部非负所以这是一个基本可行解对应顶点(0,0)目标值z0。第二组选x₂、x₃、x₄作为基变量。对应列是B | 2 | 1 | 0 | | 0 | 0 | 1 | | 4 | 0 | 0 |令非基变量x₁0x₅0解方程组 2x₂ x₃ 8 x₄ 16 4x₂ 12算出来x₂3x₃2x₄16。全部非负可行对应顶点(0,3)目标值z9。第三组选x₂、x₄、x₅作为基变量。对应列B | 2 | 0 | 0 | | 0 | 1 | 0 | | 4 | 0 | 1 |令非基变量x₁0x₃0解方程组 2x₂ 8 x₄ 16 4x₂ x₅ 12算出来x₂4x₄16x₅-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)。初始单纯形表基变量x₁x₂x₃x₄x₅RHSθx₃1210084x₄4001016—x₅04001123z行-2-30000我用的z行是移项后的形式z - 2x₁ - 3x₂ 0所以哪个非基变量在z行里的负系数绝对值最大哪个就优先入基。这里x₂对应-3最负选x₂入基。然后算θ第一行8/24第三行12/43第二行x₂系数为0不参与。最小比值是3对应x₅行所以x₅离基。注意这里不是选比值最大的x₃行因为x₂增大到3之后x₅就已经变成0了如果坚持让x₂继续增大到4第三行会变成4×4x₅12x₅-4直接违反非负约束。换基后得到新表基变量x₁x₂x₃x₄x₅RHSx₃1010-0.52x₄4001016x₂01000.253z行-20000.759此时基变量是x₃、x₄、x₂对应顶点(0,3)目标值z9。z行还剩一个负系数-2对应x₁说明x₁入基还能继续改进目标。算θx₃行2/12x₄行16/44x₂行x₁系数为0。最小比值是2x₃离基。换基基变量x₁x₂x₃x₄x₅RHSx₁1010-0.52x₄00-4128x₂01000.253z行0020-0.2513基变量是x₁、x₄、x₂对应顶点(2,3)目标值z13。z行里x₅列是-0.25说明x₅入基还能继续提升目标。算θx₄行8/24x₂行3/0.2512x₁行x₅系数为负不参与。最小比值是4x₄离基。换基基变量x₁x₂x₃x₄x₅RHSx₁1000.2504x₅00-20.514x₂010.5-0.12502z行001.50.125014此时z行所有系数都是非负的没有可入基的变量了达到最优。基变量是x₁、x₅、x₂对应顶点(4,2)目标值z14。复盘一下三次换基迭代入基变量离基变量顶点目标值第1次x₂x₅(0,3)9第2次x₁x₃(2,3)13第3次x₅x₄(4,2)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₂ ≤ 42x₁ x₂ ≤ 8x₁,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_ubA_ub, b_ubb_ub, methodhighs) print(res.x) # [4. 2.] print(-res.fun) # 14.0这个例子跑出来正好是x₁4、x₂2、最优值14和手算结果一致。用程序验证不是为了省事而是让自己对手算过程更有信心。我自己整个学下来的体会是“基”这个概念的难点不在公式多复杂而在它太抽象单靠文字很难建立直觉。一旦你亲手算过几轮单纯形表、把每个基变量对应到图形上的顶点这个坎就迈过去了。最后再分享一个小技巧每次迭代结束别急着算下一步先盯着当前表里的基变量列看几秒问自己“现在我在哪个顶点”“哪些约束被压紧了”“下一步我还能往哪个方向走”。这三个问题想清楚单纯形法就真的变成你自己的工具了。 
长河君 · 2026/10/5 6:12:27 · 阅读 1.2k 线性规划基变量：从几何直觉到单纯形法换基全解析
今天复习线性规划翻到3月3日的学习笔记发现自己在“基变量”这个词上卡了整整一个下午。书上写着“从系数矩阵A中选m个线性无关的列对应的变量叫基变量”字面意思好懂但一落到题目里就懵这些列凭什么这么选选出来有什么用为什么单纯形表每换一次基非基变量就换一批如果你也有同样的困惑这篇笔记应该能帮到你。运筹学里线性规划几乎绕不开“基”的概念后面单纯形法、对偶理论、灵敏度分析全都建立在这块地基上啃不透它后面会越学越虚。我会从最直观的几何视角讲起再配合一个完整例子手算到底把“基变量”“非基变量”“离基变量”这些术语一次性聊透。1. 先搞清楚我们为什么要讨论“基”很多教材一上来就甩定义把基变量、基阵、基本可行解排成一排学生只能硬背。我不太喜欢这种学法。一个概念如果不知道它要解决什么问题背下来也是死的。所以先把问题本身摆出来。1.1 线性规划标准形从约束方程组说起线性规划问题经过标准化之后通常长这样目标函数max或minz 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ᵀxs.t. Ax bx ≥ 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这里m3三个等式约束n5五个变量所以基变量永远是3个非基变量是2个。A矩阵是3行5列x₁x₂x₃x₄x₅约束112100约束240010约束304001从5列里选3列作为基一共有C(5,3)10种组合。我挑几组有代表性的算给你看。第一组选x₃、x₄、x₅作为基变量。这三列刚好是单位矩阵B | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 1 |令非基变量x₁0x₂0直接读出来x₃8x₄16x₅12。全部非负所以这是一个基本可行解对应顶点(0,0)目标值z0。第二组选x₂、x₃、x₄作为基变量。对应列是B | 2 | 1 | 0 | | 0 | 0 | 1 | | 4 | 0 | 0 |令非基变量x₁0x₅0解方程组 2x₂ x₃ 8 x₄ 16 4x₂ 12算出来x₂3x₃2x₄16。全部非负可行对应顶点(0,3)目标值z9。第三组选x₂、x₄、x₅作为基变量。对应列B | 2 | 0 | 0 | | 0 | 1 | 0 | | 4 | 0 | 1 |令非基变量x₁0x₃0解方程组 2x₂ 8 x₄ 16 4x₂ x₅ 12算出来x₂4x₄16x₅-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)。初始单纯形表基变量x₁x₂x₃x₄x₅RHSθx₃1210084x₄4001016—x₅04001123z行-2-30000我用的z行是移项后的形式z - 2x₁ - 3x₂ 0所以哪个非基变量在z行里的负系数绝对值最大哪个就优先入基。这里x₂对应-3最负选x₂入基。然后算θ第一行8/24第三行12/43第二行x₂系数为0不参与。最小比值是3对应x₅行所以x₅离基。注意这里不是选比值最大的x₃行因为x₂增大到3之后x₅就已经变成0了如果坚持让x₂继续增大到4第三行会变成4×4x₅12x₅-4直接违反非负约束。换基后得到新表基变量x₁x₂x₃x₄x₅RHSx₃1010-0.52x₄4001016x₂01000.253z行-20000.759此时基变量是x₃、x₄、x₂对应顶点(0,3)目标值z9。z行还剩一个负系数-2对应x₁说明x₁入基还能继续改进目标。算θx₃行2/12x₄行16/44x₂行x₁系数为0。最小比值是2x₃离基。换基基变量x₁x₂x₃x₄x₅RHSx₁1010-0.52x₄00-4128x₂01000.253z行0020-0.2513基变量是x₁、x₄、x₂对应顶点(2,3)目标值z13。z行里x₅列是-0.25说明x₅入基还能继续提升目标。算θx₄行8/24x₂行3/0.2512x₁行x₅系数为负不参与。最小比值是4x₄离基。换基基变量x₁x₂x₃x₄x₅RHSx₁1000.2504x₅00-20.514x₂010.5-0.12502z行001.50.125014此时z行所有系数都是非负的没有可入基的变量了达到最优。基变量是x₁、x₅、x₂对应顶点(4,2)目标值z14。复盘一下三次换基迭代入基变量离基变量顶点目标值第1次x₂x₅(0,3)9第2次x₁x₃(2,3)13第3次x₅x₄(4,2)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₂ ≤ 42x₁ x₂ ≤ 8x₁,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_ubA_ub, b_ubb_ub, methodhighs) print(res.x) # [4. 2.] print(-res.fun) # 14.0这个例子跑出来正好是x₁4、x₂2、最优值14和手算结果一致。用程序验证不是为了省事而是让自己对手算过程更有信心。我自己整个学下来的体会是“基”这个概念的难点不在公式多复杂而在它太抽象单靠文字很难建立直觉。一旦你亲手算过几轮单纯形表、把每个基变量对应到图形上的顶点这个坎就迈过去了。最后再分享一个小技巧每次迭代结束别急着算下一步先盯着当前表里的基变量列看几秒问自己“现在我在哪个顶点”“哪些约束被压紧了”“下一步我还能往哪个方向走”。这三个问题想清楚单纯形法就真的变成你自己的工具了。