第1章 线性规划基础

1.1 引言

20世纪30年代末，前苏联数学家康特罗维奇研究交通运输和机械加工等部门的生产管理工作，于1939年写了《生产组织与计划中的数学方法》一书初稿，为线性规划建立数学模型及解法奠定了基础；与此同时，美国数学家库普曼研究了选择最优化运输方案的方法，建立了“线性规划数学模型”，并取得了重大进展。他们二人由于科学的创建，后来成为诺贝尔经济学奖的获得者。到了40年代，线性规划得到进一步应用和发展，在工业、农业生产管理，交通运输的指挥高度，资源开发，商业和银行等领域得到广泛应用，对提高企业的经济效益有显著成效。自1947年美国数学家丹齐格（G.B.Dantzig）提出了一般线性规划问题求解方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入，特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，从解决技术问题的最优化设计，到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用，它已是现代管理科学的重要基础理论。

线性规划（Linear Programming, LP）是运筹学的基础部分，是目前应用最广泛的一种系统优化方法，广泛应用于工农业生产和经济管理等领域，其核心思想是以最少的资源消耗取得最大的经济效果，即研究在一定的人、财、物等资源条件下，取得最大的经济效益。例如，某企业生产两种产品，需要消耗三种资源，根据资源供应商可知三种资源的限量，根据生产工艺可知产品单耗（单位产品的资源消耗量），根据财务部和市场部的调研和预测可知两种产品的单位利润，现要制订两种产品的最优生产计划，使得企业能够获得的利润最大。这就是一个比较典型的线性规划问题案例，通过建立该问题的线性规划数学模型，对该模型进行优化求解获得最优解，根据该最优解即可获得最优生产计划。