1. 从一道简单的线性规划题说起最近在复盘一些量化策略的基础模型又翻出了运筹学里的线性规划。很多人觉得这东西理论性太强跟实际工作离得远但在我看来线性规划是很多复杂系统优化问题的“骨架”尤其是在处理资源分配、成本最小化这类有明确约束和目标的问题时它的思想无处不在。比如你手头有一笔资金要在几只股票里分配每只股票有预期的收益率和风险系数同时你对总风险有上限要求还想让总收益尽可能高——这本质上就是一个线性规划问题。今天不聊复杂的算法我们回到最根本的地方一个线性规划模型建立好后我们怎么去“解”它更具体地说当我们用单纯形法这类迭代算法时经常会听到“基变量”、“非基变量”、“基解”、“基可行解”这些词。它们到底是什么意思算法是怎么通过摆弄这些变量一步步找到最优解的我发现很多资料要么一上来就扔公式要么过于强调理论证明反而把最直观的“解题动作”给模糊了。所以我想结合一个具体的例子把“根据非基变量的解得到基变量解”这个过程掰开揉碎了讲清楚。理解了这一步你就能看懂单纯形法表格里那些数字变化的逻辑而不是死记硬背步骤。我们用一个经典的例子来贯穿全文生产计划问题。 假设一家小作坊生产两种产品A和B。生产一件A产品需要2小时人工和1公斤原料利润是3元。生产一件B产品需要1小时人工和2公斤原料利润是4元。作坊每天可用的人工工时为100小时原料总量为80公斤。 目标是合理安排A和B的日产量使得总利润最大。把这个问题“翻译”成数学模型就是决策变量设 ( x_1 ) 为产品A的日产量( x_2 ) 为产品B的日产量。目标函数最大化利润( \max Z 3x_1 4x_2 )约束条件人工工时约束( 2x_1 x_2 \leq 100 )原料约束( x_1 2x_2 \leq 80 )非负约束( x_1 \geq 0, x_2 \geq 0 )这就是一个标准形式的线性规划模型除了目标是最大化标准型常要求最小化但这不影响我们理解基本概念。接下来我们要看看这个模型有多少种可能的“解法”。2. 松弛变量把不等式“锁进”等式系统我们的约束条件里有两个“小于等于”的不等式。为了能用线性代数的方法系统性地处理我们需要引入松弛变量 (Slack Variables)。你可以把它们理解为未被利用的“闲置资源”。对于人工约束 ( 2x_1 x_2 \leq 100 )我们加上一个松弛变量 ( x_3 )让它把“小于等于”变成“等于” ( 2x_1 x_2 x_3 100 )且 ( x_3 \geq 0 )。 ( x_3 ) 就代表了当天没用完的人工工时。如果 ( x_3 20 )那就意味着只用了80小时人工。同理对于原料约束 ( x_1 2x_2 \leq 80 )引入松弛变量 ( x_4 ) ( x_1 2x_2 x_4 80 )且 ( x_4 \geq 0 )。 ( x_4 ) 代表了未使用的原料公斤数。现在我们的问题变成了一个有4个变量 ( (x_1, x_2, x_3, x_4) ) 和2个等式约束的方程组 [ \begin{cases} 2x_1 x_2 x_3 100 \ x_1 2x_2 x_4 80 \ x_1, x_2, x_3, x_4 \geq 0 \ \max Z 3x_1 4x_2 0 \cdot x_3 0 \cdot x_4 \end{cases} ] 注意松弛变量在目标函数里的系数是0因为闲置资源不产生利润也不消耗成本。提示如果约束是“大于等于”则需要引入“剩余变量”也可叫负松弛变量和“人工变量”来构造等式这是两阶段法或大M法要处理的内容今天我们聚焦在更简单的“小于等于”情形。现在我们有4个变量2个方程。根据线性代数的知识自由度的数量是变量数减去独立方程数也就是 ( 4 - 2 2 )。这意味着在所有满足等式的解中我们可以自由地指定其中2个变量的值然后另外2个变量的值就能被唯一确定。这个“指定”与“确定”的过程就是理解基变量与非基变量的关键。3. 基变量与非基变量谁在台上谁在台下我们把整个变量团队 ( (x_1, x_2, x_3, x_4) ) 分成两组。非基变量 (Non-basic Variables)我们自由指定其值的那一组变量。通常为了简化在迭代的初始阶段或讨论某个特定解时我们直接指定它们的值为0。你可以把它们想象成“候补队员”或“自由参数”暂时被固定在边界上。基变量 (Basic Variables)剩下的那一组变量它们的值不能自由指定必须通过求解约束方程组来确定。它们是“场上队员”其值由当前的非基变量取值和方程组共同决定。如何分组规则是基变量的数量必须等于约束方程的个数即系数矩阵的秩。在我们这个例子里方程个数是2所以我们必须且只能选出2个变量作为基变量剩下的 ( 4-22 ) 个就是非基变量。选择哪两个作为基变量这有组合数上的多种可能。从4个变量中选2个有 ( C_4^2 6 ) 种选法。每一种选法都定义了一个不同的“基”。基 (Basis)指的就是我们选出的那一组基变量构成的集合。更严格地说基对应的是约束方程中这些基变量所对应的系数列向量构成的一个可逆方阵称为基矩阵。这个可逆性是关键它保证了当我们把非基变量固定后能通过求解线性方程组唯一地解出基变量的值。所以当我们说“选定一个基”就意味着我们决定了哪两个变量是基变量在场上。与这两个基变量对应的系数列向量组成的2x2矩阵必须是可逆的满秩的这样方程组才有唯一解。同时我们 implicitly 决定了剩下的两个变量是非基变量在台下值固定为0。4. 基解一个数学上的“临时答案”好了概念铺垫完我们来玩真的。基解 (Basic Solution)的定义就是给定一个基即选定一组基变量令所有非基变量等于0然后通过求解约束方程组得到的唯一解。我们来看上面6种选基方式中的几种分别算出对应的基解。情况一选择 ( x_1, x_2 ) 作为基变量这意味着 ( x_3, x_4 ) 是非基变量令 ( x_30, x_40 )。 方程组变为 [ \begin{cases} 2x_1 x_2 100 \ x_1 2x_2 80 \end{cases} ] 解这个二元一次方程组 用消元法第二个方程乘以2( 2x_1 4x_2 160 ) 减去第一个方程( (2x_14x_2) - (2x_1 x_2) 160 - 100 ) ( 3x_2 60 ) ( x_2 20 ) 代入第一个方程( 2x_1 20 100 ) ( 2x_1 80 ) ( x_1 40 ) 所以得到基解( (x_1, x_2, x_3, x_4) (40, 20, 0, 0) )。情况二选择 ( x_1, x_3 ) 作为基变量这意味着 ( x_2, x_4 ) 是非基变量令 ( x_20, x_40 )。 方程组变为 [ \begin{cases} 2x_1 x_3 100 \ x_1 80 \end{cases} ] 从第二个方程直接得到 ( x_1 80 )。 代入第一个方程( 2*80 x_3 100 ) ( 160 x_3 100 ) ( x_3 -60 )。 所以得到基解( (80, 0, -60, 0) )。情况三选择 ( x_3, x_4 ) 作为基变量这意味着 ( x_1, x_2 ) 是非基变量令 ( x_10, x_20 )。 方程组变为 [ \begin{cases} x_3 100 \ x_4 80 \end{cases} ] 所以得到基解( (0, 0, 100, 80) )。我们可以把其他几种情况也算出来基 ( {x_1, x_4} )令 ( x_20, x_30 )。方程( 2x_1100, x_1x_480 )。解得 ( x_150, x_430 )。基解( (50, 0, 0, 30) )。基 ( {x_2, x_3} )令 ( x_10, x_40 )。方程( x_2x_3100, 2x_280 )。解得 ( x_240, x_360 )。基解( (0, 40, 60, 0) )。基 ( {x_2, x_4} )令 ( x_10, x_30 )。方程( x_2100, 2x_2x_480 )。解得 ( x_2100, x_480-200-120 )。基解( (0, 100, 0, -120) )。注意细心的你可能发现了在情况二 ( (80,0,-60,0) ) 和情况六 ( (0,100,0,-120) ) 中解出现了负值( x_3 -60 ), ( x_4 -120 )。然而我们的变量都有非负约束 ( x_i \geq 0 )。一个解要成为有实际意义的“方案”必须满足所有约束包括非负约束。这就引出了下一个更重要的概念。5. 基可行解有实际意义的“候选方案”基可行解 (Basic Feasible Solution, BFS)是基解的一个子集。它首先得是一个基解其次它必须满足所有变量的值都非负即 ( x_i \geq 0 )。这意味着这个解落在了所有约束条件包括等式和非负共同构成的“可行域”内部或边界上。回头检查我们算出的6个基解( (40, 20, 0, 0) )全部非负是基可行解。( (80, 0, -60, 0) )( x_3 -60 0 )不是基可行解。( (0, 0, 100, 80) )全部非负是基可行解。( (50, 0, 0, 30) )全部非负是基可行解。( (0, 40, 60, 0) )全部非负是基可行解。( (0, 100, 0, -120) )( x_4 -120 0 )不是基可行解。所以在这6个基解中有4个是基可行解。它们对应着可行域的四个“顶点”或“角点”( (0,0,100,80) )什么都不生产资源全闲置。利润Z0。( (50,0,0,30) )只生产50件A不用B。人工用完( 250100 )原料用了50公斤剩30公斤。利润Z350150。( (0,40,60,0) )只生产40件B不用A。原料用完( 24080 )人工用了40小时剩60小时。利润Z440160。( (40,20,0,0) )生产40件A和20件B。人工和原料恰好用完( 24020100, 4022080 )。利润Z34042012080200。可行基 (Feasible Basis)顾名思义就是能产生一个基可行解的那个“基”。例如基 ( {x_1, x_2} ) 是可行基因为它产生的基解 ( (40,20,0,0) ) 是可行的。基 ( {x_3, x_4} ) 也是可行基它产生 ( (0,0,100,80) )。而那些产生负值解的基如 ( {x_1, x_3} )就不是可行基。线性规划的一个核心定理可行域是凸集最优解一定在顶点取得告诉我们如果线性规划问题有最优解那么至少有一个最优解是基可行解即出现在可行域的某个顶点上。单纯形法这个算法的智慧就在于它不是在无边无际的可行域里盲目搜索而是从一个基可行解一个顶点出发沿着可行域的边迭代到相邻的另一个基可行解另一个顶点并且保证每次迭代目标函数值都不下降对于最大化问题是不上升。这个过程高效地遍历了那些有限的、有潜力的顶点直到找到最优的那个。6. 单纯形表基变量解动态演化的舞台理解了静态的“基解”和“基可行解”我们再看单纯形法表格就会清晰很多。单纯形表是上述计算过程的系统化、表格化呈现。它始终维护着一个当前的可行基以及对应的基可行解。初始时我们通常选择松弛变量作为初始基变量因为它们对应的系数列向量正好构成一个单位矩阵天然可逆求解极其简单。对应我们的例子就是选择 ( {x_3, x_4} ) 作为初始基得到初始基可行解 ( (0,0,100,80) )对应“不生产”方案。单纯形表的核心操作是换基选择进基变量在所有非基变量当前值为0中找一个能提升目标函数对于最大化问题检验数为正的变量让它“进基”即从0开始增加。选择出基变量由于资源有限一个变量增加必然导致当前某些基变量减少。我们根据“最小比值法则”找到最先减少到0的那个基变量让它“出基”变为非基变量值固定为0。更新基矩阵和解完成基变量集合的更换后我们实际上得到了一个新的基。然后我们需要重新根据这个新基令新的非基变量为0求解出新的基变量的值。在单纯形表里这个过程是通过高斯-约当行变换旋转运算一次性完成的变换后的表格最右边一列常数列直接给出了新基可行解下所有基变量的值。以前面计算为例从初始基 ( {x_3, x_4} ) 和基可行解 ( (0,0,100,80) ) 出发。在单纯形表中我们发现 ( x_2 ) 的检验数为正有潜力增加利润所以选 ( x_2 ) 进基。通过比值测试( 100/1100, 80/240 )取最小比值40确定 ( x_4 ) 出基。一次旋转运算后基变成了 ( {x_2, x_3} )新的基可行解直接从变换后的表格中读出( (0, 40, 60, 0) )。这和我们之前手动计算“令 ( x_10, x_40 )解方程组得到 ( x_240, x_360 )”的结果完全一致。单纯形表把这个“根据非基变量取值固定为0求解基变量值”的过程自动化、迭代化了。表格中的每一行本质上代表一个用当前基变量表示的原约束方程。常数列就是当前基变量的值。当基变换时通过行变换更新这些方程使得新的基变量对应的系数列向量化为单位阵此时常数列自然就是新基变量的解。7. 实操中的关键点与常见误区在实际建模和计算中围绕基变量和基解有几个容易踩坑的地方1. 初始可行基的构造不一定简单我们的例子很幸运所有约束都是“≤”加入松弛变量后松弛变量的系数矩阵就是单位阵直接构成一个现成的可行基单位基。这叫标准型的便利。 但在实际问题中如果存在“≥”或“”约束就需要引入人工变量来构造一个初始的单位基然后用两阶段法或大M法先把这些人造的东西赶出基才能得到第一个真正的基可行解。这个过程是单纯形法开始前的重要准备很多人在这里会混乱。2. 退化与循环理论上一个基可行解中如果有基变量的值恰好为0则称为退化的基可行解。这意味着有多于m个m是约束数的变量在边界上值为0。在单纯形法迭代时如果遇到退化并且选择进基/出基变量时出现平局多个比值相同且最小可能会发生“循环”——算法在几个相同的基可行解之间打转永远无法前进。虽然在实际问题中循环极其罕见但理论上是存在的。现代求解器都有应对机制如扰动法。3. 判断一个基解是否可行的快速方法手动计算时得到基解后除了检查所有变量≥0还有一个直观的几何对应把它画在决策变量( x_1, x_2 )的坐标系中。例如解 ( (40,20,0,0) ) 对应点(40,20)这个点恰好是两条约束直线 ( 2x_1x_2100 ) 和 ( x_12x_280 ) 的交点并且落在第一象限。而解 ( (80,0,-60,0) ) 虽然也对应点(80,0)但它不满足 ( x_30 )即 ( 2*800 \leq 100 ) 不成立所以点(80,0)并不在可行域内它位于人工约束线的外侧。基可行解一定对应可行域的顶点但并非所有约束线的交点都是基可行解如果交点在可行域外对应的基解就不可行。4. 基的数量可能少于 ( C_n^m )从n个变量中选m个基变量组合数是 ( C_n^m )。但并非所有组合都能成为“基”。关键条件是选出的m个变量对应的系数列向量必须线性无关构成可逆矩阵。如果某些列向量线性相关这个组合就不能作为基也就没有对应的基解。在构造良好的模型中例如包含松弛变量、人工变量后通常我们关心的基都是那些能构成可行基的组合。理解“根据非基变量的解得到基变量解”这个看似简单的过程是打开线性规划求解黑箱的第一把钥匙。它把抽象的“解空间”具象化为一个个由基定义的“顶点”把连续的优化问题转化为在有限顶点集合上的智能搜索。当你再看到单纯形表里数字跳动时你看到的就不再是枯燥的算术而是一个解在可行域顶点间跳跃、向着最优目标攀登的清晰路径。这种从根本定义出发的理解比记忆任何算法步骤都来得牢固和通透。