企业官网建设流程全解析

单纯形法换基操作图解：像玩魔方一样理解入基和出基

想象你手中有一个魔方，每次旋转都让某些色块进入视野中心，而另一些则被挤到边缘。这与单纯形法中的换基操作惊人地相似——通过精心设计的"旋转"（迭代），我们不断将更有潜力的变量引入基中，同时将不再重要的变量移出。本文将用这种直观类比，配合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₄是松弛变量，初始作为基变量，类似于魔方的中心色块

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₄出基，确保所有变量保持非负。

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}")

变换后的单纯形表：

5. 迭代终止与最优解识别

当所有检验数非正时，就像魔方完全还原，我们找到了最优解：

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
• 最优目标值Z=3×6 + 4×8=50

整个过程就像通过一系列精心选择的"旋转"，将线性规划问题逐步导向最优解。每次迭代都使目标值严格增大，最终达到无法再改进的状态。