把黑板上的open problem当习题做的Dantzig

发信人: hezhi (荷芝), 信区: Mathematics
标 题: 把黑板上的open problem当习题做的Dantzig（图）
发信站: 野百合海外测试站 (Fri Apr 8 11:12:49 2005)

【八阕】被大家称为线性规划之父的Dantzig (丹齐克)，据说，一次上课，Dantzig迟到了
，仰头看去，黑板上留了几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲
惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是惭
愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很 ft,
后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的
问题，他给出的那个解法也就是单纯形法。据说，这个方法是上个世纪前十位的算法。
把黑板上的open problem当习题做的Dantzig, 下面是他本人的叙述：
During my first year at Berkeley I arrived late one day to one of Neyman's cla
sses. On the blackboard were two problems which I assumed had been assigned fo
r homework. I copied them down. A few days later I apologized to Neyman for ta
king so long to do the homework - the problems seemed to be a little harder to
do than usual. I asked him if he still wanted the work. He told me to throw i
t on his desk. I did so reluctantly because his desk was covered with such a h
eap of papers that I feared my homework would be lost there forever.
About six weeks later, one Sunday morning about eight o'clock, Anne and I were
awakened by someone banging on our front door. It was Neyman. He rushed in wi
th papers in hand, all excited: "I've just written an introduction to one of y
our papers. Read it so I can send it out right away for publication."
For a minute I had no idea what he was talking about. To make a long story sho
rt, the problems on the blackboard which I had solved thinking they were homew
ork were in fact two famous unsolved problems in statistics. That was the firs
t inkling I had that there was anything special about them.
G． B Dantzig，1914年生，美国科学院、美国文理科学院与美国工程院德高望重的院士，
美国国家科学奖章获得者。他毕生从事线性规划的理论研究与应用研究，是线性规划学科
的奠基人。他于1947年所发明的单纯形算法五十多年后的今天仍然是求解线性规划问题不
可多得的好方法。 二次世界大战的后期，Dantzig在美国五角大楼空军司令部的战斗分析
处工作, 任审计员。他的工作是搞多周期的训练安排、后勤供应与兵员调度。用美国的俗
话说，就是搞 Plan (计划)。但是美国军方不叫 “Plan”，他们叫“Program”。决策的
过程是千篇一律的，下级搞计划，上级选择拍板。那时的Dantzig还不到三十，正处在人生
的黄金季节。在 W. Leontief 投入产出表的启发下， Dantzig 想，为什么不象 Leontie
f 那样利用数学理论建立Program（训练的安排，后勤供应与兵员的调度）的数学模型，让
计划的制订机械化、让计划的选择有一个尺度呢？（W. Leontief 在1932年利用矩阵理论
完成了美国经济各部门之间的第一个投入产出表，1976年获诺贝尔经济奖。）
1947年， Dantzig的研究取得了进展，他利用线性不等式建立了Program 的一个模型，几
个月后他又加了一个线性目标函数，不多日，单纯形算法亦提了出出来。与此同时， Dan
tzig 的论文 “Programming in a Linear 1947及1948两年, Dantzig 先后拜访了数学界
、经济学界的一些巨人，他们是:J. Von Neumann, T. Koopmans, A. Tucker等。 Dantzi
g的工作得到了他们充分的支持。
二次大战中， Koopmans 在盟国船舶运输委员会从事运输模型的研究， 对于 Dantzig的成
果，他非常激动。Koopmans具有和Dantzig相类似的理论背景与实践背景，他不但很快理解
了Dantzig 的研究成果，同时立即看出了它在经济规划上的广泛意义与潜在的价值。是Ko
opmans 建议将 “ Programming in a Linear Structure ” 缩减为 “ Linear Program
ming ”(线性规划)。是Koopmans热情地呼吁年轻的经济学家关注线性规划模型的潜在作用
。三四十年之后，K. Arrow, P. Samuelson, H. Simon 以及 Koopmans本人皆因他们出色
的研究获得了诺贝尔经济奖。基于Koopmans的建议，一门新的、压根儿就是为科学地制定
计划而产生的学科——线性规划——诞生了。从那以后，Non-Linear Programming ，Int
eger Programming , Dynamic Programming , Stochastic Programming (又叫Planning
Under Uncertainty)等分支一一出现。现在人们对他们的学科含义都十分清楚，但对他们
的用武之地Planning(计划)反而不甚了了。要感谢我国老一辈的数学家，他们对 “Linea
r Programming” 翻译是极其准确的。
Von. Neumann 对 Dantzig的成果既赏识又重视。在1948年于Wisconsin举行的一次计量经
济学会议上，Von. Neumann巧妙地顶住了一些人对Dantzig的研究成果的漠视与挤压，不但
为Dantzig解了围，同时亦给经济界与数学界的学人们解了惑，为线性规划的研究与应用播
下了良好的学术气氛。就在此次会议的前半年, Dantzig用一分钟向Von.Neumann报告了他
的成果。投我以木瓜，报之以琼瑶 。而Von. Neumann 则用一个半小时的时间向 Dantzig
详细讲解了他刚完成的新作《Theory of Games and Economic Behavior》(博弈论与经济
行为)，如果不是出于对这个年轻人的成果的高度赏识, Von. Neumann是不可能这样做的。
五十多年的历史证明了Von.Neumann不愧为目光远大的学者。
1949年，即在 Dantzig 完成“采用线性结构的规划”一文后的两年，由Koopmans 发起在
Chicago大学召开了一次具有历史意义的大会 “Activity Analysis of Production and
Allocation”(生产与分配活动分析)。美国空军亦参加了会议。议题是数学规划及其应用
。不必多说，人们在很短的时间内便看到了线性规划在经济计划领域中的实际意义，对线
性规划产生了浓厚的兴趣。
七十年代中后期及八十年代初，以美国与德国为首的西方发达国家利用线性规划分析与评
价国家级能源系统，为制订中长期的能源规划，为化解当时的能源危机作出了杰出的贡献
。九十年代美国利用线性规划制定全国更大规模的长期经济规划。至此，线性规划经受了
复杂大系统与复杂超大系统的严峻考验，这些情况值得我们重视。
1982年Dantzig 在波恩大学的一次演讲中（讲题为 “Reminiscences About the Origins
of Linear Programming”）对其一生的贡献做了一个谦逊、公正而又准确的总结：
1、认识到大部分实际规划的关系都可表示成线性不等式组；
2、用一般的线性目标函数作为选择好规划的一种准则；
3、发明了单纯形算法，它使描绘经济理论的复杂的线性规划模型变成了复杂大系统实际规
划的一个强有力的工具。
1997年，Dantzig在《Linear Programming ——Introduction》中对线性规划作了一个深
刻的概括：
我们把线性规划看成是重大的革命性科技进展的一部分。在我们面临高度复杂的实际问题
时，它使我们能够陈述一般的目标，同时又给我们指出一组促使目标最佳的详细决策的步
骤。

--
※ 来源:．野百合海外测试站 woft.net．[FROM: 141.157.71.28]