线性规划

出处：按学科分类—经济 中国财政经济出版社《中国物资管理辞典》第491页（918字）

运筹学的一个分支。

研究在一定的限制条件下，如何从各种可行方案中寻求能满足一定管理目标要求的最优方案的一种数学规划方法。它研究的问题主要有两个方面：一是确定了任务，如何统筹安排使完成该项任务所需资源(人力、物力、财力、时间等)最少或使完成单位任务的成本最低，这是求极小值的问题；二是有一定数量的资源，如何合理使用这些资源来完成更多的任务或使之取得的效益最大，这是求极大值的问题。

在物资管理中，常用的线性规划问题有物资资源分配、运输装卸设备和人力的任务分派及组合、配套下料、物资调运、厂库选址、合理配料等。一个线性规划问题包含三部分要素：(1)决策变量。提出问题中有待确定的未知因素，也是问题的可控因素。(2)约束条件。

决策变量的限制条件，用一组线性等式或不等式表示。(3)目标函数。

问题所要求达到的目标，它是决策变量的线性函数。线性规划问题就是求一组决策变量的值，使其既满足约束条件的限制，并且使目标函数达到极值(极大值或极小值)，取得最优解。线性规划问题具有如下特性：(1)线性关系，表现为决策变量的约束条件是线性关系，而目标函数也是决策变量的线性函数；(2)非负连续性，表现为各个决策变量的取值为非负数，且在一定范围内具有连续性，不限定为整数；(3)单目标要求，即目标函数只有一个；(4)确定性，即给定的各项参数都是确定的，不包含随机因素。线性规划是运筹学中理论最完整、应用最广泛的一个重要分支。

它起源于本世纪30年代末40年代初。苏联的康托洛维奇(L．V．Kantorovich)和美国的希奇柯克(F．L．Hitchcock)在生产组织、下料和运输问题等方面开始研究应用线性规划这一数学方法。1947年，丹西格(G．B．Dantzig)提出了单纯形法，接着，冯·纽曼(J．Van．Neumann)提出对偶性概念，奠定了线性规划的基础。60年代后，借助于电子计算机，大大增强了线性规划的解题能力，开拓了更广阔的应用领域。

近年来，苏联数学家柯汉金(L G．Khachian)和美国数学家卡马卡(Karmarkar)分别发表了椭球法和卡马卡法，对线性规划问题的应用和求解，有所创新和发展。