∑ 数学名人档案库
← 返回 乔治·伯纳德·丹齐格 简介档案 深度档案
运筹学优化计算机科学

乔治·伯纳德·丹齐格（George Bernard Dantzig）

线性规划与单纯形法的发明者，运筹学的奠基人——他为美国空军机械化后勤规划而构想出「在线性结构中规划」，进而发现了单纯形算法，使资源配置、生产调度、投资组合、网络设计等成千上万变量的复杂决策问题可以系统求解；他的工作是 20 世纪应用数学对现代经济与工业影响最深远的贡献之一，而他误把统计学家内曼课上两道未解难题当作业解出的故事，更成了数学史上最脍炙人口的传奇。

一、生平与时代背景

乔治·伯纳德·丹齐格 1914 年 11 月 8 日生于美国俄勒冈州波特兰。父亲托比亚斯·丹齐格（Tobias Dantzig）出生于俄罗斯，赴巴黎学习数学，师从庞加莱；母亲安雅·乌里松（Anja Ourisson）也在索邦学数学。两人在巴黎相遇结婚，后移民美国，定居俄勒冈。托比亚斯因俄语口音重，起初只能做伐木工人、筑路工和油漆工，家境贫寒。

父母给孩子取名寄托了职业期望：长子以剧作家萧伯纳（George Bernard Shaw）命名为「乔治·伯纳德」，希望他成为作家；弟弟以庞加莱（Henri Poincaré）命名为亨利，后来果然成了数学家。后来托比亚斯有机会在印第安纳大学攻读数学博士，安雅获法语硕士，成为国会图书馆的语言学家，家境才好转，全家迁往华盛顿特区。

在华盛顿，丹齐格就读鲍威尔初中，起初数学成绩很差，但在父亲鼓励下决心学好数学与科学，很快名列前茅。进入中央高中后他迷上几何，得到三位重要支持：一位出色的数学老师、一位后来成为伯克利数学教授的同窗，以及父亲。父亲在他高中时给了他「几千道几何题」——丹齐格后来说：「我大脑发育时解的那几千道题，比任何事情都更锻炼了我的分析能力。」1920 年代末父亲在写名著《数：科学的语言》（Number: The Language of Science，1930 出版），十几岁的丹齐格为该书准备了部分插图。

高中毕业后，因父母仍不富裕，他选择了父亲已任教职的马里兰大学。1936 年获数学与物理双学士学位，同年夏天与安妮·什穆纳（Anne Shmuner）结婚。新婚夫妇搬到安娜堡，他在密歇根大学做霍勒斯·拉克姆学者攻读研究生，1937 年获数学硕士，师从 Hildebrandt、R. L. Wilder 与 G. Y. Rainer。但他不喜欢抽象数学，唯一喜欢的是统计课，于是放弃了研究生学业，回到华盛顿，1937—1939 年在劳工统计局做初级统计员（项目「城市消费购买研究」）。

他读了内曼（Jerzy Neyman）的统计论文，1939 年写信给内曼询问能否在伯克利做助教完成博士。内曼很快安排好，他再次开始研究生学习。就在伯克利的第一年，发生了那个著名的故事（见下）——他误把内曼写在黑板上的两道著名未解统计难题当成作业解出，后来成为他的博士工作。

1941 年美国参战后，他暂停学业（此时已修完课程并写好博士论文），以平民身份加入空军，1941—1946 年任陆军航空队总部统计控制处作战分析科科长。他的办公室收集出动架次、投弹吨数、飞机损失等数据，还帮助空军参谋部制定「规划」（programs）——巨细靡遗地计划训练、后勤供给、物资采购与人员部署。1944 年他获战争部杰出平民服务奖章。

1946 年他回伯克利一个学期，获数学博士学位。伯克利给了他教职，但年薪只有 1400 美元，妻子认为无法靠它养活儿子大卫，他拒绝了。1946 年 6 月他在华盛顿，五角大楼的同事请他承担「机械化规划过程」的工作，这正好契合他的兴趣，于是他被任命为国防部数学顾问。

1947 年，他做出了最著名的贡献——单纯形法与线性规划。它源自空军的规划工作：当时「programming」是军事术语，指训练、后勤或部署的计划与调度。丹齐格把规划过程机械化，引入「线性结构中的规划」；「线性规划」（linear programming）一词是库普曼斯（Tjalling Koopmans）1948 年在他访问兰德公司讨论时提出的。

发现算法后，他做的第一批应用之一是「用最小成本获得充足饮食」的问题。1947 年秋，国家标准局的 Jack Laderman 用手摇台式计算器求解一个含 9 个方程、77 个未知数的系统，花了约 120 人日。此前斯蒂格勒（George Stigler，后来的诺贝尔奖得主）用启发式方法给出的解，只比真实最小值每年 39.69 美元高 24 美分。

1952 年他加入兰德公司任研究数学家，主导把线性规划在计算机上实现（第一代计算机上，1952—1956 年取得巨大进展）。1960 年他回伯克利任教授并任运筹学中心主任，期间写出《线性规划及其扩展》（1963）。1966 年他转任斯坦福大学运筹学与计算机科学教授，在此度过职业生涯余生。

1991 年他写道，最初引发他研究的那个问题——「在不确定性下动态规划/调度」——仍然悬而未决：「如果能成功解决这个问题，它最终能通过更好的规划为世界的福祉与稳定做出贡献。」

他获得几乎所有相关最高荣誉：1975 年运筹学冯·诺依曼理论奖、1976 年美国总统颁发的国家科学奖章、1977 年美国国家科学院应用数学与数值分析奖、1985 年以色列理工学院哈维奖、1986 年英国运筹学会银质奖章、1989 年科尔斯美国创造力奖、1994 年数学规划学会特别表彰奖。他是美国国家工程院、国家科学院、美国艺术与科学院院士，获 8 个荣誉博士学位。

2005 年 5 月 13 日，他因糖尿病与心血管疾病并发症在斯坦福家中去世，享年 90 岁。

二、学术生涯年表

年份 事件
1914 11 月 8 日生于俄勒冈州波特兰；父托比亚斯（师从庞加莱），母安雅（均学数学）
1920 年代 随家迁华盛顿特区；初中数学起初不佳，父鼓励后名列前茅
高中 迷几何，父给几千道几何题；帮父为《数：科学的语言》准备插图
1936 马里兰大学获数学与物理双学士；与 Anne Shmuner 结婚
1937 密歇根大学获数学硕士（不喜欢抽象数学，只喜欢统计），遂放弃攻读博士
1937—1939 华盛顿劳工统计局初级统计员
1939 写信给内曼，获伯克利助教资格，重攻博士
约 1939 误把内曼课上两道著名未解统计难题当作业解出，后成博士工作
1941 美参战；暂停学业（已完成课程与论文），以平民身份加入空军
1941—1946 陆军航空队总部统计控制处作战分析科科长；1944 获杰出平民服务奖章
1946 回伯克利一学期获博士；拒伯克利教职（年薪 1400 美元太低）；任国防部数学顾问
1947 发明单纯形法；提出线性规划模型；首个大型应用为「最小成本饮食问题」
1948 访兰德，库普曼斯提出「线性规划」一词
1952 加入兰德公司，主导线性规划在计算机上的实现
1960 回伯克利任教授、运筹学中心主任；提出丹齐格—沃尔夫分解
1963 出版《线性规划及其扩展》
1966 任斯坦福大学运筹学与计算机科学教授，此后一直在斯坦福
1975 获运筹学冯·诺依曼理论奖
1976 获美国国家科学奖章（总统颁发）
1977 获美国国家科学院应用数学与数值分析奖
1985 获以色列理工学院哈维奖
2005 5 月 13 日卒于斯坦福家中（糖尿病与心血管并发症），享年 90 岁

三、核心成果（逐条技术解析）

1. 线性规划的模型化（1947）——把现实决策变成数学

问题背景：二战及战后，军方与工业面临大量「在约束下求最优」的问题：如何分配飞机、零部件、原材料与人员，使产出最大或成本最低？此前这类问题靠手工经验与试错，无系统方法。

关键思想：丹齐格认识到，这类问题都可写成统一的数学形式——线性规划（LP）： $$\max\ c^T x \quad \text{s.t.}\quad Ax\le b,\ x\ge 0,$$ 其中目标函数 $c^T x$ 与约束 $Ax\le b$ 都是线性的。他把空军的「规划」（programming，军事术语，指计划与调度）转化为线性不等式系统的优化问题。

意义：这是 20 世纪应用数学最成功的模型化之一。它表明看似五花八门的资源配置、生产计划、运输调度、投资组合、网络流问题，本质上都是线性规划。「线性规划」一词由库普曼斯 1948 年提出（「programming」取军事规划之义，非今天的计算机编程）。

2. 单纯形法（1947）——线性规划的求解引擎

关键思想：线性规划的可行域是一个凸多面体（由线性不等式围成），最优值若存在，必在某个顶点（极点）上取得。单纯形法从一个顶点出发，每次沿一条棱移动到一个使目标函数值更优的相邻顶点（「枢轴步」/pivot），直到无法改进为止。算法的核心是基变换：维护一组基变量，通过高斯消元式的行运算交换进出基。

算法步骤（标准型 $\max c^T x$ s.t. $Ax=b, x\ge 0$）： 1. 找一个初始可行基； 2. 计算检验数（reduced costs），若所有非基变量检验数 $\le 0$，已最优； 3. 选一个检验数 $>0$ 的非基变量进基，用最小比值准则选离基变量； 4. 枢轴更新，回到 2。

效率与复杂性：单纯形法在实践中极其高效——通常只需 $O(m)$ 到 $O(m\log n)$ 次枢轴。但 1972 年 Klee 与 Minty 构造出最坏情况下指数时间的例子。这激发了对多项式时间算法的研究：哈奇扬（Khachiyan，1979）椭球法、卡马卡尔（Karmarkar，1984）内点法都证明了 LP 多项式可解，但单纯形法在绝大多数实际问题中仍胜过后两者。Lovász 1980 年说：「如果统计世界上哪种数学问题消耗的计算机时间最多，答案很可能是线性规划。」

意义：单纯形法被列入 20 世纪最具影响力的十大算法之一（与快速傅里叶变换、排序等并列），至今仍是工业优化软件（如 CPLEX、Gurobi）的核心引擎之一。

3. 线性规划对偶理论

结果：对原问题 $\max c^T x$ s.t. $Ax\le b, x\ge 0$，其对偶问题为 $\min b^T y$ s.t. $A^T y\ge c, y\ge 0$。核心结论： - 弱对偶：任意可行 $x,y$ 有 $c^T x\le b^T y$； - 强对偶：若原问题有最优解，则对偶也有，且最优值相等； - 互补松弛：最优解满足 $x_j(c_j-(A^T y)_j)=0$ 与 $y_i(b_i-(Ax)_i)=0$。

与前人关系：冯·诺依曼 1947 年与丹齐格讨论时猜测了对偶性（受博弈论最小最大定理启发）；Gale、Kuhn、Tucker 1951 年给出严格证明。丹齐格的《线性规划及其扩展》（1963）系统阐述了对偶理论。

意义：对偶理论是优化的核心，不仅提供了最优性证明与灵敏度分析，还衍生出经济学中的影子价格（对偶变量即资源的边际价值）、算法（对偶单纯形法）以及大规模分解方法。

4. 丹齐格—沃尔夫分解算法（1960）

问题背景：许多实际 LP 具有块对角或角结构（如多阶段、多商品流），直接求解规模过大。

结果：与菲利普·沃尔夫（Philip Wolfe）合作提出丹齐格—沃尔夫分解：把原问题分解为一个「主问题」（master problem）与若干「子问题」（subproblems），通过列生成（column generation）迭代：子问题求产生最优进基列的定价，主问题用单纯形法更新。

意义：是大规模优化、整数规划分支定价（branch-and-price）、随机规划的基础算法之一，至今广泛用于物流、航空排班、能源系统等大规模问题。

5. 线性规划与计算机实现（1952—1956，兰德）

在兰德公司，丹齐格领导团队首次在第一代计算机上系统实现线性规划（Orchard-Hays 记述，1952—1956）。这使 LP 从理论走向工业可用，催生了整个优化软件产业。他后来还与同事开发了最早的 LP 标准格式（MPS 格式）与大型求解器的原型。

6. 「作业难题」轶事与统计学贡献

故事：在伯克利读博第一年，丹齐格有一天迟到，内曼的课上黑板写着两道题，他以为是作业抄下来。几天后他向内曼道歉说作业比平时难，内曼让他放桌上。约六周后一个周日早晨 8 点，内曼兴奋地敲门，手里拿着写好的论文前言——原来那两道是统计学中著名的未解决问题（存疑：两题的确切命题在不同转述中略有出入，一说涉及两正态总体均值差的置信区域/Behrens–Fisher 问题，另一说涉及概率内容的不等式；核心事实——它们是内曼悬而未决的问题，被丹齐格误当作业解出——是确定的）。内曼帮他整理发表，这成了他的博士工作。

意义：这个故事被广泛传播，常被引为「不要预设问题不可解」的励志寓言，也是丹齐格最广为人知的个人传奇。

7. 其他重要贡献

四、代表著作与文献

五、师承、学派与同时代交往

六、争议、公案与历史评价

七、身后影响与学术谱系

八、延伸阅读与权威来源