乔治·丹齐格：从误解的难题到线性规划（一）

唐宋韵在他前几天的一篇文章里介绍了电影《心灵捕手》（Good Will Hunting）。电影里面的主角是一个麻省理工学院的清洁工，把黑板上一个数学问题误以为是作业，当即在黑板上便把它解决了。但实际上这个问题是一个未解的数学难题，自然引起人们的注意。。。

学数学的大概都知道，解题这个情节是以数学家乔治·丹齐格（George Dantzig）的真实故事为蓝本的。当然电影里面的人物的其它故事和丹齐格完全没有关系。因为我对优化这个领域比较熟悉，按唐兄建议，分享一下丹齐格的原版故事。也顺便介绍一点和丹齐格最重要的工作相关的线性规划问题。线性规划现在几乎是所有理工科学生都会学一点的。它不仅有很广泛的应用，也有很多优雅的审美性质。

导师杰里·纽曼

丹齐格和他的导师杰里·纽曼（Jerzy Neyman）师生俩都是20世纪泰斗级的数学家，在各自领域中都是大家绕不过去的丰碑。他们的工作不仅给成千上万的数学后辈提供了饭碗，还因为两人做的都是应用数学，也深入影响到现代社会每一个人的日常工作和生活。

杰里·纽曼是波兰出生的数学家，在华沙大学取得博士学位。前半生在波兰的各个研究院和英国伦敦大学学院，后半生在加州大学伯克利分校。纽曼引入了统计假设检验（Statistical Hypothesis Testing）中的“置信区间”（confidence interval）概念，并与埃贡·皮尔逊（Egon Pearson）合作提出了“纽曼-皮尔逊引理”，引入了统计假设检验的零假设，奠定了现代统计推断理论的基础。这些概念和工具现在广泛应用在医学、经济学和社会科学等领域的各种统计分析中。对于现在学习统计学的本科和研究生学生而言，零假设、置信区间、类型一错误和类型二错误等，都是学习中的重点。

纽曼不仅在学术上成就斐然，还培养了近40个博士生，很多在统计学和其他领域取得了重大突破。丹齐格就是其中之一。而电影中的做题故事，就发生在他手下。

黑板上的“作业”

丹齐格是美国人，父亲也是一位数学家。1939年，丹齐格是加州大学伯克利分校的一名研究生，修着纽曼教的统计学课。一天，丹齐格迟到了。走进教室后，发现黑板上有两个数学问题。他以为是布置的作业，便把它们抄下来带回家努力解答。几天后，他把解答交给了纽曼，还以为已经错过了”作业“的上交日期。几周后，纽曼告诉他，这两道题并不是作业，而是当时统计学中著名的未解是否有解答的难题（open problem)。一年后，丹齐格和纽曼讨论自己的博士论文选题时，纽曼不当回事地说，把那两个问题的解答放到一个文件夹里交上来，就足够作为丹齐格的博士学位论文了。

丹齐格的博士论文最终只用了其中的一个问题。另外一个问题因为没有发表，多年后被另一个数学家亚伯拉罕·沃尔德 ( Abraham Wald ) 又重复解决了。沃尔德准备发表他的工作时，才得知丹齐格当年已经解决了这个问题。结果最后这个问题的解答以他们二人的名义发表了。而丹齐格包含在他的博士论文里的那个问题，后来帮助他发现了线性规划问题最有名且最有用的单纯性算法。后面我们在再更仔细地聊这一点。

丹齐格的这个故事当然很少见，不然不会成为传奇。丹齐格后来自己也说过，如果当初知道那是未知解答的难题，他那时候也许就不会那么积极努力地去解决它们。毕竟这种问题已经被很多人尝试过且未能成功。但是把未知是否有解答的问题放进博士生资格考试里的事，还真有学校干过。我的读书时候，我前一届的师兄们的资格考试里就有这种不知是否可解的题。但我还没有听说过谁当场解决过这种题。放这种问题到博士生的资格考试里也可以是有理的：看看你对相关领域是否很了解，还有你做研究的能力——虽然不知道有没有解答，但是你可以说说你对这个问题的看法和可能去研究它的角度和途径。当然，在考试中遇上这种问题是很烦人的。因为你如果不知道它是未解的问题，你就可能在它上面浪费很多时间，影响你解答其他有解的问题。

其它作品