单纯形法‘换基’操作图解：像玩魔方一样理解入基和出基（Python代码辅助）

单纯形法换基操作图解像玩魔方一样理解入基和出基想象你手中有一个魔方每次旋转都让某些色块进入视野中心而另一些则被挤到边缘。这与单纯形法中的换基操作惊人地相似——通过精心设计的旋转迭代我们不断将更有潜力的变量引入基中同时将不再重要的变量移出。本文将用这种直观类比配合Python代码演示带你彻底掌握线性规划最核心的迭代机制。1. 魔方视角下的单纯形表结构单纯形表就像是一个被打乱的魔方我们需要通过系统性的操作将其还原到最优状态。先来看标准形式的线性规划问题import numpy as np # 示例问题max Z 3x1 4x2 # 约束条件 # 2x1 x2 ≤ 40 # x1 3x2 ≤ 30 c np.array([3, 4, 0, 0]) # 目标函数系数 A np.array([[2, 1, 1, 0], # 约束系数矩阵 [1, 3, 0, 1]]) b np.array([40, 30]) # 约束右侧常数初始单纯形表可以表示为基变量x₁x₂x₃x₄解x₃211040x₄130130检验数3400-提示x₃和x₄是松弛变量初始作为基变量类似于魔方的中心色块2. 入基选择寻找最有潜力的变量在魔方还原中我们会优先处理能带来最大进展的色块。单纯形法同样通过检验数σⱼ识别最优入基候选def calculate_sigma(c, A, basis_indices): B A[:, basis_indices] c_B c[basis_indices] y np.linalg.solve(B.T, c_B) return c - y A basis [2, 3] # 初始基变量x3,x4的索引 sigma calculate_sigma(c, A, basis) print(f检验数: {sigma[:2]}) # 输出非基变量x1,x2的检验数关键判断标准正检验数表示增加该变量能提升目标值最大正数选择能使目标函数增长最快的变量在我们的例子中x₂的检验数为4比x₁的3更大因此选择x₂入基。3. 出基选择确保可行性边界就像旋转魔方时不能破坏已还原的部分出基选择必须保证解始终可行。我们计算θ比率def find_pivot(A, b, entering_idx): ratios [] for i in range(len(b)): if A[i, entering_idx] 0: ratios.append(b[i] / A[i, entering_idx]) else: ratios.append(np.inf) return np.argmin(ratios) # 返回最小比率对应的行索引 entering 1 # x2的索引 leaving_row find_pivot(A, b, entering) print(f出基变量位于第{leaving_row}行)θ比率计算示例基变量x₂系数解θ解/系数x₃14040x₄33010 ← 最小值因此x₄出基确保所有变量保持非负。4. 基变换矩阵形式的魔方旋转实际进行基变换就像旋转魔方的一个面。我们用高斯-约当消元更新整个单纯形表def pivot(A, b, basis_indices, entering, leaving_row): # 确定出基变量在基中的位置 leaving_pos np.where(np.array(basis_indices) basis_indices[leaving_row])[0][0] # 更新基变量索引 new_basis basis_indices.copy() new_basis[leaving_pos] entering # 高斯消元 pivot_row leaving_row pivot_val A[pivot_row, entering] A[pivot_row, :] / pivot_val b[pivot_row] / pivot_val for i in range(len(b)): if i ! pivot_row and A[i, entering] ! 0: multiplier A[i, entering] A[i, :] - multiplier * A[pivot_row, :] b[i] - multiplier * b[pivot_row] return new_basis new_basis pivot(A, b, basis, entering, leaving_row) print(f新基变量索引: {new_basis})变换后的单纯形表基变量x₁x₂x₃x₄解x₃5/301-1/330x₂1/3101/310检验数5/300-4/3405. 迭代终止与最优解识别当所有检验数非正时就像魔方完全还原我们找到了最优解def is_optimal(sigma): return all(s 0 for s in sigma) while not is_optimal(sigma): entering np.argmax(sigma) leaving_row find_pivot(A, b, entering) basis pivot(A, b, basis, entering, leaving_row) sigma calculate_sigma(c, A, basis) print(f最优基变量索引: {basis}) print(f最优解: x1{b[0]/A[0,0] if 0 in basis else 0}, x2{b[1]/A[1,1] if 1 in basis else 0})最终表显示所有检验数≤0基变量x₁6, x₂8最优目标值Z3×6 4×850整个过程就像通过一系列精心选择的旋转将线性规划问题逐步导向最优解。每次迭代都使目标值严格增大最终达到无法再改进的状态。