多快好省搞四化—线性规划

一般认为，线性规划随着1947年美国数学家丹齐格制定单形法而建立，但数学规划问题早在 1781 年法国数学家蒙日在研究筑城术时已涉及开控与充填问题，即如何运输挖出来的土，使重量X运程为极小。线性规划所涉及的数学问题是解线性不等式。一般有限线性不等式组的解在1936年由莫获金得到。最早应用线性规划解决实际问题是苏联数学家康托洛维奇，他在1939年出版《生产组织与计划中的数学方法》，其中提出得出线性规划问题最初解法，但未受到重视。荷兰经济学家库普曼斯在40年代再次独立得到类似方法。但一直到丹齐格的结果发表之后，他们的工作才受到重视，而且因此共同荣获1975年度诺贝尔经济学奖。线性规划不仅解决一大批实际问题，而且推动了对算法理论的研究。至今几千个变元及约束条件的计算已经可以在计算机上进行，而且线性规划问题占有计算机工作的相当分量。 的极小值的线性规划问题，1950年以后，又根据目标函数、约束条件以及变元取值等，发展出非线性规划、整数规划以及几何规划、参数规划等，其后又发展出组合规划、动态规划、多目标规划等新兴领域，它们都有着非常重要的应用。