线性规划是一种数学方法。它帮助人们做决定。人们希望用最好的方式做事情。线性规划解决这类问题。它的历史很长。许多学者做出贡献。这个方法现在应用广泛。
线性规划的思想很早出现。古代人们思考节省材料。农民希望土地产出更多。商人寻找最赚钱的路。这些是线性规划的萌芽。没有系统的理论。人们依靠经验解决问题。
十八世纪数学发展很快。数学家研究方程和不等式。他们找到一些优化方法。法国数学家傅里叶做出贡献。他研究线性不等式组。这为线性规划打下基础。傅里叶的思考很超前。当时没有实际应用。理论停留在纸上。
二十世纪三十年代情况变化。经济学研究需要新工具。苏联数学家坎托罗维奇面对实际问题。他负责胶合板生产。工厂需要提高效率。资源有限机器有限。坎托罗维奇思考分配问题。他写出数学公式。他找到解决方法。这是一九三九年的事情。坎托罗维奇的工作很重要。这是线性规划最早的应用。他后来获得诺贝尔奖。他的书《生产组织与计划的数学方法》详细记录。这本书是重要参考文献。
第二次世界大战加速发展。战争需要调配物资。军队需要运输武器。美国军方遇到类似问题。他们寻求数学家帮助。丹齐格当时在空军部队。他研究规划问题。他想找到通用方法。丹齐格提出单纯形法。这是一九四七年。单纯形法很有效。它能解决很多问题。丹齐格发表论文《线性结构中的规划》。这篇论文影响巨大。它标志线性规划正式诞生。单纯形法成为主要工具。人们使用几十年。
学术界很快关注。冯·诺依曼是著名数学家。他研究对策论。他发现线性规划和对策论的联系。他提出对偶理论。对偶理论很深刻。它揭示问题的另一面。每个线性规划问题有对应问题。它们像镜子两面。冯·诺依曼和摩根斯坦合著《对策论与经济行为》。这本书提到相关思想。它是经典参考文献。
五十年代计算机出现。计算机改变一切。单纯形法需要大量计算。手工计算很困难。计算机可以快速计算。线性规划应用范围扩大。石油公司用它调配原油。航空公司用它安排航班。工厂用它控制生产。考利和雷布的文章《线性规划在炼油工业的应用》记录早期案例。这本书很实用。
理论研究继续深入。学者发现一些特殊情况。单纯形法不是总最快。有些问题需要很多步骤。人们寻找更优算法。苏联数学家哈奇扬提出椭球法。这是一九七九年。椭球法理论上有突破。实际计算不理想。它没有取代单纯形法。
一九八四年出现新方法。印度数学家卡马卡提出内点法。内点法完全不同。它从问题内部出发。它穿过可行域中心。对于大规模问题内点法很快。它引发新的研究热潮。卡马卡的论文《一种新的多项式时间线性规划算法》非常重要。现在内点法和单纯形法都在使用。
线性规划扩展很多领域。整数规划要求解是整数。运输问题是特殊类型。目标规划处理多个目标。这些属于规划大家庭。丹齐格和萨瑟的著作《线性规划导论》系统介绍知识。这本书多次再版。它适合初学者阅读。
教材和参考书很多。卢恩伯格的《线性与非线型规划》理论深入。它适合高年级学生。伯特西蒙斯的《线性规划及其应用》侧重实际。它有很多例子。这些书帮助学生学习。
中国学者也有贡献。华罗庚推广优选法。他走遍中国工厂。他教工人用数学方法。他写的《优选法平话》很通俗。吴文俊研究数学机械化。他的方法可用于规划。这些工作有中国特色。
现在线性规划无处不在。它进入大学课程。工程学生学它。经济学生学它。管理学生也学它。软件实现很简单。电脑有求解工具。人们输入问题得到答案。它支持决策自动化。超市用它安排货架。快递用它规划路线。电网用它分配电力。医院用它排手术时间。
历史发展显示规律。实践提出需求。数学提供工具。计算机放大能力。应用反哺理论。线性规划还在发展。新问题不断出现。大数据时代需要新算法。学者们继续研究。
参考文献记录历程。早期文献有坎托罗维奇的报告。它用俄文写成。后来翻译成英文。丹齐格的论文是奠基之作。图书馆可以找到。会议论文集收录进展。数学杂志发表新成果。互联网方便查找资料。许多经典文献可以下载。
学习历史有帮助。我们知道思想来源。我们明白方法本质。我们看见数学的力量。线性规划是人类智慧的结晶。它解决资源有限的问题。它追求最优结果。这个追求不会停止。未来会有新方法。未来会有新应用。参考文献将继续增加。