第二季 · 第 36 章

战争中的数学家

《算法的故事》第二季 · 第二篇：寻找世界的最优解——丹齐格与单纯形法的诞生

1947年，美国华盛顿。第二次世界大战已经结束。但战争留给世界的，并不只有废墟与伤痛。一场规模空前的工业动员，让政府、军队与工厂开始面对一个共同的难题：如何在有限的资源下，组织数量庞大的生产与运输活动？一支空军需要飞机，也需要飞行员。飞机需要发动机、燃料、维修人员和零配件。每一种物资都有库存限制，每一道工序都需要时间，每一个计划又会影响其他计划。增加飞机产量，可能导致发动机供应不足。增加训练规模，可能使燃料消耗超过预算。将更多工人投入一条生产线，又可能让另一条生产线陷入停顿。当所有选择彼此关联时，人们该怎样制定一份真正最优的计划？这时候，一位三十二岁的数学家正在美国军方从事计划研究。他的名字叫乔治·伯纳德·丹齐格（George Bernard Dantzig）。他所面临的，不是一个简单的算术问题。而是一种人类社会长期存在、却始终难以彻底解决的困境。当资源永远有限，怎样才能找到最好的分配方式？1947年，丹齐格为这一问题发展出了一种计算方法。它不要求研究者列出所有可能的计划。相反，它让算法从一个可行的方案出发，沿着数学空间中的特殊路径，不断寻找更好的方案。这项方法叫作单纯形法（Simplex Method）。它后来成为线性规划和运筹学最重要的基础算法之一。但它的诞生并非一帆风顺。丹齐格后来回忆，自己最初其实想到了沿着多面体边缘移动的方法，却因为觉得这种方法太低效而将其否定。他没有想到，最终改变世界的，恰恰是他一度不愿意采用的道路。

第一幕：战争结束之后，计划工作并没有结束

1944年，美军运输机装载物资的历史场景。大规模军事行动需要协调飞机、货物、人员、燃料和运输能力。此图用于呈现时代背景，并非丹齐格的研究现场。^{[ORMS Today][INFORMS]}1941年12月，美国正式进入第二次世界大战。此后数年，美国的工业与军事组织迅速扩张。工厂生产飞机、舰船、车辆和武器。铁路与港口承担大量运输任务。各军事部门则需要不断计算人员、装备、后勤保障与行动计划之间的关系。庞大的战争机器，让一种原本容易被忽视的工作突然变得极其重要。那就是计划。一个计划并不只是写下一份需要完成的任务清单。它必须回答许多具体问题。下一季度能够生产多少架飞机？生产计划需要多少发动机？这些发动机能否及时交付？有多少维修人员可以投入使用？有限的燃料应该优先分配给训练，还是分配给运输和其他任务？任何一个数字发生变化，其他计划都可能跟着改变。在那个年代，这些工作很大一部分依靠人工表格、机械计算设备与部门之间反复传递的报告完成。计划人员能够制定方案，也能够计算许多资源需求。但他们很难保证：这份方案已经是所有可行方案中最好的。

一名数学家进入军事计划部门

乔治·丹齐格出生于1914年11月8日。他的父亲托比亚斯·丹齐格（Tobias Dantzig）是一名数学家，母亲安雅（Anja Dantzig）从事语言研究。他最初并不是一位一路成绩出众、没有任何挫折的数学天才。根据后来留下的传记资料，他年轻时曾在数学学习上遇到困难，后来逐渐对几何产生兴趣。1936年，他毕业于马里兰大学。此后又前往密歇根大学继续学习数学。1937年至1939年，他在美国劳工统计局工作，接触到实际统计调查中的数据与计算问题。1939年，他进入加利福尼亚大学伯克利分校，师从著名统计学家耶日·内曼（Jerzy Neyman）。第二次世界大战期间，他的研究生涯一度中断。丹齐格进入美国陆军航空队的统计控制部门，负责与军事计划和分析有关的工作。他因此积累了大量与资源管理有关的实际经验。对于一名数学家来说，这样的工作环境十分特别。每天面对的不是孤立的定理。而是一种复杂的组织系统。每个部门都希望得到足够的资源。但所有部门加在一起，却往往超过实际能够提供的总量。

1946年，一项留住数学家的研究计划

战争结束后，丹齐格曾考虑离开军方，到大学任教。但军方同事希望他继续留下。在2001年的一次口述历史访谈中，丹齐格回忆了这段经历。他表示，军方同事试图为他寻找一项值得继续研究的工作。最终提出的方向，就是使原来主要依赖人工进行的计划工作机械化。这项研究后来成为美国空军 Project SCOOP 的重要组成部分。SCOOP 是 Scientific Computation of Optimal Programs 的缩写，可以理解为“最优计划的科学计算”。^{[INFORMS][ORMS Today]}这里有一个容易产生误解的词：Programming。今天，程序员看到这个词，通常想到编写计算机程序。但在当时的军事与经济管理语境中，它更多指向计划、调度和活动安排。因此，线性规划中的 programming，原本并不是专门指我们今天的代码编程。所谓线性规划（Linear Programming），是在给定线性约束条件的情况下，寻找能够使线性目标函数达到最大或最小的决策方案。对于丹齐格而言，这正好对应他在战争中接触过的实际问题。他想让数学帮助人们回答：在一组已知资源限制下，怎样安排活动才是最好的？这一次，计划不再只是由人凭经验反复调整。它开始被转化为能够进行严格数学分析的对象。而这，正是整个故事真正的开端。

第二幕：在丹齐格之前，另一位数学家已经发现了相似的问题

列昂尼德·康托罗维奇（Leonid Kantorovich，1912—1986），苏联数学家。他在1930年代末已经研究利用数学优化改善生产资源配置的问题。如果我们把所有功劳都归于丹齐格，就会忽略一段重要的数学历史。在1947年之前，已经有人研究过类似问题。尤其是在苏联，另一名数学家独立探索了一条与线性规划非常接近的道路。他的名字是列昂尼德·康托罗维奇。1938年，列宁格勒。康托罗维奇接触到一个来自木材工业的实际问题。胶合板生产需要将木材加工成不同尺寸的板材。不同切割方式会消耗不同的原料，也会获得不同数量的产品。如果原料供应有限，工厂应该怎样组合不同的切割方案，才能提高产出？这种问题与战争中的飞机计划看起来相差甚远。但它们拥有相同的数学结构：存在若干种可选择的活动。每种活动消耗一定数量的资源。资源总量有限。研究者希望找到最优的活动组合。康托罗维奇开始使用数学方法研究这种资源配置问题。1939年，他出版了一本小册子：Mathematical Methods in the Organization and Planning of Production。《生产组织与计划中的数学方法》。它已经系统地讨论了与线性规划密切相关的优化问题，并运用了乘子等数学思想。^{[Cambridge Core][INFORMS]}

20世纪前半叶木材加工厂的生产环境示意。不同切割方案、设备产能与原料限制构成了康托罗维奇早期优化研究的实际背景。

为什么两项研究会独立出现？

在第二次世界大战前后，国际学术交流受到了严重影响。不同国家的研究人员可能面对相似的问题，却无法及时了解彼此的研究成果。丹齐格后来回忆，他在1947年研究线性规划时，并不知道康托罗维奇1939年的有关工作。类似的数学思想也曾出现在法国数学家傅里叶、比利时数学家 de la Vallée Poussin，以及美国研究人员弗兰克·希区柯克（Frank Hitchcock）等人的特定问题中。1941年，希区柯克发表了关于运输分配问题的研究。不同研究者分别从近似计算、生产管理、运输规划等方向，触及了后来线性规划理论的某些结构。这些研究并不是一条所有人彼此引用、逐步传承的连续研究链。其中有些是相互独立的发现。^{[archive.computerhistory.org][Google Books]}这也正是科学史有趣的地方。有时候，同一种数学思想并不属于某一个时代里唯一的发明者。当工业和社会发展到一定规模，不同地区的研究者会独立面对类似的困难。数学结构本身，成为他们共同的探索对象。

两条道路，最终汇聚

康托罗维奇的工作后来逐渐获得国际认可。1975年，他与荷兰裔美国经济学家佳林·库普曼斯（Tjalling Koopmans）共同获得诺贝尔经济学奖，表彰他们对资源最优配置理论的贡献。^{[诺贝尔奖官方网站]}而丹齐格在1947年的贡献，则是提出了现代线性规划的通用建模框架，并发展出能够实际解决大规模问题的单纯形算法。因此，我们可以把这段历史理解为：康托罗维奇等先驱，探索了最优资源配置的数学表达与早期求解思想。丹齐格则在战后军事计划问题的推动下，使线性规划获得了一个更具通用性、并且能够在计算机时代广泛应用的算法体系。接下来，我们暂时离开历史，进入一个很小的工厂。通过它，我们将看到丹齐格所研究的问题究竟是什么。

第三幕：一家小工厂，如何把利润做到最大？

20世纪中期的工业生产场景。下面的小工厂案例为教学构造，并非丹齐格1947年实际求解的空军计划数据。假设1947年，有一家小型工厂。它同时生产两种产品。A型产品比较复杂，但利润较高。B型产品相对简单，利润略低。工厂负责人很快面临一个问题：应该生产多少件A，又生产多少件B？表面看，这似乎只需要比较哪一种产品更赚钱。但真正的生产决策，并没有那么简单。

两种产品，共享有限的资源

为了让问题容易理解，我们只设置两种资源。第一种是原材料。第二种是工时。工厂每天最多拥有100单位原材料，以及80单位工时。两种产品消耗的资源不同。

指标	A型产品	B型产品	每日上限
每件利润	40元	30元	—
原材料消耗	2单位	1单位	100单位
工时消耗	1单位	2单位	80单位

假设所有产品都能够卖出，而且利润与资源消耗都是稳定的线性关系。我们先不考虑开机固定成本、批量折扣、原料损耗波动等现实因素。这是为了提炼出一个标准的线性规划模型。

第一种方案：只生产A

A型产品每件利润40元，比B型的30元更高。是不是应该把全部资源投入A？让我们算一算。如果只生产A，原材料最多支持：

100\div2=50

件。工时最多支持：

80\div1=80

件。所以真正的生产上限是50件。利润：

50\times40=2000\text{元}

这似乎是一个不错的结果。但是，它有一个问题。生产50件A只消耗50单位工时。剩下的30单位工时没有被利用。原材料已经耗尽，无法继续生产。于是，我们找到了一项被浪费的资源。

第二种方案：只生产B

如果只生产B：原材料最多支持100件。但工时只能支持：

80\div2=40

件。因此最多生产40件B。利润：

40\times30=1200\text{元}

比全部生产A更少。但这两种方案都有同一个缺陷。它们只考虑单一产品，没有尝试混合生产。

第三种方案：两种产品一起生产

假设我们生产40件A，以及20件B。原材料消耗：

2\times40+1\times20=100

刚好全部用完。工时消耗：

1\times40+2\times20=80

也刚好全部用完。总利润：

40\times40+30\times20=2200

比只生产A多了200元。

图36-1：三种生产方案

生产方案	A产品	B产品	利润
全部生产A	50	0	2,000元
全部生产B	0	40	1,200元
混合生产	40	20	2,200元

在这个案例中，混合生产的方案优于两个单一生产方案。但我们尚未证明它就是全局最优方案。

这是一个重要的转折。直觉认为，我们应该优先生产利润最高的产品。但现实告诉我们：单件利润最高，不一定意味着整体利润最高。真正决定最优方案的，是不同产品对所有有限资源的共同消耗。这里还有一个问题。我们找到2200元的方案，只能证明它比2000元更好。怎样证明它已经是所有可能方案中最好的？总不能把全部组合都试一遍吧？如果产品只有两种，或许还勉强可以。但如果工厂有200种产品、几十种原材料、数百条设备生产线呢？穷举可能性将变得越来越困难。我们需要一个更加普遍的数学方法。

第四幕：把工厂搬进数学空间

线性规划中的可行域，是全部满足约束条件的解形成的几何区域。在二维问题里，它经常表现为凸多边形。丹齐格面临的真实问题，规模远比刚才的小工厂复杂。但其中最重要的数学结构，我们已经可以看到了。我们先定义两个未知数。

x=\text{A型产品的数量}

y=\text{B型产品的数量}

然后，将所有要求写成数学表达式。

第一条约束：原材料不允许超额使用

每件A消耗2单位原材料。每件B消耗1单位原材料。全部原材料不超过100单位。因此：

\boxed{2x+y\le100}

第二条约束：工时同样有限

每件A需要1单位工时。每件B需要2单位工时。总工时不能超过80单位。所以：

\boxed{x+2y\le80}

第三条约束：不能生产负数个产品

x\ge0,\qquad y\ge0

现在，我们已经构造了一个完整的数学模型。所有满足这些条件的

(x,y)

，都代表一个允许的生产方案。例如：

(20,20)

是一个可行方案。因为：

2\times20+20=60\le100

20+2\times20=60\le80

但是：

(60,30)

就不是可行方案。仅原材料一项就需要：

2\times60+30=150

已经超过了100单位上限。

最后，我们要定义目标

目标非常简单。希望利润越高越好。利润函数是：

\boxed{Z=40x+30y}

于是，整个问题变成：

\begin{aligned} \text{最大化}\quad&Z=40x+30y\\[2mm] \text{满足}\quad&2x+y\le100\\ &x+2y\le80\\ &x\ge0,\ y\ge0 \end{aligned}

这就是一项标准的线性规划问题。它包含三个核心组成部分：

决策变量： 我们能够改变的数量。
约束条件： 所有方案必须满足的限制。
目标函数： 我们希望最大化或最小化的数学指标。

问题看起来只是几行不等式。但如果把它画在坐标系中，一件非常美妙的事情就会发生。

数学中的可行域

在坐标平面上，横轴表示A产品数量

x

。纵轴表示B产品数量

y

。约束：

2x+y\le100

表示某条直线下方的区域。约束：

x+2y\le80

又表示另一条直线下方的区域。再加上非负条件，我们只保留第一象限。这些区域相互重叠的部分，就是可行域（Feasible Region）。它代表所有满足资源限制的生产方案。这块区域并不是任意形状的。因为所有约束都是线性的，它形成了一个凸多边形。所谓凸，就是在这块区域中任取两点，它们之间的线段仍然位于区域之内。这个性质，接下来将发挥非常重要的作用。

可行域的四个顶点

先看坐标原点：

O=(0,0)

它意味着不生产任何产品。显然是可行的。然后，沿着横轴前进。当

y=0

时：

2x\le100

所以最大：

x=50

得到：

A=(50,0)

沿着纵轴前进。当

x=0

时：

2y\le80

所以最大：

y=40

得到：

C=(0,40)

最后，求两条资源约束边界的交点：

\begin{cases} 2x+y=100\\ x+2y=80 \end{cases}

解得：

x=40,\qquad y=20

于是：

B=(40,20)

我们得到四个顶点：

\boxed{O(0,0),\ A(50,0),\ B(40,20),\ C(0,40)}

为什么只需要关注顶点？

这正是线性规划的几何核心。对于一个非空且有界的线性规划可行多面体，线性目标函数至少有一个最优解位于顶点上。为什么？假设某个最优解处于一条线段内部。那么它可以写成两端点的加权平均：

P=\lambda A+(1-\lambda)B

其中：

0<\lambda<1

由于目标函数是线性的：

Z(P)=\lambda Z(A)+(1-\lambda)Z(B)

一个加权平均，不可能严格大于两端点的最大值。所以，其中至少有一个端点的目标函数值不低于内部点。不断沿着这种结构分析，就可以理解为什么顶点具有如此重要的地位。这里的结论还需要适当限定。如果可行域无界，目标可能没有有限最优值。如果问题不可行，则根本没有允许的解。如果目标函数恰好与某条边平行，还可能出现整条边上的点都达到最优值的情形。因此，并不是所有线性规划问题都只有唯一的顶点最优解。但对于我们这个工厂问题，最优值一定可以通过比较顶点找到。计算一下：

Z(O)=0

Z(A)=40\times50=2000

Z(B)=40\times40+30\times20=2200

Z(C)=30\times40=1200

最大的是：

\boxed{Z_{\max}=2200}

而对应的生产方案：

\boxed{x=40,\quad y=20}

现在，我们终于拥有了严格的最优性结论。但丹齐格真正要解决的问题，还没有结束。因为对于两个变量，我们可以直接画图。如果变量有一百个呢？一千个呢？我们无法把一千维的可行多面体画在纸上，更不可能轻易列出其中全部顶点。丹齐格需要的是一种不用画出完整空间，也能够不断寻找最优顶点的通用算法。而这，正是单纯形法真正出场的地方。

第五幕：丹齐格曾经否定了后来让自己闻名的想法

丹齐格在斯坦福大学任职时期的留影。1987年，他在《单纯形法的起源》中详细回顾了1947年的算法探索，包括最初否定沿多面体边缘移动的思路。1947年夏天。丹齐格已经明确了需要研究的问题。他希望在满足一组线性约束的所有方案中，找到使目标函数最优的方案。从几何角度来看，就是在一个高维凸多面体上寻找最优点。这种问题自然会让数学家想到：既然最优解可能出现在顶点，那么为什么不从某个顶点开始，沿着边移动到相邻顶点呢？如果下一顶点更好，就走过去。再寻找更好的相邻顶点。如此重复。看上去似乎很合理。但丹齐格最初并不喜欢这个想法。

为什么要绕着外面走？

1987年，丹齐格在一篇回顾论文《单纯形法的起源》（Origins of the Simplex Method）中，留下了一段很坦率的自述。他表示，自己在1947年夏天最先想到的，就是沿着凸多面体的边，从一个顶点移动到另一个顶点。但他很快否定了这种思路。理由是直觉上的：如果一个多面体拥有数量巨大的顶点，那么沿着边缘寻找最优解，似乎会产生漫长的迂回路径。他因此尝试寻找其他方法，例如穿过可行域内部、更加直接地接近最优位置。^{[archive.computerhistory.org]}这段历史格外值得讲述。因为它提醒我们，数学家的探索并不是一条从灵感直接通往成功的道路。一个想法，可能看起来幼稚。一种方法，可能因为直觉认为太慢而被放弃。但是在进一步的数学分析之后，原本被否定的思路，又可能展现完全不同的价值。

一次数学上的转向

丹齐格随后从另一种几何表达方式重新分析问题。在现代教材里，我们通常把约束写成：

Ax=b,\quad x\ge0

再研究这些方程定义的可行域。丹齐格当时的探索还采用了与约束矩阵的列向量有关的几何观点。他考虑将候选活动表示为向量，再通过选择少量活动及其权重，满足资源需求并优化目标。这种几何解释，让某些原本显得复杂的计算步骤变得容易理解。每一次更新并不需要重新求解整个问题。只需要调整一组有限的基本变量，就可能得到一个更好的方案。于是，沿着相邻基本可行解移动的方法，再次获得了吸引力。在这项研究中，丹齐格与数学家莱昂尼德·赫维茨（Leonid Hurwicz）等人有过合作。他后来回忆，研究人员当时曾用攀爬豆杆的形象比喻这一求解过程，因为他们正在沿着目标函数不断向上改进方案。^{[archive.computerhistory.org]}

一次与冯·诺依曼的会面

1947年秋天，丹齐格前往普林斯顿，希望向约翰·冯·诺依曼请教线性规划背后的数学问题。这是本系列中冯·诺依曼再次出场。在前面的随机数与蒙特卡洛章节里，我们已经看到他对数值计算和电子计算机的兴趣。而在这里，他又出现在另一条重要的数学发展道路上。丹齐格后来回忆，自己起初试图用军事计划的语言向冯·诺依曼介绍问题。但对方很快希望他直接给出数学形式。当丹齐格在黑板上写出相应的代数与几何表达后，冯·诺依曼立刻看出了问题的数学结构，并展开了关于线性规划理论的讨论。冯·诺依曼对博弈论与优化的研究，为线性规划的对偶理论发展提供了重要思想基础。不过，这次会面的作用应当准确理解。它不是单纯形算法被冯·诺依曼当场发明的故事。丹齐格明确说过，在1947年秋季会面之前，他已经提出了单纯形方法。^{[engineering.iastate.edu][archive.computerhistory.org]}这段相遇体现的是另一件事：一项从军事计划中发展出来的计算方法，开始与更广阔的数学理论发生联系。单纯形法逐渐不再只是军事计划人员的工具。它开始成为一个能够被数学家、经济学家和工程师共同研究的通用算法。

为什么沿着边走反而可能有效？

回到我们的工厂。可行域只有四个顶点。我们不需要在平面里的每个位置都尝试利润。只需要从一个顶点出发。检查相邻顶点中有没有更好的。如果存在，就沿着边走过去。重复这一过程。而在常规的单纯形法中，算法也不需要真的在几何空间里画出多面体。它只需要通过代数运算，维护一组基本变量，并根据目标函数的改善情况与约束限制，决定下一次应该如何更新。这就是它的精妙之处。它并没有枚举所有顶点。而是根据当前解的数学结构，有选择地寻找下一个解。当然，现代优化理论也告诉我们，单纯形法并不是在任何输入上都拥有理想的运行次数。但在大量实际线性规划问题中，它的表现非常出色。这项事实，要等到后来才被更完整地理解。现在，让我们先亲手执行一次简单的单纯形搜索。

第六幕：单纯形法怎样一步步找到2200元的利润？

图36-2：沿着可行域的边寻找最优解

查看 SVG 配图原件

36-009-882b7d3f04b3.svg · 点击查看大图

黄色路径展示从原点 O 出发，经顶点 A 到达最优点 B 的过程。这里使用二维图形解释单纯形法的核心思想。

我们现在开始执行算法。先假设工厂还没有生产任何产品。此时：

x=0,\qquad y=0

利润：

Z=0

这是一个满足所有约束的可行方案。在图形里，它就是原点：

O=(0,0)

第一步：从原点沿着一条边前进

当我们位于原点时，可以考虑增加A或B的产量。增加一件A，利润提高40元。增加一件B，利润提高30元。对于这个简单模型，如果采用“优先选择能够带来更大目标系数的变量”这一入基规则，那么我们先增加A。现在令：

y=0

然后不断增加

x

。由于原材料约束：

2x\le100

因此：

x\le50

此时，工时约束只要求：

x\le80

所以真正限制我们的是原材料。能够走到的最大位置是：

A=(50,0)

利润：

Z=2000

我们完成了第一次移动。

(0,0)\rightarrow(50,0)

利润从0增加到了2000。但是，这是不是最优？还不是。

第二步：寻找另一条能够改善利润的边

现在我们站在：

(50,0)

这个位置。原材料已经全部用完。所以，如果继续增加B，就必须减少A。因为：

2x+y=100

整理得到：

x=50-\frac y2

这意味着，每增加1件B，需要减少0.5件A。但这样调整是否有利可图？代入利润函数：

Z=40x+30y

得到：

Z=40\left(50-\frac y2\right)+30y

化简：

\boxed{Z=2000+10y}

这个公式非常重要。它告诉我们：沿着当前原材料约束边界，每增加1单位B，利润净增加10元。所以，只要还满足其他约束，我们就应该继续沿着这条边走。

第三步：另一种资源开始变成限制

我们还必须满足工时约束：

x+2y\le80

将：

x=50-\frac y2

代入：

50-\frac y2+2y\le80

得到：

\frac32y\le30

因此：

y\le20

也就是说，当B产量增加到20时，工时恰好用完。对应的A产量：

x=50-\frac{20}{2}=40

于是，我们到达：

B=(40,20)

利润：

Z=2000+10\times20=2200

算法完成了第二次移动：

(50,0)\rightarrow(40,20)

第四步：为什么不能继续改进？

现在，我们位于两条资源约束的交点。原材料已经全部使用。工时也已经全部使用。如果继续试图增加某一种产品，就必须减少另一种产品。沿着连接B与C的边移动时，利润会下降。沿着B与A的边返回，利润同样会下降。因此，没有能够进一步提高利润的相邻方向。对于一个线性规划问题，单纯形法通过相应的检验数（Reduced Costs）判断是否还存在改善目标函数的入基变量。当不存在允许的改善方向时，就可以根据线性规划的凸性结构，确认当前解已经达到全局最优。我们因此得到：

\boxed{x^*=40,\quad y^*=20,\quad Z^*=2200}

这项过程只移动了两次。当然，这不意味着所有线性规划问题都只需要两次移动。我们的小工厂只有两个决策变量，且具有非常简单的约束结构。对于一般问题，算法需要处理更大的矩阵、更复杂的基本变量组合，以及退化和数值稳定性等问题。但它所利用的核心结构已经显现出来：从一个可行顶点出发，通过数学计算寻找更优的相邻顶点，并持续更新，直到无法继续改善。

算法内部真正维护的是什么？

在正式的单纯形法中，程序并不是保存一张多边形图像。它保存的是线性方程和一组基变量。例如，把原来的两个资源约束改写成等式：

2x+y+s_1=100

x+2y+s_2=80

其中

s_1,s_2

是松弛变量（Slack Variables）。它们表示尚未使用的资源。如果：

x=y=0

那么：

s_1=100,\quad s_2=80

这代表工厂完全没有生产，全部资源都剩下。如果：

x=50,\quad y=0

那么：

s_1=0,\quad s_2=30

原材料已耗尽，但仍剩下30单位工时。到达最优解：

x=40,\quad y=20

则有：

s_1=s_2=0

所有资源都被充分利用。单纯形算法通过基变换，维护这些变量之间的关系。每次决定哪个变量进入基、哪个变量离开基，就对应一次基本可行解的变化。在几何上，这通常表现为从一个顶点移动到相邻顶点；发生退化时，也可能出现换基但几何位置不变的情况。我们刚才看到的顶点移动，其实只是这些代数操作在二维平面上的直观影像。

第七幕：从纸上的几何图形，到真正能够计算的机器

美国国家标准局研制的 SEAC（Standards Eastern Automatic Computer）早期电子计算机。1951年前后，它被用于执行线性规划计算，成为单纯形法进入电子计算时代的重要标志。^{[ORMS Today]}1947年，丹齐格已经发展出单纯形方法。但一项数学算法，距离真正改变大规模组织管理，还有很长的道路。首先，实际计划问题远不像刚才的工厂模型那么简单。可能有几十种资源。几百种活动。数千个相互依赖的约束。其次，当时的电子计算机尚处于早期发展阶段。计算设备的内存容量有限，输入与输出缓慢，数值计算的软件基础也十分薄弱。在今天，我们能够很容易地编写一个线性规划模型，交给成熟的软件求解器。但在1950年前后，连“怎样让计算机高效保存和更新这些矩阵”本身，都是一个重大的工程问题。

1951年的一次实际计算

美国空军的 SCOOP 研究计划，对早期计算机技术发展产生了重要推动作用。1948年，美国空军向国家标准局提供资金，支持计算机研制。随后，SEAC 成为一台重要的早期存储程序电子计算机。根据运筹学界保留的历史资料，1951年，研究人员使用早期单纯形软件，在 SEAC 上求解了一个空军部署计划模型。它包含48个方程和71个变量。计算耗时大约18小时。^{[ORMS Today]}

历史计算案例 · 1951年

48

方程

71

变量

18h

约18小时

这是一项真实的历史计算规模，不是当代计算机的性能基准。今天类似规模的问题通常十分容易求解。

对于现代工程师而言，71个变量并不算多。一个稍微复杂的生产管理系统，就可能产生数万甚至更多的决策变量。但在当时，这已经是一项非常具有代表性的成就。因为研究人员开始证明：那些原本需要大量人工反复协调的计划问题，可以被写成数学模型，并交给电子计算机系统地求解。数学、管理与计算设备之间，开始形成一种新的合作关系。

线性规划进入工业世界

这项技术随后被推广到更多领域。企业可以使用它优化生产组合。运输公司可以研究货物应当怎样在不同路线间分配。石油企业可以利用它协调原料与加工流程。农业生产者可以在土地、肥料、劳动力与水资源限制下安排种植计划。大型组织可以利用它研究库存、采购、能源和运输成本。但这里需要强调一个重要前提。线性规划模型给出的最优结果，永远只是在给定目标函数、约束条件和输入数据之下的最优结果。如果企业遗漏了一项重要约束，那么数学上的最优方案可能在现实中无法执行。如果成本数据不准确，求解器仍然可以得到一个精确的数学答案，但这个答案未必符合实际经济效果。如果现实问题包含不可分割的决策、固定成本和非线性行为，普通线性规划模型可能不再足够。因此，一项优化项目的成功，并不只是调用某个算法。还依赖于对真实问题的正确建模。丹齐格最重要的贡献之一，恰恰是帮助研究人员建立了从实际计划问题到数学优化模型的桥梁。

第八幕：1972年，一只被压扁的立方体向单纯形法发起挑战

Klee–Minty 立方体的数学可视化。1972年，Victor Klee 和 George Minty 构造出特定线性规划问题，证明某些单纯形选主元规则可能出现指数级运行路径。单纯形法在许多实际问题中表现优秀。但它真的在任何问题上都很快吗？这个问题，困扰了研究人员很长时间。我们知道，单纯形法通常沿着可行多面体的顶点与边移动。如果一个多面体拥有大量顶点，算法是否有可能走过许多不必要的路径？丹齐格最初否定边缘搜索的直觉，并没有完全失去意义。因为从理论上说，某些特殊构造的问题，确实能够迫使特定的单纯形算法走很长的路。1972年，数学家 Victor Klee 和 George Minty 给出了一项著名结果。他们构造出一类经过特殊扭曲的高维立方体。后来，它被称为 Klee–Minty Cube。对于采用特定选主元规则的单纯形法，这种多面体可以迫使算法经过指数数量级的顶点，才找到最优解。对于相应构造，顶点数量可以达到：

2^n

而算法可能不得不访问其中极大部分，甚至在经典构造下遍历全部

2^n

个顶点。^{[Wolfram MathWorld][ScienceDirect]}

这意味着单纯形法失败了吗？

并不是。我们需要区分两种概念。一种叫作实际表现。另一种叫作最坏情况复杂度。单纯形法在许多真实工业问题上具有很好的表现。但这不等于它在所有可能构造的输入中都能够保持同样的高效。Klee–Minty 的结果说明，至少对于某些经典选主元规则，存在能够诱发指数级运行步数的线性规划实例。因此，不能把单纯形法笼统描述成一个对于任意输入都具有多项式最坏时间保证的算法。但最坏情况反例，也不能直接推出它在一般实际工业问题中都很慢。这两项结论并不矛盾。

1979年：椭球法的理论突破

1979年，苏联数学家列昂尼德·哈奇扬（Leonid Khachiyan）发表研究，证明可以使用椭球法，在输入规模的多项式时间内求解线性规划问题。这是一项重要的计算复杂性理论突破。它表明，一般线性规划问题具有多项式时间算法。但椭球法在大量实际应用中，并未取代当时高度成熟的单纯形实现。一种算法拥有优良的理论复杂度，并不必然意味着它在常见实际问题上运行最快。

1984年：卡马卡的另一条道路

1984年，Narendra Karmarkar 提出一种新的多项式时间线性规划算法。这项工作引发了人们对内点法（Interior-Point Methods）的大量研究。与单纯形法通常沿可行域的边界移动不同，内点法利用可行域内部的路径和相关数值方法逼近最优解。

图36-3：寻找最优解的两种道路

查看 SVG 配图原件

36-012-56530c4debf9.svg · 点击查看大图

概念示意，并不是某一种内点算法的精确迭代轨迹。不同求解方法的具体实现与收敛性质，均需要更严格的数学条件。

这段历史表明，数学算法的发展并不是一次发明之后就停止。丹齐格的方法解决了大规模资源配置的实际计算问题。Klee 与 Minty 揭示了它在某些条件下的理论局限。哈奇扬推动了复杂性理论的发展。卡马卡则让人们重新探索穿过可行域内部的高效计算路径。非常有意思的是，1947年丹齐格曾经考虑过的“从内部寻找最优解”的方向，几十年后成为另一个重要的优化研究领域。这不是说他当年已经发明了后来的内点法。而是说明，对于同一个数学问题，不同的几何思路可能在不同技术条件下不断发展出新的算法。数学从来不是一条只有唯一答案的探索之路。^{[数字对象标识符][AlgConj_2010_IPAM.pptx]}

第九幕：互动实验室——亲自经营一家工厂

现在，我们已经了解了线性规划的数学结构和单纯形法的基本思路。接下来，你可以真正成为工厂经营者。这一次，原材料数量、工时上限，以及两种产品的利润都由你决定。观察数学上的最优方案如何随着资源与价格变化而改变。

实验一：给工厂分配有限资源

图36-4：可调节的线性规划工厂修改工厂的资源和利润参数，下方会重新计算所有可行域顶点，并选出利润最高的方案。

原材料100

总工时80

A产品利润40元

B产品利润30元

当前可行域与最优解

查看 SVG 配图原件

示意图原件 36-013-9a67c286fbde.svg — 36-013-9a67c286fbde.svg · 点击查看大图

最佳A产量

40

最佳B产量

20

最大利润

2,200

元

全部候选顶点的利润

顶点	生产方案 (A, B)	利润
O	(0.0, 0.0)	0.0
A	(50.0, 0.0)	2000.0
B	(40.0, 20.0)	2200.0
C	(0.0, 40.0)	1200.0

当前数学模型

\max Z=40x+30y

2x+y\le100,\quad x+2y\le80

实验采用连续变量，结果允许小数产量，可理解为生产批量或连续生产能力。如产品必须整件生产，则还需要整数规划约束。

观察一：增加原材料，利润一定增加吗？

先把原材料从100调整到110。观察最优产量和利润是否发生变化。然后继续增加原材料。你会发现，利润并不会永远以同样的速度增长。因为当某一种资源越来越充足时，另一种资源可能开始成为新的瓶颈。多余的原材料不一定能够转化为更高的产量。

观察二：改变产品利润，最优方案会不会跳到另一个顶点？

先恢复初始设置。然后将B产品利润从30提高到50。观察最优点是否仍然位于原来的位置。当B产品变得足够赚钱，算法可能会选择增加B的生产比例，甚至转向另一个顶点。这说明最优决策不仅取决于资源，还受到价格和利润参数的影响。

观察三：如果最佳方案出现小数怎么办？

线性规划模型默认决策变量允许连续变化。例如，某些参数组合可能给出：

x=31.67,\quad y=23.33

如果变量代表可按重量生产的化工原料，或者连续的能源生产量，这未必有问题。但如果变量代表完整的飞机、汽车或其他不可拆分的产品，就不能直接生产0.67架飞机。这时，问题需要增加整数约束。例如：

x,y\in\mathbb Z_{\ge0}

这就进入了整数线性规划领域。我们将在后续涉及组合优化的章节中，再研究这类更加困难的决策问题。

实验二：控制单纯形法的每一步

图36-5：单纯形法逐步演示

起点：全部资源未使用当前基变量为两种资源的松弛量。选择增加A产量，作为首次改善目标的方向。

A产量

0

B产量

0

剩余原料

100

剩余工时

80

当前利润

0 元

实验三：用 Python 求出真正的最优解

下面，我们不再手工枚举顶点。使用 Python 的 SciPy 优化工具求解这个线性规划。SciPy 的 linprog 在现代版本中可以调用 HiGHS 求解器，它支持现代单纯形方法和内点法等数值优化技术。


from scipy.optimize import linprog

# 最大利润 40x + 30y
# linprog 默认求最小值，因此取负号
c = [-40, -30]

# 资源约束
A = [
    [2, 1],  # 原材料
    [1, 2],  # 工时
]

b = [100, 80]

result = linprog(
    c,
    A_ub=A,
    b_ub=b,
    bounds=[(0, None), (0, None)],
    method="highs-ds"  # HiGHS 双单纯形求解器
)

if result.success:
    x, y = result.x

    print("A产品数量:", x)
    print("B产品数量:", y)
    print("最大利润:", -result.fun)
    print("剩余资源:", result.slack)
else:
    print("求解失败:", result.message)

这段程序会得到接近：

A产品数量: 40.0
B产品数量: 20.0
最大利润: 2200.0
剩余资源: [0. 0.]

这里存在一个很重要的工程实践问题。现代求解器可能提供多种算法。如果使用 method="highs"，程序会自动选择适当的求解方法。如果使用 method="highs-ds"，则明确使用 HiGHS 的双单纯形求解器。它与1947年丹齐格最初发展的原始单纯形方法存在历史继承关系，但不是完全相同的软件实现。真实的现代优化求解器还包含预处理、数值稳定控制、稀疏矩阵运算以及许多其他工程技术。这也是为什么七十多年前的数学算法，今天依然能够高效服务复杂的工业系统。

第十幕：资源真正的价值，未必等于它的市场价格

20世纪中期工业计划工作的时代场景。线性规划的应用，让资源不仅可以按照库存数量管理，还能够通过数学方法分析其对最优目标的边际贡献。现在，我们已经能够求出最优产量。但对于工厂管理者来说，故事还没有结束。他可能提出一个更加实际的问题：如果明天可以额外购买一些原材料，那么最多应该愿意支付多少钱？如果工厂能够增加十小时工时，又能带来多少额外利润？这两个问题看起来属于经济学。但它们的答案，竟然也隐藏在线性规划模型之中。

一单位原材料，究竟值多少钱？

回到最优方案：

x=40,\quad y=20

两种资源约束都恰好用尽。假设现在工厂额外增加1单位原材料，工时仍然是80。由于原材料增加，我们便可以稍微调整生产组合。如果最优方案仍然位于两种资源约束的交点，那么新的条件是：

\begin{cases} 2x+y=101\\ x+2y=80 \end{cases}

解得：

x=\frac{122}{3}

y=\frac{59}{3}

新的最大利润是：

Z=40\times\frac{122}{3}+30\times\frac{59}{3}

结果：

Z=2216\frac23

比原来增加了：

\frac{50}{3}\approx16.67\text{元}

因此，在当前模型和有效的资源变化范围内，增加1单位原材料，可以使最优利润增加约16.67元。再试试增加1单位工时。类似地，可以得到最优利润增加：

\frac{20}{3}\approx6.67\text{元}

这两个数字，称为资源约束的影子价格（Shadow Prices），也可以理解为对应资源的边际价值。它们不是原材料或工时在市场上的实际售价。而是在当前优化模型中，增加一单位资源上限对最优目标值产生的边际影响。

一份不需要枚举顶点的最优证明

更精彩的地方来了。假设我们给两种资源分别赋予一个非负的数学价值：

u=\frac{50}{3}

v=\frac{20}{3}

一件A消耗2单位原材料与1单位工时。这些资源的合计价值是：

2u+v=40

恰好等于A的单位利润。而一件B消耗1单位原材料与2单位工时。对应资源价值：

u+2v=30

又恰好等于B的单位利润。因此，对于任意可行生产方案：

40x+30y =u(2x+y)+v(x+2y)

而由于：

2x+y\le100

x+2y\le80

并且

u,v\ge0

，所以：

40x+30y\le100u+80v

代入：

100\times\frac{50}{3} +80\times\frac{20}{3}

得到：

\boxed{Z\le2200}

我们于是得到了一个极为有力的结论。无论选择什么可行生产方案，利润都不可能超过2200元。而我们已经找到一个方案：

x=40,\qquad y=20

恰好达到2200元。因此它必定是最优解。这一次，我们没有枚举全部顶点。而是利用另外一组数学变量，为最优结果构造了一个严格的上界证明。这就是线性规划**对偶理论（Duality）**的一个具体例子。

图36-6：原问题与对偶问题

原问题决定生产多少件产品

\max\ 40x+30y

资源使用不得超过库存

对偶问题寻找资源的数学价值

\min\ 100u+80v

资源价值须覆盖产品利润

两边的最优目标值

2,200元

在满足线性规划强对偶条件的情况下，原问题与对偶问题的最优目标值相等。本例是这一结论的简单展示。

对偶理论之所以重要，是因为它为最优性提供了另一种观察方式。原问题寻找最好的生产方案。对偶问题寻找能够解释生产利润上限的资源价格。它们看起来是在解决不同的问题，最终却在最优值上汇合。这使线性规划不仅能帮助人们制定计划，也能帮助人们理解：哪些资源真正稀缺？增加哪一类资源最有价值？哪些约束限制了系统进一步改善？而在现代 ERP、供应链管理和生产计划系统中，这些问题仍然具有极高的现实价值。

一段历史插曲：那两道被误当作作业的难题

在结束之前，还有一段真实经历值得补充。丹齐格的名字经常和一个著名故事联系在一起。1939年，他在伯克利求学时，有一次迟到了。走进教室之后，他看见黑板上写着两道数学题。他以为那是内曼老师布置的家庭作业，便将题目抄了下来。几天后，他完成了计算并将结果交给老师。过了一段时间，内曼兴奋地告诉他：那些题目实际上是统计学中尚未解决的问题。丹齐格回忆，自己当时并不知道这些题目有什么特别之处。他只是把它们当作比平时稍微困难的作业来处理。这段经历并不是单纯流传于网络上的励志传说。丹齐格在后来接受访谈时，确实讲述过这个故事，相关内容也保存于数学史档案和运筹学界的传记资料之中。^{[MacTutor History of Mathematics][INFORMS]}但这里必须区分：1939年误将未解统计问题当作作业，与1947年发明单纯形法，是两个不同的历史事件。我们不能把这两件事合并，写成“丹齐格因为不知道某道单纯形法难题没有答案，所以突然发明了单纯形法”。那样虽然戏剧性更强，却不符合历史。真正值得注意的是，这两段经历展现了丹齐格研究生涯中的不同特点。1939年，他作为学生认真处理看似普通的数学问题。1947年，他已经积累了大量统计学与军事计划经验，尝试把抽象数学结构转化为能够实际使用的算法。前者是一项引人入胜的个人经历。后者则是一段跨越数学、经济与工程的长期研究过程。历史本身已经足够精彩，并不需要把不同事件拼接成更加传奇的故事。

尾声：最优解不是凭空出现的

1947年，当丹齐格开始研究线性规划时，电子计算机才刚刚进入新的发展阶段。资源配置仍然是一项很大程度依赖人工经验和繁重计算的工作。他想解决的问题十分现实。如何合理组织生产？如何协调运输？如何在预算和资源限制之下，找到更好的计划？这些问题看起来都属于管理。但丹齐格发现，可以使用数学语言，把它们转化成同一种结构。把每种活动表示为变量。把资源限制写成约束条件。把目标写成函数。再寻找满足所有约束、并且能够优化目标的方案。这项思想本身已经非常重要。但真正使它在实践中拥有强大生命力的，是单纯形法。它利用线性规划的几何结构，不必逐一计算所有可能的决策组合，就能够有方向地寻找更好的基本可行解。随着计算机的发展，这种数学方法迅速进入工业生产、运输调度、经济分析和企业管理。但丹齐格的故事，也提醒我们不要把算法的历史理解得过于简单。他并不是第一个思考资源最优配置问题的人。康托罗维奇等研究者，在他之前已经作出了重要探索。他也不是一开始就坚信沿多面体边缘移动是正确的方向。相反，他曾经否定过这种思路。随后又通过更深入的数学分析，发现其中隐藏的计算价值。到了1972年，Klee 和 Minty 又证明，单纯形法的某些具体实现，确实可能遭遇非常困难的最坏情况。再后来，椭球法与内点法，为线性规划提供了新的计算道路。这是一段不断探索、修正和发展的科学史。从中，我们能够看到一个与前几章不同的算法思想。欧几里得算法，通过保持不变量不断缩小问题。快速傅里叶变换，通过分治与重用减少重复计算。蒙特卡洛方法，通过随机抽样估计复杂系统的性质。而单纯形法，则试图利用问题本身的几何与代数结构，在庞大的决策空间中，有方向地寻找最优方案。它改变的不只是某个数学问题的计算方式。它改变了人们看待管理和资源的方式。在它出现之前，管理者可能会问：“我们能不能完成这份计划？”在它出现之后，人们开始进一步追问：“在所有能够完成的计划中，哪一份最好？”从可行，到最优。这个看似很小的变化，却打开了现代运筹学的大门。算法不再只是帮助人类完成某项计算。它开始帮助人类，在有限的世界里作出更好的选择。

历史档案：事实、回忆与创作边界

本章重点依据丹齐格本人的历史回忆，以及运筹学组织、数学史研究机构和诺贝尔奖官方保存的资料。

George B. Dantzig：《Origins of the Simplex Method》（1987）。本章最重要的一手资料，记录他1947年对单纯形方法的探索、最初否定沿边搜索的原因、与其他研究者的交流，以及对算法实际效率的思考。
INFORMS：George Dantzig 2001年口述历史。用于核查军方计划机械化、SCOOP 以及算法早期应用的历史背景。
INFORMS：Leonid Kantorovich 传记。用于核查康托罗维奇在1930年代末对生产优化与数学规划的早期贡献。
诺贝尔奖官网：1975年经济学奖新闻公告。用于核查康托罗维奇与库普曼斯对资源最优配置理论的贡献。
INFORMS：《Air Force Salutes Project SCOOP》。用于核查1947年后的军事计划研究、早期电子计算机应用，以及1951年SEAC求解48方程、71变量模型的历史案例。
Wolfram MathWorld：Klee–Minty 立方体。用于核查1972年单纯形法指数级最坏情况反例。
Narendra Karmarkar：1984年线性规划多项式时间算法论文。用于核查后来的内点优化发展。

本章开篇的战后计划困境以真实历史背景为基础，但具体人物动作和氛围属于文学性叙事；小工厂的产量、资源、利润及所有二维图形均为教学设计，不是丹齐格1947年研究的原始军事计划数据。关于丹齐格最初否定沿多面体边缘移动、后来重新认识其价值的经历，直接依据他1987年的本人回忆。有关1939年课堂难题的事件，也明确与1947年单纯形法的研究区分。

下一章预告 · 第37章

《水管、铁路与最大流：福特和富尔克森的突破》

1950年代，美国。一张交通网络图摆在研究者面前。每一条铁路都有运输能力的上限。每一个交通节点，都可能同时接收与发送货物。如果需要从一个起点向终点运输尽可能多的物资，究竟应该怎样分配每条线路的流量？某条运输线路看起来已经满载，但整个网络也许仍有尚未利用的能力。更令人意外的是，有时候，为了让更多货物抵达终点，算法竟然需要撤销之前作出的某些运输分配。下一章，我们将进入 Lester Ford 与 Delbert Fulkerson 的研究，追踪最大流算法与最大流最小割定理的发展。从一组简单的水管开始，理解为什么局部最优的运输方案，并不一定是整个网络的最优方案。

——《算法的故事》第二季 · 第36章完