单纯形开关

关掉的是哪一行

单纯形做的事只有一句：站在一个顶点上，看哪条棱能让目标变好，就走过去。关掉它，就只能把所有基都枚举一遍——从 m 个约束加 n 个非负条件里挑 m 个当作等式，解出交点，再检查它可不可行。

左图上红色虚线圈出的就是那些候选交点，其中只有一部分落在可行域里。两条路给的最优值必须一样——右边那一栏在逐组核对。

⚠ 我预期错了：不是 2m~3m

动手前我写下「单纯形访问的顶点数约 2m ~ 3m」（这是流传很广的经验值）。实测是 0.38m ~ 0.57m，比它小四到八倍——而且这已经是换了「更硬」的随机 LP 之后的结果，那个太软的生成器给出的是 0.17m ~ 0.32m。

⇒ 真正站得住的是「线性于 m」这个形状：六档 m 上的比值是 0.57 / 0.44 / 0.47 / 0.38 / 0.45 / 0.45，不随 m 增长；而那个常数取决于你喂它什么样的 LP。教科书那个 2m~3m 说的是真实世界的问题，比随机造出来的难得多。

标准扫描（定死的，页面和闸门跑同一份）：m ∈ {10, 20, 30, 40, 60, 100}，n = m，每档 40 个实例，Dantzig 进基，单一确定性随机流。 ⚠ 换成那个太软的生成器，比值反而随 m 下降（0.32 / 0.26 / 0.22 / 0.19 / 0.17 / 0.17）—— 连「线性于 m」都不成立，所以从它身上读出来的那个常数根本不该被当成一个常数。

Klee–Minty：最坏情况真的是指数

1972 年 Klee 和 Minty 构造出了一族「歪掉的立方体」，专门让单纯形把 2ⁿ 个顶点全走一遍。这里实测 n = 2…12，枢轴数恰好等于 2ⁿ − 1，一次不差。

⚠ 但它卡的是 Dantzig 进基规则。换成 Bland 规则，n = 10 时从 1023 步降到 177 步——可这不是解药：对每一条已知的确定性进基规则，都有人构造出了对应的指数反例。「单纯形最坏情况是多项式吗」至今没有答案。

它什么时候不赢

① Klee–Minty 那一族，见上。而更要紧的是 ②：一旦要求解必须是整数（排班里的「派几个人」显然是整数），问题立刻变成 NP 难的整数规划，单纯形帮不上忙，只能当分支定界里的一个子步骤。

而真实的排班问题恰恰大多是整数的。这一句必须说出来，否则这份演示就是在骗人——线性规划解决的是那一层连续放松的问题，剩下那一半是另一场仗。