George B. Dantzig · 1914–2005

丹齐格

他把「在一堆限制下求最好」写成了机器能算的一道题，又给了一个至今还在跑的算法：单纯形法

\max\ c^{\top}x \quad \text{s.t.}\quad Ax \le b,\ \ x \ge 0

线性规划的标准提法：变量不许为负，限制是一条条线性不等式，要最大（或最小）的也是线性的。1947 年 7 月为美国空军的计划工作写下，同年夏末有了单纯形法

乔治·伯纳德·丹齐格 1914 年 11 月 8 日生于俄勒冈州波特兰。父亲托比亚斯·丹齐格也是数学家，写过《数：科学的语言》；中间名「伯纳德」是父母盼他像萧伯纳那样当作家。他自己说九年级第一门代数「挂了」，气不过才发奋，父亲给他出了「成千道」射影几何题。1936 年马里兰大学毕业，1938 年在密歇根拿到硕士，嫌课程太抽象，去劳工统计局当统计员；在那里审一篇奈曼的论文，读得兴奋，写信要跟奈曼读博士。1939 年进伯克利，只上过奈曼两门课——其中一门迟到，把黑板上的两道题当成了作业（见本页第六件）。

1941 年他去了美国陆军航空队（后来的空军）的统计控制处，管作战分析科；1946 年回伯克利答辩，谢绝留校，去做空军审计长办公室的数学顾问，任务是把空军的计划工作「机械化」。1947 年 7 月他写出线性规划的模型，夏末有了单纯形法，10 月在普林斯顿见冯·诺依曼、听到了对偶。此后在兰德公司八年（1952–1960），1963 年写成《线性规划及其推广》；1960 年去伯克利工业工程系，1966 年转到斯坦福的计算机系与运筹学项目，带出五十多个博士。1975 年康托罗维奇与库普曼斯因资源的最优配置获诺贝尔经济学奖，他没有在内，两位得主在演讲里都提了他的独立工作，库普曼斯把三分之一的奖金捐给国际应用系统分析研究所以表敬意；同年他获国家科学奖章。2005 年 5 月 13 日卒，九十岁。

1976 年 10 月 18 日白宫国家科学奖章颁奖仪式，福特总统（右，画面只留下握手的那只手）为他颁发 1975 年度的奖章 · 白宫摄影办公室摄 · 杰拉尔德·R·福特总统图书馆藏 · Wikimedia Commons，公有领域（美国联邦政府雇员的职务作品）

生平

1914年11月8日
生于俄勒冈州波特兰
父亲托比亚斯·丹齐格与母亲安雅在巴黎学数学时相识；父亲最有名的书是《数：科学的语言》。
1936 · 1938
马里兰学士、密歇根硕士
在密歇根上过卡弗的统计课；嫌其余课程太抽象，硕士一毕业就去工作。
1938
劳工统计局的统计员
被派去审一篇奈曼的论文，从此认定要跟他读博士。
1939
伯克利：黑板上的两道题
奈曼课上迟到，把两道未解的题当作业做完交了上去。见本页第六件。
1940
《论「学生」假设不存在功效与 σ 无关的检验》
《数理统计年刊》第 11 卷 186–192 页，两道题里的第一道。
1941
陆军航空队统计控制处
管作战分析科，给各作战单位定下报告出击数据的制度；1944 年获陆军部杰出文职服务奖章。
1946
博士；空军审计长办公室的数学顾问
谢绝伯克利的职位，去五角大楼把空军的计划工作「机械化」。
1947年7月
线性规划的模型
把列昂季耶夫的投入产出模型推广成可以有多种可行计划、再从中挑最好的一个。
1947年夏末
单纯形法
与赫维茨一起试过各种算法，库普曼斯也出过主意。见本页第一件。
1947年10月
普林斯顿，见冯·诺依曼
对方当场把博弈论的定理翻成线性不等式，讲了一个半小时——对偶从这次谈话来。见本页第三件。
1947年秋
斯蒂格勒的营养问题
标准局的拉德曼拿它试单纯形法：九个方程、七十七个未知数，台式计算器约 120 个人日。见本页第二件。
1951
《生产与配置的活动分析》
库普曼斯编，考尔斯委员会专著第 13 号。他写了模型、单纯形法与运输问题三章。见本页第五件。
1952
兰德公司
在那里八年；1954 年与富尔克森、约翰逊用线性规划加割平面，解出走遍华盛顿与四十八个州府的最短巡回路线。
1963
《线性规划及其推广》
兰德公司报告 R-366-PR，普林斯顿大学出版社印行；第 2 章「起源与影响」是他自己写的来历。
1966
斯坦福
计算机系与运筹学项目，此后一直在那里。
1975
国家科学奖章
1976 年 10 月 18 日在白宫由福特总统颁发（本页肖像）。同年诺贝尔经济学奖颁给康托罗维奇与库普曼斯。
2005年5月13日
去世
九十岁生日的纪念会开过不到半年。

展品厅

绝大多数展品都可以亲手把玩——这是本馆的立馆之本；少数以叙述为主的，做成故事展签。

镇馆之宝 · 亲手玩

沿着多面体的棱往上爬

线性不等式围出一个凸多面体，最好的点一定在某个顶点上；单纯形法从一个顶点出发，每步沿一条棱走到更好的邻居，走不动了就是最优。

x_B = B^{-1}b,\quad \bar c_j = c_j - c_B^{\top}B^{-1}A_j > 0 \ \Rightarrow\ \text{让 } x_j \text{ 进基}

1947 年夏天，他在五角大楼要解的是空军那种成百上千个活动互相牵扯的计划。他在 1963 年那本书第 2 章里交代了算法的来路：那个夏天赫维茨和他一起试过好几种解法，库普曼斯出过主意，结果就是单纯形法；而「沿着凸多面体的棱，从一个顶点走到下一个」这个显而易见的念头，起初凭直觉被当作太低效而放弃了——顶点多得吓人。换一种几何去看（他后来叫它「列几何」，与他博士论文里的那种凸组合一脉相承），它才显得有效，「于是幸好试了一下，留了下来」。道理不复杂：线性的目标在凸多面体上没有「局部最高而全局不是」的陷阱，只要站在一个顶点、所有相邻的棱都不再往上，这里就是最高；而一次换基就是从一个顶点沿一条棱走到相邻的顶点。首创权要分层写：他自己在同书第 21 页说，傅里叶 1826 年为「最大偏差最小」的拟合把问题化成找一个多面体的最低点，提议从顶点到顶点往下走，「这大概是已知最早的线性规划问题」，1911 年德拉瓦莱普桑也提过类似的办法——可两人都没往下做，也没有人把它当成一类有用的问题；让它变成一门算得动的学问，是 1947 年的事。他第一次公开讲单纯形法是 1947 年 12 月 29 日美国统计学会与数理统计学会的联合年会，那篇稿子没有发表。演示里的多面体有 32 个顶点、49 条棱；从原点出发，六个方向最多走五条棱就到顶。

点一个目标方向，看单纯形法从原点出发沿哪几条棱爬到顶；右边逐步列出顶点与目标值

目标方向 (1, 1, 1)：从原点出发走了 5 条棱（换基 6 次，有 1 次是退化的、原地不动），停在目标值 18.032 的顶点；多面体一共 32 个顶点，逐个去试要算 32 次。

九个方程、七十七个未知数、一百二十个人日

第一次大规模试算单纯形法，算的是一个人一年最少花多少钱能吃够营养：手摇计算器算了约 120 个人日，答案一年 39.69 美元。

\min \sum_j x_j \quad \text{s.t.}\quad \sum_j a_{ij}x_j \ge b_i,\ \ x_j \ge 0

他 1963 年那本书第 27 章专讲这个例子。1945 年经济学家斯蒂格勒发表《维持生存的成本》：一个中等活动量的男子每天要 3000 千卡热量、70 克蛋白质，以及钙、铁、维生素 A 等共九项营养，从七十七种食物里怎么买最便宜？斯蒂格勒先把「每一美元营养更多」的食物替换掉较差的，再在可能的 510 种组合里看了「一小把」，给出一个答案，并说有理由相信一年省不了几块钱。1947 年秋，国家标准局数学用表项目的拉德曼拿这道题试刚提出的单纯形法——九个方程、七十七个未知数，用手摇的台式计算器，大约 120 个人日才算完。书上说，斯蒂格勒的答案折成一年，只比真正的最小值多 24 美分，而最小值是一年 39.69 美元，每天 10.9 美分。1953 年在 IBM 701 上用兰德公司的单纯形程序，同一道题连打印共 12 分钟。书里也说得明白，这个模型本身很粗：营养需要量除了热量都只知道个大概，食物的营养含量随品种、季节、烹调而变，而价钱是 1939 年 8 月的；他写道，过去是个恶性循环——模型粗，就拿粗糙的快速解法来凑，没有精确的解法，又成了模型粗的理由。演示用的是书上第 560 页那张约化表：斯蒂格勒剔到的九种食物、五项不会超额的营养。今天照同一张表重解，最省一年 39.66 美元，用到面粉、牛肝、卷心菜、菠菜与白芸豆五种；书上印 39.69，同一组五种食物，差的 3 美分我们不去猜是哪一步手算的舍入。

只用勾选的 9 种，最省一年 39.66 美元，与九种全开时相同；真正买了的是面粉、牛肝、卷心菜、菠菜、干白芸豆。

每一样营养值多少钱

同一道题反过来问：给每样营养定个价，让没有一种食物按这个价「值」得超过它的售价，需要量最多能值多少钱？答案与最省的花费分文不差。

\min\{c^{\top}x : Ax \ge b,\ x \ge 0\} = \max\{b^{\top}y : A^{\top}y \le c,\ y \ge 0\}

1947 年 10 月他去普林斯顿高等研究院见冯·诺依曼。据他后来的回忆，他照讲给普通人的办法从头讲线性规划的模型，对方打断他：「说重点。」他不到一分钟把几何与代数两种说法写上黑板，冯·诺依曼站起来说：「哦，那个呀。」接着讲了一个半小时线性规划的数学理论。他在 1963 年那本书第 24 页写：冯·诺依曼在第一次见面时就把博弈论的基本定理翻成了线性不等式组的等价说法，「提出并强调了对偶的根本重要性」，还猜到博弈与线性规划等价；同页一条脚注顺带更正了一个流传的错：富尔克森一次谈话里把单纯形法记到冯·诺依曼名下，本意是说对偶，这个错被写进了卡林、查恩斯与库珀的书。第一个严格的证明是塔克与他的学生盖尔、库恩 1948 年起给出的。首创权还要再往前推一层：同书第 22 页他写明，康托罗维奇 1939 年那本小册子里已经给短缺的资源定过「解乘数」——没叫它价格，意思却是价格。演示拿第二件那道营养题做对偶：五样营养各有一个影子价格，热量每千卡 0.8765 美分、钙每克 3.1738 美分、维生素 A 每千国际单位 0.0400 美分、核黄素每毫克 1.6358 美分、维生素 C 每毫克 0.0144 美分；一天的需要量按这组价值 10.8662 美分，正是最省的一天。被买下的五种食物按这组价恰好值它的售价，没买的四种都不值（淡奶 0.956、利马豆 0.897、切达 0.765、红薯 0.650 美元）——这叫互补松弛。把热量需要量拨高，花费沿一条折线上升，斜率就是热量的影子价格；过了 3100 与 3500 之间某处，牛肝被挤出去，价就跳到每千卡 2.0624 美分。

热量需要 3000 千卡

热量需要 3000 千卡时，最省一年 39.66 美元；按影子价格，一天的需要量值 10.8662 美分，与最省的一天相等。买了的 5 种按这组价恰好值 1 美元，没买的都不到 1 美元。

一个专门凑出来的立方体

单纯形法在实际问题上快得出奇，可有人专门造了一个压扁的 n 维立方体，按他的规则走，要把 2 的 n 次方个顶点全走一遍。

\max \sum_{j=1}^{n} 2^{n-j}x_j \quad \text{s.t.}\quad 2\sum_{j<i} 2^{i-j}x_j + x_i \le 5^i,\ \ x \ge 0

他在 1951 年那篇运输问题的末尾已经预感到了。那里他用的进基准则是「挑差额最大的那一格」，而他写道：这并不是说理论上凑不出让这条准则变弱的问题，只是在实际问题里，步数一直离下限不远。二十一年后克利与明蒂真把它凑了出来（1972 年《单纯形算法有多好？》）：把一个立方体一维一维地压扁、扭斜，于是按他的规则，单纯形法会沿着一条蛇形的路把所有顶点挨个走完。演示用的是这个例子最常见的写法：第 i 条约束是 2 乘上前面各变量的加权和、再加 x_i，不超过 5 的 i 次方；目标是按 2 的幂加权的和。原刊我们没有取到，式子与结论由演示里同一段单纯形代码逐维验证：n 从 1 到 12，步数依次是 1、3、7、15、31……4095，恰为 2 的 n 次方减 1，终点目标值恰为 5 的 n 次方。这个例子逼出了三个问题。线性规划到底能不能在多项式时间里解？哈奇扬 1979 年用椭圆法说能，卡马卡 1984 年的内点法在实际中也跑得快。单纯形法为什么在实际中还是快？2001 年施皮尔曼与滕尚华的「光滑分析」给了一个回答：把输入随便抖一抖，期望的步数就是多项式的。而有没有哪条进基规则能让单纯形法在最坏情形下也只走多项式步，至今没有答案。

维数 n = 3

n = 3：约束只有 3 条，单纯形法却走了 7 条棱，把 8 个顶点全走遍；每多一维，步数翻一倍再加一。

从西北角起步，八步运到最省

三个产地、五个销地，单纯形法在一张运价表上：先从左上角把运量排满，再一格一格换，每一步都比原来省——他 1951 年的例子，八步到最小运价 13。

u_i + v_j = c_{ij}\ \text{（基内）},\qquad M = \max_{(i,j)} \left(u_i + v_j - c_{ij}\right)

运输问题比线性规划本身早：希区柯克 1941 年就发表了《一种产品从几个产地运到许多地方的分配》，康托罗维奇 1939 年、1942 年已在苏联做过，库普曼斯战时也独立做过；希区柯克那篇库普曼斯与他都不知道，康托罗维奇的工作希区柯克也不知道。他的贡献是把单纯形法用到它上面，1951 年登在库普曼斯编的《生产与配置的活动分析》第二十三章，并给了一个完整的算例：三个产地各有 1、5、7 件，五个销地各要 3、3、3、2、2 件，单位运价第二行里还有一个 −1，他说那只是为了说明运价的正负不受限制。起步的办法就写在这一章：先定左上角那一格，取它的供与需中较小的那个数，删掉满了的那一行或一列，照此往下——今天叫西北角法。然后由基里七个格子解出每行一个数 u、每列一个数 v，使 u + v 等于运价；别的格子上 u + v 是「绕道」运一件的价钱，比直接运贵得最多的那一格就请进来，沿一条闭路一加一减调出 θ 件。碰到运量为零的退化，他给每个产地的供量加一个无穷小的 ε，最后一个销地加 3ε。按这套规则从头跑一遍，他表 VII 里的八行逐格对得上：总运价 52、52、32、32、23、17、15、13。末尾他自己检讨：起点那组七格里只有两格在最优解里，至少要六步，却走了八步——第 1 步把最后要用的 (2,3) 删掉了，后来又得请回来；(1,2) 第 4 步进来，后来又得删掉。这种问题还有一个好性质：供需都是整数时，顶点解自动是整数，运一件就是一件，不会出现半辆车。

第 1 步

第 1 步：z = 52；间接运价比直接运价贵出最多的是格 (2,4)，贵 5，把它请进来，沿闭路调 θ = 0（退化的一步，z 不变）。

迟到的那节课，黑板上的两道题

1939 年他在伯克利上奈曼的课迟到了，把黑板上的两道题当作业抄回去做——那是统计学里两个没人解出来的问题。

这件事后来被讲成了各种版本，这里只照他本人 1984 年接受阿尔伯斯与里德访谈时的说法（1986 年刊于《大学数学杂志》，据科特尔、约翰逊与韦茨 2007 年在《美国数学会通讯》上的纪念文转述）。他来伯克利是冲着奈曼的，只上过奈曼两门课。有一次迟到，看见黑板上写着两道题，以为是作业，觉得比平常难一些，还是做了出来，直接交给奈曼。结果那是数理统计里两个悬而未决的问题。他的五十七页博士论文就是这两道题的解。第一道很快投了出去，1940 年登在《数理统计年刊》第 11 卷，题目本身就是结论：检验「学生」的假设（也就是 t 检验所检验的那个），不存在功效函数与 σ 无关的检验。第二道要晚得多：1951 年才与瓦尔德联名发表，题为《论奈曼与皮尔逊的基本引理》。他在 1963 年那本书第 23 页交代了原委——奈曼与皮尔逊 1936 年证明，对一大类假设，若有满足他们那条广义引理的检验，它就是最优的；而他 1939 年首先证明，在很一般的条件下这样的检验总是存在，瓦尔德大约 1950 年独立得到了同一个结果。瓦尔德 1950 年 12 月在印度坠机身亡，没有看到那篇论文印出来。他在同一页还写了一句后来的眼光：那条广义引理的条件，恰好就是一个带上下界的线性规划取到最优的条件；这份博士论文里的研究，是他后来做线性规划的背景。

故事展签

传承

他的工作没有留在十八世纪——每条链的终点，都是你今天正在使用的东西。

1947：单纯形法，沿多面体的棱走到最优的顶点→商用求解器把规模推到上百万个变量，单纯形法与内点法并用→航班与机组排班、电网调度、炼油调和都交给线性规划求解器

1947 年秋：斯蒂格勒的营养问题，第一次大规模试算单纯形法→「最便宜又达标的混合」：饲料配方、炼油调和、合金配料→饲料厂与化工厂的配方最优化，每天都在跑

1947：对偶，每一条约束都有一个影子价格→库恩与塔克 1950 年那篇推广到非线性的情形，凸优化的对偶由此而来→支持向量机在对偶问题上训练，机器学习里的核方法由此而来

1972：克利与明蒂的立方体，最坏情形要走遍全部顶点→1979 年椭圆法、1984 年内点法：线性规划可以在多项式时间内解→「最坏情形慢、实际中快」成了算法理论的常规问题，2001 年的光滑分析是一个回答

1951：运输问题的单纯形，顶点解自动是整数→网络流、指派问题；1954 年用线性规划加割平面解出 49 个城市的旅行商问题→物流配送、车辆路径与导航里的路线规划

他在哪几条专题里

专题是按技术组织的演进线，一条从概念提出拉到今天的器物。这里一个字都没手写，全是 tracks.ts 推出来的。

航天一枚正在落回发射场的一级火箭1947 在一堆不等式围出来的地方，找最好的那个角（最优）

语录

「我开始讲线性规划模型的提法……就像讲给一个普通人听那样。他打断我：「说重点。」……不到一分钟，我就把这个问题的几何说法和代数说法都写上了黑板。他站起来说：「哦，那个呀。」」
—— 回忆 1947 年 10 月在普林斯顿第一次见冯·诺依曼；1984 年阿尔伯斯与里德的访谈（《大学数学杂志》1986 年第 309 页），据科特尔等人 2007 年《美国数学会通讯》纪念文所引译出，大意

「沿着凸多面体的棱从一个顶点走到下一个——这个显而易见的想法，起初凭直觉被当作低效而放弃了。换一种几何去看，它显得有效，于是幸好试了一下，被接受了。」
—— 《线性规划及其推广》（1963）第 2 章第 24 页，据兰德公司印本原文译出，大意

「过去是个恶性循环：模型粗糙，就拿粗糙的快速「解法」来凑；没有精确的解法，又成了模型粗糙的理由。」
—— 《线性规划及其推广》（1963）第 27 章第 551–552 页，讲斯蒂格勒营养模型时所说；据原文译出，大意