文章以数字线索串起单纯形法的历史：1939 年 Dantzig 在柏克莱误抄题目解出两个统计学公开难题，1946 年取得博士后进入美国空军做资源配置。近 80 年后，单纯形法仍广泛用于含上百到上千变数的物流与供应链决策，且实务上常被观察到「跑得很快」。

理论阴影来自 1972 年的结果：在最坏情况下，步数（因而时间）可能随限制条件数量呈指数成长。文中用线性规划例子强调比例与上限：利润目标为 3a+2b+c（衣柜是椅子的 3 倍、床是 2 倍），每月总量 a+b+c≤50、衣柜 a≤20、椅子 c<24；几何上等同在多面体上沿边走到最优顶点，错路会造成「迷宫式」长路径。

2001 年 Spielman 与 Teng 证明加入微量随机性可把最坏行为压到多项式时间：例如在每个角落有 6 个选择时，随机能以 5/6 机率避开最差方向，并把形如 2^n 的指数界换成 n^k（文中举例 n^2）。但早期界仍高，包含 30 次方等大指数；Bach 与 Huiberts 在 arXiv:2504.04197（将于 2025 年 12 月的 FOCS 发表）用更多随机性把保证界再压低，并证明在该模型下已达最优，因而更有力地解释了实务上为何看不到指数爆炸。

The story tracks simplex through key dates and scales: in 1939 George Dantzig copied two “homework” problems and solved two famous open questions; he earned his PhD in 1946 and soon advised the newly formed US Air Force on allocating scarce resources. Nearly 80 years later, simplex remains a dominant tool for logistics and supply-chain decisions with hundreds or thousands of variables, and it is widely observed to run fast in practice.

The numerical tension is theoretical: a 1972 result showed worst-case runtimes can grow exponentially with the number of constraints. A toy linear program highlights ratios and caps—maximize 3a+2b+c (armoires worth 3× chairs; beds 2×), subject to a+b+c≤50, a≤20, and c<24—then interprets simplex as walking edges on a polyhedron from one vertex to another, where consistently choosing “wrong” edges can force a labyrinthine, longest-possible path.

A 2001 breakthrough by Spielman and Teng argued that tiny randomness prevents those adversarial paths, replacing exponential behavior like 2^n with polynomial bounds such as n^k (illustrated as n^2), akin to having a 5/6 chance to avoid the worst of 6 options at each corner. Yet early polynomial guarantees were still large, including a term to the 30th power; Bach and Sophie Huiberts (arXiv:2504.04197, to be presented at FOCS in December 2025) use more randomness to prove substantially lower guarantees and show this smoothed-analysis approach cannot be improved beyond their bound, strengthening the case for why practice avoids exponential blowups.