单纯形法可视化教学台

看清 σⱼ 怎么选入基、θ 怎么定出基,以及每次换基到底把基可行解挪到了哪个顶点

cⱼ 目标系数 C_B 基变量目标系数 X_B 基变量 b 右端项 σⱼ 检验数 θ 比值
⇄ 图解法

④ 单纯形表(版式同教材表 2-4)

基变量列 主元 入基列(σⱼ > 0) 离基行(θ 最小)
提示:在"我来选"模式下,直接点击底部检验系数行里的 σⱼ 选入基变量、点击最右侧 θᵢ 列选离基变量。

⑤ 这一步为什么这样走

尚未求解。点击左侧"求解并生成单纯形表"。

θ 比值检验(最小比值规则)

θᵢ = bᵢ / aᵢₖ,只对 aᵢₖ > 0 的行计算,取最小者对应的基变量离基。

为什么要取最小 θ? xₖ 进基后从 0 开始增大,所有基变量都会跟着变: xB(i) = bᵢ − aᵢₖ·xₖ。要让每个基变量都不小于 0,必须有 xₖ ≤ bᵢ / aᵢₖ(当 aᵢₖ > 0),所以 xₖ 最多只能取到最小的那个比值; 那个最先被压到 0 的基变量就离基。

⑥ 结果判定

等待求解…

⑦ 几何直观(2 个决策变量时)

可行域 单纯形法走过的顶点 目标函数等值线 当前紧约束

单纯形法到底在干什么?

线性规划的可行域是一个凸多面体(二维时就是多边形)。一个基本事实是: 如果最优解存在,就一定能在可行域的某个顶点上取到。单纯形法的全部工作,就是 从一个顶点出发,沿着可行域的棱,一步步走到更好的相邻顶点,直到再也找不到更好的顶点为止。

它之所以能"只看表不看图",是因为一个顶点和一个基是一一对应的: 顶点处有 n 个变量取 0(非基变量),其余 m 个变量(基变量 X_B)由方程组唯一确定。 于是"换一个顶点"就变成了"换一组基",而换基在表上就是一次 Gauss-Jordan 消元,纯粹是机械的行运算。

1. 标准形:先把问题铺平成表格

人工变量是"假变量",原问题里并不存在它。为了逼它在最优解中取 0,大 M 法把它的目标系数取成 −M (M 是一个任意大的正数),于是只要它取值大于 0,目标函数就会被罚得很惨。 这就是表中 C_B 列会出现 −M、σⱼ 会出现含 M 的项的原因。

2. σⱼ 检验数:判断"还能不能更好",并挑出谁进基

表中最后一行就是检验数:

σⱼ = cⱼ − Σᵢ C_B(i)·aᵢⱼ ,z = Σᵢ C_B(i)·bᵢ

它的含义是:非基变量 xⱼ 每增加 1 个单位,目标函数会改变多少。 因为把 xⱼ 增加 1 时,为了保持等式约束,基变量必须相应调整,调整的代价正好是 Σ C_B(i)aᵢⱼ, 所以净收益就是 cⱼ 减掉这个代价。

3. θ 最小比值规则:定出谁离基

选好进基变量 xₖ 之后,它从 0 开始变大。由 x_B(i) = bᵢ − aᵢₖ·xₖ 可知, 只有 aᵢₖ > 0 的基变量会随 xₖ 增大而减小。为了不破坏 X_B ≥ 0(可行性), 必须

xₖ ≤ θ = min{ bᵢ / aᵢₖ | aᵢₖ > 0 }

4. Gauss-Jordan 消元:把新顶点"算"出来

几何上,这一步就是沿着一条棱滑到相邻顶点:进基变量从 0 变为 θ,离基变量从它的值变为 0,目标函数值由 z 变为 z + σₖ·θ。

5. 四种结局

情况表上的特征结论
唯一最优解所有非基变量 σⱼ ≤ 0(max)当前顶点即唯一最优解
多重最优解某个非基变量 σⱼ = 0该变量可进基而 z 不变,最优解有无穷多个(最优解在一条边/一个面上)
无界解σₖ > 0 但主元列所有 aᵢₖ ≤ 0目标函数无上界,不存在有限最优解
无可行解最优表中仍有人工变量在基内且取值 > 0可行域为空,原问题无解

6. 手算流程(照着走就不会错)

  1. 化标准形:补松弛/剩余/人工变量,把 b 调成非负,目标一律化成 max。
  2. 填初始表:基变量取单位列对应的变量,写上 C_B、X_B、b。
  3. 算 σⱼ = cⱼ − Σ C_B(i)aᵢⱼ 与 z = Σ C_B(i)bᵢ。
  4. 检验:σⱼ 全部满足最优性条件 → 停,写出最优解;否则挑一个进基变量。
  5. 算 θ,取最小者定离基变量与主元;所有 aᵢₖ ≤ 0 则说明无界。
  6. Gauss-Jordan 消元,换基,回到第 3 步。

常见疑问

为什么初始基可行解就是 b?

因为标准形里松弛变量(和人工变量)的系数列正好是单位向量,把非基变量全部取 0 时,方程 Ax=b 直接给出基变量的值就是 b。这也解释了为什么要求 b ≥ 0 —— 否则初始解不可行。

σⱼ 为什么能用整行消元维护?

因为 σⱼ 行本质上是"目标函数行"的系数,消元是线性运算,对目标行和约束行做同样的初等变换,得到的仍是等价方程组,公式 σⱼ = cⱼ − Σ C_B(i)aᵢⱼ 自动成立。你也可以每步重算一遍来验证。

大 M 法里 M 怎么算?

不用算出具体数值,只需把每个数看成 a + bM 的形式,比较时先比 M 的系数、再比常数项(因为 M 足够大)。本页的表里就把这两部分分开显示:括号里的"含 M 项"就是这个系数。

怎么检查自己算的表没错?

三个自检:① 基变量所在的列必须是单位向量;② 基变量的 σⱼ 必须都是 0;③ z = Σ C_B(i)bᵢ 且 bᵢ ≥ 0。

符号对照表(全站统一)

符号名称含义与算法中的角色
cⱼ目标函数系数目标函数里 xⱼ 的系数。标准形中人工变量的 cⱼ 记为 −M。
C_B基变量系数列基变量在目标函数中的系数,写成列向量,与 X_B 一一对应。它是 σⱼ 和 z 的计算依据。
X_B基变量(列)当前取作基的那 m 个变量。X_B 的取值就是 b 列;X_B 所在列在表中是单位向量。
b右端项(列)约束等式右边的常数。初始表要求 b ≥ 0,X_B 的初始取值就等于它。
σⱼ检验数σⱼ = cⱼ − Σᵢ C_B(i)·aᵢⱼ。max 时 σⱼ ≤ 0 为最优,取 σⱼ > 0 最大者进基;min 时判据相反。
θ比值θᵢ = bᵢ / aᵢₖ(仅 aᵢₖ > 0)。取最小 θ 所在行的基变量离基,决定 xₖ 能增到多少。
z目标函数值z = Σᵢ C_B(i)·bᵢ。每换一次基,若进基变量取 θ,则 z 增加 σₖ·θ。
aᵢⱼ技术系数第 i 行第 j 列的元素。入基列的 aᵢₖ 决定 θ,主元就是被选中的 aᵣₖ。
M大正数大 M 法中惩罚人工变量的"任意大的正数"。表中以 a + bM 形式精确记录,不取具体数值。

记法约定:max 问题写作 σⱼ = cⱼ − Σ C_B(i)aᵢⱼ ≤ 0 判最优; 若你的教材把 min 问题也统一成"σⱼ ≤ 0 判最优",那它实际上是把目标函数取了负号。 本页的做法是:内部统一按 max 计算,显示 min 问题时把 σⱼ 与 z 整体取反, 这样屏幕上出现的 σⱼ 就等于你按 cⱼ − Σ C_B(i)aᵢⱼ 手算的结果。