作者 | 越民义
来源 | 重庆师范大学学报(自然科学版)，2011-2012年，原文分5期连载。
数学如何联系实际，这已是一个老问题了。我自1945年从浙江大学毕业，在担任一年的中学教师之后，又回到浙大陈建功先生的班上作助教，为他管理函数论课(实变和复变)的习题，照顾他的研究生的学习。对自己的工作，我感到很满意。但从那之后，经常会遇到有一些学历不高的人问我：你搞的数学有什么用?我虽自认为我所唱的是阳春白雪，不需要这些人理解，但总感到有必要弄清楚以下问题：引导一些年轻人去发展“纯数学”这类东西，真正的目的是什么?如果说这可以提高数学本身的水平，这水平显示在何处?解放后，由于学生可以向教师提意见，这一问题显得很突出。从20世纪50年代初期的少数人提意见，发展到1957年的教改，干脆将“纯数学”称之为伪科学。科学院数学研究所的数论等五学科的研究工作停止活动，合并组成大队，由年轻人担任总指挥和政委，这种状况一直持续到1961年。这中间，在经历过“跑任务”、“搞课题”等忙乱之后，组织上命我去讲授我未曾学过的《公共事业理论的数学方法》一书(辛钦著[苏])，我总算有了一份固定的工作。但数学如何联系实际，这一问题仍未解决。
在我国的生产实际中，数学工作是否就无事可做呢?1962年，我受命到鞍钢第三轧钢厂去工作三个月(任务是搞课题)。初去时，我在厂调度室随班待了一个多月。所谓调度室，实际上是一个宽约1m长约2m的平台，俯瞰着一个4x8(32m²)的巨大均热炉的厂房。沿着平台的长边放着十几个对讲机和一个簿子，每页上印上32x24个小方格，32道横行对应于32个炉子，24个直列表示24h，各有标号。调度员的工作有：根据当时产量的要求(由上级决定)，决定要开多少炉子;确定调入多少热钢(平炉)和冷钢(库存)，哪一号炉子的钢应该出炉等等。他的调度全凭对讲机。他只要拿起某一对讲机，对方就知道他是谁，他只要讲一句话，对方就完全了解他的意思。我能做的就是：当某一个钢锭放入某一编号的炉子时，我就在该标号所在的一行，在放入的时间所对应的一格画上一条竖线，并从那里开始向右画线直到该钢锭出炉时为止。表示其占用该炉子的时间。
我在这个调度室待了一个多月，发现什么也插不上手。我就把几本过去的记录带到宿舍，进行图解研究。通过图解，我发现：有时几个钢锭已经可以出炉但轧机无空，有时又是轧机空等待钢。这种现象直接来自于开炉的数目。此外还有别的因素也影响产量……。我对调度员谈了我的意见。他说，调度失误时有发生，但都是事后才发现。当时我想，至少有两件事可做：如何对问题进一步研究，设计出一个求最优解的算法;同时还要设计出一个简单的工具，根据接班时获得的数据，调度员可以轻易地得到一个好的调度方案。这两件事我虽然想了，但都没有做。三个月期满，我就回所了。
鞍山之行，使我获得一个信念：数学必能在我国的生产中发挥作用。当然不是轻易就可达到的。
02
在去鞍山之前，大约是在1961年，我曾在英国的运筹学季刊上看到一篇简短的文章，讲的是关于3个零件在3台机器上同顺序加工的问题。文中的方法很简单(因为只有3个零件)，但却有些新意。我就将文中的方法作些修改，推广到4、5个零件上去，应邀到所里做了一次通俗报告。(我的这个推广后来就发展成可行线方法，那是70年代的事了)。之后便到安徽六安去搞“四清”。此时就有人将讲稿打印油印出来寄到六安。我便寄了一份给华罗庚先生。他看后给我寄来一封20个字的短信：“寄来油印稿，带来感情深，有暇当拜读，一意为人民。”足见华先生对数学联系实际的重视。
接下来进入了“文化大革命”时期。1970年秋，我由“干校”回到研究所。当时还不许我们看业务书，但图书馆仍旧开着，有时我便走进去看看。我发现日本的锅岛一郎关于3台机器上的同顺序加工问题写了不少文章，这引起我对这问题早先的想法。于是，就与韩继业同志一起对这问题进行了较为深入的钻研，写出了我们共同署名的一篇文章(其中的算法设计部分是由韩继业同志完成的)。同时我们还一起收集了一些国外发表的已经解决了的一些排序模型方面的文章，整理成文，发表在《数学的实践与认识》杂志。这些属于科普性的文章，在当时颇受欢迎，使我想到：将数学付诸实践的气氛已开始形成。但这类文章并不好写，我们又将工作转到非线性规划方面。
1993年，我到西安电子工业大学访问。在与王宇平等年轻同志的一次座谈会上，他们告诉我：在80年代，他们在西安附近发现某工厂的生产过程中与上述我们所发表的文章中的模型甚为类似。而该厂每年的产量总是达不到上级所规定的标准。具体的情况是：该厂所生产的是单一产品，上级要求每年要出产3万台，而该厂每年至多只能出产1万3千台。这种产品是由45个零件组装而成的，而每个零件从原材料开始需要经过多道(≤12)工序加工，工件的加工顺序是一样的，但各自有其固定的加工时间，安排不当，则易造成有的机器成天忙碌，有的却很空闲。当时的工作是：如何对这45种工件本身安排一个加工顺序。这几位年轻教师在受到上述文章启发之后，根据文中的算法(并根据具体情况作了一些修改)，给出了一个新的安排，结果是令人吃惊的：年产量达到5万台。据他们说：当把这一算法提交厂方时，厂领导无论如何也不相信。直到他们将厂中当时的排法编成程序进行表演，证明年产量至多为1万3千台，厂方才让他们进行试验，之后，才接受了他们的方案。我曾与王宇平同志谈过几次，明确了此事的真实性。对此有兴趣的读者可参阅他们1990年发表在《数学的实践与认识》的文章。
这是我第一次切实了解到数学方法在我国生产实际中得到成功应用的例子。这样的事，在别的地方可能还有存在。他们之所以得到成功，一方面固然是因为他们勤于思考，将所发现的某些现象和得到的问题与其所学到的知识联系起来考虑；另一方面也是得力于计算技术在我国的兴起，不借助计算机，像这样规模的问题，用人工处理是不容易的。
03
近日，我从唐国春教授那里得知，他们所研究的“1对多对1收发不同货物可以分车运输的路径问题”所得出的算法已为上海一家公司所采用，他们的问题来源是上海某第三方物流公司在生产中提出来的。该公司为汽车厂提供汽车零部件，这零部件品种多、数量大、时间要求紧、供应点分散。公司在指定时间到各个供货点提取(已经包装好的)由整车厂提供的料箱直接送到整车厂的流水线，由厂方的机械手取下，同时又要为下一次到供应点取货时顺便带去空箱。由于供应点数目多，每天提取和送达的数量不尽相同。要使这一复杂的运输系统得到尽可能省钱省时的安排，没有精密的数学上的分析(建模)并建立相应的算法是达不到的。物流是一门很大的学问，工商业现已逐渐向全球化发展，物流将牵涉到运输、存储、选址等诸多问题。唐国春教授等的工作是这一方面很好的开始。
下面我想谈一下我所了解的国外的一点情况，当然是管中窥豹。
我要谈的是德国波恩大学离散数学研究所将数学用到芯片设计上所取得的成就。首先来介绍该研究所是如何发展起来的。在1982年，中国科学院应用数学所组织一个5人小组到汉堡去参加“国际运筹学学术会议”。会后，我们一起到波恩大学运筹学研究所去访问。所长是Korte教授。
我记得在当时，他们的所很小，讨论会安排在一间面积不大的地下室，由Bachem 教授来介绍他们的工作，主要是讲关于图论和拟阵方面的一些结果。由于我当时对这些问题一窍不通，就说了一些不太客气的话。我的意见主要来自北京理工大学孙树本教授。因为在去德国前不久，我们偶然在公共汽车上相遇，我问他在干些什么，他说在搞图论。我当时感到有些奇怪。他说，十几年不拿书本了，要他带研究生，只好找来一本图论，一本三百多页的书，后面有许多“猜想”，可作为学生的论文题目。我便将他的这番话作为自己的意见发表一遍。Bachem 教授对此并不生气，他说，在西德，图论在70年代也成为一种潮流，但现在情况已大为改变。他们所作的已经是另一回事了。回到北京不久，他们就连续寄来大量的他们工作的预印本和一本新出版的《近代应用数学》。阅读之后，我多少知道人家在干些什么，将来要干些什么。自1984年开始，我几乎每两年应邀到他们那里去访问一次，多则半年，少则三月，发现该研究所正在扩大，有些人在搞“课题”。慢慢地我才明白，他们正从事芯片设计的工作。
现在就比较清楚了：在1985年，Korte 在一次偶然的机会遇上一位芯片设计师，这项工作当时正处于初始阶段。在问及之下，这位工程师向 Korte 介绍了他做的工作。Korte 立刻认识到这些正与他和他的同事们所从事研究的组合优化问题密切相关。通过一些测试，利用组合优化中的方法可以将工程师们当时的设计结果改进三分之一。这样一来，便开始了该运筹研究所与IBM公司的非常成功的合作。创造了一个具体的芯片设计系统，发展出一套他们称之为Bonn-To11的技术，广泛地用于上千种芯片设计。
04
下述三种设计可能是他们的设计中具有里程碑意义的。
(1)电信芯片 ZORA。在芯片设计中运用离散优化的第一次大挑战是在1987年。IBM在 Zurich/Ruschlikon 研究实验室为美国电信公司 Rolm 所作的芯片设计。虽然现今的芯片复杂度比当时的至少要大10的2~3次方倍。即使如此，ZORA 在当时确实是一个真正的挑战。一个边长为12.7mm的正方形芯片要安放一百万个晶体管、15566个网和58738个连接栓，最大的困难是配线(wiring)。就当时的技术水平来说，只可能是在两张(相互垂直的)配线平面上。这芯片所纳入一个非常巨大的记忆宏指令(memory macro)，它只能放在当中。由于双层配线不可能横跨该宏指令，所有的设计师和专家都认为不可能存在可行的配线。然而，离散数学研究所的人，在当时布线算法(routing)仍处于初始阶段的情况下，都以一个配线总长为14.9和91439个vias(空际间的连接)给出答案并投入生产。这是第一次得到赞扬的一个完全与他们的算法做出的设计相匹配的硬件。
(2)微处理器P2SC。1995年，IBM生产出一种作为他的 Power 系列的微处理之用的 Power2 芯片。该芯片要求时间优化到7.4x10秒，它有149613个网，配线总长为166.3 m，1.4百万个vias(它是深蓝电脑中的微处理器，该机因在国际象棋人-机比赛中战胜 Kasparov创造历史而闻名)。
若采用分层设计，要将逻辑部分分解成几百个单元，各自需要满足一定的要求，再行连接，而需要总体最优，工作量将要求几百个人工作1年。仅实体设计一项就需要20个人1年。微处理器P2SC造就了展示平面设计优越性的机会。此时无需将总体分成几百个单元，但却要求利用组合优化方法来作出安置与布线的算法，其结果是惊人的!新的设计只需要两组工作人员花费6周的时间做出;并使网的总长和vias的个数减少20%。循环时间没有缩小，这是因为有些瓶口不能改变，新设计的芯片比原要求的更为坚固。
(3)苹果 Power Mac 设计的系统控制器U3。2002年，苹果公司决定要设计一个新的 Power Mac P5.要使之成为世界上最快的PC(个人电脑)。该系统的控制器实体设计是IBM的一位工程师在2002-2003年利用Bonn-To11在波恩设计的。该芯片的边长为93mm，其上安置100万个具有多于100万个网的电路，并用400万个栓用金属丝固定下来，网的总长大约是260m，用了6个配线层。U3的设计中出现的一个特殊问题是其循环时间(cycle time)。为了使这一时间优化，他们使用了一种称之为 Bonn cycle OPT 的新方法。
05
Bonn Cycle OPT 的成就是巨大的，两个暂存器之间的最大距离决定了芯片的循环时间。瓶颈的循环时间是否可得到进一步改进，这问题的答复是肯定的。
上面所说，是根据波恩大学离散数学研究所的一份报告编写的。限于笔者的水平和篇幅的限制，所能谈的就是这些。
我自离开学校开始工作到现在，已经过了65个春秋了。这些年来，经常萦绕于心的一个问题，就是如何能看到数学在生产实践中发挥一种必不可少的作用。在我的上一篇文章(“关于数学发展之我见”，《科学》2006年第5期)中曾谈到数学在历史的许多阶段中曾发挥巨大的作用，没有数学的发展就不会有今天的自然科学和工业技术的发展。但离开社会的需要，数学就会走上一条自生自灭“外行听不懂，内行道不清”的死胡同。要使数学能为社会接受，一方面要求社会的生产萌生对数学的需要，另一方面要使我们的数学成为一种能有助于促进社会生产发展的工具。当然，这样一来，也就促进了计算工具和计算技术的发展。
从上述的几个例子可以看到，我国现在工业生产中确实需要数学。上面提到的王宇平同志所从事的排序问题，唐国春等同志研究的物流问题，都显示出有数学和无数学情况就是不一样。这样的例子可能还有很多。经过这些年的努力，许多学校也培养出不少人才，如何让他们去了解市场的需要，这是一个相当重要而又困难的问题。一般说来，由于过去许多年来数学发展的情况，工程技术人员一般是不相信数学家的，认为他们所搞的都是“纸上谈兵”，无补于实际。这就要求数学工作者能与工业界人士交流，像上面提到的 Korte 教授那样，假如不是因为他主动与那位芯片设计师交流，IBM公司的芯片生产竞争力可能会与今天的情况大不一样。另一方面，由于技术本身发展的需要，也会推动数学的发展。
老师要培养学生勤于动手动脑，“勤奋生出百巧来”(华罗庚语)，使之敢于面对现实，勇往直前，有了一两次成功的经验，就会建立自信，不畏艰险。
不可放弃理论研究，没有深入坚实的理论基础，就不可能开拓重大的新的方法和方向，要像上面提到的波恩大学的离散数学那样，由于有了坚实的基础，才敢于去解决新的更加复杂的问题。
作者简介
越民义
中国运筹学的开拓者之一和学术带头人越民义先生，是贵阳花溪人，1940年考入浙江大学数学系，受教于陈建功、苏步青两位数学大师，1951年进入中国科学院数学研究所工作，曾任应用数学研究所副所长。在排队论、非线性最优化和组合优化方面取得了多项具有国际领先水平的重要研究成果。在数论方面，解决了美国格罗斯·沃尔德提出的新情况，对三维除数情况作了较显著的改良。在排队论方面，初次给出了多台排队系统M/M/s的瞬时性态的解析表达式，并研究了此系统的平稳分布的存在性质。在排序理论方面，对Flow-Shop排序情况得出了差异先后顺序的最优条件，并设计出寻求最优顺序的效率高的新算法。在数学规划方面，解决了非线性最优化情况Wolfe既约梯度算法的不收敛问题，设计出解非凸规划的具有全局收敛性的新既约梯度。
斗转星移，越民义先生已为中国的运筹学发展拼搏了40余年。1980年他在华罗庚先生的支持下组建了中国运筹学会，1982年创办了《运筹学杂志》。作为这一领域的泰斗，他深知运筹学的发展对于社会经济和生产的重要意义，他不顾年事已高，走出书斋，举办运筹学研讨会和讲习班，撰写文章启发诱导青年人才。本文是越民义先生在九十高龄为启发数学专业的年轻人而写，本号谨此转载，以飨读者。
