线性规划2012.docVIP

「线性规划」带来巨额财富 现代企业的规模越来越庞大，管理也越来越复杂。单凭人力对管理问题进行分析与判断，已属力不从心。例如汽车装配线上成千上万的部件之库存与分配，银行对多种股票债券的投资与管理，或港口多种货物的装卸与调度，都必须在电脑的帮助下完成。而电脑总是按照某种数学模型来运算的。所以，现代企业家了解一些与管理有关的数学模型，应该是很重要的。 　　本文所介绍的，是一种叫作「线性规划」的数学模型。我们不介绍这种模型的具体内容，只谈这种模型的发展历史及有关的故事。希望读者可以从中了解，管理问题是如何促进数学的研究，而数学的进展又如何推动了管理的革新。 从军用转到商用 　　二十世纪三十代，苏联科学院院士康托洛维奇写过一本书，讲述解决经济问题的数学方法，其中已有线性规划的论述。不过线性规划真正成为一门学科并得到应用，还是从二次世界大战开始。当时一批在军队中服务的英国科学家，可能为了必威体育官网网址，把他们的工作对外统称为「线性规划」，这个名称居然沿用到今。其後在美国军队中也有了类似的机构。当时在美国空军服役的科学家丹茨格把他用来解决某一些管理问题的方法加以总结，提出了「单纯形方法」。这个方法一直必威体育官网网址，直到战後的1947年，当丹茨格离开军队，转任斯坦福大学教授之後，才公开发表。同时，一批从军队中转业到工商界的科学家，也把他们在处理军事问题中研究出来的方法，应用到工业和商业的管理中去，使得战後的管理科学蓬勃发展。加上高速电脑的帮助，大量的数学方法，在管理中得到广泛应用。康托洛维奇由於在这方面的创造贡献，得到诺贝尔奖；而丹茨格由於发明了单纯形法，也被誉为「线性规划」之父。 　　为了说明什麽是线性规划，我们引用丹茨格解决的一个问题来作例子。这个问题称为「配餐问题」。美国空军为了保证士兵的营养，规定每餐的食品中，要保证一定的营养成份，例如蛋白质、脂肪、维生素等等，都有定量的规定。当然这些营养成份可以由各种不同的食物来提供，例如牛奶提供蛋白质和维生素，黄油提供蛋白质和脂肪，胡萝卜提供维生素??等等。由於战争条件的限制，食品种类有限，又要尽量降低成本，於是在一盒套餐中，如何决定各种食品的数量，使得既能满足营养成份的需要，又可以降低成本，把这些要求列成数学方程式，用单纯形法加以求解，就得出最佳的配餐方案。现代管理问题虽然千变万化，但大致上总是要利用有限的资源，去追求最大的利润或最小的成本，所以其中许多总是可以归结为线性规划问题。用数学语言来说，线性规划问题就是在线性约束下，求线性函数的极大或极小的问题。 　　线性规划问题，小的只有几十到几百个变量，例如配餐问题，供选择的食物至多几百种；而大的则可以有几十万到几百万个变量。虽然电脑越来越快，但总有电脑也解决不了的问题出现。因此在五十年代到六十年代，数学家们致力於单纯形法的改进，使之能够解决越来越大的问题。这一段时间可说是单纯形法独领风骚的时代。在这段时间里，数学家对算法的优劣也做了仔细的分析。大致上说，电脑总是通过有限次的四则运算（加减乘除）来求得问题的答案。算法的好坏，便可以用电脑的运算次数来衡量。给定一个问题，电脑最多需要多少次运算才能解决这个问题呢？当然这个运算次数与问题的大小有关。问题越大，变量越多，则所需的运算次数也越多。这种运算次数对问题大小的依赖关系，就可以用来判断一种算法的好与坏。好的算法，其运算次数的增加对问题大小不太敏感。反之，坏的算法，当问题稍微变大一点，运算次数就增加很多，因此就不能解决大的问题。按照这种标准可以证明，单纯形法是一种坏算法。这结果是由美国华盛顿大学的两位教授在1971年得出的。这在当时的理论界引起了轰动。原来我们使用了如此之久的单纯形算法，竟是一个「坏」算法！ 不断探求更好算法 　　那麽究竟有没有解线性规划的好算法呢？这个问题有两种可能的答案。一种是没有，也就是说线性规划本身的特点，决定了这种问题不可能有好的算法。另一种可能的答案，是有。也就是说线性规划本身并不那麽糟糕，还是可以有好的算法的，只不过人类还没有找到那种算法而已。 　　1979年，一位名不见经传的苏联数学家哈奇扬，发明了一种新算法来解决线性划问题。他从理论上证明这种称这「椭球法」的算法，是一种好算法。这使得一件拖了八年之久的公案，即线性规划到底有没有好算法的问题，彻底解决了。哈奇扬本人因此一炮而红。另一方面，他的发现，也引起了对线性规划研究的新一轮热潮，颇有点类似二次大战後那一段时期。许多人拿出越来越大的问题，让椭球算法去解。奇怪的是，在所有的计算实验中，椭球法都败在单纯形法手下。所谓生姜还是老的辣，在理论上「坏」的单纯形法，在实际上表现，远胜於理论上「好」的椭球法。这件事给数学家带来了巨大的精神危机：理论不符合实际，是不是我们的理论本身出了毛病？如果理论不对，那麽过去十几年我们在这种