南方企业文化宣传网----文章编号:2681----加入日期:2010/11/17

『关闭窗口』

线性规划 带来巨额财富-从军用转到商用

从军用转到商用

　　二十世纪三十代，苏联科学院院士康托洛维奇写过一本书，讲述解决经济问题的数学方法，其中已有线性规划的论述。不过线性规划真正成为一门学科并得到应用，还是从二次世界大战开始。当时一批在军队中服务的英国科学家，可能为了保密，把他们的工作对外统称为「线性规划」，这个名称居然沿用到今。其後在美国军队中也有了类似的机构。当时在美国空军服役的科学家丹茨格把他用来解决某一些管理问题的方法加以总结，提出了「单纯形方法」。这个方法一直保密，直到战後的1947年，当丹茨格离开军队，转任斯坦福大学教授之後，才公开发表。同时，一批从军队中转业到工商界的科学家，也把他们在处理军事问题中研究出来的方法，应用到工业和商业的管理中去，使得战後的管理科学蓬勃发展。加上高速电脑的帮助，大量的数学方法，在管理中得到广泛应用。康托洛维奇由於在这方面的创造贡献，得到诺贝尔奖；而丹茨格由於发明了单纯形法，也被誉为「线性规划」之父。

　　为了说明什麽是线性规划，我们引用丹茨格解决的一个问题来作例子。这个问题称为「配餐问题」。美国空军为了保证士兵的营养，规定每餐的食品中，要保证一定的营养成份，例如蛋白质、脂肪、维生素等等，都有定量的规定。当然这些营养成份可以由各种不同的食物来提供，例如牛奶提供蛋白质和维生素，黄油提供蛋白质和脂肪，胡萝卜提供维生素，等等。由於战争条件的限制，食品种类有限，又要尽量降低成本，於是在一盒套餐中，如何决定各种食品的数量，使得既能满足营养成份的需要，又可以降低成本，把这些要求列成数学方程式，用单纯形法加以求解，就得出最佳的配餐方案。现代管理问题虽然千变万化，但大致上总是要利用有限的资源，去追求最大的利润或最小的成本，所以其中许多总是可以归结为线性规划问题。用数学语言来说，线性规划问题就是在线性约束下，求线性函数的极大或极小的问题。

　　线性规划问题，小的只有几十到几百个变量，例如配餐问题，供选择的食物至多几百种；而大的则可以有几十万到几百万个变量。虽然电脑越来越快，但总有电脑也解决不了的问题出现。因此在五十年代到六十年代，数学家们致力於单纯形法的改进，使之能够解决越来越大的问题。这一段时间可说是单纯形法独领风骚的时代。在这段时间里，数学家对算法的优劣也做了仔细的分析。大致上说，电脑总是通过有限次的四则运算（加减乘除）来求得问题的答案。算法的好坏，便可以用电脑的运算次数来衡量。给定一个问题，电脑最多需要多少次运算才能解决这个问题呢？当然这个运算次数与问题的大小有关。问题越大，变量越多，则所需的运算次数也越多。这种运算次数对问题大小的依赖关系，就可以用来判断一种算法的好与坏。好的算法，其运算次数的增加对问题大小不太敏感。反之，坏的算法，当问题稍微变大一点，运算次数就增加很多，因此就不能解决大的问题。按照这种标准可以证明，单纯形法是一种坏算法。这结果是由美国华盛顿大学的两位教授在1971年得出的。这在当时的理论界引起了轰动。原来我们使用了如此之久的单纯形算法，竟是一个「坏」算法！
文章来源：www.5s886.com

>>上篇文章:线性规划 带来巨额财富
>>下篇文章:线性规划 带来巨额财富-不断探求更好算法